Discussion :

[fatango]

Bonjour,

Je me suis amusé à réaliser le jeu de la vie en python et je suis surpris du temps pour un cycle de vie : 2 à 4 sec alors qu'en C j'obtiens 6 msec hors affichage!!
J'ai essayé d'optimiser mon code hors affichage. Pourriez vous me dire si il y aurait une manière de plus l'optimiser ?
Merci pour votre aide :-)
Pour info, le programme va lire un fichier json (ci-joint compressé dans conf.zip) pour initialiser la première grille qui dans mon cas est une grille d'environ 800 / 800
Je vous laisse tester le programme

Fabrice

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#!/usr/bin/python3
 
import pygame
import json
import sys
import numpy
import time
 
mat=""
outputmat=""
switchmat=""
conf=""
screen=""
 
def load_conf():
  try:
    with open('conf.json') as json_conf:
      data = json.load(json_conf)
      return data
  except:
    print("Le fichier conf.json n'existe pas.")
    sys.exit(1)
 
def init_pygame():
  global conf
  pygame.init()
 
  size = width, height = conf["width"], conf["height"]
  screen1 = pygame.display.set_mode(size)
  pygame.display.set_caption(conf["title"])
  return screen1
 
def init_game_of_life_mat():
  global conf
  mmat = numpy.zeros(shape=(conf["number_cellulars_y"], conf["number_cellulars_x"]), dtype=bool)
  for point in conf["cellulars"] :
    mmat[point["y"]][point["x"]] = 1
  return mmat
 
def draw_game_of_life_cellular(x, y, size_x, size_y, color):
  global screen
  for index_x in range(x * size_x, (x * size_x) + size_x):
    for index_y in range(y * size_y, (y * size_y) + size_y):
      screen.set_at((index_x, index_y), color)
 
def draw_game_of_life():
  global outputmat, switchmat, conf, screen
  size_x = int(conf["width"] / conf["number_cellulars_x"])
  size_y = int(conf["height"] / conf["number_cellulars_y"])
  screen.fill((0,0,0))
  for y in range(0, len(outputmat)):
    for x in range(0, len(outputmat[y])):
      if outputmat[y][x]:
        draw_game_of_life_cellular(x, y, size_x, size_y, (255, 255, 255))
 
def quit_event():
  for event in pygame.event.get():
    if event.type == pygame.QUIT:
      return True
  return False
 
def rules_game_of_life(x, y, size_x, size_y):
  global mat
  count = 0
  if mat[y - 1 if y - 1 > -1 else size_y - 1][x - 1 if x - 1 > -1 else size_x - 1]:
    count = count + 1
  if mat[y - 1 if y - 1 > -1 else size_y - 1][x]:
    count = count + 1
  if mat[y][x - 1 if x - 1 > -1 else size_x - 1]:
    count = count + 1
  if mat[y + 1 if y + 1 < size_y else 0][x + 1 if x + 1 < size_x else 0]:
    count = count + 1
  if mat[y + 1 if y + 1 < size_y else 0][x]:
    count = count + 1
  if mat[y][x + 1 if x + 1 < size_x else 0]:
    count = count + 1
  if mat[y + 1 if y + 1 < size_y else 0][x - 1 if x - 1 > -1 else size_x - 1]:
    count = count + 1
  if mat[y - 1 if y - 1 > -1 else size_y - 1][x + 1 if x + 1 < size_x else 0]:
    count = count + 1
 
  if mat[y][x]:
    if count == 2 or count == 3:
      return True
    else:
      return False
  else:
    if count == 3:
      return True
    else:
      return False
 
def compute_game_of_life(size_x, size_y):
  global mat, outputmat
  for y in range(0, len(mat)):
    for x in range(0, len(mat[y])):
      outputmat[y][x] = rules_game_of_life(x, y, size_x, size_y)
 
def init():
  global conf, screen, mat, outputmat, switchmat
  conf=load_conf()
  print(conf["width"])
  screen = init_pygame()
  mat = init_game_of_life_mat()
  outputmat = init_game_of_life_mat()
  switchmat= init_game_of_life_mat()
 
def main_loop():
  global mat, outputmat, switchmat
  exit_loop = False
  while not exit_loop:
    exit_loop = quit_event()
    draw_game_of_life()
    t1 = time.process_time()
    switchmat = outputmat
    outputmat = mat
    mat = switchmat
    compute_game_of_life(conf["number_cellulars_x"], conf["number_cellulars_y"])
    t2 = time.process_time()
    print("Time =", (t2 - t1)*1000.0 , " ms")
    pygame.display.flip()
 
