Keresési táblázat

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. május 21-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A keresőtábla egy olyan  adatstruktúra , amely egy függvény interpolációjának eredményeit tárolja . Ez általában egy tömb vagy asszociatív tömb , amellyel a számításokat egy egyszerű keresési művelettel helyettesítik . A sebességnövekedés jelentős lehet, mivel az adatok memóriából való előhívása gyakran gyorsabb, mint az időigényes számítások elvégzése.

A keresőtáblák használatának klasszikus példája a trigonometrikus függvények , például a szinusz értékeinek kiszámítása . Közvetlen számítása nagymértékben lelassíthatja az alkalmazást. Ennek elkerülése érdekében az alkalmazás az első indításkor előre kiszámít egy bizonyos számú szinuszértéket, például minden teljes fokra. Ezután, amikor a programnak szüksége van a szinusz értékére, a keresési táblát használja a szinusz hozzávetőleges értékének a memóriából való kinyerésére, ahelyett, hogy kiszámítaná az értékét (például sorozat használatával ). A keresőtáblákat matematikai társprocesszorokban is használják ; az Intel Pentium processzorainak keresőtáblájában lévő hiba a hírhedt hibához vezetett , amely csökkentette a felosztási művelet pontosságát.

Jóval azelőtt, hogy a keresőtáblákat a programozásban elkezdték volna, az emberek már használták a kézi számítások megkönnyítésére. Különösen gyakoriak voltak a logaritmustáblázatok , valamint a trigonometrikus és statisztikai függvények.

Van egy köztes megoldás, ha a keresőtáblát egyszerű számításokkal – interpolációval – kombináljuk . Ez lehetővé teszi, hogy pontosabban megtalálja az értékeket két előre kiszámított pont között. Az időköltségek kismértékben növekednek, de cserébe a számítások pontosabbak lesznek. Ezzel a technikával a pontosság elvesztése nélkül is csökkenthető a keresőtábla mérete.

A keresőtáblákat a számítógépes képfeldolgozásban is széles körben használják (ezen a területen a megfelelő táblázatokat általában "palettáknak" nevezik).

Fontos megjegyezni, hogy a keresőtáblák használata azokban a feladatokban, amelyekben nem hatékonyak, a munka sebességének csökkenéséhez vezet. Ennek nem csak az az oka, hogy az adatok memóriából való lekérése lassabb, mint a számítás, hanem azért is, mert a keresőtábla megtöltheti a memóriát és a gyorsítótárat . Ha a tábla nagy, minden hozzá való hozzáférés nagy valószínűséggel gyorsítótár kihagyást eredményez . Egyes programozási nyelveken (mint például a Java ) a keresési tábla elérése még "drágább" lehet a kötelező határellenőrzés miatt, amely további összehasonlításokat és elágazásokat tartalmaz minden keresési művelethez.

A keresőtáblák létrehozásának két alapvető korlátja van. Az első a rendelkezésre álló memória teljes mennyisége: a táblának bele kell férnie a rendelkezésre álló helyre, bár a keresési táblát lemezen is megteheti, ezzel növelve a keresési művelet idejét. Egy másik korlát a keresőtábla létrehozásához szükséges idő az első futtatáskor – bár erre a műveletre általában csak egyszer van szükség, túlságosan időigényes lehet, így a keresőtáblák használata nem megfelelő megoldás.

A szinusz kiszámítása

A legtöbb számítógép csak az alapvető aritmetikát támogatja , és nem tudja közvetlenül kiszámítani a szinuszértéket. Ehelyett a szinusz értékének nagy pontosságú kiszámításához a CORDIC módszert vagy a Taylor sorozatot használják :

Egy ilyen számítás azonban sokáig tarthat, különösen lassú processzoron, és sok olyan alkalmazás van, mint például a számítógépes grafika , amelynek másodpercenként több ezer szinusz értékét kell kiszámítania. Gyakori megoldás a szinuszértékek táblázatának előre kiszámítása, majd a szám szinuszának megtalálása a számhoz legközelebbi argumentum kiválasztására redukálódik a táblázatból (a megfelelő függvényérték közel lesz a helyes értékhez, mert a szinusz folytonos és korlátos függvény) . Például:

