Hashleven - Hashlife
Hashlife is een gememoriseerd algoritme voor het berekenen van het lot op lange termijn van een bepaalde startconfiguratie in Conway's Game of Life en gerelateerde cellulaire automaten , veel sneller dan mogelijk zou zijn met alternatieve algoritmen die elke tijdstap van elke cel van de automaat simuleren. Het algoritme werd voor het eerst beschreven door Bill Gosper in het begin van de jaren tachtig, terwijl hij bezig was met onderzoek in het Xerox Palo Alto Research Center . Hashlife werd oorspronkelijk geïmplementeerd op Symbolics Lisp-machines met behulp van de Flavours- extensie.
Hashleven
Hashlife is ontworpen om in de meeste Life-regels gebruik te maken van grote hoeveelheden ruimtelijke en temporele redundantie . In Conway's Life eindigen bijvoorbeeld veel schijnbaar willekeurige patronen als verzamelingen van eenvoudige stillevens en oscillatoren .
Vertegenwoordiging
Het veld wordt typisch behandeld als een theoretisch oneindig raster, met het patroon in kwestie gecentreerd nabij de oorsprong . Een quadtree wordt gebruikt om het veld weer te geven. Gegeven een vierkant van 2 2 k cellen, 2 k aan een zijde, op het k- de niveau van de boom, slaat de hashtabel het 2 k −1 -bij-2 k −1 vierkant van cellen op in het midden, 2 k − 2 generaties in de toekomst. Voor een vierkant van 4 × 4 slaat het bijvoorbeeld het 2 × 2-centrum op, één generatie vooruit; en voor een vierkant van 8 × 8 slaat het het 4 × 4-centrum op, twee generaties vooruit.
hashen
Hoewel een quadtree doorgaans veel meer overhead heeft dan andere eenvoudigere representaties (zoals het gebruik van een matrix van bits ), maakt het verschillende optimalisaties mogelijk. Zoals de naam al doet vermoeden, gebruikt het algoritme hash-tabellen om de knooppunten van de quadtree op te slaan. Veel subpatronen in de boom zijn meestal identiek aan elkaar; het bestudeerde patroon kan bijvoorbeeld veel exemplaren van hetzelfde ruimteschip bevatten , of zelfs grote delen lege ruimte. Deze deelpatronen zullen alle hash naar dezelfde positie in de hashtabel, en dus veel kopieën van hetzelfde subpatroon kan worden opgeslagen met dezelfde hashtabelingang. Bovendien hoeven deze subpatronen slechts één keer te worden geëvalueerd, niet één keer per kopie zoals in andere Life-algoritmen.
Dit leidt zelf tot aanzienlijke verbeteringen in de resourcevereisten; bijvoorbeeld een generatie van de verschillende fokkers en spacefillers , die met polynomiale snelheden groeien , kan in Hashlife worden geëvalueerd met behulp van logaritmische ruimte en tijd.
Supersnelheid en caching
Een verdere versnelling voor veel patronen kan worden bereikt door verschillende knooppunten met verschillende snelheden te ontwikkelen. Men zou bijvoorbeeld tweemaal het aantal generaties vooruit kunnen berekenen voor een knoop op het ( k +1)-de niveau vergeleken met één op het k de. Voor schaarse of repetitieve patronen zoals het klassieke zweefvliegtuigkanon , kan dit resulteren in enorme versnellingen, waardoor men grotere patronen bij hogere generaties sneller , soms exponentieel , kan berekenen . Om optimaal van deze functie te profiteren, moeten ook subpatronen van vorige generaties worden opgeslagen .
Omdat verschillende patronen op verschillende snelheden kunnen worden uitgevoerd, hebben sommige implementaties, zoals het eigen hlifeprogramma van Gosper , geen interactief scherm, maar berekenen ze eenvoudig een vooraf ingesteld resultaat voor een startpatroon, meestal uitgevoerd vanaf de opdrachtregel . Recentere programma's zoals Golly hebben echter een grafische interface die een op Hashlife gebaseerde engine kan aansturen.
Het typische gedrag van een Hashlife-programma op een gunstig patroon is als volgt: ten eerste werkt het algoritme langzamer in vergelijking met andere algoritmen vanwege de constante overhead die gepaard gaat met hashen en het bouwen van de boom ; maar later zullen er voldoende gegevens worden verzameld en zal de snelheid enorm toenemen - de snelle toename in snelheid wordt vaak beschreven als " exploderend ".
nadelen
Zoals veel gememoriseerde codes, kan Hashlife aanzienlijk meer geheugen verbruiken dan andere algoritmen, vooral op patronen van gemiddelde grootte met veel entropie, of die subpatronen bevatten die slecht zijn uitgelijnd met de grenzen van de quadtree-knooppunten (dwz power-of-two-groottes); de cache is een kwetsbaar onderdeel. Het kan ook meer tijd kosten dan andere algoritmen op deze patronen. Golly , naast andere Life-simulators, heeft opties om te schakelen tussen Hashlife en conventionele algoritmen.
Hashlife is ook aanzienlijk complexer om te implementeren . Het heeft bijvoorbeeld een speciale garbage collector nodig om ongebruikte nodes uit de cache te verwijderen.
Omdat ze zijn ontworpen voor het verwerken van over het algemeen voorspelbare patronen, werken chaotische en explosieve regels over het algemeen veel slechter onder Hashlife dan onder andere implementaties.
Zie ook
- Puur functionele datastructuur , waarvan de gehashte quadtree er één is
- Hash consing , de belangrijkste strategie die werd gebruikt bij de oorspronkelijke implementatie van Hashlife.
Referenties
- Gosper, Bill (1984). "Het benutten van regelmatigheden in grote cellulaire ruimtes". Physica D . Elsevier. 10 (1-2): 75-80. doi : 10.1016/0167-2789(84)90251-3 .
