Hashlife - Hashlife
Hashlife est un algorithme mémorisé pour calculer le sort à long terme d'une configuration de départ donnée dans le jeu de la vie de Conway et les automates cellulaires associés , beaucoup plus rapidement que cela ne serait possible en utilisant des algorithmes alternatifs qui simulent chaque pas de temps de chaque cellule de l'automate. L'algorithme a été décrit pour la première fois par Bill Gosper au début des années 1980 alors qu'il était engagé dans des recherches au Xerox Palo Alto Research Center . Hashlife a été initialement implémenté sur les machines Symbolics Lisp à l'aide de l' extension Flavours .
Hashlife
Hashlife est conçu pour exploiter de grandes quantités de redondance spatiale et temporelle dans la plupart des règles de vie. Par exemple, dans Conway's Life , de nombreux motifs apparemment aléatoires finissent par être des collections de natures mortes et d' oscillateurs simples .
Représentation
Le champ est généralement traité comme une grille théoriquement infinie , avec le motif en question centré près de l' origine . Un quadtree est utilisé pour représenter le champ. Étant donné un carré de 2 2 k cellules, 2 k de côté, au k ième niveau de l'arbre, la table de hachage stocke le carré 2 k −1 -par-2 k −1 de cellules au centre, 2 k − 2 générations dans le futur. Par exemple, pour un carré 4×4, il stocke le centre 2×2, une génération en avant ; et pour un carré 8×8, il stocke le centre 4×4, deux générations en avant.
Hachage
Alors qu'un quadtree a généralement beaucoup plus de temps système que d'autres représentations plus simples (comme l'utilisation d'une matrice de bits ), il permet diverses optimisations. Comme son nom l'indique, l'algorithme utilise des tables de hachage pour stocker les nœuds du quadtree. De nombreux sous-modèles de l'arbre sont généralement identiques les uns aux autres ; par exemple, le motif étudié peut contenir de nombreuses copies du même vaisseau spatial , ou même de grandes étendues d'espace vide. Ces sous - modèles seront tous hachage à la même position dans la table de hachage, et donc plusieurs copies du même subpattern peuvent être stockés en utilisant la même entrée de table de hachage. De plus, ces sous-modèles ne doivent être évalués qu'une seule fois, pas une fois par copie comme dans les autres algorithmes Life.
Cela en soi conduit à des améliorations significatives des besoins en ressources ; par exemple, une génération des divers reproducteurs et remplisseurs d'espace , qui se développent à des vitesses polynomiales , peut être évaluée dans Hashlife en utilisant l' espace et le temps logarithmiques .
Supervitesse et mise en cache
Une accélération supplémentaire pour de nombreux modèles peut être obtenue en faisant évoluer différents nœuds à différentes vitesses. Par exemple, on pourrait calculer deux fois le nombre de générations en avant pour un nœud au ( k + 1)-ième niveau par rapport à un au k ième. Pour les modèles clairsemés ou répétitifs tels que le canon de planeur classique , cela peut entraîner des accélérations considérables, permettant de calculer plus rapidement des modèles plus grands à des générations plus élevées , parfois de manière exponentielle . Pour tirer pleinement parti de cette fonctionnalité, les sous-modèles des générations précédentes doivent également être enregistrés .
Étant donné que différents modèles sont autorisés à s'exécuter à différentes vitesses, certaines implémentations, comme le propre hlifeprogramme de Gosper , n'ont pas d'affichage interactif, mais calculent simplement un résultat prédéfini pour un modèle de départ, généralement exécuté à partir de la ligne de commande . Des programmes plus récents tels que Golly , cependant, ont une interface graphique qui peut piloter un moteur basé sur Hashlife.
Le comportement typique d'un programme Hashlife sur un modèle favorable est le suivant : d'abord, l'algorithme s'exécute plus lentement par rapport aux autres algorithmes en raison de la surcharge constante associée au hachage et à la construction de l' arbre ; mais plus tard, suffisamment de données seront recueillies et sa vitesse augmentera considérablement – l'augmentation rapide de la vitesse est souvent décrite comme « explosant ».
Désavantages
Comme de nombreux codes mémorisés , Hashlife peut consommer beaucoup plus de mémoire que d'autres algorithmes, en particulier sur des motifs de taille modérée avec beaucoup d'entropie, ou qui contiennent des sous-motifs mal alignés sur les limites des nœuds du quadtree (c'est-à-dire des tailles de puissance de deux); le cache est un composant vulnérable. Il peut également consommer plus de temps que d'autres algorithmes sur ces modèles. Golly , parmi d'autres simulateurs de vie, propose des options pour basculer entre Hashlife et les algorithmes conventionnels.
Hashlife est également beaucoup plus complexe à mettre en œuvre . Par exemple, il a besoin d'un ramasse-miettes dédié pour supprimer les nœuds inutilisés du cache.
En raison du fait qu'elles sont conçues pour traiter des modèles généralement prévisibles, les règles chaotiques et explosives fonctionnent généralement beaucoup plus mal sous Hashlife qu'elles ne le feraient sous d'autres implémentations.
Voir également
- Structure de données purement fonctionnelle , dont le quadtree haché fait partie
- Hash consing , qui était la stratégie clé utilisée dans la mise en œuvre originale de Hashlife.
Les références
- Gosper, Bill (1984). "Exploiter les régularités dans les grands espaces cellulaires". Physica D . Elsevier. 10 (1–2) : 75–80. doi : 10.1016/0167-2789(84)90251-3 .
