Discussion :

[xavierdestev]

Bonjour,

Je voudrais savoir si au lieu d'écrire tous ces for à la suite les uns des autres, j'écrivais
un seul for de 0 à n^2 avec une panoplie de if alors jé gagne en performance et lisibilité.

Merci d'avance.

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
for (int i=0; i<n; ++i)
{
 
	a[i] = 4; a[i+1] = -1; a[i+2] = -1; a[i+3] =-1;
}
a[n+4] = 4; a[n+5] = -1; a[n+6] = -1;
for (int k=n+7; k<n*(n-2); ++k)
{
	a[k] = 4; a[k+1] = -1; a[k+2] = -1; a[k+3] = -1; a[k+4] = -1;
}
a[n*(n-2)] = 4; a[n*(n-2)+1] = -1; a[n*(n-2)+2] = -1;
for (int j=n*(n-2)+2, j< n*n; ++j)
{
	a[j] = 4; a[j+1] = -1; a[j+2] = -1; a[j+3] = -1;
}
a[n*n]=4;

[Neckara]

Bonjour,

Déjà si tu veux gagner en lisibilité, commence à indenter correctement tout ton code et à utiliser des noms de variables explicites, car là il est vraiment illisible

[koala01]

Salut,

D'un point de vue des performances, il est toujours intéressant d'éviter les itérations superflues.

Par contre, il faut te dire que, du point de vue du processeur, la boucle est généralement vue comme une comparaison et un saut vers une étiquette.

En gros, une boucle sera représentée sous la forme de

Code :

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

1
2
3
4
5
6
7
debut_boucle :
   on fait tout ce qui doit être fait
si compteur == valeur finale
sauter fin_boucle
sauter à debut_boucle
fin_boucle:
on continue après la boucle

et, classiquement, un test "simple" sera souvent vu comme une comparaison et un saut vers une étiquette car il prendra la forme de

Code :

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

1
2
3
4
5
si valeur_testee == valeur_souhaitee
saut fin_else
tout ce qui se fait dans la partie "false"
fin_else:
tout ce qui se fait dans la partie "true"

tu constatera que, à part les étiquettes, le principe reste fort similaire

Dés lors, il faut pouvoir "quantifier" le gain que tu auras en termes de performances par rapport à la complexité supplémentaire que tu apporteras à ton algorithme (et donc à la facilité de relecture).

Quantifier le gain de performances, c'est assez facile ici car tu pars d'un nombre équivalent à N*N + (3N) itérations et tu envisage de te retrouver avec un nombre équivalent à N*N itérations.

Le gain en performances sera d'autant plus grand que N sera petit :
1 - à N=10, tu passerais de 130 itérations à 100 itération, ce qui fait un tiers de performances en plus. La complexité supplémentaire peut parfaitement se justifier à ce niveau là.

2 - à N=100, tu passerais de 10300 itération à 10000, ce qui te ferait encore 3% de gain. Une complexité supplémentaire devient difficile à justifier

3 - à N=1000, tu passerait de 1 003 000 itérations à 1 000 000 soit à peine 0.03%. Si c'est pour gagner 3 millièmes de secondes sur un traitement qui en prend une, la complexité supplémentaire devient très difficile à justifier.

A titre de comparaison, un être humain en bonne santé qui est aux aguets mets entre 15 et 20 millièmes de secondes pour réagir par réflex. Un être humain ne verra simplement pas la différence. A moins bien sur que l'on parle de jour ou de semaine de traitement (mais la différence se contera à peine en minutes !!!)

Ceci dit, il y a très certainement moyen de parfaire ton algorithme.
Commençons donc par voir ce que fait ton algorithme avec N = 8

La première boucle va placer ton tableau dans un état correspondant à

Code :

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

1
2
3
4
5
6
7
8
9
 
  4  4  4  4  4  4  4  4
  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0

(j'ai regroupé les valeurs par 8 pour la facilité d'écriture ) ou 0 correspond à "une valeur inconnue"
La ligne qui suit la première boucle aura pour effet de placer ton tableau dans l'état

Code :

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

1
2
3
4
5
6
7
8
 4  4  4  4  4 -1 -1  4
-1 -1 -1  4 -1 -1 -1  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0

La deuxième boucle aura pour résultat de placere ton tableau dans un état proche de

Code :

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

1
2
3
4
5
6
7
8
9
 
  4  4  4  4  4  4  4  4
 -1 -1 -1 -1  4 -1 -1  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0

La ligne qui suit la deuxième boucle aura pour résultat de placer ton tableau dans l'état

Code :

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

1
2
3
4
5
6
7
8
9
 
  4  4  4  4  4  4  4  4
 -1 -1 -1 -1  4 -1 -1  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  4 -1 -1  0  0  0  0  0
  0  0  0  0  0  0  0  0

La dernière boucle aura pour résultat de placer ton tableau dans l'état

Code :

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

