Petit quiz sur les performances des structures de données en Python

Une implémentation performante d'un algorithme passe souvent par un choix judicieux des structures de données. La première étape de ce choix, c'est la comparaison asymptotique du comportement des structures envisagées (la notation grand O si vous préférez). La deuxième étape, c'est de faire un choix parmi plusieurs structures candidates aux comportements asymptotiques équivalents. Et là, on rentre dans des considérations moins joyeuses car elles dépendent de détails techniques qui sont loin d'être évidents.

Prenons Python, par exemple. J'ai, personnellement, toujours du mal à décider de la meilleure option car les impacts de diverses implémentations ne me paraissent pas intuitivement évidents. Vous pensez faire mieux ? Jouons à un petit jeu.

On a un tableau carré en 2 dimensions de taille NxN. Chaque case du tableau peut être identifiée par des coordonnées entières (x,y). On coche aléatoirement 10% des cases du tableau. Ensuite, on tire au sort un très grand nombre de coordonnées (dont certaines ne sont peut être même pas dans le tableau) et on doit vérifier, pour chacune d'entre elle, si elle correspond à une case cochée.

On doit décider d'une implémentation pour représenter cette grille sur laquelle la vérification d'une case cochée doit être la plus rapide possible.

On peut exprimer le problème avec ce code. Une grille est une classe à 2 opérations : ajouter des coordonnées et vérifier si les coordonnées ont été ajoutées.

 1N = 100
 2
 3class Grid:
 4  def add(self, x, y):
 5    pass
 6
 7  def check(self, x, y) -> bool:
 8    pass
 9
10def run(grid: Grid) -> int:
11  random.seed(42)
12  total_points_placed = N * N / 10
13  points_placed = 0
14  while points_placed < total_points_placed:
15    x = random.randint(0, N - 1)
16    y = random.randint(0, N - 1)
17    if grid.check(x, y):
18      continue
19    grid.add(x, y)
20    points_placed += 1
21  matches = 0
22  for _ in range(10_000_000):
23    x = random.randint(-1, N)
24    y = random.randint(-1, N)
25    if grid.check(x, y):
26      matches += 1
27  return matches

D'un point de vue théorique, la méthode check s'exécute en O(1). L'implémentation la plus simple en Python -et dans de nombreux langages- est de faire un tableau de tableaux de booléens.

1class UsingArrayOfArrays(Grid):
2  def __init__(self):
3    self.grid = [[False for _ in range(N)] for _ in range(N)]
4
5  def add(self, x, y):
6    self.grid[x][y] = True
7
8  def check(self, x, y) -> bool:
9    return 0 <= x < N and 0 <= y < N and self.grid[x][y]

Les tableaux en 2 dimensions n'existent pas nativement en Python mais on en trouve dans des bibliothèques répandues comme NumPy. Peut être est-ce un meilleur choix ?

1class UsingNumpyArray(Grid):
2  def __init__(self):
3    self.grid = np.zeros((N, N), dtype=bool)
4
5  def add(self, x, y):
6    self.grid[x, y] = True
7
8  def check(self, x, y) -> bool:
9    return 0 <= x < N and 0 <= y < N and self.grid[x, y]

Une approche radicalement différente serait d'utiliser un ensemble de tuples (x,y). Les coordonnées ne sont alors plus des indices d'un tableau mais de simples éléments d'un objet hachable.

1class UsingSetOfTuples(Grid):
2  def __init__(self):
3    self.grid = set()
4
5  def add(self, x, y):
6    self.grid.add((x, y))
7
8  def check(self, x, y) -> bool:
9    return (x, y) in self.grid

Et pourquoi se contenter de tuples génériques ? Il y a en Python une structure native qui colle parfaitement avec une paire de coordonnées : les nombres complexes.

1class UsingSetOfComplex(Grid):
2  def __init__(self):
3    self.grid = set()
4
5  def add(self, x, y):
6    self.grid.add(x+y*1j)
7
8  def check(self, x, y) -> bool:
9    return x+y*1j in self.grid

Nous voilà donc avec quatre implémentations possibles. La question est simple : sauriez-vous, à la simple lecture du code, les trier de la moins rapide à la plus rapide.

Moi, j'ai eu tout faux à cette question.

Réponse dans un prochain numéro.