Keresőtábla
From Wikipedia, the free encyclopedia
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 kulccsal
, egy hash tábla tárolná az értéket
a nyílásban
ahol
egy hash függvény, azaz
a slot számítására szolgál, míg LUT esetén az érték
slotban van tárolva
, így közvetlenül címezhető.[2]:466