Automate de Fredkin (aller/retour)

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 :

Étape 0 Étape 8 Étape 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.

Référénces