Keresőtábla

A számítástechnikában a keresőtábla vagy keresési táblázat (lookup table, LUT) egy olyan tömb, amely a futásidejű számítást egy egyszerűbb tömbindexelési művelettel helyettesíti, a közvetlen címzésnek nevezett folyamatban. A feldolgozási idő megtakarítása jelentős lehet, mivel egy érték visszakeresése a memóriából gyakran gyorsabb, mint egy "drága" számítás vagy input/output művelet végrehajtása.^[1] A táblázatok előre kiszámíthatók és statikus programtárolóban tárolhatók, kiszámíthatók (vagy "előre letölthetők") a program inicializálási fázisának részeként (memoizálás), vagy akár hardveren is tárolhatók alkalmazás-specifikus platformokon. A keresőtáblákat széles körben használják a bemeneti értékek érvényesítésére is, egy tömbben lévő érvényes (vagy érvénytelen) elemek listájához való illeszkedés révén, és egyes programozási nyelveken mutatófüggvényeket (vagy címkék eltolásait) is tartalmazhatják az illesztő bemenet feldolgozásához. Az FPGA-k emellett széles körben alkalmazzák az újrakonfigurálható, hardveresen megvalósított keresőtáblákat, hogy programozható hardverfunkciókat biztosítsanak. A LUT-ok abban különböznek a hash-tábláktól, hogy lekérnek egy értéket $v$ kulccsal $k$ , egy hash tábla tárolná az értéket $v$ a nyílásban $h(k)$ ahol $h$ egy hash függvény, azaz $k$ a slot számítására szolgál, míg LUT esetén az érték $v$ slotban van tárolva $k$ , így közvetlenül címezhető.^[2]^:466

Történelem

Az Abramowitz és Stegun kézikönyvében található tízesalapúlogaritmus-táblázat részlete

A számítógépek megjelenése előtt az értékek keresőtábláit használták az összetett függvények kézi számításának felgyorsítására, például a trigonometriában, a logaritmusban és a statisztikai sűrűségfüggvényekben.^[3]

Az ókori (i.sz. 499) Indiában Árjabhata megalkotta az egyik első szinusztáblát, amelyet szanszkrit betűalapú számrendszerbe kódolt. Kr. u. 493-ban Aquitániai Viktor írt egy 98 oszlopos szorzótáblát, amely (római számokkal) megadta minden szám szorzatát 2-től 50-ig, a sorok pedig „ezerrel kezdődő számok listája, amelyek százával egyre csökkennek. száz, majd tízzel tízre, majd eggyel az egyre csökken, majd a törteket 1/144-ig^[4] legfeljebb 9 x 9 vagy 12 x 12).

A számítógépek történetének korai szakaszában a bemeneti/kimeneti műveletek különösen lassúak voltak – még az akkori processzorsebességekhez képest is. Érdemes volt csökkenteni a költséges olvasási műveleteket a kézi gyorsítótárazással, statikus keresési táblák (a programba ágyazva) vagy dinamikus előre letöltött tömbök létrehozásával, amelyek csak a leggyakrabban előforduló adatelemeket tartalmazzák. A rendszerszintű gyorsítótárazás bevezetése ellenére, amely immár automatizálja ezt a folyamatot, az alkalmazásszintű keresési táblák továbbra is javíthatják a teljesítményt azon adatelemek esetében, amelyek ritkán, ha egyáltalán változnak.

A keresőtáblák az egyik legkorábbi számítógépes táblázatokban implementált funkciók voltak, a VisiCalc kezdeti verziója (1979) az eredeti 20 funkciója között tartalmazott egy LOOKUP funkciót is.^[5] Ezt követték a későbbi táblázatok, például a Microsoft Excel, és speciális VLOOKUP és HLOOKUP függvények egészítették ki a függőleges vagy vízszintes táblázatokban történő keresés egyszerűsítése érdekében. A Microsoft Excelben az XLOOKUP funkció 2019. augusztus 28-tól került bevezetésre.

Korlátozások

Bár egy LUT teljesítménye garantált $O(1)$ , egy keresési műveletnél nem lehet két entitás vagy érték ugyanazzal a kulccsal $k$ . Amikor a kulcsokat tartalmazó $\cup$ univerzum mérete nagy, esetleg nem praktikus vagy lehetetlen a memóriában tárolni. Ezért ebben az esetben egy hash tábla előnyös alternatíva lehet.^[2]^:468

Példák

Triviális hash függvény

