Hashlife - Hashlife
Hashlife è un algoritmo memorizzato per calcolare il destino a lungo termine di una determinata configurazione di partenza in Game of Life di Conway e relativi automi cellulari , molto più rapidamente di quanto sarebbe possibile utilizzando algoritmi alternativi che simulano ogni passaggio temporale di ciascuna cellula dell'automa. L'algoritmo è stato descritto per la prima volta da Bill Gosper nei primi anni '80 mentre era impegnato nella ricerca presso lo Xerox Palo Alto Research Center . Hashlife è stato originariamente implementato su macchine Symbolics Lisp con l'aiuto dell'estensione Flavours .
Hashlife
Hashlife è progettato per sfruttare grandi quantità di ridondanza spaziale e temporale nella maggior parte delle regole Life. Ad esempio, in Conway's Life , molti modelli apparentemente casuali finiscono come raccolte di semplici nature morte e oscillatori .
Rappresentazione
Il campo è tipicamente trattato come una griglia teoricamente infinita , con il modello in questione centrato vicino all'origine . Un quadtree viene utilizzato per rappresentare il campo. Dato un quadrato di 2 2 k celle, 2 k per lato, al k- esimo livello dell'albero, la tabella hash memorizza il quadrato di celle 2 k −1 per 2 k −1 al centro, 2 k − 2 generazioni nel futuro. Ad esempio, per un quadrato 4×4 memorizza il centro 2×2, una generazione in avanti; e per un quadrato 8×8 memorizza il centro 4×4, due generazioni avanti.
Hashing
Sebbene un quadtree abbia in genere molto più sovraccarico rispetto ad altre rappresentazioni più semplici (come l'utilizzo di una matrice di bit ), consente varie ottimizzazioni. Come suggerisce il nome, l'algoritmo utilizza tabelle hash per memorizzare i nodi del quadtree. Molti sottoschemi nell'albero sono solitamente identici tra loro; ad esempio il modello in esame può contenere molte copie della stessa astronave , o anche ampie fasce di spazio vuoto. Questi sottoschemi verranno tutti hash nella stessa posizione nella tabella hash, e quindi molte copie dello stesso sottoschema possono essere archiviate utilizzando la stessa voce della tabella hash. Inoltre, questi sottopattern devono essere valutati solo una volta, non una volta per copia come in altri algoritmi Life.
Questo stesso porta a miglioramenti significativi nei requisiti di risorse; ad esempio una generazione dei vari allevatori e spacefiller , che crescono a velocità polinomiali , può essere valutata in Hashlife usando spazio e tempo logaritmici .
Supervelocità e memorizzazione nella cache
Un'ulteriore accelerazione per molti modelli può essere ottenuta evolvendo nodi diversi a velocità diverse. Ad esempio, si potrebbe calcolare il doppio del numero di generazioni successive per un nodo al livello ( k +1)-esimo rispetto a uno al k esimo. Per modelli sparsi o ripetitivi come il classico cannone a aliante , ciò può comportare enormi accelerazioni, consentendo di calcolare modelli più grandi a generazioni più elevate più velocemente , a volte in modo esponenziale . Per sfruttare appieno questa funzionalità, è necessario salvare anche i sottopattern delle generazioni passate .
Poiché modelli diversi possono essere eseguiti a velocità diverse, alcune implementazioni, come il hlifeprogramma di Gosper , non hanno un display interattivo, ma calcolano semplicemente un risultato preimpostato per un modello iniziale, solitamente eseguito dalla riga di comando . I programmi più recenti come Golly , tuttavia, hanno un'interfaccia grafica in grado di pilotare un motore basato su Hashlife.
Il comportamento tipico di un programma Hashlife su un modello favorevole è il seguente: in primo luogo l'algoritmo viene eseguito più lentamente rispetto ad altri algoritmi a causa del sovraccarico costante associato all'hashing e alla costruzione dell'albero ; ma in seguito verranno raccolti dati sufficienti e la sua velocità aumenterà enormemente - il rapido aumento della velocità è spesso descritto come " esplosione ".
Svantaggi
Come molti codici memorizzati , Hashlife può consumare molta più memoria rispetto ad altri algoritmi, specialmente su modelli di dimensioni moderate con molta entropia, o che contengono sottoschemi scarsamente allineati ai limiti dei nodi quadtree (cioè potenza di due dimensioni); la cache è un componente vulnerabile. Può anche consumare più tempo rispetto ad altri algoritmi su questi modelli. Golly , tra gli altri simulatori di Life, ha opzioni per alternare Hashlife e algoritmi convenzionali.
Hashlife è anche molto più complesso da implementare . Ad esempio, ha bisogno di un Garbage Collector dedicato per rimuovere i nodi inutilizzati dalla cache.
Essendo progettate per elaborare modelli generalmente prevedibili, le regole caotiche ed esplosive generalmente funzionano molto più male con Hashlife rispetto ad altre implementazioni.
Guarda anche
- Struttura dati puramente funzionale , di cui il quadtree con hash è uno
- Hash consing , che era la strategia chiave utilizzata nell'implementazione originale di Hashlife.
Riferimenti
- Gosper, Bill (1984). "Sfruttare le regolarità nei grandi spazi cellulari". Physica D . Altrove. 10 (1–2): 75–80. doi : 10.1016/0167-2789(84)90251-3 .
