Hashlife
Hashlife är en memoiserad algoritm för att beräkna det långsiktiga ödet för en given startkonfiguration i Conways Game of Life och relaterade cellulära automater, mycket snabbare än vad som skulle vara möjligt med alternativa algoritmer som simulerar varje tidssteg för varje cell i automaten. Algoritmen beskrevs första gången av Bill Gosper i början av 1980-talet medan han var engagerad i forskning vid Xerox Palo Alto Research Center . Hashlife implementerades ursprungligen på Symbolics Lisp-maskiner med hjälp av tillägget Flavours .
Hashlife
Hashlife är designat för att utnyttja stora mängder rumslig och tidsmässig redundans i de flesta livsregler. Till exempel, i Conway's Life , slutar många till synes slumpmässiga mönster som samlingar av enkla stilleben och oscillatorer .
Representation
Fältet behandlas vanligtvis som ett teoretiskt oändligt rutnät, med mönstret i fråga centrerat nära ursprunget . Ett quadtree används för att representera fältet. Givet en kvadrat med 2 2 k celler, 2 k på en sida, på k: te nivån av trädet, lagrar hashtabellen 2 k −1 -x-2 k −1 kvadraten av celler i mitten, 2 k − 2 generationer i framtiden. Till exempel, för en 4×4 kvadrat lagrar den 2×2 mitten, en generation framåt; och för en 8×8 kvadrat lagrar den 4×4 centrum, två generationer framåt.
Hashing
Medan ett quadtree vanligtvis har mycket mer overhead än andra enklare representationer (som att använda en matris av bitar ), tillåter det olika optimeringar. Som namnet antyder använder algoritmen hash-tabeller för att lagra noderna i quadtreet. Många delmönster i trädet är vanligtvis identiska med varandra; till exempel kan mönstret som studeras innehålla många kopior av samma rymdskepp , eller till och med stora delar av tomt utrymme. Dessa undermönster kommer alla att hash till samma position i hashtabellen, och därför kan många kopior av samma undermönster lagras med samma hashtabellpost. Dessutom behöver dessa delmönster bara utvärderas en gång, inte en gång per kopia som i andra Life-algoritmer.
Detta leder i sig till betydande förbättringar av resurskraven; till exempel kan en generation av olika uppfödare och spacefillers , som växer med polynomhastigheter , utvärderas i Hashlife med hjälp av logaritmiskt rum och tid.
Superhastighet och cachning
En ytterligare snabbhet för många mönster kan uppnås genom att utveckla olika noder med olika hastigheter. Till exempel skulle man kunna beräkna två gånger antalet generationer framåt för en nod på ( k +1)-te nivån jämfört med en på k: te. För glesa eller repetitiva mönster som den klassiska segelpistolen kan detta resultera i enorma hastigheter, vilket gör att man kan beräkna större mönster hos högre generationer snabbare , ibland exponentiellt . För att dra full nytta av denna funktion bör undermönster från tidigare generationer också sparas .
Eftersom olika mönster tillåts köras med olika hastigheter, har vissa implementeringar, som Gospers eget hlife -program, ingen interaktiv skärm, utan beräknar helt enkelt ett förinställt resultat för ett startmönster, vanligtvis körs från kommandoraden . Nyare program som Golly har dock ett grafiskt gränssnitt som kan driva en Hashlife-baserad motor.
Det typiska beteendet för ett Hashlife-program på ett befrämjande mönster är följande: för det första går algoritmen långsammare jämfört med andra algoritmer på grund av den konstanta omkostnaden som är förknippad med hashning och byggande av trädet ; men senare kommer tillräckligt med data att samlas in och dess hastighet kommer att öka enormt – den snabba hastighetsökningen beskrivs ofta som " exploderande ".
Nackdelar
Liksom många memoiserade koder kan Hashlife förbruka betydligt mer minne än andra algoritmer, särskilt på måttliga mönster med mycket entropi, eller som innehåller undermönster som är dåligt anpassade till gränserna för quadtree-noderna (dvs. power-of-two-storlekar); cachen är en sårbar komponent. Det kan också ta mer tid än andra algoritmer på dessa mönster. Golly , bland andra Life-simulatorer, har alternativ för att växla mellan Hashlife och konventionella algoritmer.
Hashlife är också betydligt mer komplext att implementera . Till exempel behöver den en dedikerad sopsamlare för att ta bort oanvända noder från cachen.
På grund av att de är designade för att bearbeta allmänt förutsägbara mönster, fungerar kaotiska och explosiva regler generellt mycket sämre under Hashlife än de skulle under andra implementeringar.
Se även
- Rent funktionell datastruktur , varav det hashade quadtree är ett
- Hash consing , som var nyckelstrategin som användes i den ursprungliga implementeringen av Hashlife.
- Gosper, Bill (1984). "Utnyttja regelbundenhet i stora cellulära utrymmen". Physica D . Elsevier. 10 (1–2): 75–80. doi : 10.1016/0167-2789(84)90251-3 .
externa länkar
- HashLife från Eric Weissteins Treasure Trove of Life
- Tomas Rokickis implementering av hashlife
- Inträde i Livslexikonet
- Förklaring av algoritmen från Dr. Dobb's Journal
- Gospers algoritm (Hashlife) förklaras