Optimisation du jeu de la vie en python (4 sec alors qu'en C 6 ms !)

**fatango** · 06/01/2021, 22h51

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** · 07/01/2021, 00h17

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** · 07/01/2021, 10h48

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** · 07/01/2021, 19h26

Envoyé par lg_53

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** · 07/01/2021, 20h15

Envoyé par fred1599

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** · 07/01/2021, 20h44

Envoyé par marco056

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

**fatango** · 07/01/2021, 23h42

Merci infiniment pour vos retours. J'ai besoin de temps maintenant pour faire des tests avec ce que vous proposez.

En fait j'ai réalisé le jeux de la vie dans différents langages et j'ai mesuré le temps d'exécution pour un cycle de vie sans compter le temps d'affichage.

Pour Python : 2 à 4 sec
Pour Javascript sur un Firefox : 25 msec !
Pour Java : oscille de 16 à 23 msec (surement le garbage collector)
En C : 16 ms (sans optimisation de compilation)
En C : 6 ms (avec optimisation de compilation -Ofast)
En GPU (GTX 1060) : 0.05 ms !!!

J'ai forcé tous les exe à tourner sur un seul CPU pour que ce soit équitable.

Si je regarde le ratio de performance Python / GPU pour le cas que je suis en train de traiter, de 11h à 22h de Python = 1s de GPU
Pour Python / CPU optimisé, de 5 min à 11min de python = 1s de CPU

Comme ces résultats me semblent délirants, je me dis qu'il y a quelque chose que je n'ai pas bien optimisé.
Lorsque j'aurais amélioré mon code, je compléterais ce post avec mes résultats. Et oui, j'utiliserai la balise CODE, je n'avais pas vu qu'elle existait :-)

**lg_53** · 08/01/2021, 10h33

Envoyé par fred1599

terrible -> sens 1 de la définition

Ah oui en effet c'est cette phrase qui m'a induit en erreur. Chez moi, quand on dit que qqch est terrible, c'est que ca envoie, ca dépote ! Bon donc en fait on est d'accord

.

Je vais donc laisser ce sujet à notre ami, en attendant son retour (il a du boulot je crois

)

**Sve@r** · 09/01/2021, 21h15

Envoyé par fatango

Code python :

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

1
2
3
4
5
6
7
8
9
10
if mat[y][x]:
    if count == 2 or count == 3:
      return True
    else:
      return False
  else:
    if count == 3:
      return True
    else:
      return False

Comme ces résultats me semblent délirants, je me dis qu'il y a quelque chose que je n'ai pas bien optimisé.

Ben... oui !!!
Rien que dans cette structure... évaluer un booléen via "if" pour retourner alors un booléen est totalement absurde. Autant retourner directement le booléen !!!

Code python :

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

1
2
3
4
if mat[y][x]:
    return count in (2, 3)
  else:
    return count == 3

**fatango** · 10/01/2021, 10h25

Ah oui, c'est vrai que c'est un peu lourd de faire des if alors que l'évaluation de l'expression suffit à elle même !

Merci ! :-)

**Sve@r** · 10/01/2021, 13h07

Ben voilà. Commence par optimiser (au sens Python) ton code puis tu pourras alors faire des benchs qui auront du sens.
Ceci dit, Python reste de l'interprété et face au C qui est compilé il n'aura aucune chance. C'est pour ça qu'en Python on tente au maximum d'utiliser des libairies externes dédiées à certaines opérations, librairies qui peuvent (comme numpy) être écrites en C...

**CosmoKnacki** · 11/01/2021, 00h51

Envoyé par lg_53

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** · 11/01/2021, 11h02

Envoyé par CosmoKnacki

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.

Envoyé par CosmoKnacki

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).

Envoyé par CosmoKnacki

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** · 12/01/2021, 01h30

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.

**lg_53** · 12/01/2021, 10h25

Envoyé par CosmoKnacki

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

Ah oui effectivement j'ai regardé un peu trop vite ces conditions, et j'ai amalgamé cela à un max(x-1,0) mal fait

. Alors du coup d-3 remarques :
1) numpy accepte les indices négatifs.

Code :

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

if mat[y - 1 if y - 1 > -1 else size_y - 1]

autant écrire

Code :

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

if mat[y - 1]

c'est pareil
2) On a donc en effet des conditions limites périodiques, donc pas besoin d'augmenter le domaine. On peut garder 800x800.
3) Et c'est grace à np.roll qu'on va pouvoir faire ca sans parcourir le domaine, et sans détaillé les cas pour les bords.
Pour comprendre, exécuter ceci :

Code :

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

1
2
3
4
5
a=np.arange(16).reshape((4,4))
print(np.roll(a,1,axis=0))
print(np.roll(a,-1,axis=0))
print(np.roll(a,1,axis=1))
print(np.roll(a,-1,axis=1))

Optimisation du jeu de la vie en python (4 sec alors qu'en C 6 ms !)

Python

Discussions similaires

Partager

Partager