Différences

Ci-dessous, les différences entre deux révisions de la page.

--- travaux:game_of_life [2010/11/16 18:54]
nico
+++ travaux:game_of_life [2010/11/16 20:49] (Version actuelle)
nico
@@ Ligne 14: / Ligne 14: @@
 Les voisines d'une cellule sont les huit cellules l'entourant : N, S, E, O, NE, NO, SE, SO.
-La programmation de cet automate est très simple, il s'agit généralement de créer et manipuler un tableau de deux dimensions.
+=====Introduction=====
-Ce travail - en python - visait à créer le moteur fonctionnel de l'automate (résultat affiché en console) en moins de lignes possible et le plus optimisé possible.
+La programmation de cet automate est assez simple, il s'agit généralement de créer et manipuler un tableau de deux dimensions.
-=====Version 2=====
+Ce travail - en python - vise à créer le moteur fonctionnel de l'automate (et son affichage en console) le plus optimisé possible... en moins de lignes possible.
-//15/11/2010//
+=====Source=====
-Cette version utilise au maximum générateurs, listes et diverses syntaxes courtes, et un tableau d'une seule dimension parcouru par une seule boucle associé à une technique d'index relatifs permettant de l'analyser comme une grille en deux dimensions.
+Ce programme utilise au maximum générateurs, listes et diverses syntaxes courtes, et un tableau d'une seule dimension parcouru par une seule boucle associé à une technique d'index relatifs permettant de l'analyser comme une grille en deux dimensions.
-Le code fait 14 lignes, les trois lignes d'affichage en console comprises.
+Le programme crée une grille de taille donnée, la remplit aléatoirement selon un taux de remplissage, la calcule et met à jour selon les règles de l'automate cellulaire puis l'affiche en console (en indiquant chaque cellule vivante par son nombre de voisins) quand l'utilisateur le demande, et permet de quitter le programme simplement.
+Le code fait 13 lignes et 334 caractères.
 <code python>
 from random import random
-l = 500
+l=10
-rnge = range(l*l)
+r=range(l*l)
-nbrs = (1,-1,l,-l,l+1,l-1,-l+1,-l-1)
+n=(1,-1,l,-l,l+1,l-1,-l+1,-l-1)
-grid = list(int(random()*1.8) for i in rnge)
+g=list(int(random()*1.8) for i in r)
 while not raw_input():
-  last = list(grid)
+  p = list(g)
-  for i in rnge:
+  for i in r:
-    s = sum(last[i+n] for n in nbrs if 0 < i+n < l*l)
+    s = sum(p[i+x] for x in n if 0<i+x<l*l)
-    if not last[i] and s == 3 : grid[i] = 1
+    if not p[i] and s==3 : g[i]=1
-    if last[i] and (s < 2 or s > 3): grid[i] = 0
+    if p[i] and (s<2 or s>3): g[i]=0
-    print str(grid[i]),
+    print chr(32+p[i]*(16+s)),
     if i+1 and not (i+1)%l: print
-  print
 </code>
-====Variables====
+Appuyer sur <key>Enter</key> pour calculer un cycle, rester appuyé pour calculer en boucle.
+Appuyer sur n'importe quelle touche et appuyer sur <key>Enter</key> pour quitter.
+=====Explication=====
+Je décrit ci-dessous le fonctionnement du programme, ligne par ligne.
+====Préparation des variables====
 <code python>
@@ Ligne 51: / Ligne 60: @@
 <code python>
-l = 500
+l=10
 </code>
-''l'' définit la largeur (et longueur) de la grille en nombre de cases. Pour être visible sans problème en console, préférer un tableau inférieur à 50x50 cases. Le programme peut toutefois calculer sans problème un tableau de 600x600 cases par exemple (hors affichage).
+''l'' comme **length** : définit la largeur (et longueur) de la grille en nombre de cases. Pour être visible sans problème en console, préférer un tableau inférieur à 50x50 cases. Le programme peut toutefois calculer sans problème un tableau de 600x600 cases par exemple (hors affichage).
 <code python>
