Lukap tabela

U računarstvu, lukap tabela je niz koji zamenjuje izračunavanje sa jednostavnijim nizom indeksirane operacije. Ušteda vremena u smislu procesiranja je značajna, jer preuzimanje vrednosti iz memorije je često brže nego prolaziti kroz komplikovano računanje ili ulazno/izlazne operacije. Tabele mogu biti izračunate unapred i sačuvane u statičkoj memoriji programa, izračunate ( ili „unapred učitane“) kao deo faze inicijalizacije, ili čak čuvane u hardveru. Lukap tabele se takođe koriste za proveru unetih vrednosti tako što porede sa listom tačnih( ili netačnih) stavki u nizu i u nekim programskim jezicima, mogu da sadrže funkcije pokazivača za obradu odgovarajućeg niza.

Istorija

Pre doba računara, lukap tabele vrednosti, korišćene su za računanje složenih funkcija, kao što su logaritamske i trigonometrijske funkcije.

U Indiji (490god.), Arjabhata je napravio jednu od prvih tabela za vrednost funkcije sinus, koju je kodirao brojni sistem zasnovan an sanskritskom alfabetu U 493god., Vuktorus od Akuatane je napisao tablicu množenja u 98 kolana, koja je davala proizvod (u rimskim ciframa) svakog broja množenog brojevima od do 50, a redovi su bili „lista brojeva koja kreće od hiljadu, opada u stotinama do sto, zatim opada deseticama do 10, pa jedinicama do 1 i na kraju razlomcima do 1/144.

Deo tablice prirodnih logaritama iz dvadesetog veka

Deca u današnjim školama uče tablicu množenja napamet da bi izbegli računanje najčešće korišćenih brojeva (do 9h9 ili 12h12)

U ranoj istoriji računara, ulazno/izlazne operacije su bile vemoa spore (čak i u poredđenju sa brzinom tadašnjih procesora). Bilo je potrebno redukovati „skupu“ opciju čitanja uz pomoć ručnog keširanja kreiranjem statičkih lukap tabela (ugrađenih u program) ili dinamičkim, unapred učitanim, nizovima koji bi sadržali najčešće korišćene podatke. Uprkos uvođenju rasprostranjenog sistema keširanja koje automatizuje proces, nivo lukap tabela aplikacija još ima prostor za unapređenje preformansi za podatke koji se retko, ili nikad, menjaju.

Primeri korišćenja lukap tabela

Jednostavno pronalaženje u nizu, asocijativnom nizu ili povezanoj listi (nesortirana lista)

Ovo je poznato kao linearna pretraga ili pretraga grubom silom, svaki element se proverava da li je jednak zadatoj vrednosti i ukoliko ima poklapanja taj element je rezultat pretrage. Ovo je često najsporiji metod pretrage, osim ako se pojavljuju česte vrednosti u početku. Za jednodimenzioni niz ili povezanu listu, lukap tabela uglavnom ustanovljava da li je došlo do poklapanja sa unetom vrednošću.

Binarna pretraga u nizu ili asocijativnom nizu (sortirana lista)

Primer podeli pa vladaj algoritma, binarna pretraga uključuje traženje elementa utvrđivanjem u kojoj polovini tabele može doći do poklapanja i ponavljanje procesa dok se ne pronađe tražena vrednost ili se ustanovi da je nema. Jedino je moguće ukoliko je lista sortirana ali daje dobre preformanse čak i ako je lista duža.

Trivijalne heš tabele

Za lukap tabele trivijalne heš funkcije, nedodeljena vrednost se direktno koristi kao indeks za jedno dimenzione tabele za tačan rezultat. Za nizove manjeg opsega ovo može biti najbrža pretraga, čak bolja i od binarne pretrage.

Brojanje bitova u nizu bajtova

Jedan problem koji je skupo rešiti na mnogim računarima, jeste brojanje bitova koji su postavljeni na 1 (binarnom sistemu). Često se naziva i naziva funkciju stanovništva. Na primer, decimalni broj "37" je "00100101" u binarnom sistemu, tako da sadrži tri bita koji su postavljeni na logičku "1".

Jednostavan primer S koda, dizajniran da brojimo 1 bitova u tipu int, može izgledati ovako:

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

Ovaj naizgled jednostavni algoritam može da potencijalno „odradi“ stotine ciklusa čak i na modernim arhitekturama, jer se može stvoriti mnogo grananja u petlji - a grananje je sporo. Ovo se može ublažiti korišćenjem odmotavanja petlje i nekih optimizacija kompajlera. Postoji, međutim, jednostavna i mnogo brže algoritamsko rešenje – korišćenjem trivijalnih heš funkcija lukap tabele.