1
2
3
4
5
6
7
8
9
  4  4  4  4  4  4  4  4
 -1 -1 -1 -1  4 -1 -1  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  4 -1 -1  4  4  4  4  4 
  4  4  4  4  4  4  4  4   // j'espère que tu as bien prévu ( 8*9 ) éléments :D
 -1 -1 -1  0  0  0  0  0

Et enfin, la ligne qui suit la dernière boucle placera le tableau dans l'état

Code :

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

1
2
3
4
5
6
7
8
9
  4  4  4  4  4  4  4  4
 -1 -1 -1 -1  4 -1 -1  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4
  4 -1 -1  4  4  4  4  4 
  4  4  4  4  4  4  4  4   // j'espère que tu as bien prévu ( 8*9 ) éléments :D
 -4 -1 -1  0  0  0  0  0

Humm... Peut être ai-je eu tord de prendre, justement, N = 8... essayons avec N = 10...

La première boucle aura pour résultat de placer ton tableau (de 10*10 + 10 = 110 éléments) dans un état correspondant à

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
  4  4  4  4  4  4  4  4  4  4
 -1 -1 -1  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

La ligne qui suit la première boucle le placera dans un état correspondant à

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
  4  4  4  4  4  4  4  4  4  4
 -1 -1 -1  4 -1 -1  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

La deuxième boucle le placera dans un état correspondant à

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
  4  4  4  4  4  4  4  4  4  4
 -1 -1 -1  4 -1 -1  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

Après la ligne qui suit la deuxième boucle, on aura

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
 
  4  4  4  4  4  4  4  4  4  4
 -1 -1 -1  4 -1 -1  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4 -1 -1  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0

après la dernière boucle, on aura

Code :

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

1
2
3
4
5
6
7
8
9
10
11
  4  4  4  4  4  4  4  4  4  4
 -1 -1 -1  4 -1 -1  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4 -1 -1  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4   // j'espère que tu as bien prévu ( 10*11 ) éléments :D
 -1 -1 -1  0  0  0  0  0  0  0

et enfin, après la dernière ligne on aura

Code :

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

1
2
3
4
5
6
7
8
9
10
11
  4  4  4  4  4  4  4  4  4  4
 -1 -1 -1  4 -1 -1  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4
  4 -1 -1  4  4  4  4  4  4  4
  4  4  4  4  4  4  4  4  4  4   // j'espère que tu as bien prévu ( 10*11 ) éléments :D
  4 -1 -1  0  0  0  0  0  0  0

La première pensée qui me vient à l'esprit, elle prend corps dans le commentaire que j'ai indiqué : on se rend compte que l'on agit sur des élément qui atteignent l'indice (N*N)+3.

Si N est ton nombre de référence, tu devrais au minimum avoir N * (N+1) éléments pour éviter tout problème, autrement, ta dernière boucle et la dernière ligne vont toutes les deux aller taper dans des adresses mémoires qui leur sont normalement interdites, avec des catastrophes prévisibles

Dans le même ordre d'idée, on se rend compte que, quelque soit N et pour autant que tu as bien prévu d'avoir N *(N+1) éléments, il restera toujours N-3 éléments non initialisés.

Cela risque d'occasionner certaines surprises si tu essayes d'utiliser les valeurs que contiennent ces éléments

Enfin, on se rend compte que ce que tu cherches sans doute, c'est d'avoir une matrice carrée et que si tu t'en tiens au N*N premiers éléments, tu vas mettre la valeur d'une très grosse majorité d'éléments à 4 et qu'il n'y aura que "quelques éléments" dont la valeur sera placée à -1.

Dés lors, la question que l'on pourrait se poser est:

Pourquoi perdre son temps à mettre systématiquement a[compteur+1], a[compteur+2] et a[compteur+3] à -1 si c'est pour, de toutes manières, changer la valeur à l'itération suivante et, dans le pire des cas, à la ligne qui suit la boucle

Finalement, au lieu de modifier (plusieurs fois en plus !!! ) N*N éléments, pourquoi ne pas initialiser d'office tous les éléments à 4 puis ne modifier que les éléments (dont il est facile de déterminer les indices) dont la valeur doit être définie à -1

au lieu d'avoir au final N*N*3 changements de valeur, tu n'aurais plus que quelques modifications à apporter (je crois qu'on tourne à moins de 8, quelque soit la valeur de N... si je ne me suis pas trompé dans mes calculs .

Tu auras bien quelques calculs à effectuer, mais ils seront malgré tout particulièrement simples (multiplication et addition de base), limités en nombre ( huit, si j'ai bien saisi ) et surtout, tu auras quelque chose qui se fera en temps constant.

Autrement dit, que N soit égal à 8, à 1000 ou même à 1 000 000, toute la logique prendra toujours le même temps d'exécution, avec des performances qui grimperont en flêche (comparativement, la logique prendra beaucoup moins de temps sur des valeurs de N plus grandes) !

Bien sur, cela ne s'applique que si ton algorithme est correct, et le fait que tu essayes de modifier des valeurs se trouvant à des indices plus grands ou égaux à N*N me fait quelque peu douter de ce point

[xavierdestev]

Merci.

Je suis assez impressionné par la réponse de Koala.

Encore Merci.