Egy triviális hash függvényes kereséshez az előjel nélküli nyers adatértéket közvetlenül egy egydimenziós tábla indexeként használják az eredmény kinyeréséhez. Kis tartományok esetén ez lehet az egyik leggyorsabb keresés, még a bináris keresési sebességet is túllépve nulla elágazás mellett, és konstans idő alatt végrehajtva.^[6]

Bitszámlálás egy bájtsorozatban

Az egyik diszkrét probléma, amelynek megoldása sok számítógépen költséges, az 1-re beállított bitek számának (Hamming-súly, populációs függvény) megszámlálása egy (bináris) számban. Például a „37” decimális szám binárisan „00100101”, tehát három olyan bitet tartalmaz, amelyek bináris „1”-re vannak beállítva.^[7]^:282

Egy egyszerű példa a C-kódra, amelyet úgy terveztek, hogy megszámolja az int 1 bitjét, így nézhet ki:^[7]^:283

int count_ones(unsigned int x) {
 int result = 0;
 while (x != 0) {
  x = x & (x - 1);
  result++;
 }
 return result;
}

A fenti megvalósítás 32 műveletet igényel egy 32 bites érték kiértékeléséhez, amely az elágazás miatt több órajelet is igénybe vehet. Ki lehet bontani egy keresőtáblázatba, amely viszont triviális hash funkciót használ a jobb teljesítmény érdekében.^[7]^:282-283

A 256 bejegyzésből álló bits_set bittömb úgy épül fel, hogy minden lehetséges bájtértékben megadjuk az egy bitkészlet számát (pl. 0x00 = 0, 0x01 = 1, 0x02 = 1 és így tovább). Bár egy futásidejű algoritmus használható a bits_set tömb létrehozására, ez az óraciklusok nem hatékony használata, ha a méretet figyelembe vesszük, ezért előre kiszámított táblát használnak – bár a fordítási időszkript használható a tábla dinamikus generálására és hozzáfűzésére. a forrásfájlhoz. Az egyesek összege az egész szám minden egyes bájtjában kiszámítható triviális hash függvény kereséssel minden bájton; így hatékonyan elkerülhető az elágazás, ami jelentős teljesítményjavulást eredményez.^[7]

„"Lookup tables (LUTs) are an excellent technique for optimizing the evaluation of functions that are expensive to compute and inexpensive to cache. ... For data requests that fall between the table's samples, an interpolation algorithm can generate reasonable approximations by averaging nearby samples."^[8]”

Keresőtáblák a képfeldolgozásban

real array sine_table[-1000..1000]
for x from -1000 to 1000
  sine_table[x] = sine(pi * x / 1000)

function lookup_sine(x)
  return sine_table[round(1000 * x / pi)]

Piros (A), zöld (B), kék (C) 16 bites keresőtábla fájlminta. (A 14-65524-es sorok nem láthatók)

function lookup_sine(x)
  x1 = floor(x*1000/pi)
  y1 = sine_table[x1]
  y2 = sine_table[x1+1]
  return y1 + (y2-y1)*(x*1000/pi-x1)

Az adatelemző alkalmazásokban, például a képfeldolgozásban, egy keresési táblát (LUT) használnak a bemeneti adatok kívánatosabb kimeneti formátummá alakítására. Például a Szaturnusz bolygó szürkeárnyalatos képe színes képpé alakul, hogy kiemelje a gyűrűi közötti különbségeket.

A képfeldolgozás során a keresőtáblákat gyakran LUT -nak (vagy 3DLUT-nak) nevezik, és az indexértékek tartományának mindegyikéhez egy kimeneti értéket adnak. Egy elterjedt LUT-t, a színtérképet vagy palettát használják annak meghatározására, hogy egy adott kép milyen színekkel és intenzitásértékekkel jelenjen meg. A számítógépes tomográfiában az "ablakozás" egy kapcsolódó fogalomra utal, amely meghatározza, hogyan kell megjeleníteni a mért sugárzás intenzitását.

Vita

A futási idejű számítások keresőtáblákkal történő csökkentésének klasszikus példája egy trigonometriai számítás eredményének, például egy érték szinuszának a megszerzése.^[9] A trigonometrikus függvények kiszámítása jelentősen lelassíthatja a számítástechnikai alkalmazást. Ugyanaz az alkalmazás sokkal hamarabb befejeződhet, amikor először kiszámolja számos érték szinuszát, például minden egyes fokszámra (a táblázatot statikus változóként definiálhatjuk a fordítási időben, csökkentve az ismételt futási költségeket). Ha a program megköveteli egy érték szinuszát, akkor a keresőtáblázat segítségével lekérheti a legközelebbi szinuszértéket egy memóriacímből, és a matematikai képlettel történő számítás helyett interpolálhat a kívánt érték szinuszára. A keresőtáblákat így a matematikai társprocesszorok használhatják számítógépes rendszerekben. Az Intel hírhedt lebegőpontos felosztási hibájáért egy keresési tábla hibája volt felelős.