-rnge = range(l*l)
+r=range(l*l)
 </code>
-Cette liste correspond aux index des cases de la grille et sera utilisée pour la créer et la parcourir. La grille est de taille ''l*l'', afin de correspondre à une grille de deux-dimensions de côté ''l''.
+''r'' comme **range** : liste des index des cases de la grille utilisée pour la créer et la parcourir. La grille est de taille ''l*l'' afin de correspondre à une grille de deux-dimensions de côté ''l''.
-Elle est pré-calculée pour une question de performance, cf. [[http://nliautaud.fr/wiki/articles/python_benchmark#while_et_for|python benchmark]].
+Cette liste est pré-calculée pour une question de performance, cf. [[http://nliautaud.fr/wiki/articles/python_benchmark#while_et_for|python benchmark]].
 <code python>
-nbrs = (1,-1,l,-l,l+1,l-1,-l+1,-l-1)
+n=(1,-1,l,-l,l+1,l-1,-l+1,-l-1)
 </code>
-Cette liste décrit les index relatifs des huit voisins (//neighbours//) ramenés au tableau d'une seule dimension. Le processus est détaillé plus bas.
+''n'' comme **neighbours** : Cette liste décrit les index relatifs des huit voisins dans le tableau d'une seule dimension. Le processus est détaillé plus bas.
 ====Initialisation de la grille====
 <code python>
-grid = list(int(random()*1.8) for i in rnge)
+g=list(int(random()*1.8) for i in r)
 </code>
+''g'' comme **grid**.
-Il s'agit d'un "générateur de liste" :
+Il s'agit d'un générateur de liste utilisant la syntaxe :
 <code python>
 list(value for i in range)
 </code>
-Proche de syntaxe courte de création de liste :
+C'est proche de la syntaxe courte de boucle :
 <code python>[value for i in range]</code>
@@ Ligne 85: / Ligne 95: @@
 La valeur ajoutée à la liste est une manière d'obtenir aléatoirement soit ''0'' soit ''1'' : convertir en entier la valeur à virgule flottante aléatoire comprise entre ''0'' et ''1'' renvoyée par ''random()''.
 <code python>int(random()*1.8)</code>
-''1.8'' est un "taux de remplissage" de la grille.
+''1.8'' est donc un "taux de remplissage" de la grille pouvant être manipulé entre ''0'' (''0*0 < résultat < 0*1'', donc grille toujours vide) et ''1.99'' (''1.99*0 < résultat < 1.99*1'', donc grille aléatoirement remplie).
@@ Ligne 92: / Ligne 102: @@
 <code python>
 while not raw_input():
-  last = list(grid)
+  p=list(g)
-  # analyse et mise à jour de la grille
-  print
 </code>
-Cette boucle permet de mettre à jour la grille en appuyant sur <key>Enter</key>. Pour stopper le programme, entrer n'importe quelle valeur puis appuyer sur <key>Enter</key>.
+Cette boucle permet de mettre à jour la grille en appuyant sur <key>Enter</key> (la condition d'exécution est vraie puisque ''raw_input()'' n'a rien renvoyé).
-''last'' est une copie de la grille permettant par la suite l'analyse de la grille dans son état précédent, non modifié, tout en modifiant l'état actuel.
+Pour stopper le programme, entrer n'importe quelle valeur puis appuyer sur <key>Enter</key> (la condition d'exécution est fausse puisque ''raw_input()'' a renvoyé une valeur).
-Le ''print'' vide inscrit un espace dans la console entre l'affichage de deux cycles.
+''p'' comme **previous** est une copie de la grille permettant par la suite l'analyse de la grille dans son état précédent, non modifié, tout en modifiant l'état actuel.
 ====Analyse et modification de la grille====
 <code python>
-  for i in rnge:
+  for i in r:
 </code>
-On répète l'opération suivante pour chaque élément de ''rnge'', i correspondant alors à l'index des cellules de la grille.
+On répète l'opération suivante pour chaque élément de ''r'', i correspondant donc tour à tour à l'index de chaque cellule de la grille.
 ===Somme des voisins===
@@ Ligne 114: / Ligne 122: @@
 <code python>
-    s = sum(last[i+n] for n in nbrs if 0 < i+n < l*l)
+    s=sum(p[i+x] for x in n if 0<i+x<l*l)
 </code>
-Il s'agit encore d'un "générateur de liste" créant la liste des états des huit voisins, intégré à la fonction ''sum()'' faisant directement la somme chacun des éléments de la liste.
+Il s'agit encore d'un générateur de liste créant la liste des états des huit voisins, intégré à la fonction ''sum()'' retournant directement la somme chacun des éléments de la liste.
 Cette ligne est similaire à :
@@ Ligne 122: / Ligne 130: @@
 <code python>
 nbrsList = []
-for n in nbrs:
+for x in n:
-  if 0 < i+n < l*l:
+  if 0 < i+x < l*l:
-    nbrsList.append(last[i+n])
+    nbrsList.append(last[i+x])
 s = sum(nbrsList)
 </code>
-On ajoute les index relatifs stockés dans ''nbrs'' à l'index courant ''i'' pour déterminer l'index des voisins ''i+n''. L'état des voisin lors du cycle précédent est alors déterminé par ''last[i+n]''.
+On ajoute les index relatifs stockés dans ''n'' à l'index courant ''i'' pour déterminer l'index des voisins ''i+x''. L'état des voisin lors du cycle précédent est alors déterminé par ''last[i+x]''.
-Par exemple ''nbr[0]'' est ''1'', l'index de ce voisin est ''i+1'' et son état ''last[i+1]'', ce qui correspond à la case suivante du tableau, donc au voisin de droite.
+Par exemple ''n[0]'' est ''1'', l'index de ce voisin est ''i+1'' et son état ''p[i+1]'', ce qui correspond à la case suivante du tableau, donc au voisin de droite.
 Description des index relatifs :
@@ Ligne 146: / Ligne 154: @@
 La condition impose que l'index du voisin soit bien dans le tableau (une cellule au bord de la grille va observer des cases qui n'existent pas), c'est à dire que son index soit supérieur à ''0'' et inférieur à la taille du tableau :
 <code python>
-  if 0 < i+n < l*l
+  if 0<i+x<l*l
 </code>
 La syntaxe ''x < y < z'', peu courante dans d'autres langages, correspond à ''x < y and y < z''.
-//La technique de la première version de "[[#bordures_mortes|bordure morte]]" n'a pas été réutilisée car elle s'avère peu utile dans un tableau uni-dimensionnel n'ayant que deux bords à vérifier.//
+La technique de la première version de "[[#bordures_mortes|bordure morte]]" n'a pas été réutilisée car elle s'avère peu utile dans un tableau uni-dimensionnel n'ayant que deux bords à vérifier. Mais du coup les bords droite/gauche de la grille sont infinis (un objet sortant à droite réapparaît à gauche).
 ===Modification de la grille===
@@ Ligne 156: / Ligne 164: @@
 Les règles énoncées plus haut peuvent être décrites en deux règles générales de changement.
 <code python>
-    if not last[i] and s == 3 : grid[i] = 1
+    if not p[i] and s==3:g[i]=1
 </code>
 Si l'état de la cellule courante est ''0'' (morte), mais que la somme des voisins vivants est égal à ''3'', on change son état à ''1'' (vivante).
 <code python>
-    if last[i] and (s < 2 or s > 3): grid[i] = 0
+    if p[i] and(s<2 or s>3):g[i]=0
 </code>
 Si l'état de la cellule courante est ''1'' (vivante), mais que la somme des voisins vivants n'est pas comprise entre ''2'' et ''3'', on change son état à ''0'' (morte).
@@ Ligne 170: / Ligne 178: @@
 <code python>
-    print str(grid[i]),
+    print chr(32+p[i]*(16+s)),
-    if i+1 and not (i+1)%l: print
 </code>
-On affiche l'état de la cellule courante, et l'on ne va à la ligne que pour les index multiplicateurs de la largeur de la grille afin d'afficher le tableau en deux dimensions..
+Cette ligne affiche un espace pour les cellules mortes et le nombre de voisins pour les cellules vivantes, en générant le code ASCII en base 10 du caractère visé. Cf. [[wp>ASCII]] et [[http://pyref.infogami.com/chr|chr()]]
-====Benchmark====
+Si la cellule est morte, le calcul sera ''32+0*(16+s)'' donc toujours ''32'', qui est le code ASCII du caractère ''Espace''.
-Le programme s'exécute (hors affichage en console) en ''0.6934'' secondes par cycle (1.67 cycles par seconde) pour une grille de 500x500, soit 250.000 cellules.
+Si la cellule est vivante, le calcul sera ''32+1*(16+s)'' donc toujours ''48+s''. A ''48'' (le code du chiffre ''0'') est rajouté le nombre de voisins, ce qui donne ''49'' (le code du chiffre ''1''), ''50'' (le code du chiffre ''2''), etc...
+<code python>
+    if i+1 and not(i+1)%l:print
+</code>
+On va à la ligne pour les index multiplicateurs de la largeur de la grille afin d'afficher le tableau en deux dimensions.
+=====Benchmark=====
+Les temps ci-après concernent l'exécution du programme légèrement modifié afin d'indiquer une moyenne (sur 100 cycles) des temps de calcul sans affichage de la grille en console :
+<code python>
+from time import time
+t=time()
+cycles = 100
+from random import random
+l=100
+r=range(l*l)
+n=(1,-1,l,-l,l+1,l-1,-l+1,-l-1)
+g=list(int(random()*1.8) for i in r)
+for bench in range(cycles):
+  p=list(g)
+  for i in r:
+    s=sum(p[i+x] for x in n if 0<i+x<l*l)
+    if not p[i] and s==3:g[i]=1
+    if p[i] and(s<2 or s>3):g[i]=0
+print str((time()-t) / cycles)
+</code>
-=====Version 1=====
+^  Taille  ^  Nombre de cellules  ^  Secondes par cycle  ^  Cycles par seconde  ^
+| ''50''   |       ''5.000''      |      ''0.0068''      |    ''147''      |
+| ''100''  |      ''10.000''      |      ''0.0267''      |    ''37.2''     |
+| ''500''  |      ''250.000''     |      ''0.6934''      |    ''1.67''     |
+| ''600''  |      ''360.000''     |      ''1.0087''      |    ''0.99''     |
-//03/11/2010//
+=====Version précédente=====
-Cette version utilise certaines syntaxes courtes et un tableau à deux dimensions.
+Cette version utilise certaines syntaxes courtes, un tableau à deux dimensions et affiche l'état de toutes les cellules un certain nombre de fois.
 lignes, les trois lignes d'affichage en console comprises.
@@ Ligne 208: / Ligne 248: @@
 </code>
-====Bordures mortes====
+===Bordures mortes===
 Un problème à résoudre pour l'optimisation du code était de trouver un moyen court et efficace d'éviter les cases inexistantes. Lorsqu'une cellule est au bord de la grille, elle n'a pas huit voisins, le processus doit donc s'assurer  de ne pas demander l'état de cases en dehors du tableau.
@@ Ligne 221: / Ligne 261: @@
 Toutes les cellules mises à jour ayant alors bien huit voisines et les bordures n'ayant aucune influence sur le résultat des règles car toujours définies à ''0'', il n'est plus besoin d'ajouter une quelconque condition durant le processus.
-====Benchmark====
+===Benchmark===
 Cette version s'exécute (hors affichage en console) en ''0.9613'' secondes par cycle (1.04 cycles par seconde) pour une grille de 500x500, soit 250.000 cellules.