Лукап табела

У рачунарству, лукап табела је низ који замењује израчунавање са једноставнијим низом индексиране операције. Уштеда времена у смислу процесирања је значајна, јер преузимање вредности из меморије је често брже него пролазити кроз компликовано рачунање или улазно/излазне операције. Табеле могу бити израчунате унапред и сачуване у статичкој меморији програма, израчунате ( или „унапред учитане“) као део фазе иницијализације, или чак чуване у хардверу. Лукап табеле се такође користе за проверу унетих вредности тако што пореде са листом тачних( или нетачних) ставки у низу и у неким програмским језицима, могу да садрже функције показивача за обраду одговарајућег низа.

Историја

Пре доба рачунара, лукап табеле вредности, коришћене су за рачунање сложених функција, као што су логаритамске и тригонометријске функције.

У Индији (490год.), Арјабхата је направио једну од првих табела за вредност функције синус, коју је кодирао бројни систем заснован ан санскритском алфабету У 493год., Вукторус од Акуатане је написао таблицу множења у 98 колана, која је давала производ (у римским цифрама) сваког броја множеног бројевима од до 50, а редови су били „листа бројева која креће од хиљаду, опада у стотинама до сто, затим опада десетицама до 10, па јединицама до 1 и на крају разломцима до 1/144.

Део таблице природних логаритама из двадесетог века

Деца у данашњим школама уче таблицу множења напамет да би избегли рачунање најчешће коришћених бројева (до 9х9 или 12х12)

У раној историји рачунара, улазно/излазне операције су биле вемоа споре (чак и у поредђењу са брзином тадашњих процесора). Било је потребно редуковати „скупу“ опцију читања уз помоћ ручног кеширања креирањем статичких лукап табела (уграђених у програм) или динамичким, унапред учитаним, низовима који би садржали најчешће коришћене податке. Упркос увођењу распрострањеног система кеширања које аутоматизује процес, ниво лукап табела апликација још има простор за унапређење преформанси за податке који се ретко, или никад, мењају.

Примери коришћења лукап табела

Једноставно проналажење у низу, асоцијативном низу или повезаној листи (несортирана листа)

Ово је познато као линеарна претрага или претрага грубом силом, сваки елемент се проверава да ли је једнак задатој вредности и уколико има поклапања тај елемент је резултат претраге. Ово је често најспорији метод претраге, осим ако се појављују честе вредности у почетку. За једнодимензиони низ или повезану листу, лукап табела углавном установљава да ли је дошло до поклапања са унетом вредношћу.

Бинарна претрага у низу или асоцијативном низу (сортирана листа)

Пример подели па владај алгоритма, бинарна претрага укључује тражење елемента утврђивањем у којој половини табеле може доћи до поклапања и понављање процеса док се не пронађе тражена вредност или се установи да је нема. Једино је могуће уколико је листа сортирана али даје добре преформансе чак и ако је листа дужа.

Тривијалне хеш табеле

За лукап табеле тривијалне хеш функције, недодељена вредност се директно користи као индекс за једно димензионе табеле за тачан резултат. За низове мањег опсега ово може бити најбржа претрага, чак боља и од бинарне претраге.

Бројање битова у низу бајтова

Један проблем који је скупо решити на многим рачунарима, јесте бројање битова који су постављени на 1 (бинарном систему). Често се назива и назива функцију становништва. На пример, децимални број "37" је "00100101" у бинарном систему, тако да садржи три бита који су постављени на логичку "1".

Једноставан пример С кода, дизајниран да бројимо 1 битова у типу инт, може изгледати овако:

int broji_jedinice(unsigned int x) {
    int rezultat = 0;
    while (x != 0)
        rezultat++, x = x & (x-1);
    return rezultat;
}

Овај наизглед једноставни алгоритам може да потенцијално „одради“ стотине циклуса чак и на модерним архитектурама, јер се може створити много гранања у петљи - а гранање је споро. Ово се може ублажити коришћењем одмотавања петље и неких оптимизација компајлера. Постоји, међутим, једноставна и много брже алгоритамско решење – коришћењем тривијалних хеш функција лукап табеле.

Једноставно конструисати статичку табелу, битс_сет, са 256 уноса даје број битова постављених на један један у свакој могућој вредности бајтова (нпр. 0к00 = 0, 0к01 = 1, 0к02 = 1, и тако даље). Затим користите ову табелу да бисте пронашли број јединица у сваком бајту Интиџера помоћу тривијалних хеш функција лукап-а на сваком бајту и сумирамо их. Ово не захтева гране и знатно је бржи него ранији код.

 /* (ovaj kod pretpostavlja da je 'int' širine 32 bita) */
 int broji_jedinice(unsigned int x) {
    return bits_set[ x        & 255] + bits_set[(x >>  8) & 255]
         + bits_set[(x >> 16) & 255] + bits_set[(x >> 24) & 255];
}