def main():
  init()
  main_loop()
 
main()

[fred1599]

Bonsoir,

Le code n'est pas testable, il manque le fichier de configuration.

Ensuite, le plus simple est de chercher le goulot d'étranglement et de présenter la fonction seule posant problème, avec ce qu'elle doit avoir en arguments et les types de ces arguments, puis ce qu'elle doit retourner comme objet, ainsi que le/les types du retour.

Présenter le code afin qu'on puisse reproduire, avec le test de temps... Sans pouvoir reproduire, pas possible de vous aider, à savoir qu'on se doute de la fonction qui pose problème

Code :

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

1
2
3
4
5
def compute_game_of_life(size_x, size_y):    
    global mat, outputmat
    for y in range(0, len(mat)):
        for x in range(0, len(mat[y])):
            outputmat[y][x] = rules_game_of_life(x, y, size_x, size_y)

qui appelle cette fonction

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def rules_game_of_life(x, y, size_x, size_y):    
    global mat
    count = 0
    if mat[y - 1 if y - 1 > -1 else size_y - 1][x - 1 if x - 1 > -1 else size_x - 1]:
        count = count + 1
    if mat[y - 1 if y - 1 > -1 else size_y - 1][x]:
        count = count + 1
    if mat[y][x - 1 if x - 1 > -1 else size_x - 1]:
        count = count + 1
    if mat[y + 1 if y + 1 < size_y else 0][x + 1 if x + 1 < size_x else 0]:
        count = count + 1
    if mat[y + 1 if y + 1 < size_y else 0][x]:
        count = count + 1
    if mat[y][x + 1 if x + 1 < size_x else 0]:
        count = count + 1
    if mat[y + 1 if y + 1 < size_y else 0][x - 1 if x - 1 > -1 else size_x - 1]:
        count = count + 1
    if mat[y - 1 if y - 1 > -1 else size_y - 1][x + 1 if x + 1 < size_x else 0]:
        count = count + 1
 
    if mat[y][x]:
        if count == 2 or count == 3:
            return True
        else:
            return False
    else:
        if count == 3:
            return True
        else:
            return False

Niveau algorithme on peut guère faire plus terrible...

[lg_53]

J'enfonce le clou par rapport à mon prédecesseur : Présentez un code sans interface graphique, avec le fichier de configuration, et avec le minutage (qui minute donc seulement l'éxécution du jeu de la vie, et pas son affichage).

Par contre sur l'optimisation de l'algo, je ne suis pas d'accord avec mon prédécesseur. J'ai déjà regardé ce problème de très près, et en python, donc je peux vous dire que vous pouvez gagner beaucoup ! Il faut exploiter la force de numpy : il peut réaliser des opérations sur des tableaux ! Donc faire des boucles for sur l'ensemble des indices x,y ... ça plombe le temps de calcul.

Si vous voulez vous en convaincre, faites le test juste sur addition. Soit A un array (random). Comparer A+=1 (donc numpy se charge d'ajouter 1 à tous les éléments du tableaux), à une boucle avec un indice i pour parcourir tous les éléments de A, puis faire A[i]+=1. Minutez ca, vous allez voir, c'est impressionant. (Répétez l'opéartion plusieurs fois si ce que vous mesurez est trop petit pour etre mesurable, et aussi sur une grande matrice).

Et aussi tout vos if, ils servent... à rien. Pour compter des choses, si votre matrice initiale est remplie de 0 et de 1, et bien il suffit de faire une somme (np.sum de la sous matrice correspondant au voisinage du point que vous regardez). Pas besoin d'aller examiner et de boucler sur chacun des voisins.

Pour la gestion des cellules au bord, 2 possibilités:
1) vous pouvez écrire min(size_x,x+1) qui est plus élégant que x + 1 if x + 1 < size_x else 0 qui d'ailleurs est peut être bien faux ... (et pareil pour l'autre bord en x, et les 2 autres bord en y).
2) 2ieme facon, certainement plus rapide, vous considérez une matrice avec des couches limites. C'est à dire si vous voulez modéliser 800x800, vous vous donner une matrice de 802x802. Vous laissez les 0 sur le bord de cette nouvelle matrice. Ainsi quand vous considérez le voisinage d'une cellule au bord du domaine 800x800, et bien vous n'avez pas à gérer ce cas particulier de cellule au bord : vous pouvez prendre tout un voisinage autour, ca ira chercher une partie du voisinage dans la couche limite, qui est nulle, et ca n'aura donc pas d'incidence sur votre calcul. En terme de cout de calcul, c'est moins cher d'additionner des 0 pour certain x et y, que de faire des if pour tous les x et les y.
Dans cette manière de faire, à chaque itération, vous n'avez pas à mettre à jour la couche limite. Il faut aussi toujours bien penser qu'on a un décalage de 1.

