Mot-clé - Concept

Fil des billets - Fil des commentaires

03/25/2016

Complexité Algorithmique

Dans le dernier article nous nous quittions notamment sur la question de savoir s'il est possible de mieux faire ? Mais je n'ai pas dit par rapport à quoi. Il y a deux choses qui nous intéressent. La rapidité d'exécution de notre programme et la qualité du rendu final. Ce qui va nous intéresser aujourd'hui c'est la rapidité de notre algorithme et en particulier comment on peut déterminer celle-ci approximativement sans en mesurer le temps d'exécution, mais plutôt en analysant l'algorithme lui-même.

À l'origine je souhaitais continuer sur ma lancée en traitant toujours de génération procédurale de terrain. J'envisageais d'y parler très rapidement de complexité algorithmique dans les mots clefs en introduction et je me suis finalement rendu compte que ce n'était pas suffisant pour comprendre l'importance de ce concept et comme le sujet est intéressant, nous nous retrouvons finalement avec un billet à part entière ! Précisons cependant que c'est un vaste domaine et que cet article n'a pas du tout la prétention de tout couvrir, nous n'aborderons ici en fait que ce qui me semble nécessaire pour la suite.

Avant de commencer, définissons deux termes importants utilisés ici:

  • Notion de limite: C'est un concept mathématique qui vise à étudier l'évolution d'une fonction. En particulier, quand la variable de cette dernière tend vers une valeur donnée, on regarde vers quoi la fonction se rapproche à mesure que cette variable tend vers la valeur que l'on se propose. Par exemple on se donne une fonction f(x) = 1/x. La limite de f pour x qui tend vers l'infini s'écrit

lim2.png

  • Asymptote: C'est un terme très fortement lié à la notion de limite. De façon naïve, quand on représente graphiquement une fonction on peut éventuellement s'apercevoir que celle-ci tend vers une valeur ou une forme particulière. Pour mettre en évidence cette tendance, on utilise une droite dite asymptotique telle que l'équation de droite soit approximativement égale à la fonction quand celle-ci tend vers une valeur particulière.

asymptote.png

  • Par exemple ici nous aurions

lim.png

  • En effet, graphiquement nous voyons bien que plus x tend vers l'infini, plus la courbe F semble rejoindre la droite A en sorte de se confondre.

La notion de complexité est très importante quand on s'attarde sur l'optimisation et l'efficacité d'un programme. En particulier, on parle de complexité spatiale et temporelle pour évaluer, respectivement, la quantité de mémoire utilisée et le nombre d'instructions exécutées par un algorithme. Moins un algorithme consomme de mémoire et nécessite d'instructions à exécuter, plus celui-ci est efficace en termes de temps d'exécution et de ressources consommées. L'optimisation d'un programme consiste donc à réduire au mieux la complexité algorithmique. Réduire la complexité temporelle peut impliquer d'augmenter la complexité spatiale et inversement. Selon le contexte, on peut donc préférer plus de rapidité au détriment d'une utilisation massive de la mémoire. Cela peut notamment être le cas pour des programmes dits en temps réel.

L'analyse de la complexité est pertinente en particulier pour des algorithmes de tri, de recherche ou bien, dans notre cas, de calcul intensif, nous ferions donc bien de voir de quoi il en retourne.

Dans la pratique, on ne cherche pas à quantifier avec précision la complexité d'un programme, mais plutôt à déterminer vers quoi celle-ci va tendre. La notion de complexité algorithmique rejoint donc celle des limites en mathématiques. La complexité algorithmique est notée O() et est exprimée par exemple ainsi.

O(n²)

Cette écriture, dit de grand O de n carré (notation de Landau), signifie que, si l'on parle de la complexité temporelle, le temps d’exécution du programme sera proportionnel à n², où n est une variable qui désigne généralement la quantité de données à traiter. Par exemple on se donne le pseudo code suivant qui sert à remplir une matrice:

nouvelle matrix[n][n]

pour y=0 allant jusqu’à n-1, incrémenter y de 1: 
      pour x=0 allant jusqu’à  n-1, incrémenter x de 1:
             matrix[y][x] = x + y * n

