Hashlife - Hashlife
Hashlife er en husket algoritme for å beregne den langsiktige skjebnen til en gitt startkonfigurasjon i Conways Game of Life og relaterte mobilautomater , mye raskere enn det som ville være mulig ved hjelp av alternative algoritmer som simulerer hvert gangstrinn i hver celle i automaten. Algoritmen ble først beskrevet av Bill Gosper tidlig på 1980-tallet mens han var engasjert i forskning ved Xerox Palo Alto Research Center . Hashlife ble opprinnelig implementert på Symbolics Lisp-maskiner ved hjelp av Flavours- utvidelsen.
Hashlife
Hashlife er designet for å utnytte store mengder romlig og tidsmessig redundans i de fleste livsregler. For eksempel, i Conways liv , ender mange tilsynelatende tilfeldige mønstre som samlinger av enkle stilleben og oscillatorer .
Representasjon
Feltet blir vanligvis behandlet som et teoretisk uendelig rutenett, med det aktuelle mønsteret sentrert nær opprinnelsen . Et kvadratree brukes til å representere feltet. Gitt et kvadrat på 2 2 k celler, 2 k på en side, på k th nivå av treet, lagrer hash-tabellen 2 k −1 -by-2 k −1 kvadrat av celler i midten, 2 k - 2 generasjoner i fremtiden. For eksempel, for en 4 × 4 firkant lagrer den 2 × 2 sentrum, en generasjon fremover; og for en 8 × 8 firkant lagrer den 4 × 4 sentrum, to generasjoner fremover.
Hashing
Mens et firetre vanligvis har langt mer overhead enn andre enklere representasjoner (for eksempel å bruke en matrise av biter ), tillater det forskjellige optimaliseringer. Som navnet antyder, bruker algoritmen hash-tabeller for å lagre nodene i firetreet. Mange undermønstre i treet er vanligvis identiske med hverandre; for eksempel kan mønsteret som studeres inneholde mange kopier av samme romskip , eller til og med store deler av tomt rom. Disse subpatterns vil alle hash til den samme stilling i nøkkeltabellen, og således mange kopier av samme subpattern kan lagres ved hjelp av den samme nummertabellen for oppføring. I tillegg trenger disse undermønstrene bare å bli evaluert en gang, ikke en gang per kopi som i andre Life-algoritmer.
Dette fører til betydelige forbedringer i ressurskravene; for eksempel en generasjon av de forskjellige oppdrettere og spacefillers , som vokser ved polynomfunksjoner hastigheter, kan evalueres i Hashlife bruke logaritmisk tid og rom.
Superspeed og hurtigbufring
En ytterligere hastighet for mange mønstre kan oppnås ved å utvikle forskjellige noder med forskjellige hastigheter. For eksempel kan man beregne dobbelt så mange generasjoner fremover for en node på ( k +1) -th nivå sammenlignet med en på k th. For sparsom eller repetitive mønstre som den klassiske glider pistol , kan dette resultere i enorme speedups, tillater en å beregne større mønstre på høyere generasjoner raskere , noen ganger eksponentielt . For å dra full nytte av denne funksjonen, bør også mønstre fra tidligere generasjoner lagres .
Siden forskjellige mønstre får kjøre i forskjellige hastigheter, har noen implementeringer, som Gospers eget hlifeprogram, ikke en interaktiv skjerm, men bare beregner et forhåndsinnstilt resultat for et startmønster, vanligvis fra kommandolinjen . Nyere programmer som Golly har imidlertid et grafisk grensesnitt som kan kjøre en Hashlife-basert motor.
Den typiske oppførselen til et Hashlife-program på et gunstig mønster er som følger: først går algoritmen langsommere sammenlignet med andre algoritmer på grunn av den konstante overhead forbundet med hashing og bygging av treet ; men senere vil nok data bli samlet, og hastigheten vil øke voldsomt - den raske hastighetsøkningen blir ofte beskrevet som " eksploderende ".
Ulemper
Som mange memoiserte koder, kan Hashlife forbruke betydelig mer minne enn andre algoritmer, spesielt på mønstre med moderat størrelse med mye entropi, eller som inneholder undermønstre som er dårlig justert til grensene til firetrinnodene (dvs. kraft av to størrelser) hurtigbufferen er en sårbar komponent. Det kan også ta mer tid enn andre algoritmer på disse mønstrene. Golly , blant andre Life-simulatorer, har muligheter for å veksle mellom Hashlife og konvensjonelle algoritmer.
Hashlife er også betydelig mer komplisert å implementere . For eksempel trenger den en dedikert søppeloppsamler for å fjerne ubrukte noder fra hurtigbufferen.
På grunn av å være designet for å behandle generelt forutsigbare mønstre, fungerer kaotiske og eksplosive regler generelt mye dårligere under Hashlife enn de ville gjort under andre implementeringer.
Se også
- Rent funksjonell datastruktur , som det hashede firetreet er en av
- Hash consing , som var nøkkelstrategien som ble brukt i den opprinnelige implementeringen av Hashlife.
Referanser
- Gosper, Bill (1984). "Exploiting Regularities in Large Cellular Spaces". Physica D . Elsevier. 10 (1–2): 75–80. doi : 10.1016 / 0167-2789 (84) 90251-3 .