Код изнад се може лако поправити (избегавањем операције логичко И и шифтовања) променом типа променљивој Х у четворобајтни неозначени низ карактера, и пожељно, кодиран у линији као један исказ, уместо да буде функција. Приметите да чак и овај једноставни алгоритам сада може бити преспор, зато што првобитни код може радити брже од кеша модерних процесора, а (велике) лукап табеле преоптерећују кеш и могу да изазову спорији приступ меморији (поред тога, у претходном примеру, то захтева рачунарске адресе у табели, да обавља четири потребних лукапова).

Лукап табеле у обради слика

У апликацијама за анализу података, као што су апликације за обраду слика, лукап табела се користи за трансформацију улазних података у пожељнији излазни формат. На пример, црно-бела слика Сатурна ће бити транформисана у слику у боји која ће нагласити разлику у прстеновима.

Класичан пример смањења компјутерског рачунања коришћењем лукап табеле је да се добије резултат тригонометријског рачунања, као што је синус. Израчунавање тригонометријских функција може може значајно да успори апликацију. Иста апликација може завршити рад знатно раније ако израчуна вредност синуса раније, на пример за сваки степен. Када програм захтева синус неке вредности, може да користи лукап табеле за проналажење најближег синуса са меморијске адресе, такође може интерполирати синус тражене вредности, уместо да користи математичке формуле. Лукап табелетако користи аритметички копроцесор у компјутерском систему. Грешка у лукап табели је била одговорна за чувени Интелов проблем при дељењу у покретном зарезу.

Функције једне променљиве (као што су синус и косинус) могу бити имплементиране једноставним низом. Функције које имају две или више променљивих захтевају мултидимензионалне низове. Функције које имају више од једног резултата могу бити имплементиране са лукап табелама које су низови струкура.

Као што је поменуто, постоје помоћна решења која користе табеле у комбинацији са малом количином рачунања, често интерполација. Израчунавање унапред у комбинацији са интерполацијом може да пружи већу тачност вредности које се налазе између две вредности израчунате унапред Ова техника захтева мало више времена да се изврши али може знатно да побољша тачност у апликацији која то захтева. У зависности од тога да ли су вредности унапред израчунате, преизрачунавање са интерполацијом може да смањи лукап табелу а да задржи тачност.

У процесу обраде слике, лукап табеле се често називају LUT-ови (3Д микро табеле) и дају излазну вредностза сваки опсег индексиране вредности. Један уобичајни ЛУТ, зове се колор мапа или палета, се користи за одрећивање боје и интензитета вредности са којом ће бити приказана слика. У компјутеризованој томографији се користи за утврћивање приказивања интензитета измереног зрачења.

Иако често ефикасно, коришћење лукап тебеле може довести до велике штете у прорачуну ако то што ЛУТ замењује је једноставно. Време за које се пронађе меморија и сложеност захтева меморије може повећати време извршавање апликације. Могућност загађивања кеша такође постаје проблем. Приступ великој табели ће сигурно довести до промашаја у кешу. Овај феномен све више постаје проблем како процеоси превазилазе меморију по брзини. Сличан проблем се појављује у оптимизацији компајлирања. У неким окружењима као што су Јава пограмирање, лукап табеле могу бити још скупље због обавезне провере граница укључујући додадтно поређење и ширење за сваки лукап.

Постоје два основна ограничења око тога када је могуће конструисати лукап табелу за потребну операцију. Једно је количина меморије која је доступна: не може се конструисати лукап табела већа од простора који је предвиђен за њу, мада је могуће да се конструише табела заснована на диску на рачун времена за лукап. Друга је време које је потребно да се израчунају вредности за табелу у првом кораку; мада је то потребно да израчуна само једном, и ако је потребно доста времена, онда можда лукап табела није прикладно решење. Као што је раније наведено табеле могу бити статички дефинисане у већини случајева.

Рачунање синуса

Већина рачунара, који обављају само основне аритметичке операције, не могу директно израчунати синус дате вредности. Уместо тога, они користе КОРДИК алгоритам или сложену формулу, као што је Тејлоров полином, да израчунају вредност синуса са високим степеном прецизности:

$\operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}$ (за x приближно 0)

Међутим, то може бити скупо за израчунавање, поготово на спорим процесорима, а постоји много апликација, нарочито у компјутерској графици, које требају да израчунају више хиљада синусних вредности сваке секунде. Заједничко решење је да се у почетку израчуна синус многих равномерно распоређених вредности, а затим да пронађе синус Х. Бирамо синус вредности најближи Х. Ово ће бити близу исправну вредност јер синус је непрекидна функција са стопом ограничене промене. На пример:

 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)]