Egyetlen változó függvényei (például szinusz és koszinusz) megvalósíthatók egy egyszerű tömb segítségével. A két vagy több változót tartalmazó függvények többdimenziós tömbindexelési technikákat igényelnek. Az utóbbi esetben tehát a hatvány [x][y] kétdimenziós tömbjét alkalmazhatja egy függvény helyettesítésére az x ^y kiszámításához az x és y értékek korlátozott tartományára. Az egynél több eredménnyel rendelkező függvények olyan keresőtáblákkal valósíthatók meg, amelyek struktúrák tömbjei.

Mint említettük, vannak olyan köztes megoldások, amelyek a táblázatokat kis mennyiségű számítással kombinálják, gyakran interpolációt használva. Az interpolációval kombinált előszámítás nagyobb pontosságot eredményezhet azoknál az értékeknél, amelyek két előre kiszámított érték közé esnek. Ez a technika valamivel több időt igényel a végrehajtásához, de nagymértékben növelheti a pontosságot az ezt igénylő alkalmazásokban. Az előre kiszámított értékektől függően az interpolációval végzett előszámítás is használható a keresőtábla méretének csökkentésére a pontosság megőrzése mellett.

Bár gyakran hatékony, a keresőtábla alkalmazása súlyos büntetést vonhat maga után, ha a LUT által helyettesített számítás viszonylag egyszerű. A memória-visszakeresési idő és a memóriaigények összetettsége növelheti az alkalmazások működési idejét és a rendszer bonyolultságát ahhoz képest, ami az egyenes képletszámításhoz lenne szükséges. Problémát jelenthet a gyorsítótár szennyezésének lehetősége is. A nagy táblák tábla-hozzáférése szinte biztosan gyorsítótár-kihagyást okoz. Ez a jelenség egyre nagyobb problémát jelent, mivel a processzorok túlszárnyalják a memóriát. Hasonló probléma jelentkezik az újramaterializálásnál, a fordítóoptimalizálásnál. Egyes környezetekben, például a Java programozási nyelvben, a táblázatkeresések még drágábbak lehetnek a kötelező határellenőrzés miatt, amely minden kereséshez további összehasonlítást és elágazást foglal magában.

Két alapvető korlátja van arra vonatkozóan, hogy mikor lehet létrehozni egy keresőtáblát egy szükséges művelethez. Az egyik a rendelkezésre álló memória mennyisége: nem lehet létrehozni a tábla számára rendelkezésre álló helynél nagyobb keresőtáblát, bár lehetséges lemezalapú keresési táblákat készíteni a keresési idő rovására. A másik a táblaértékek első lépésben történő kiszámításához szükséges idő; bár ezt általában csak egyszer kell megtenni, ha túl hosszú ideig tart, előfordulhat, hogy a keresőtábla használata nem megfelelő megoldás. Ahogy azonban korábban említettük, a táblázatok sok esetben statikusan definiálhatók.

Szinuszok számítása

A legtöbb számítógép csak alapvető aritmetikai műveleteket hajt végre, és nem tudja közvetlenül kiszámítani egy adott érték szinuszát. Ehelyett a CORDIC algoritmust vagy egy összetett képletet, például a következő Taylor-sort használják a szinusz értékének nagy pontosságú kiszámításához:^[10]^:5

\operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}\quad (x\approx 0)

Ennek kiszámítása azonban költséges lehet, különösen lassú processzorokon, és sok olyan alkalmazás van, különösen a hagyományos számítógépes grafikákban, amelyeknek másodpercenként sok ezer szinuszértéket kell kiszámítaniuk. Gyakori megoldás, hogy kezdetben sok egyenletes eloszlású érték szinuszát számítjuk ki, majd az x szinuszának megtalálásához tömbindexelési művelettel kiválasztjuk az x- hez legközelebb eső érték szinuszát. Ez közel lesz a helyes értékhez, mert a szinusz egy folytonos függvény, korlátos változási sebességgel.^[10] Például:^[11] : 545–548

int count_ones(int input_value) {
  union four_bytes {
    int big_int;
    char each_byte[4];
  } operand = input_value;
  const int bits_set[256] = {
      0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4,
      2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
      2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
      4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
      3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
      4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
      4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
  return (bits_set[operand.each_byte[0]] + bits_set[operand.each_byte[1]] +
          bits_set[operand.each_byte[2]] + bits_set[operand.each_byte[3]]);
}}