EDIT: Mettez votre code entre les balises CODE (le bouton avec le symbole # lorsque vous rédigez votre message)

[fred1599]

Par contre sur l'optimisation de l'algo, je ne suis pas d'accord avec mon prédécesseur.

Euh... à la vue de ce que t'écris et ce que j'écris, je vois pas le désaccord ?

[marco056]

Euh... à la vue de ce que t'écris et ce que j'écris, je vois pas le désaccord ?

Je pense que c'est cette phrase qui est mal tournée :
"Niveau algorithme on peut guère faire plus terrible."

[fred1599]

Je pense que c'est cette phrase qui est mal tournée :
"Niveau algorithme on peut guère faire plus terrible."

terrible -> sens 1 de la définition

[CosmoKnacki]

2) 2ieme facon, certainement plus rapide, vous considérez une matrice avec des couches limites. C'est à dire si vous voulez modéliser 800x800, vous vous donner une matrice de 802x802. Vous laissez les 0 sur le bord de cette nouvelle matrice. Ainsi quand vous considérez le voisinage d'une cellule au bord du domaine 800x800, et bien vous n'avez pas à gérer ce cas particulier de cellule au bord : vous pouvez prendre tout un voisinage autour, ca ira chercher une partie du voisinage dans la couche limite, qui est nulle, et ca n'aura donc pas d'incidence sur votre calcul. En terme de coût de calcul, c'est moins cher d'additionner des 0 pour certain x et y, que de faire des if pour tous les x et les y.
Dans cette manière de faire, à chaque itération, vous n'avez pas à mettre à jour la couche limite. Il faut aussi toujours bien penser qu'on a un décalage de 1.

L'idée est intéressante, mais peut-on appliquer cette méthode de manière pratique alors qu'il semble que la matrice est gérée dans le code original comme une sorte de "dallage infini", c'est à dire que la colonne size_y + 1 est la colonne 0 et que la ligne size_x + 1 est la ligne 0? Ça demande à chaque génération de recopier ces lignes et colonnes surnuméraires d'après leurs versions recalculées.