Jednostavno konstruisati statičku tabelu, bits_set, sa 256 unosa daje broj bitova postavljenih na jedan jedan u svakoj mogućoj vrednosti bajtova (npr. 0k00 = 0, 0k01 = 1, 0k02 = 1, i tako dalje). Zatim koristite ovu tabelu da biste pronašli broj jedinica u svakom bajtu Intidžera pomoću trivijalnih heš funkcija lukap-a na svakom bajtu i sumiramo ih. Ovo ne zahteva grane i znatno je brži nego raniji kod.

 /* (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];
}

Kod iznad se može lako popraviti (izbegavanjem operacije logičko I i šiftovanja) promenom tipa promenljivoj H u četvorobajtni neoznačeni niz karaktera, i poželjno, kodiran u liniji kao jedan iskaz, umesto da bude funkcija. Primetite da čak i ovaj jednostavni algoritam sada može biti prespor, zato što prvobitni kod može raditi brže od keša modernih procesora, a (velike) lukap tabele preopterećuju keš i mogu da izazovu sporiji pristup memoriji (pored toga, u prethodnom primeru, to zahteva računarske adrese u tabeli, da obavlja četiri potrebnih lukapova).

Lukap tabele u obradi slika

U aplikacijama za analizu podataka, kao što su aplikacije za obradu slika, lukap tabela se koristi za transformaciju ulaznih podataka u poželjniji izlazni format. Na primer, crno-bela slika Saturna će biti tranformisana u sliku u boji koja će naglasiti razliku u prstenovima.

Klasičan primer smanjenja kompjuterskog računanja korišćenjem lukap tabele je da se dobije rezultat trigonometrijskog računanja, kao što je sinus. Izračunavanje trigonometrijskih funkcija može može značajno da uspori aplikaciju. Ista aplikacija može završiti rad znatno ranije ako izračuna vrednost sinusa ranije, na primer za svaki stepen. Kada program zahteva sinus neke vrednosti, može da koristi lukap tabele za pronalaženje najbližeg sinusa sa memorijske adrese, takođe može interpolirati sinus tražene vrednosti, umesto da koristi matematičke formule. Lukap tabeletako koristi aritmetički koprocesor u kompjuterskom sistemu. Greška u lukap tabeli je bila odgovorna za čuveni Intelov problem pri deljenju u pokretnom zarezu.

Funkcije jedne promenljive (kao što su sinus i kosinus) mogu biti implementirane jednostavnim nizom. Funkcije koje imaju dve ili više promenljivih zahtevaju multidimenzionalne nizove. Funkcije koje imaju više od jednog rezultata mogu biti implementirane sa lukap tabelama koje su nizovi strukura.

Kao što je pomenuto, postoje pomoćna rešenja koja koriste tabele u kombinaciji sa malom količinom računanja, često interpolacija. Izračunavanje unapred u kombinaciji sa interpolacijom može da pruži veću tačnost vrednosti koje se nalaze između dve vrednosti izračunate unapred Ova tehnika zahteva malo više vremena da se izvrši ali može znatno da poboljša tačnost u aplikaciji koja to zahteva. U zavisnosti od toga da li su vrednosti unapred izračunate, preizračunavanje sa interpolacijom može da smanji lukap tabelu a da zadrži tačnost.

U procesu obrade slike, lukap tabele se često nazivaju LUT-ovi (3D mikro tabele) i daju izlaznu vrednostza svaki opseg indeksirane vrednosti. Jedan uobičajni LUT, zove se kolor mapa ili paleta, se koristi za odrećivanje boje i intenziteta vrednosti sa kojom će biti prikazana slika. U kompjuterizovanoj tomografiji se koristi za utvrćivanje prikazivanja intenziteta izmerenog zračenja.

Iako često efikasno, korišćenje lukap tebele može dovesti do velike štete u proračunu ako to što LUT zamenjuje je jednostavno. Vreme za koje se pronađe memorija i složenost zahteva memorije može povećati vreme izvršavanje aplikacije. Mogućnost zagađivanja keša takođe postaje problem. Pristup velikoj tabeli će sigurno dovesti do promašaja u kešu. Ovaj fenomen sve više postaje problem kako proceosi prevazilaze memoriju po brzini. Sličan problem se pojavljuje u optimizaciji kompajliranja. U nekim okruženjima kao što su Java pogramiranje, lukap tabele mogu biti još skuplje zbog obavezne provere granica uključujući dodadtno poređenje i širenje za svaki lukap.

Postoje dva osnovna ograničenja oko toga kada je moguće konstruisati lukap tabelu za potrebnu operaciju. Jedno je količina memorije koja je dostupna: ne može se konstruisati lukap tabela veća od prostora koji je predviđen za nju, mada je moguće da se konstruiše tabela zasnovana na disku na račun vremena za lukap. Druga je vreme koje je potrebno da se izračunaju vrednosti za tabelu u prvom koraku; mada je to potrebno da izračuna samo jednom, i ako je potrebno dosta vremena, onda možda lukap tabela nije prikladno rešenje. Kao što je ranije navedeno tabele mogu biti statički definisane u većini slučajeva.

Računanje sinusa

Većina računara, koji obavljaju samo osnovne aritmetičke operacije, ne mogu direktno izračunati sinus date vrednosti. Umesto toga, oni koriste KORDIK algoritam ili složenu formulu, kao što je Tejlorov polinom, da izračunaju vrednost sinusa sa visokim stepenom preciznosti:

$\operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}$ (za x približno 0)

Međutim, to može biti skupo za izračunavanje, pogotovo na sporim procesorima, a postoji mnogo aplikacija, naročito u kompjuterskoj grafici, koje trebaju da izračunaju više hiljada sinusnih vrednosti svake sekunde. Zajedničko rešenje je da se u početku izračuna sinus mnogih ravnomerno raspoređenih vrednosti, a zatim da pronađe sinus H. Biramo sinus vrednosti najbliži H. Ovo će biti blizu ispravnu vrednost jer sinus je neprekidna funkcija sa stopom ograničene promene. Na primer:

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

Linearna interpolacija sinusne funkcije

Nažalost, tabela zahteva dosta prostora: ako se koriste IEEE brojevi u pokretnom zarezu sa dvostrukom preciznošču biće potrebno više od 16.000 bajtova. Možemo koristiti manje uzorke, ali onda će se naša preciznost znatno pogoršati. Jedno dobro rešenje je linearna interpolacija, koji povlači liniju između dve tačke u tabeli sa obe strane vrednosti i locira rešenje na toj liniji. Ovo je idalje poprilično brzo za izračunavanje, a mnogo preciznije za glatke funkcije kao što je sinus funkcija. Ovde je naš primer korišćenja linearne interpolacije

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)

Drugo rešenje koje koristi četvrtinu prostora, ali je potreblo malo više vremena za izračunavanje, bilo bi da uzme u obzir odnose između sinusa i kosinusa, zajedno sa njihovim pravilima simetrije. U tom slučaju, lukap tebela se izračunava korišćenjem sinus funkcije za prvi kvadrant (tj. sin (0 .. pi / 2)). Kada nam je potrebna vrednost, dodelimo vrednost promenljivoj da bude ugao koji se nalazi u prvom kvadrantu. Zatim smo postavljamo ugao na četiri kvadranta (nije potrebna ako su vrednosti uvek između 0 i 2*pi) i vratićamo tačnu vrednost (tj. Za prvi kvadrant odmah vraća vrednost, za drugi kvadrant se čita iz pi/2-k, za treći i četvrti su negativi prvi i drugi). Za kosinus, samo moramo da vrati uglove pomerene za pi / 2 (odnosno k + pi / 2). Za tangens, delimo sinus kosinusom (u zavisnosti od implementacije, može biti potrebno obraditi slučaj deljenja nulom):

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

Prilikom korišćenja interpolacije, veličina lukap tabela se može smanjiti korišćenjem neravnomernog uzorkovanja, što znači da tamo gde je funkcija je skoro ravna, koristimo par uzorka, dok tamo gde se vrednost menja, brzo koristimo više uzoraka da zbog aproksimizacije sličnoj pravoj krivoj. Za više informacija, pogledajte interpolacije.

Ostale upotrebe lukap tabela

Keš

Keš memorija (disk keš za fajlove ili procesorski keš za podatke ili kod) takođe funkcioniše uz pomoć lukap tabela. Tabela je napravljen veoma brzom memorijom, umesto da se čuva na sporijim, eksternim memorijama i održava dva komada podataka za podopsega bitova koji sačinjavaju jednu spoljnu memoriju (ili disk) adresa (naročito najnižeg bita bilo koje moguće spoljne adrese):

• jedan deo (oznaka) sadrži vrednost preostalih bitova adrese; ako se ovi bitovi poklapaju sa onima sa memorijske adrese za čitanje ili pisanje, onda drugi komad sadrži keširanu vrednost za ovu adresu.
• drugi deo sadrži podatke vezane za tu adresu.

Jedan (brzi) pregled se koristi za čitanje oznake u lukap tabeli na poziciji određenoj najnižim bitovima željene adrese spoljašnje memorije, kao i za utvrđivanje da li je došlo do pogotka u kešu. Ukoliko je došlo do pogotka, nije potreban pristup eksternoj memoriji je (osim operacije pisanja, gde postoji mogućnost da keširane vrednosti moraju da se ažuriraju asinhrono na sporioj memoriji posle određenog vremena, ili ako položaj u kešu mora biti zamenjen da bi se keširala druga adresa).

Hardverski LUT

U digitalnoj logici, n-bitna lukap tabela se može implementirati sa multiplekserom čiji selektivni ulazi su inputi LUT-a, i čiji ulazi su konstante. N-bitni LUT može da kodira bilo koju n-bitnu Bulovu funkciju modelovanjem takve funkcije u istinitosnu tablicu. Ovo je efikasan način kodira Bulovih logičkih funkcija- LUT-ovi sa 4-6 bitonih ulaza su u stvari ključna komponenta savremenih FPGA.

Literatura

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

Spoljašnje veze

• 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.