Lineáris interpoláció a szinuszfüggvény egy részén

Sajnos a táblázat elég sok helyet igényel: ha IEEE dupla pontosságú lebegőpontos számokat használunk, akkor több mint 16 000 bájtra lenne szükség. Kevesebb mintát használhatunk, de akkor a pontosságunk jelentősen romlik. Az egyik jó megoldás a lineáris interpoláció, amely vonalat húz a táblázat két pontja közé az érték mindkét oldalán, és ezen a vonalon keresi meg a választ. Ez még mindig gyorsan kiszámítható, és sokkal pontosabb olyan sima függvényeknél, mint a szinuszfüggvény. Íme egy példa a lineáris interpoláció használatára:

function lookup_sine(x)
  x1 = floor(x*1000/pi)
  y1 = sine_table[x1]
  y2 = sine_table[x1+1]
  return y1 + (y2-y1)*(x*1000/pi-x1)

A lineáris interpoláció olyan interpolált függvényt biztosít, amely folytonos, de általában nem lesz folytonos deriváltja. A folytonos és folytonos első deriválttal rendelkező táblázatkeresés simább interpolációjához a kocka alakú Hermite spline-t kell használni.

Interpoláció esetén a keresőtábla mérete csökkenthető egyenetlen mintavételezéssel, ami azt jelenti, hogy ahol a függvény közel van az egyeneshez, ott kevés mintapontot használunk, míg ahol gyorsan változtat az érték, ott több mintapontot használunk a közelítés megtartásához. közel a valódi görbéhez. További információkért lásd az interpolációt.

A keresőtáblák egyéb felhasználási módjai

Gyorsítótárak

A tároló-gyorsítótárak (beleértve a fájlok lemezes gyorsítótárát, vagy a kód vagy az adatok processzor-gyorsítótárai) szintén keresőtáblaként működnek. A táblázat nagyon gyors memóriával készült, ahelyett, hogy lassabb külső memóriában tárolná, és két adatot tart fenn a külső memória (vagy lemez) címét alkotó bitek altartományához (nevezetesen a lehetséges külső cím legalacsonyabb bitjeihez). :

egy darab (a címke) tartalmazza a cím fennmaradó bitjeinek értékét; ha ezek a bitek egyeznek az olvasási vagy írási memóriacímből származó bitekkel, akkor a másik darab tartalmazza ennek a címnek a gyorsítótárazott értékét.
a másik darab az adott címhez tartozó adatokat tartja karban.

Egyetlen (gyors) keresést hajtanak végre, hogy beolvassák a címkét a keresőtáblában a kívánt külső tárolócím legalacsonyabb bitjei által meghatározott indexen, és megállapítsák, hogy a memóriacímet elérte-e a gyorsítótár. Ha találatot talál, nincs szükség a külső memóriához való hozzáférésre (kivéve az írási műveleteket, ahol előfordulhat, hogy a gyorsítótárazott értéket egy idő után aszinkron módon frissíteni kell a lassabb memóriához, vagy ha a gyorsítótárban lévő pozíciót le kell cserélni egy másik gyorsítótárazásához cím).

Hardveres LUT-ok

A digitális logikában egy keresőtábla megvalósítható egy multiplexerrel, amelynek kiválasztott sorait a címjel hajtja meg, és amelynek bemenetei a tömbben lévő elemek értékei. Ezek az értékek vagy vezetékesek lehetnek, például egy ASIC-ben, amelynek célja egy adott funkcióra vonatkozik, vagy D reteszekkel biztosíthatók, amelyek lehetővé teszik a konfigurálható értékek megadását (ROM, EPROM, EEPROM vagy RAM).

Egy n -bites LUT bármilyen n -bemenetű Boole-függvényt kódolhat, ha a függvény igazságtáblázatát a LUT-ban tárolja. Ez egy hatékony módja a logikai függvények kódolásának, és a 4-6 bites bemeneti LUT-ok valójában a modern mezőprogramozható kaputömbök (FPGA-k) kulcsfontosságú összetevői, amelyek újrakonfigurálható hardveres logikai képességeket biztosítanak.

Adatgyűjtő és ellenőrző rendszerek

Az adatgyűjtő és -ellenőrző rendszerekben a keresőtáblákat általában a következő műveletek elvégzésére használják:

A kalibrációs adatok alkalmazása a kalibrálatlan mérési vagy alapjelértékek korrekcióinak alkalmazása érdekében; és
Mértékegység-átalakítás vállalása; és
Általános, felhasználó által definiált számítások végrehajtása.

