Automate de Fredkin (aller/retour)
Introduction
Dans ce billet, je propose, sous le prétexte de la programmation de l’automate de Fredkin, de regarder un petit peu du côté :
- de l’outil de profiling Python ;
- de la vectorisation de code avec NumPy ;
- de l’affichage de matrices avec PyGame.
Automate de Fredkin
L’automate de Fredkin est un automate cellulaire 2D. Il est très facile de trouver des informations à son sujet sur le Web. La version que nous allons programmer ici peut être décrite ainsi :
- chaque cellule est soit ON, soit OFF
- l’état suivant d’une cellule dépend du nombre de cellules ON parmi ses 8 voisins directs :
- si ce nombre est pair, la cellule centrale sera OFF
- sinon elle sera ON
- nous allons utiliser un automate 100×100, et le bord de l’automate sera figé à la valeur OFF
Une particularité de cet automate est de répliquer la forme initiale en plusieurs exemplaires. C’est pour observer ceci que la fonction d’initialisation proposée ne met à ON que quelques cellules au centre. Voici ce qui se passe, par exemple, si la forme initiale est un P (on le voit aussi dans l’animation de l’automate en haute de page) aux étapes 0, 8 et 40 :
Programme naïf
Dans cette première version, nous procédons de la manière la plus classique possible, le tableau
est balayé, on compte les voisins de chaque cellule, et on en conclut l’état suivant de la
cellule. Pour l’affichage on balaie aussi le tableau et on affiche un élément graphique
(gfxdraw.box) pour chaque cellule.
# Fichier fredkin.py
import numpy as np
import random
import pygame
import pygame.gfxdraw
_st = {"OFF":0, "ON":1}
_cote = 3
_n = 100
def afficher_naif(screen,tab):
for i in range(tab.shape[0]):
for j in range(tab.shape[1]):
if tab[i,j]==_st["OFF"]:
c=[50,50,100]
elif tab[i,j]==_st["ON"]:
c=[255,255,0]
else:
c=[0,0,0]
pygame.gfxdraw.box(screen, (_cote*i, _cote*j, _cote, _cote), c)
pygame.display.flip()
def init(tab):
for i in range(1, tab.shape[0]-1):
for j in range(1, tab.shape[1]-1):
tab[i,j] = _st["OFF"]
if i in range(19 * _n // 40, 21 * _n // 40) and
j in range(19 * _n // 40, 21 * _n // 40) and random.random()>0.5 :
tab[i,j] = _st["ON"]
def suivant_naif(tab):
""" Calcule l'étape suivante de l'automate """
##########################################
def comptevoisins(i, j):
""" Renvoie le nombre de voisins ON de (i,j) """
c = 0
for x in range(i-1, i+2) :
for y in range(j-1, j+2) :
if tab2[x,y] ==_st["ON"]:
c+=1
if tab2[i][j] == _st["ON"]:
c-=1
return c
##########################################
tab2=tab.copy()
for i in range(1, tab2.shape[0]-1):
for j in range(1, tab2.shape[1] -1):
c=comptevoisins(i, j)
if c%2==0:
tab[i,j] = _st["OFF"]
else:
tab[i,j] = _st["ON"]
def unesimu(screen,tab):
init(tab)
for i in range(10):
suivant_naif(tab)
afficher_naif(screen, tab)
print(i)
def main() :
pygame.init()
tab=np.zeros((_n, _n),dtype = np.uint32)
screen=pygame.display.set_mode((_n * _cote, _n * _cote))
unesimu(screen, tab)
pygame.quit()
main()
Le programme est fonctionnel, mais il n’est pas très rapide… L’outil de profilage cProfile va nous permettre de
chercher les points à optimiser :
$ python3 -m cProfile -o stats.dat fredkin.py
$ python3 -m pstats
% read stats.dat
stats.dat% callees unesim
Function called...
ncalls tottime cumtime
fredkin.py:77(unesimu) 10 0.601 0.689 fredkin.py:11(afficher_naif)
1 0.022 0.022 fredkin.py:39(init)
10 0.131 5.588 fredkin.py:48(suivant_naif)
10 0.001 0.001 {built-in method print}
La colonne qui nous intéresse ici est la colonne cumtime (cumulative time).
Elle contient, pour une exécution de la fonction unesimu le temps passé dans
chaque fonction (et sous fonction des fonctions). On constate que le temps
est perdu essentiellement dans suivant_naif (5.5 sec), puis dans
afficher_naif (0.7 sec).
À l’intérieur de suivant_naif, le temps est utilisé ainsi :
stats.dat% callees suivant_naif
Function called...
ncalls tottime cumtime
fredkin.py:48(suivant_naif) 100000 5.456 5.456 fredkin.py:51(comptevoisins)
10 0.000 0.000 {method 'copy' of 'numpy.ndarray' objects}
Nous constatons que la copie du tableau ne coûte presque rien et que sur les 5.6 sec de suivant_naif, près de 5.5
sont passées dans compte_voisins.
Nous allons donc essayer d’optimiser cette fonction en premier
Les tranches et les vues (slices, views) dans NumPy
Adresser uniquement certaines cases d’un tableau NumPy est très rapide grâce aux vues. Nous voulons sommer les 8 cases voisines d’une case donnée. Pour cela, nous allons créer une vue qui ne contient que ces cases, faire la somme des cases de la vue et retirer la case centrale (en une seule ligne) :
def suivant_naif(tab):
""" Calcule l'étape suivante de l'automate """
##########################################
def comptevoisins(i,j):
""" Renvoie le nombre de voisins ON de (i,j) """
c = tab2[i-1:i+2,j-1:j+2].sum() - tab2[i][j]
return c
##########################################
tab2=tab.copy()
for i in range(tab2.shape[0]):
for j in range(tab2.shape[1]):
c = comptevoisins(i,j)
if c%2 == 0:
tab[i, j] = _st["OFF"]
else:
tab[i, j] = _st["ON"]
Utilisons à nouveau l’outil de profilage :
$ python3 -m cProfile -o stats.dat fredkin.py
$ python3 -m pstats
Welcome to the profile statistics browser.
% read stats.dat
% callees unesimu
ncalls tottime cumtime
fredkin.py:83(unesimu) 10 0.603 0.688 fredkin.py:11(afficher_naif)
1 0.014 0.014 fredkin.py:39(init)
10 0.398 1.983 fredkin.py:48(suivant_naif)
10 0.001 0.001 {built-in method print}
Nous sommes passés de 5.5 à 2 secondes, ce qui n’est pas rien.
L’idée des vues peut néanmoins être appliquée de manière plus radicale. Plutôt que d’examiner chaque cellule une à une,
il est possible, uniquement avec des opérations sur les tableaux de calculer une matrice contenant le nombre de voisins
de chaque case. Il suffit pour cela d’ajouter 8 vues décalées du tableau complet, et nous obtiendrons une matrice
contenant le nombre de voisins. Cette opération, qui consiste à remplacer des boucles par des opérations matricielles
s’appelle la vectorisation. Un ancien numéro de Linux Magazine (Hors Série 40 spécial Python) en a parlé, en
utilisant NumPy et Python, dans le cadre du tracé d’images fractales. Voici donc notre nouvelle fonction de passage
au tableau suivant (on en profite pour passer de 10 à 100 générations dans la fonction unesimu car ça va aller très
vite maintenant) :
def suivant(tab):
""" Fonction suivant, après vectorisation.
Les bords du tableau ne sont pas mis à jour
"""
comptage = tab[1:-1,0:-2] + tab[0:-2,0:-2] + tab[2:,0:-2] +
tab[0:-2,1:-1] + tab[2:,1:-1] + tab[1:-1,2:] +
tab[0:-2,2:] + tab[2:,2:]
tab[1:-1, 1:-1] = comptage % 2
def unesimu(screen,tab):
init(tab)
# On passe à 100 générations, car notre programme
# est bien plus rapide maintenant
for i in range(100):
suivant(tab)
afficher(screen, tab)
print(i)
Non seulement cette fonction va être plus rapide, mais en plus, elle est plus courte…
Utilisons à nouveau le profiler :
$ python3 -m cProfile -o stats.dat fredkin.py
$ python3 -m pstats
% read stats.dat
% callees unesimu
Function called...
ncalls tottime cumtime
fredkin.py:85(unesimu) 100 6.603 7.479 fredkin.py:11(afficher_naif)
1 0.010 0.010 fredkin.py:39(init)
100 0.089 0.029 fredkin.py:74(suivant)
100 0.005 0.005 {built-in method print}
Le gain de temps est spectaculaire (il faut tenir compte du fait que nous calculons 100 générations au lieu de 10
maintenant..). La nouvelle fonction suivant est plusieurs milliers de fois plus rapide que la toute première
version… Si bien que maintenant, le temps n’est plus perdu dans suivant, mais dans l’affichage. Notre simulation
passe en effet maintenant 300 fois plus de temps à afficher qu’à calculer.
Si l’automate de Fredkin se prête bien à la vectorisation, cela peut être plus difficile dans d’autres cas, mais il
est généralement possible de s’en sortir en utilisant les masques de NumPy, qui permettent de n’adresser que
certaines cases. La fonction suivant aurait pu être écrite ainsi, en utilisant les masques, ce qui la rend plus
facilement adaptable à d’autres automates (et un petit peu plus lente, mais elle sera encore beaucoup plus rapide
que la version avec les boucles) :
def suivant(tab):
comptage = tab[1:-1, 0:-2] + tab[0:-2, 0:-2] + tab[2:, 0:-2] +
tab[0:-2, 1:-1] + tab[2:, 1:-1] + tab[1:-1, 2:] +
tab[0:-2, 2:] + tab[2:, 2:]
view=tab[1:-1, 1:-1] # Vue sur la partie centrale
# Utilisation d'un masque pour la mise à jour
view[comptage % 2 == 0] = 0
view[comptage % 2 == 1] = 1
NumPy / Pygame, mêmes surfaces
PyGame, que nous utilisons pour afficher, utilise lui même NumPy. Si nous pouvions calculer matriciellement l’image à afficher, plutôt que balayer la surface et dessiner des petits carrés, nous gagnerions certainement beaucoup de temps.
L’outil de profilage nous indique que sur les 7.479 sec d’exécution de afficher_naif, 6.603 sec sont passées dans
la structure même de la fonction, et seulement 0.765 sec, par exemple, dans l’affichage des carrés (box).
% callees unesimu
ncalls tottime cumtime
fredkin.py:85(unesimu) 100 6.603 7.479 fredkin.py:11(afficher_naif)
1 0.010 0.010 fredkin.py:39(init)
100 0.089 0.029 fredkin.py:74(suivant)
100 0.005 0.005 {built-in method print}
% callees afficher_naif
ncalls tottime cumtime
fredkin.py:11(afficher_naif) 1000000 0.765 0.765 {built-in method box}
100 0.076 0.076 {built-in method flip}
Par chance, il est possible de construire un tableau NumPy, et de l’utiliser comme surface (image…) PyGame.
Dans un premier temps, nous allons donc réaliser un placage de la matrice sur l’écran (l’inconvénient est que chaque cellule de l’automate sera représentée par un seul pixel, mais nous améliorerons ceci dans la suite). Pour réaliser cet affichage, nous allons construire une matrice qui contiendra les valeurs des pixels, puis nous la plaquerons à l’écran.
La première opération (construction de la matrice) nécessite de savoir comment sont représentés les valeurs des pixels
en mémoire. Le seconde (placage à l’écran) utilise la fonction pygame.surfarray.blit_array() et nécessite que la
matrice et la zone d’affichage aient la même taille.
Représenation des pixels
Le nombre de chiffres binaires utilisés pour représenter un pixel est donné par la profondeur. Une valeur courante pour la profondeur est 32, c’est à dire 32 bits par pixel. Sur ces 32 chiffres, 8 sont prévus pour la transparence, puis 8 pour le rouge, 8 pour le vert et 8 pour le bleu. Il est habituel de représenter les 3 composantes de couleur sur 24 bits en écrivant leur valeur en hexadécimal (ainsi, chaque composante correspond à 2 chiffres hexadécimaux). Le rouges est par exemple : 0xFF0000, le vert : 0x00FF00, et le bleu 0x0000FF. On obtient du jaune avec du vert et du rouge (il s’agit de synthèse additive des couleurs) : 0xFFFF00.
Si nous pouvons remplir un tableau directement avec ces valeurs, nous aurons donc un pixel par case du tableau de départ .
Premier essai
Nous utiliserons la fonction afficher suivante. Il faudra aussi penser à modifier la taille de la fenêtre de départ. Redonnons le programme complet :
import numpy as np
import random
import pygame
import pygame.gfxdraw
_st = {"OFF":0, "ON":1}
_cote = 3
_n = 100
def afficher(screen, tab):
A = (tab * 0xFFFFFF)
pygame.surfarray.blit_array(screen, A)
pygame.display.flip()
def init(tab):
for i in range(1, tab.shape[0] - 1):
for j in range(1, tab.shape[1] - 1):
tab[i, j] = _st["OFF"]
if i in range(19 * _n // 40, 21 * _n // 40) and \
j in range(19 * _n // 40, 21 * _n // 40) and \
random.random() > 0.5:
tab[i, j] = _st["ON"]
def suivant(tab):
# On additionne les 8 matrices de voisinage
comptage = tab[1:-1, 0:-2] + tab[0:-2, 0:-2] + tab[2:, 0:-2] + \
tab[0:-2, 1:-1] + tab[2:, 1:-1] + tab[1:-1, 2:] + \
tab[0:-2, 2:] + tab[2:, 2:]
tab[1:-1, 1:-1] = comptage % 2
def unesimu(screen,tab):
init(tab)
for i in range(100):
suivant(tab)
afficher(screen, tab)
print(i)
def main():
pygame.init()
tab = np.zeros((_n, _n), dtype=np.uint32)
screen = pygame.display.set_mode((_n, _n), 0, 32)
unesimu(screen, tab)
pygame.quit()
main()
% callees unesimu
Function called...
ncalls tottime cumtime
fredkin.py:86(unesimu) 100 0.002 0.025 fredkin.py:20(afficher)
1 0.015 0.015 fredkin.py:39(init)
100 0.025 0.025 fredkin.py:74(suivant)
100 0.002 0.002 {built-in method print}
Le nouveau programme obtenu est vraiment très rapide (ce nouvel affichage est 300 fois plus rapide que le précedent). Mais son défaut majeur est que chaque cellule est représentée par un (tout petit) pixel, et non plus par un carré, bien visible à l’écran.
Y-a-t-il un moyen, à partir d’un tableau de taille 100×100, de construire un nouveau tableau de taille 300×300 dans lequel chaque valeur du tableau initial est recopiée 9 fois (formant ainsi des petits carrés) ?
Produit de Kronecker
Parmi les opérations proposées par le module NumPy, c’est le produit de Kronecker qui va nous servir (vous en trouverez une description ici Produit de Kronecker).
Voici un exemple :
import numpy as np
a=np.array([[1,2,3],[4,5,6],[7,8,9]])
forme=np.array([[1,1],[1,1]])
print(a)
[[1 2 3]
[4 5 6]
[7 8 9]]
print(forme)
[[1 1]
[1 1]]
np.kron(a,forme)
array([[1, 1, 2, 2, 3, 3],
[1, 1, 2, 2, 3, 3],
[4, 4, 5, 5, 6, 6],
[4, 4, 5, 5, 6, 6],
[7, 7, 8, 8, 9, 9],
[7, 7, 8, 8, 9, 9]], dtype='int32')
Nous avons obtenu l’effet souhaité : chaque valeur de la matrice de départ est recopiée, de manière à ce que chaque
valeur forme un carré 2×2. Cela fonctionnera aussi avec un carré plus gros. La matrice forme, si elle ne contient
que des 1, indique par son nombre de cases la taille des carrés qui seront représentés à l’écran.
Voici à nouveau le programme complet avec la nouvelle version de l’affichage :
import numpy as np
import random
import pygame
import pygame.gfxdraw
_st = {"OFF": 0, "ON": 1}
_cote = 3
_n = 100
def afficher(screen, tab):
# forme est une matrice carrée remplies de 1
forme=np.ones((_cote, _cote),dtype=np.uint32)
A=np.kron(tab*0xFFFFFF, forme)
pygame.surfarray.blit_array(screen, A)
pygame.display.flip()
def init(tab):
for i in range(1, tab.shape[0] - 1):
for j in range(1, tab.shape[1] - 1):
tab[i,j] = _st["OFF"]
if i in range(19 * _n // 40, 21 * _n // 40) and \
j in range(19 * _n // 40, 21 * _n // 40) and \
random.random() > 0.5:
tab[i,j] = _st["ON"]
def suivant(tab):
# On additionne les 8 matrices de voisinage
comptage = tab[1:-1, 0:-2] + tab[0:-2, 0:-2] + tab[2:, 0:-2] + \
tab[0:-2, 1:-1] + tab[2:, 1:-1] + tab[1:-1, 2:] + \
tab[0:-2, 2:] + tab[2:, 2:]
tab[1:-1, 1:-1] = comptage % 2
def unesimu(screen,tab):
init(tab)
for i in range(100):
suivant(tab)
afficher(screen, tab)
print(i)
def main():
pygame.init()
tab = np.zeros((_n, _n), dtype=np.uint32)
screen = pygame.display.set_mode((_n * _cote, _n * _cote), 0, 32)
unesimu(screen, tab)
pygame.quit()
main()
Conclusion
Le programme obtenu, dans sa dernière version est environ 100 fois plus rapide que la version présentée en haut de ce
document. L’effort nécessaire pour le concevoir a essentiellement consisté en la vectorisation de l’automate
(fonction suivant), et en l’amélioration de l’affichage. En ce qui concerne ce second point, le choix des couleurs
et des formes est plus technique qu’avec un affichage classique (utilisant gfxdraw comme dans le premier programme).
Il faut aussi noter que le programme optimisé, outre sa rapidité, est plus court de manière non négligeable. Enfin,
la matrice forme ne contient que des 1 dans le programme donné ici.
En y mettant d’autres valeurs, il est possible de représenter les cellules par autre chose qu’un simple carré uniforme en couleur.