valós tömb szinusz_tábla[-1000..1000] x esetén -1000 és 1000 között szinusz_tábla[x] := szinusz(pi * x / 1000) függvény lookup_sine(x) return sine_table[round(1000 * x / pi)]

A táblázat sok memóriát igényel – például ha dupla pontosságú lebegőpontos számokat használunk, akkor 16 000 bájtra lesz szükség . Kevesebb pontot használhat, de akkor csökken a pontosság. Ilyen esetekben jó gyakorlat a lineáris közelítés .

Íme egy példa a lineáris közelítésre:

függvény lookup_sine(x) x1 := emelet (x*1000/pi) y1 := szinusz_tábla[x1] y2 := szinusz_tábla[x1+1] return y1 + (y2-y1)*(x/1000/pi-x1)

Az interpoláció használatakor gyakran előnyös az adatok egyenetlen eloszlása: ott, ahol a függvény a legközelebb van az egyeneshez, a függvény kiszámításához vegyen kevés pontot, de ha a függvény görbülete nagy, akkor vegyen több pontot. ebből a tartományból, hogy a közelítés inkább valós görbének tűnjön (lásd még Interpoláció ).

Példák

Példa szinusztáblázatra ( C programozási nyelven ):

// 8 bites szinusztábla const unsigned char sinetable [ 256 ] = { 128 , 131 , 134 , 137 , 140 , 143 , 146 , 149 , 152 , 156 , 159 , 162 , 165 , 168 , 171 , 174 , 176 , 179 , 182 , 185 , 188 , 191 , 193 , 196 , 199 , 201 , 204 , 206 , 209 , 211 , 213 , 216 , 218 , 220 , 222 , 224 , 226 , 228 , 230 , 232 , 234 , 236 , 237 , 239 , 240 , 242 , 243 , 245 , 246 , 247 , 248 , 249 , 250 , 251 , 252 , 252 , 253 , 254 , 254 , 255 , 255 , 255 , 255 , 255 , 255 , 255 , 255 , 255 , 255 , 255 , 254 , 254 , 253 , 252 , 252 , 251 , 250 , 249 , 248 , 247 , 246 , 245 , 243 , 242 , 240 , 239 , 237 , 236 , 234 , 232 , 230 , 228 , 226 , 224 , 222 , 220 , 218 , 216 , 213 , 211 , 209 , 206 , 204 , 201 , 199 , 196 , 193 , 191 , 188 , 185 , 182 , 179 , 176 , 174 , 171 , 168 , 165 , 162 , 159 , 156 , 152 , 149 , 146 , 143 , 140 , 137 , 134 , 131 , 128 , 124 , 121 , 118 , 115 , 112 , 109 , 106 , 103 , 99 , 96 , 93 , 90 , 87 , 84 , 81 , 79 , 84 , 81 , 79 , 7 , 6 , 5 , 6 _ _ _ 54 , 51 , 49 , 46 , 44 , 42 , 39 , 37 , 35 , 33 , 31 , 29 , 27 , 25 , 23 , 21 , 19 , 18 , 16 , 19 , 18 , 16 , 19 , 18 , 16 , 1 , 8 7 , 6 , 5 , 4 , 3 , 3 , 2 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 2 , 3 , _ _ 4 , 5 , 6 , 7 , 8 , 9 , 10 , 12 , 13 , 15 , 16 , 18 , 19 , 21 , 23 , 25 , 27 , 29 , 31 , 33 , 3 , 4 , 2 _ _ _ _ _ 46 , 49 , 51 , 54 , 56 , 59 , 62 , 64 , 67 , 70 , 73 , 76 , 79 , 81 , 84 , 87 , 90 , 93 , 96 , 90 , 93 , 96 , 90 , 93 , 96 , 10 , 9 118 , 121 , 124 };

Ebben az esetben a [-1;1]-től kezdődő szinuszértékek a minimális 0-tól a maximális 255-ig terjedő egész számtartományban tükröződnek, a nulla 128-nak felel meg. A CPU-k túlnyomó többségében az egész számokkal végzett műveletek sokkal gyorsabbak, mint lebegőpontos.