Uppslagstabell

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 21 maj 2018; kontroller kräver 5 redigeringar .

En uppslagstabell är en  datastruktur som lagrar resultaten av en funktions interpolation . Detta är vanligtvis en array eller associativ array som används för att ersätta beräkningar med en enkel uppslagsoperation . Hastighetsökningen kan vara betydande, eftersom det ofta går snabbare att hämta data från minnet än att göra tidskrävande beräkningar.

Ett klassiskt exempel på användningen av uppslagstabeller är beräkningen av värdena för trigonometriska funktioner , till exempel sinus . Dess direkta beräkning kan avsevärt sakta ner applikationen. För att undvika detta förberäknar applikationen ett visst antal sinusvärden vid första starten, till exempel för alla hela grader. Sedan, när programmet behöver värdet på sinus, använder det uppslagstabellen för att få det ungefärliga värdet på sinus från minnet, istället för att beräkna dess värde (till exempel med serier ). Uppslagstabeller används också i matematiska samprocessorer ; en bugg i uppslagstabellen i Intels Pentium- processorer ledde till den ökända buggen som minskade noggrannheten i divisionsoperationen.

Långt innan uppslagstabeller var i programmering, användes de redan av människor för att göra manuella beräkningar enklare. Särskilt vanligt var tabeller av logaritmer , såväl som trigonometriska och statistiska funktioner.

Det finns en mellanlösning när man använder en uppslagstabell i kombination med enkla beräkningar - interpolation . Detta gör att du mer exakt kan hitta värden mellan två förberäknade punkter. Tidskostnaderna kommer att öka något, men i gengäld kommer större noggrannhet i beräkningarna att tillhandahållas. Denna teknik kan också användas för att minska storleken på uppslagstabellen utan förlust av precision.

Uppslagstabeller används också i stor utsträckning vid datorbildbehandling (i detta område brukar motsvarande tabeller kallas "paletter").

Det är viktigt att notera att användningen av uppslagstabeller i de uppgifter där de är ineffektiva leder till en minskning av arbetshastigheten. Detta beror inte bara på att det är långsammare att hämta data från minnet än att beräkna det, utan också för att uppslagstabellen kan fylla minnet och fylla cachen . Om tabellen är stor kommer varje åtkomst till den med största sannolikhet att resultera i en cachemiss . I vissa programmeringsspråk (som Java ) kan åtkomst till uppslagstabellen vara ännu "dyrare" på grund av obligatorisk kontroll av gränser, vilket inkluderar ytterligare jämförelser och grenar för varje uppslagsoperation.

Det finns två grundläggande begränsningar för att skapa uppslagstabeller. Den första är den totala mängden tillgängligt minne: tabellen måste passa in i det tillgängliga utrymmet, även om du kan skapa uppslagstabellen på disken och därigenom öka tiden för uppslagsoperationen. En annan begränsning är den tid det tar att skapa en uppslagstabell vid första körningen - även om denna operation vanligtvis bara behövs en gång, kan den vara för tidskrävande, vilket gör användningen av uppslagstabeller till en olämplig lösning.

Beräknar sinus

De flesta datorer stöder bara grundläggande aritmetik och kan inte beräkna sinusvärdet direkt. Istället, för att beräkna värdet på sinus med en hög grad av noggrannhet, använder de CORDIC- metoden eller Taylor-serien :

En sådan beräkning kan dock ta lång tid, särskilt på en långsam processor, och det finns många applikationer, som datorgrafik , som behöver beräkna värdet av tusentals sinus varje sekund. En vanlig lösning är att förberäkna en tabell med sinusvärden, och att sedan hitta sinus för ett tal reduceras till att välja det argument som ligger närmast detta tal från tabellen (motsvarande funktionsvärde kommer att vara nära det korrekta värdet, eftersom sinus är en kontinuerlig och avgränsad funktion). Till exempel:

real array sine_table[-1000..1000] för x från -1000 till 1000 sinustabell[x] := sinus(pi * x / 1000) funktion lookup_sine(x) return sinus_table[round(1000 * x / pi)]

Tabellen kräver mycket minne - om till exempel flyttaltal med dubbla precision används, kommer 16 000 byte att behövas . Du kan använda färre poäng, men då sjunker noggrannheten. En bra praxis i ett sådant fall är en linjär approximation .

Här är ett exempel på en linjär approximation:

function lookup_sine(x) x1 := golv(x*1000/pi) y1 := sinustabell[x1] y2 := sinustabell[x1+1] returnera y1 + (y2-y1)*(x/1000/pi-x1)

När du använder interpolation är det ofta fördelaktigt att använda en ojämn fördelning av data: på de platser där funktionen är närmast en rät linje, ta några punkter för att beräkna funktionen, men om krökningen av funktionen är stor, ta fler punkter från detta intervall så att approximationen ser mer ut som en verklig kurva (se . även Interpolation ).

Exempel

Sinustabellexempel (i programmeringsspråk C ):

// 8-bitars sinustabell konst unsigned char sinustabell [ 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 , 7 6 , 7 , 6 , 7 , 6 , 7 , 6 , 7 , 7 54 , 51 , 49 , 46 , 44 , 42 , 39 , 37 , 35 , 33 , 31 , 29 , 27 , 25 , 23 , 21 , 19 , 18 , 16 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 3 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 , 3 , 3 , 4 , 3 , 3 , 3 , 3 46 , 49 , 51 , 54 , 56 , 59 , 62 , 64 , 67 , 70 , 73 , 76 , 79 , 81 , 84 , 87 , 90 , 93 , 96 , 1 0 9 , 1 , 1 0 9 , 1 , 1 , 1 , 1 , 1 118 , 121 , 124 };

I det här fallet reflekteras sinusvärdena från [-1;1] i heltalsområdet från minimum 0 till maximalt 255, noll motsvarar 128. I de allra flesta CPU:er är operationer med heltal mycket snabbare än med flyttal.