Forudberegning - Precomputation
I algoritmer er forudregning handlingen ved at udføre en indledende beregning før kørselstid for at generere en opslagstabel, der kan bruges af en algoritme for at undgå gentagen beregning hver gang den udføres. Forudberegning bruges ofte i algoritmer, der afhænger af resultaterne af dyre beregninger, der ikke afhænger af algoritmens input. Et trivielt eksempel på forberegning er brugen af hårdkodede matematiske konstanter, såsom π og e , snarere end at beregne deres tilnærmelser til den nødvendige præcision ved kørselstid.
I databaser bruges udtrykket materialisering til at henvise til lagring af resultaterne af en forudberegning, såsom i en materialiseret visning .
Oversigt
Forudberegning af et sæt mellemresultater i starten af en algoritmes udførelse kan ofte øge den algoritmiske effektivitet væsentligt. Dette bliver fordelagtigt, når en eller flere indgange er begrænset til en lille nok rækkevidde til, at resultaterne kan lagres i en rimelig stor hukommelsesblok. Da hukommelsesadgang i det væsentlige er konstant i tidskompleksitet (bortset fra cacheforsinkelser ), kan enhver algoritme med en komponent, der har dårligere end konstant effektivitet over et lille inputområde, forbedres ved forud beregningsværdier. I nogle tilfælde kan effektive tilnærmelsesalgoritmer opnås ved at beregne en diskret delmængde af værdier og interpolere for mellemliggende inputværdier, da interpolering også er en lineær operation.
Historie
Før computere kom til, blev trykte opslagstabeller af værdier brugt af mennesker til at fremskynde håndberegninger af komplekse funktioner, såsom i trigonometriske tabeller , logaritmetabeller og tabeller med statistiske tæthedsfunktioner Skolebørn læres ofte at huske " tidstabeller " for at undgå beregninger af de mest anvendte tal (op til 9 x 9 eller 12 x 12). Allerede så tidligt som 493 e.Kr. skrev Victorius fra Aquitaine en multiplikationstabel med 98 søjler, som gav (i romerske tal ) produktet af hvert nummer fra 2 til 50 gange, og rækkerne var "en liste med tal, der startede med tusind, faldende med hundreder til hundrede, derefter faldende med tiere til ti, derefter med en til en, og derefter fraktionerne ned til 1/144 "
Eksempler
Selv moderne computerimplementeringer af digitale trigonometriske funktioner bruger ofte forudberegnede opslagstabeller til enten at give koefficienter til interpolationsalgoritmer eller til at initialisere successive tilnærmelsesalgoritmer .
Mange angreb på kryptosystemer involverer forberegning.
Eksempler på forudberegning i stor skala som en del af moderne effektive algoritmer inkluderer:
- Rainbow borde
- Perfekt hash
- Den terning angreb
- Forudberegnede BSP-træer til synlighedsberegninger i 3D-grafik
- Forudberegning af radiositet til belysning i 3D-grafik
Kompilatorer bruger forudberegning i udstrakt grad som et middel til at øge kørehastigheden for den resulterende kode: denne forudberegning kan betragtes som en form for delvis vurdering af selve programkoden. Eksempler på denne slags precomputation indbefatter dataflow analyse og styrkereduceringsoptimeringer trin.