Egyes rendszerekben ezekhez a számításokhoz polinomok is definiálhatók a keresőtáblák helyett.

Jegyzetek

↑ McNamee: Automated Memoization in C++, 1998. augusztus 21. [2019. április 16-i dátummal az eredetiből archiválva].
↑ ^a ^b Kwok (1995). „An efficient data structure for the advancing-front triangular mesh generation technique”. Communications in Numerical Methods in Engineering 11 (5), 465–473. o, Kiadó: Wiley & Sons. DOI:10.1002/cnm.1640110511.
↑ szerk.: Campbell-Kelly: The History of Mathematical Tables: From Sumer to Spreadsheets. Oxford University Press (2003)
↑ Maher, David. W. J. and John F. Makowski. "Literary Evidence for Roman Arithmetic With Fractions", 'Classical Philology' (2001) Vol. 96 No. 4 (2001) pp. 376–399. (See page p.383.)
↑ Bill Jelen: "From 1979 – VisiCalc and LOOKUP"!, by MrExcel East, 31 March 2012
↑ Cormen, Thomas H.. Introduction to algorithms, 3rd, Cambridge, Mass.: MIT Press, 253–255. o. (2009. június 19.). ISBN 9780262033848. Hozzáférés ideje: 2015. november 26.
↑ ^a ^b ^c ^d Jungck P.. Developing for Performance. In: packetC Programming. Apress. DOI: 10.1007/978-1-4302-4159-1_26 (2011). ISBN 978-1-4302-4159-1
↑ nvidia gpu gems2 : using-lookup-tables-accelerate-color
↑ Sasao, T.; Butler, J. T.; Riedel, M. D.: Application of LUT Cascades to Numerical Function Generators. Defence Technical Information Center. NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING. (Hozzáférés: 2024. május 17.)
↑ ^a ^b Sharif (2014). „High-performance mathematical functions for single-core architectures”. Journal of Circuits, Systems and Computers 23, Kiadó: World Scientific. DOI:10.1142/S0218126614500510.
↑ Randall Hyde. The Art of Assembly Language, 2nd Edition. No Starch Press (2010. március 1.). ISBN 978-1593272074

Fordítás

Ez a szócikk részben vagy egészben a Lookup table című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

Az összeszerelés művészete: Számítás táblázatos kereséssel
"Bit Twiddling Hacks" (keresőtáblákat is tartalmaz) Írta: Sean Eron Anderson , a Stanford Egyetemről
Paul McNamee, Johns Hopkins Egyetem memoizációja C++ nyelven, amely megtakarításokat mutat
Henry S. Warren Jr. "A felgyorsított népességszámlálás keresése"

[1] McNamee: Automated Memoization in C++, 1998. augusztus 21. [2019. április 16-i dátummal az eredetiből archiválva].

[Kwok95-2] Kwok (1995). „An efficient data structure for the advancing-front triangular mesh generation technique”. Communications in Numerical Methods in Engineering 11 (5), 465–473. o, Kiadó: Wiley & Sons. DOI:10.1002/cnm.1640110511.

[3] szerk.: Campbell-Kelly: The History of Mathematical Tables: From Sumer to Spreadsheets. Oxford University Press (2003)

[4] Maher, David. W. J. and John F. Makowski. "Literary Evidence for Roman Arithmetic With Fractions", 'Classical Philology' (2001) Vol. 96 No. 4 (2001) pp. 376–399. (See page p.383.)

[5] Bill Jelen: "From 1979 – VisiCalc and LOOKUP"!, by MrExcel East, 31 March 2012

[6] Cormen, Thomas H.. Introduction to algorithms, 3rd, Cambridge, Mass.: MIT Press, 253–255. o. (2009. június 19.). ISBN 9780262033848. Hozzáférés ideje: 2015. november 26.

[apress11-7] Jungck P.. Developing for Performance. In: packetC Programming. Apress. DOI: 10.1007/978-1-4302-4159-1_26 (2011). ISBN 978-1-4302-4159-1

[8] vidia gpu gems2 : using-lookup-tables-accelerate-color

[9] Sasao, T.; Butler, J. T.; Riedel, M. D.: Application of LUT Cascades to Numerical Function Generators. Defence Technical Information Center. NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING. (Hozzáférés: 2024. május 17.)

[sharif14-10] Sharif (2014). „High-performance mathematical functions for single-core architectures”. Journal of Circuits, Systems and Computers 23, Kiadó: World Scientific. DOI:10.1142/S0218126614500510.

[11] Randall Hyde. The Art of Assembly Language, 2nd Edition. No Starch Press (2010. március 1.). ISBN 978-1593272074

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]