Hakutaulukkoon

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 21. toukokuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Hakutaulukko on tietorakenne , joka tallentaa  funktion interpoloinnin tulokset . Tämä on yleensä taulukko tai assosiatiivinen matriisi , jota käytetään korvaamaan laskelmat yksinkertaisella hakutoiminnolla . Nopeuden lisäys voi olla merkittävää, koska tietojen hakeminen muistista on usein nopeampaa kuin aikaa vievien laskelmien tekeminen.

Klassinen esimerkki hakutaulukoiden käytöstä on trigonometristen funktioiden , esimerkiksi sinin , arvojen laskenta . Sen suora laskenta voi hidastaa sovellusta huomattavasti. Tämän välttämiseksi sovellus laskee ennalta tietyn määrän siniarvoja ensimmäisessä käynnistyksessä, esimerkiksi kaikille kokonaisille asteille. Sitten, kun ohjelma tarvitsee sinin arvon, se käyttää hakutaulukkoa saadakseen sinin likimääräisen arvon muistista sen arvon laskemisen sijaan (esimerkiksi käyttämällä sarjaa ). Hakutaulukoita käytetään myös matemaattisissa apuprosessoreissa ; Vika Intelin Pentium - prosessorien hakutaulukossa johti pahamaineiseen virheeseen , joka heikensi jakotoiminnan tarkkuutta.

Kauan ennen hakutaulukoiden ohjelmointia ihmiset käyttivät niitä jo manuaalisten laskelmien helpottamiseksi. Erityisen yleisiä olivat logaritmitaulukot sekä trigonometriset ja tilastolliset funktiot.

On olemassa väliratkaisu käytettäessä hakutaulukkoa yhdessä yksinkertaisten laskelmien - interpoloinnin kanssa . Tämän avulla voit löytää tarkemmin arvot kahden ennalta lasketun pisteen välillä. Aikakustannukset nousevat hieman, mutta vastineeksi saadaan parempi laskelmien tarkkuus. Tätä tekniikkaa voidaan myös käyttää pienentämään hakutaulukon kokoa ilman tarkkuuden menetystä.

Hakutaulukoita käytetään laajalti myös tietokoneen kuvankäsittelyssä (tällä alueella vastaavia taulukoita kutsutaan yleensä "paletteiksi").

On tärkeää huomata, että hakutaulukoiden käyttö tehtävissä, joissa ne ovat tehottomia, johtaa työn nopeuden laskuun. Tämä ei johdu vain siitä, että tietojen hakeminen muistista on hitaampaa kuin niiden laskeminen, vaan myös siitä, että hakutaulukko voi täyttää muistin ja välimuistin . Jos taulukko on suuri, jokainen pääsy siihen johtaa todennäköisesti välimuistin puuttumiseen . Joissakin ohjelmointikielissä (kuten Java ) hakutaulukon käyttö voi olla vielä "kallimpaa" pakollisen rajatarkistuksen vuoksi, joka sisältää lisävertailuja ja -haaroja jokaiselle hakutoiminnolle.

Hakutaulukoiden luomisessa on kaksi perusrajoitusta. Ensimmäinen on käytettävissä olevan muistin kokonaismäärä: taulukon täytyy mahtua käytettävissä olevaan tilaan, vaikka voit tehdä hakutaulukon levylle, mikä pidentää hakutoiminnon aikaa. Toinen rajoitus on aika, joka kuluu hakutaulukon luomiseen ensimmäisellä kerralla - vaikka tämä toiminto tarvitaan yleensä vain kerran, se voi olla liian aikaa vievää, joten hakutaulukoiden käyttö ei ole sopiva ratkaisu.

Sinin laskeminen

Useimmat tietokoneet tukevat vain perusaritmetiikkaa , eivätkä ne voi laskea siniarvoa suoraan. Sen sijaan sinin arvon laskemiseksi suurella tarkkuudella he käyttävät CORDIC -menetelmää tai Taylor-sarjaa :

Tällainen laskenta voi kuitenkin kestää kauan, varsinkin hitaalla prosessorilla, ja on monia sovelluksia, kuten tietokonegrafiikka , joiden on laskettava tuhansien sinien arvo sekunnissa. Yleinen ratkaisu on laskea esilaskemalla siniarvojen taulukko ja sitten luvun sinin löytäminen pelkistetään tätä lukua lähinnä olevan argumentin valitsemiseen taulukosta (vastaava funktion arvo on lähellä oikeaa arvoa, koska sini on jatkuva ja rajoitettu funktio) . Esimerkiksi:

todellinen taulukko sinitaulukko[-1000..1000] x : lle välillä -1000 - 1000 sinitaulukko[x] := sini(pi * x / 1000) funktio haku_sini(x) return sini_taulukko[kierros(1000 * x / pi)]

Taulukko vaatii paljon muistia - jos esimerkiksi käytetään kaksinkertaisen tarkkuuden liukulukuja, tarvitaan 16 000 tavua . Voit käyttää vähemmän pisteitä, mutta silloin tarkkuus laskee. Hyvä käytäntö tällaisessa tapauksessa on lineaarinen approksimaatio .

Tässä on esimerkki lineaarisesta approksimaatiosta:

funktio lookup_sini(x) x1 := kerros (x*1000/pi) y1 := sinitaulukko[x1] y2 := sinitaulukko[x1+1] paluu y1 + (y2-y1)*(x/1000/pi-x1)

Interpolaatiota käytettäessä on usein hyödyllistä käyttää epätasaista tiedon jakautumista: niissä paikoissa, joissa funktio on lähinnä suoraa, ota muutama piste funktion laskemiseen, mutta jos funktion kaarevuus on suuri, ota enemmän pisteitä. tältä alueelta niin, että approksimaatio näyttää enemmän todelliselta käyrältä (katso . myös Interpolointi ).

Esimerkkejä

Esimerkki sinitaulukosta ( C-ohjelmointikielellä ):

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

Tässä tapauksessa siniarvot [-1;1]:stä heijastuvat kokonaislukualueella minimin 0:sta maksimiarvoon 255, nolla vastaa 128:a. liukulukulla.