Discussion :

[chlab]

Bonjour, j'aimerai faire revivre un sujet qui s'est fini bien trop tôt !

Il s'agit d'un sujet à propos de l'algorithme hashlife : la discussion que j'ai lu est sur cette page, mais elle est marquée résolue, alors je la relance.

Du coup je remet le dernier post :

Dans l'article sur DrDobbs, le coeur de l'algorithme qui va être transcrit dans la fonction récursive est décrit dans la figure 4: http://www.drdobbs.com/showArticle.j...dj0604b&pgno=6.
La structure quadtree est un noeud d'arbre à 4 branches: NE, NO, SE, SW.
Chaque branche est à son tour un noeud, ou une feuille quand on arrive au "bout de l'arbre". Dans le jeu de la vie, la feuille représente une cellule de l'univers.
Pour ce qui est des niveaux, considérons que la feuille est au niveau 0. Le niveau 1 sera donc un quadtree de 4 feuilles (donc 2x2 cellules de l'univers), Le niveau 2 un quadtree de 4 noeuds de niveau 1 (4x4 cellules), etc...
Initialement, on doit donc construire le quadtree a partir du pattern en entrée, la racine du quadtree sera à un niveau variable suivant sa taille.
Le principe de base de l'algorithme est de calculer la 2^nième génération de la partie centrale d'un quadtree Q1 au niveau n qui est lui même un quadtree Q2 de niveau n-1 composé de:
Q2->NE = Q1->NE->SO
Q2->NO = Q1->NO->SE
Q2->SE = Q1->SE->NO
Q2->SO = Q1->SO->NE
C'est pour cela que le quadtree est la structure idéale pour implémenter l'algorithme hashlife, on composera toujours le noeud central au niveau n-1 à partir d'un ensemble de 4 noeuds au niveau n-2 d'un noeud au niveau n... Si tu me suis toujours je continue dans un prochain post

personnellement, Je viens juste de comprendre la dernière phrase de Hashmike (après beaucoup de temps de réflexion néanmois ) et j'aimerai comprendre la suite !
Notamment pourquoi calculer la 2kième génération de la partie centrale d'un noeud de niveau n? (sur wikipedia ils parlent de calculer la 2n-2ième génération).
Et la structure est-elle vraiment un quadtree ? (parceque on découpe bien en 4 zones, mais finalement c'est la zone centrale qui est interressante ?)

merci beaucoup !!
chlab

[HashMike]

Bonjour,
Heureux de reprendre le cours de cette discussion... Pour répondre à tes questions:
- On calcule la partie centrale d'un noeud car c'est la meilleure méthode (ce n'est pas la seule) pour enclencher la récursivité de l'algorithme et effectuer correctement les calculs en recouvrant tout l'espace de l'univers à calculer sans "oublier" des cellules.
- La structure est réellement un quadtree car le calcul du noeud central (comme expliqué dans l'article sur Dr Dobbs) est effectué à partir d'un calcul récursif effectué sur les 4 noeuds qui le composent... Donc la structure quadtree est réellement la pierre angulaire de hashlife !
- Le calcul est exprimé par le code java fourni dans l'article sur Dr Dobbs fourni dans le listing 3, le voici

Node horizontalForward(Node w, Node e) {
return node(w.ne, e.nw, w.se, e.sw).nextGeneration();
}
Node verticalForward(Node n, Node s) {
return node(n.sw, n.se, s.nw, s.ne).nextGeneration();
}
Node centeredForward() {
return node(nw.se, ne.sw, sw.ne, se.nw).nextGeneration() ;
}
Node nextGeneration() {
if (level == 2) {
... do base case through normal simulation ...
} else {
Node n00 = nw.nextGeneration(),
n01 = horizontalForward(nw, ne),
n02 = ne.nextGeneration(),
n10 = verticalForward(nw, sw),
n11 = centeredForward(),
n12 = verticalForward(ne, se),
n20 = sw.nextGeneration(),
n21 = horizontalForward(sw, se),
n22 = se.nextGeneration() ;
return new Node(
new Node(n00, n01, n10, n11).nextGeneration(),
new Node(n01, n02, n11, n12).nextGeneration(),
new Node(n10, n11, n20, n21).nextGeneration(),
new Node(n11, n12, n21, n22).nextGeneration());
}
}

La stucture Node étant de type quadtree composée des sous-noeuds nw,ne,sw,se... C'est la fonction NextGeneration qui est appelée récursivement pour effectuer les calculs.
Je pense que tu saisis de plus en plus la complexité de cet algorithme... Enfin si tu arrive à comprendre ce que fait la fonction NextGeneration tu auras fait un grand pas !

[chlab]

Merci beaucoup pour ta réponse !
En fait je m'étais déjà rendu sur le site de DrDobbs, mais n'étant pas d'un bon niveau en anglais et en Java, je n'y ai pas passé beaucoup de temps

En fait si je comprends bien l'algorithme, il crée 9 noeuds à partir des 16 sous-sous-noeuds de niveau N-2 du noeud de niveau N, puis les recolle en 4 nouveaux quadruplets de noeuds de niveaux N-1?

ca ferai un truc comme ca :
au lieu d'avoir un arbre (quadtree)
Q-> (Q.nw Q.ne Q.se Q.sw) avec Q,nw , ... , de niveau N-1
on travaille avec un arbre
Q-> ( (n00,n01,n10,n11) (...) (...) (...) ) avec n00, ... , de niveau N-1 ??

Soit! J'imagine que le problème de segmenter en quadtree de manière traditionnelle impliquait des problèmes sur les bords (vu que la nouvelle génération dépend de son voisinage, il aurai fallu se balader dans les noeuds adjecents), et que ce problème est corrigé par cette structure.
Mais du coup comment on utilse ça pour calculer les nouvelles générations de l'automate?
D'après ce que je vois, par exemple le nouveau noeud (n00,n01,n10,n11) contient tout l'information nécessaire pour faire évoluer le noeud (Q.nw).se ? Donc au final, on fait évoluer la "zone centrale" de Q?

Merci pour tes éclaircissements !
Chlab

[HashMike]

Petit correctif par rapport à ton mail précédent:

Q-> ( (n00,n01,n10,n11) (...) (...) (...) ) avec n00, ... , de niveau N-1 ??

C'est plutôt

Q.nextGeneration() = ( Node(n00,n01,n10,n11).nextGeneration, Node(...).nextGeneration(),Node(...).nextGeneration(), Node(...).nextGeneration() ) avec n00, ... , de niveau N-2

Les noeuds n00, ... , n22 sont eux mêmes des noeuds centraux calculés à partir de 9 noeuds de niveaux n-1 constitués à partir des 16 noeuds de niveau n-2 du noeud Q.

L'appel de NextGeneration pour un noeud de niveau n fera avancer le pattern de 2^(n-2) générations. C'est un effet mécanique de l'algo hashlife basé sur la structure quadtree... Quand on est au niveau 2 on fait le calcul standard de la prochaine génération qui stoppe la récursivité.

Voilà pour le principe de base de l'algo... Ensuite bien sûr il faudra stocker au niveau de chaque noeud le résultat du calcul de NextGeneration() pour ne pas avoir à le recalculer à chaque fois... On aura donc une structure Node contenant 5 noeuds : nw,ne,sw,se et ng qui sera un pointeur nul au départ.

[chlab]

Merci beaucoup pour ta réponses ! Je ne sais pas si je suis pret de sortir du tunnel, parce que j'avoue que là ça commence à devenir hardue en effet, il a plein de points que je ne saisi pas.
par exemple, je ne comprend toujours pas l'histoire des tailles (ce n'est peut-être pas important, mais en comprenant ça j'y verrai peut-être plus clair):

admettons que j'applique à un noeud Q de niveau N le programme nextGeneration.
par exemple,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

n01 = horizontalForward(Q.nw, Q.ne) = Node (Q.nw.ne, Q.ne.nw, Q.ne.sw, Q.ne.se).nextG

donc n01 est bien vu comme un noeud dont les sousnoeuds sont de niveau N-2 ; donc n01 est bien de niveau N-1 ??

Ensuite pour les appels récursifs (j'écris juste pour vérifier que j'ai bien compris):
si j'appelle Q1, ... , Q4 les noeuds Node(n00,n01,n11,n10), Node (...) , Node (...), Node (...),

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Q.nextG=Node( Q1,Q2,Q3,Q4).nextG =
=Node[ Node(n00,n01,n11,n10).nextG, Q2,Q3,Q4].nextG
=Node[ Node{ Node(Q.nw.ne, Q.ne.nw, Q.ne.sw, Q.ne.se).nextG, n01,n10,n11}.nextG , Q2,Q3,Q4].nextG
=...

donc au niveau 0, on calcule pour chaque feuille, une évolution, donc au final comme il y a 2^N feuilles, on a 2^N calculs ; au niveau 1, on a 2^(N-1) noeud dont il faut calculer 2 évolutions, soit 2^N calculs ; ... jusqu'au niveau N, donc au final on fait N*2^N calculs (en faisant fi du fait qu'on s'arrête au niveau 2 et que le terme "calcul" soit un peu simple);
cela ne va-t-il pas faire exploser la capacité de l'ordinateur ? Ou bien est-ce là que les tables de hashages interviennent ?

Enfin, l'intérêt de calculer la 2^N-ième évolution au niveau permet "d'aller 2^N fois plus vite" dans la génération de l'automate ?

merci pour tes réponses et ta patience !!

[HashMike]

Concernant la taille du noeud n01 dans ton premier exemple, il est au niveau n-2 car comme tu le dis il est égal à :

Node (Q.nw.ne, Q.ne.nw, Q.ne.sw, Q.ne.se).NextGeneration

NextGeneration calcule le noeud central du noeud d'origine, qui est dans cet exemple de niveau n-1 car les 4 sous-noeuds qui le compose sont de niveau n-2, Q étant de niveau n... Pour résumer NextGeneration calcule toujours un noeud de niveau immédiatement inférieur au noeud d'origine.

Ensuite concernant les appels récursifs tu as entièrement raison, si on ne stocke pas le résultat du calcul de NextGeneration pour un noeud donné alors l'algo HashLife est inutile car le nombre d'appels à cette méthode sera exponentiel suivant le nombre de niveaux de l'arbre.

Il est donc absolument nécessaire de stocker dans un 5ème noeud de la structure Node le résultat de ce calcul afin de ne pas le répéter à chaque fois que l'on a affaire au même noeud. Tous les noeuds distincts seront conservés dans une hashtable avec le résultat du calcul. C'est pour cela que l'algo hashlife sera particulièrement performant pour des univers où le même motif se répète souvent, comme le spacefiller par exemple.

Tu connais je pense le principe de la hashtable qui comporte un certain nombre d'entrées au départ, en général un nombre premier pour que la répartition dans la hashtable soit la plus homogène possible. On associe à la hashtable une fonction de hashing qui permettra de déterminer dans quelle entrée on va stocker le noeud pour lequel on effectue le calcul. Dans toutes les implémentations que j'ai vu pour l'instant la fonction de hashing et le résultat d'un calcul sur la valeur du pointeur des sous-noeuds. Pour chaque entrée de la table on gère ensuite une liste chainée pour stocker tous les noeuds présents dans cette entrée.

La première chose que fera la fonction NextGeneration c'est une recherche dans la hashtable du noeud d'origine à l'aide de ses sous-noeuds. Si le noeud est présent alors NextGeneration retournera immédiatement comme résultat le sous-noeud ng, sinon il effectuera le calcul...

Voilà pour la précision sur le niveau des noeuds et pour une petite introduction à la partie "hash" de hashlife, indispensable pour que la magie de l'algo opère . Est-ce que tu me suis toujours ?

[chlab]

merci beaucoup, je crois que j'ai enfin compris la structure de l'algorithme. Même si j'ai encore du mal à me représenter comment fonctionne nextGeneration, j'ai bien compris l'idée et le fil de l'algorithme.

Maintenant mon principal problème vient du codage
Je suis débutant en C, et j'ai du mal à trouver une bonne méthode de représentation des noeuds (vu qu'on ne peut pas à priori créer de matrice de taille n quelconque).
Je vais essayer de trouver une solution à ce problème.
Si j'ai d'autres question sur l'algorithme, quelquechose que je croyais avoir compris mais qui pose problème finalement, je viendrai poser la question.

En tout cas merci beaucoup pour tes explications

[chlab]

Bonjour,
en fait il me reste une question
C'est à propos du hashage : quand doit-on commencer à référencer les évolutions dans une table ?
Est-ce que ce sont seulement les feuilles (de niveau 2 avec une évolution de niveau 1) qui sont référencées dans la table ? Ou bien doit-on y stocker tous les noeuds de niveau inférieur à un niveau N, qui soit le meilleur compromis entre espace mémoire untilisé et accélération du programme ?

Parce qu'on peut imaginer que à partir d'un certain temps (très grand mais certainement atteint vu le nombre de génération effectuées), tous les patterns possibles de niveaux inférieurs à N seront stoqués.
Et le nombre de patterns possible au niveau N est 2^(2^(2N)), ce qui représente déjà 65536 patterns de niveau 2(de coté 4 cases)!!

ESt-ce qu'il faut donc se cantoner juste aux feuilles, ou bien y a-t-il une astuce qui consiste à supprimer de la table de hachage les évolution de patterns peu rencontrés,... ?

Merci d'avance !

[HashMike]

Bonjour,
Concernant le haschage on stocke tous les noeuds dans la table qui sont de niveau supérieur à 2. En fait les noeuds de niveau 2 sont au nombre de 65536 comme tu l'as dit et le résultat de NextGeneration pour ces noeuds peut être pré-calculé et stocké dans un tableau à part à l'initialisation du programme. Pour beaucoup de patterns tu verras que le nombre de noeuds différents ne sera pas en fait si grand que ça, bien sûr la consommation mémoire du programme pourra être importante mais reste gérable surtout avec la capacité mémoire des machines maintenant. Mais si le programme travaille sur des patterns avec un grand nombre de sous motifs différents et/ou sur un très grand nombre de générations, il faudra alors mettre en place un garbage collector pour nettoyer la mémoire des noeuds qui peuvent l'être, il faut au moins que ces noeuds ne fassent pas partie du pattern final dans l'état où il est au moment où on déclenche le garbage collector...
Dans mon implémentation, je passe en paramètre un nombre de noeuds disponibles alloués statiquement au départ (exemple 10000000), et au cours de l'exécution du programme, si plus aucun noeud n'est disponible alors le garbage collector est déclenché (ce test est effectué à chaque fois qu'on a besoin d'un nouveau noeud, c'est à dire qu'il n'a pas été trouvé dans la table de haschage). Tous les noeuds non utilisés dans le pattern final sont rendus disponibles (à l'aide d'un indicateur dans la structure Node) pour pouvoir être réutilisés dans de futurs calculs... L'algorithme hashlife sera rendu plus lent bien sûr car de nombreux calculs temporaires ne seront plus directement disponibles et devront être recalculés. C'est le prix à payer pour ne pas exploser la mémoire.

[chlab]

en fait on pourrait par exemple dans la table de hachage mettre un indice, qu'on incrémente à chaque fois qu'on accède à l'entrée de la table, et dès que le garbage collector se met en route, on efface les entrée dont l'indice est à 0?
Et si il n'y a toujours pas assez de place, on supprime les entrée d'indice les plus faibles?
J'ai un peu du mal à m'imaginer de stocker tous les noeuds d'un pattern type meta_galaxy par exemple (qui fait tourner 6 millions de cellules)! Mais bon faudra que je test ça alors.

Mais du coup, par exemple pour la racine de meta_galaxy qui est peut-être une grille de 10000x10000, comment on fait pour lui associer une valeur (avec la fonction de hachage)?

[HashMike]

Ce qui est important c'est de ne pas collecter des noeuds qui sont utilisés dans le pattern final qu'on est en train de construire, donc en fait les noeuds à conserver sont ceux qui sont le résultat final de chaque calcul de NextGeneration. Dans mon implémentation tout à la fin de NextGeneration j'ajoute dans un pool spécial de pointeurs de noeuds, le noeud qui va être retourné par la fonction. Quand le pool de base des noeuds est épuisé, j'appelle une fonction qui va parcourir le pool spécial et marquer les noeuds qu'il contient (le marqueur est un entier stocké dans la structure Node). Chaque noeud du pool spécial est la racine d'un arbre donc on marque récursivement tout les noeuds de l'arbre (sauf si bien sûr on tombe sur un noeud déjà marqué auquel cas on arrête la récursion). Ensuite on parcoure le pool de base des noeuds: tous les noeuds qui ne sont pas marqués peuvent être libérés et réutilisés pour des calculs ultérieurs... Le garbage collector est je pense la partie la plus délicate à implémenter, si tu peux faire fonctionner ton programme sans cette fonctionnalité ce sera déjà bien, ensuite tu pourras implémenter le garbage collector.
Ensuite le nombre de noeuds utilisés dépendra vraiment du pattern, pour le breeder par exemple quand je calcule la génération 2^4096 la population du pattern final est de l'ordre de 10^2465, et le nombre de noeuds qui décrivent ce pattern est de 360000... Pour le meta_galaxy si tu as un fichier rle qui le décrit je veux bien faire quelques essais avec mon programme pour te donner quelques stats.
Pour ce qui est de la fonction de hachage pour un noeud donné, dans toutes les implémentations que j'ai vu on effectue un calcul sur les adresses mémoire des 4 sous-noeuds (qui sont des entiers de 32 ou 64 bits suivant la plateforme) modulo le nombre d'entrées de la table de hachage.