Ici la complexité spatiale est de n² puisque nous réquisitionnons n² zone mémoire. Le lecteur attentif que vous êtes pourrait arguer que ce n'est pas tout à fait exact et qu'en fait ce serait plutôt t*n² avec t ayant pour valeur la taille de chaque élément de la matrice. En effet, quel est le type de la donnée ? S'agit-il d'un entier long, d'un octet ou d'un flottant ? En général ce détail n'a pas tant que ça d'importance parce que ce que nous voulons déterminer c'est un ordre de grandeur. Ce qui impacte vraiment sur la complexité spatiale c'est n. On peut donc raisonnablement dire que cette complexité spatiale est en O(n²).

Qu'en est-il de la complexité temporelle? De la même façon, on voit que l'on effectue, trois opérations. Une affectation, une addition et une multiplication. On répète le tout n² fois. On serait tenté de dire que la complexité spatiale est de 3n², mais non, là encore nous dirons que la complexité temporelle est en O(n²) parce que l'on considère que le triplé d'instructions tiens pour une seule opération élémentaire dans notre algorithme. Dit autrement, on peut considérer qu'une opération élémentaire est une action que l'on répète un certain nombre de fois et dont le temps d'exécution est borné.

Pour généraliser, la détermination de la complexité d'un algorithme se fait en excluant les constantes et les termes d'ordres inférieurs. On parle alors de complexité asymptotique. C'est ce que nous avons fait dans notre exemple en utilisant la notation de Landau. Dans un autre algorithme, nous pourrions avoir une complexité plus précise exprimée sous la forme d'une fonction

C(n) = 1n³ +  3n + 7

qui deviendrait alors

O(n³)

Le moins qu'on puisse dire, c'est que c'est approximatif. C'est parce que l'on évalue la complexité dans le pire des cas. C'est à dire quand n est vraiment très grand. En ce qui concerne l'algorithme de Perlin que nous avons présenté dans l'article précédent, on évalue en général sa complexité temporelle en O(2^n). C'est énorme, on dit de ce type de complexité qu'elle est exponentielle. Oui mais voilà. Ici, n ne représente pas le jeu de donnée à traiter, mais le nombre de dimensions dans lequel l'algorithme opère. Dans l'implémentation que je vous proposais, nous travaillions alors en deux dimensions, et pour des raisons dont nous ne parlerons pas pour le moment, il est très probable que nous continuons à travailler dans un espace bidimensionnel. Cette complexité, telle que formulée, ne nous avance donc à rien. Pour évaluer la complexité du Bruit de Perlin dans notre cas d'utilisation il faut se donner une variable, et comme le nombre de dimensions est constant, ce qui nous reste c'est la taille de la heightmap que l'on souhaite générer. Dans l'algorithme du Bruit Perlin, nous avions deux grosses étapes:

  • Le calcul de chacun des produits scalaires en quatre points.
  • L 'interpolation de chacun de ses points.

Ces deux étapes étaient répétées (2^n)² fois. En effet nous travaillons sur une surface plane carré dont la dimension est une puissance de deux (128,256,512, etc), n détermine donc l'échelle de notre surface. Mais ce n'est pas tout. Dans notre algorithme, nous calculons le bruit local pour plusieurs octaves. n octaves pour être exacts. Nous pouvons alors exprimer cette complexité ainsi.

Nous aurions donc une complexité temporelle formulée ainsi

O(n) =  n(2^n)²

Pour généraliser cette expression à un nombre arbitraire de dimensions, noté m, nous aurions alors:

O(n,m) = n(2^n)^m

On peut finalement reprendre les résultats que nous avions obtenus avec notre implémentation du Bruit de Perlin. Je parle évidemment des temps d'exécution affichés:

29 ms pour une surface de 256 pixels²

126 ms pour une surface de 512 pixels²

556 ms pour une surface de 1024 pixels²

2249 ms pour une surface de 2048 pixels²

Pour n = 7 jusqu'à n = 10 le temps d’exécution est multiplié en moyenne par un facteur 4,26. Et je dis bien en moyenne parce que le temps d'exécution, pour un même n varie selon la charge du CPU à un instant donné.

Or on s’aperçoit avec la complexité que l'on s'est donnée précédemment que si on calcule

O(n) / O(n-1)

pour n = 7 jusqu'à n = 10 on a

  • 4,66 pour n=7
  • 4,57 pour n=8
  • 4,50 pour n=9
  • 4,44 pour n =10

C'est sans surprise très proche du temps moyen effectivement mesuré !

Merci à Théo Fish et Benjamin Loubet pour la relecture orthographique!