Линеарна интерполација синусне функције

Нажалост, табела захтева доста простора: ако се користе ИЕЕЕ бројеви у покретном зарезу са двоструком прецизношчу биће потребно више од 16.000 бајтова. Можемо користити мање узорке, али онда ће се наша прецизност знатно погоршати. Једно добро решење је линеарна интерполација, који повлачи линију између две тачке у табели са обе стране вредности и лоцира решење на тој линији. Ово је идаље поприлично брзо за израчунавање, а много прецизније за глатке функције као што је синус функција. Овде је наш пример коришћења линеарне интерполације

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)

Друго решење које користи четвртину простора, али је потребло мало више времена за израчунавање, било би да узме у обзир односе између синуса и косинуса, заједно са њиховим правилима симетрије. У том случају, лукап тебела се израчунава коришћењем синус функције за први квадрант (тј. син (0 .. пи / 2)). Када нам је потребна вредност, доделимо вредност променљивој да буде угао који се налази у првом квадранту. Затим смо постављамо угао на четири квадранта (није потребна ако су вредности увек између 0 и 2*пи) и вратићамо тачну вредност (тј. За први квадрант одмах враћа вредност, за други квадрант се чита из пи/2-к, за трећи и четврти су негативи први и други). За косинус, само морамо да врати углове померене за пи / 2 (односно к + пи / 2). За тангенс, делимо синус косинусом (у зависности од имплементације, може бити потребно обрадити случај дељења нулом):

 function init_sine()
     for x from 0 to (360/4)+1
         sine_table[x] := sine(2*pi * x / 360)
 
 function lookup_sine(x)
     x  = wrap x from 0 to 360
     y := mod (x, 90)
 
     if (x <  90) return  sine_table[   y]
     if (x < 180) return  sine_table[90-y]
     if (x < 270) return -sine_table[   y]
                  return -sine_table[90-y]
 
 function lookup_cosine(x)
     return lookup_sine(x + 90)
 
 function lookup_tan(x)
     return (lookup_sine(x) / lookup_cosine(x))

Приликом коришћења интерполације, величина лукап табела се може смањити коришћењем неравномерног узорковања, што значи да тамо где је функција је скоро равна, користимо пар узорка, док тамо где се вредност мења, брзо користимо више узорака да због апроксимизације сличној правој кривој. За више информација, погледајте интерполације.

Остале употребе лукап табела

Кеш

Кеш меморија (диск кеш за фајлове или процесорски кеш за податке или код) такође функционише уз помоћ лукап табела. Табела је направљен веома брзом меморијом, уместо да се чува на споријим, екстерним меморијама и одржава два комада података за подопсега битова који сачињавају једну спољну меморију (или диск) адреса (нарочито најнижег бита било које могуће спољне адресе):

• један део (ознака) садржи вредност преосталих битова адресе; ако се ови битови поклапају са онима са меморијске адресе за читање или писање, онда други комад садржи кеширану вредност за ову адресу.
• други део садржи податке везане за ту адресу.

Један (брзи) преглед се користи за читање ознаке у лукап табели на позицији одређеној најнижим битовима жељене адресе спољашње меморије, као и за утврђивање да ли је дошло до поготка у кешу. Уколико је дошло до поготка, није потребан приступ екстерној меморији је (осим операције писања, где постоји могућност да кеширане вредности морају да се ажурирају асинхроно на спориој меморији после одређеног времена, или ако положај у кешу мора бити замењен да би се кеширала друга адреса).

Хардверски ЛУТ

У дигиталној логици, н-битна лукап табела се може имплементирати са мултиплексером чији селективни улази су инпути ЛУТ-а, и чији улази су константе. Н-битни ЛУТ може да кодира било коју н-битну Булову функцију моделовањем такве функције у истинитосну таблицу. Ово је ефикасан начин кодира Булових логичких функција- ЛУТ-ови са 4-6 битоних улаза су у ствари кључна компонента савремених FPGA.

Литература

• Campbell-Kelly, Martin; Croarken, Mary; Robson, Eleanor, ур. (2. 10. 2003) [2003]. The History of Mathematical Tables From Sumer to Spreadsheets (1st изд.). New York, USA. ISBN 978-0-19-850841-0. 

Спољашње везе

• Fast table lookup using input character as index for branch table
• Art of Assembly: Calculation via Table Lookups
• "Bit Twiddling Hacks" (includes lookup tables) By Sean Eron Anderson of Stanford university
• Memoization in C++ by Paul McNamee, Johns Hopkins University showing savings
• "The Quest for an Accelerated Population Count" by Henry S. Warren, Jr.