Voilà pourquoi je me demande s'il ne serait pas plus performant, quitte à générer plus de code, d'écrire des fonctions spécialisées (dans lesquelles il n'y aurait aucun test à effectuer) pour les bords. Quelque chose dans ce goût là:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def compute_game_of_life(size_x, size_y):
    global mat, outputmat
 
    outputmat[0][0] = rules_gol_left_top(size_x, size_y)
 
    for x in range(1, size_x - 1):
        outputmat[0][x] = rules_gol_top(x, size_y)
 
    outputmat[0][size_x] = rules_gol_right_top(size_x, size_y)
 
    for y in range(1, size_y - 1):
        outputmat[y][0] = rules_gol_left(y)
        for x in range(1, size_x -1):
            outputmat[y][x] = rules_gol(x, y)
 
        outputmat[y][size_x] = rules_gol_right(y, size_x)
 
    outputmat[size_y][size_x] = rules_gol_right_bottom(size_x, size_y)

Le point noir, c'est qu'il faut écrire 7 fonctions rules_gol_... à la place d'une seule.

[lg_53]

L'idée est intéressante, mais peut-on appliquer cette méthode de manière pratique alors qu'il semble que la matrice est gérée dans le code original comme une sorte de "dallage infini",

Du dallage infini ? En pratique votre machine a une mémoire finie, bien que grande. Donc vous êtes obligé de définir la taille de votre domaine. Et donc si vous avez défini une taille N, vous pouvez toujours considérer un domaine de taille N+2 plutot que N.

c'est à dire que la colonne size_y + 1 est la colonne 0 et que la ligne size_x + 1 est la ligne 0? Ça demande à chaque génération de recopier ces lignes et colonnes surnuméraires d'après leurs versions recalculées.

Alors ca c'est ce qu'on appelle des conditions limites. Et en l'occurence ici on les qualifie de périodique. Si c'était une particule en mouvement que l'on modélisait alors, ca voudrait dire que ce qui sort par un côté rentre par le coté opposé. Mais ce n'est pas forcément le comportement :
1-usuel et naturel. En général on fait plutôt des conditions de Dirichlet dans ce genre de problème, condition qui consiste à dire qu'à l'extérieur du domaine de calcul il n'y a pas de cellules, ou autrement dit, que le voisinage d'une cellule au bord est réduit à la partie qui se trouve à l'intérieur du domaine.
2-voulu. Fatango n'a pas détaillé ce point, mais au vu du code qu'il présente, ca ressemble plutot à des conditions de Dirichlet

Donc on peut faire des conditions limites périodiques, le code serait juste un peu différent (On utiliserait très probablement np.roll).

Voilà pourquoi je me demande s'il ne serait pas plus performant, quitte à générer plus de code, d'écrire des fonctions spécialisées (dans lesquelles il n'y aurait aucun test à effectuer) pour les bords. Quelque chose dans ce goût là:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def compute_game_of_life(size_x, size_y):
    global mat, outputmat
 
    outputmat[0][0] = rules_gol_left_top(size_x, size_y)
 
    for x in range(1, size_x - 1):
        outputmat[0][x] = rules_gol_top(x, size_y)
 
    outputmat[0][size_x] = rules_gol_right_top(size_x, size_y)
 
    for y in range(1, size_y - 1):
        outputmat[y][0] = rules_gol_left(y)
        for x in range(1, size_x -1):
            outputmat[y][x] = rules_gol(x, y)
 
        outputmat[y][size_x] = rules_gol_right(y, size_x)
 
    outputmat[size_y][size_x] = rules_gol_right_bottom(size_x, size_y)

Le point noir, c'est qu'il faut écrire 7 fonctions rules_gol_... à la place d'une seule.

Non ça ne serait pas plus performant. Car il faut utiliser la puissance de numpy, et faire des opérations directement sur la grille entière. Le code final ne doit plus contenir une seul for, à part celui qui doit boucler sur les itérations en temps ! Il ne faut plus parcourir la grille ! Et c'est pour ça que c'est intéressant d'avoir une couche limite tout autour: ça évite de faire des cas particulier pour les bords, et donc devoir faire des trucs bout par bout alors que notre machine peut traiter toute la grille d'un coup (suffit que l'opération à faire soit la même sur toute la grille).

Pour illustrer mon propos, je vais considérer un problème un peu différent (histoire de ne pas donner directement la solution de celui-ci). Je fais un problème en 1D. J'ai une grille (1D) de départ, et à l'itération d'après je veux que chaque point de ma grille contienne la somme de moi même et de mes 2 voisins (1 seul voisin si je suis au bord)

Code 1 : Remarquer que là je me suis déjà affranchi des if

Code :

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

1
2
3
4
5
6
7
8
 
x=np.array([1,2,3,4,5])
y=np.zeros_like(x)
 
### Chose que je ferais à chaque itération en temps
y[0]=x[0]+x[1]  ### condition à gauche
y[-1]=x[-1]+x[-2] ### condition à droite
y[1:-1]=x[:-2]+x[1:-1]+x[2:]

Code 2 : 1 seule et unique opération, permise grâce à la couche limite

Code :

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

1
2
3
4
5
6
 
x=np.array([0,1,2,3,4,5,0])  ### Je met un '0' en plus de chaque côté (mais je continue de ne regarder l'évolution que de [1,2,3,4,5,6])
y=np.zeros_like(x)
 
### Chose que je ferais à chaque itération en temps
y[1:-1]=x[:-2]+x[1:-1]+x[2:]

Maintenant si je boucle 10 000 fois sur ca, voici les temps d'éxécution que j'obtiens :

Code :

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

1
2
0.25276899337768555
0.17205548286437988

Différence qui serait encore accrue en 2D. Et on peut tester avec un plus grand tableau, pareil la différence est significative.

[CosmoKnacki]

Par "dallage infini", il faut comprendre que la colonne n+1 est la colonne 0 (même chose pour les lignes) comme dans un jeu de pacman. Ça ne veut pas dire que la matrice est infinie!

ça voudrait dire que ce qui sort par un côté rentre par le coté opposé.

Voilà!

Fatango n'a pas détaillé ce point, mais au vu du code qu'il présente, ça ressemble plutôt à des conditions de Dirichlet

Bah non! Regarde ses conditions if:

Code :

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

1
2
if mat[y - 1 if y - 1 > -1 else size_y - 1][x - 1 if x - 1 > -1 else size_x - 1]:
        count = count + 1

On utiliserait très probablement np.roll

Je vois pas trop comment exploiter cette méthode en particulier pour ce qui nous occupe, mais je regarderai ce que numpy propose pour s'affranchir au maximum des boucles au niveau python.