Discussion :

[wiwaxia]

Bonjour,

... Etant curieux j'ai programmé la fonction définie plus haut la fonction donne bien les éléments voulus ...

Je comptais programmer cette vérification; voilà une bonne chose de faite. Picodev a une intuition de calcul tout à fait étonnante.

... sauf que le parcours de la matrice n'est pas correct
puisqu'il est parcouru ligne à ligne ...

Effectivement, c'est le détournement que j'évoquais à propos d'une autre possibilité de calculer les éléments de la matrice:

Mais un autre procédé plus rapide pourrait être envisagé, en deux étapes:
a) remplissage de la matrice par les entiers naturels successifs de [0 ; n2-1] à partir du coin supérieur gauche (a0,0), en suivant dans le sens toujours descendant les rangées consécutives parallèles à la seconde diagonale;
b) transposition des mêmes rangées d'ordre impair > 2 (pour les coins extrêmes, c'est inutile).

Cette dernière transformation est involutive, puisque son renouvellement conduit à la matrice d'origine. Ce procédé constitue cependant une tricherie, dans la mesure où l'obtention de la matrice transformée ne passe plus par le parcours imposé. A voir cependant ...

Il m'a paru, d'après la documentation consultée, que le parcours ainsi programmé a une importance essentielle, dans le traitement des images notamment. Un spécialiste expliquerait cela beaucoup mieux que moi.

Quel langage as-tu utilisé ? Les instructions me sont familières ... Free Pascal peut-être ? Je ne m'y suis pas encore investi à fond. (*)
Juste un détail, assez secondaire: je n'aurais pas utilisé directement la fonction puissance power(-1,i+j) ,
mais plutôt quelques instructions comme:

Code :

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

1
2
3
 
s:= i + j; IF Odd(s)  THEN Epsilon:= -1
                             ELSE Epsilon:= 1;

susceptibles d'alléger un peu la suite du calcul.
Mais il est vrai que chaque langage a son style approprié, et de même chaque programmeur ...

(*) Je viens d'apercevoir la fonction booléenne Odd(s) donc c'est du Pascal, vraisemblablement.

[Flodelarab]

Là, je veux bien connaître ton programme, et le voir fonctionner ...

J'avais la flemme de faire les calculs concrets, mais devant votre courage à tous pour écrire du code, je vais le faire.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
END{
	for (ind=2;ind<=2*n;ind++)
	{	
		e=n-abs(ind-n-1);
		for (lec=1;lec<=e;lec++)
		{
			x=(ind%2)*(e+1-2*lec)+lec+(ind-e-1)/2;
			y=ind-x;
			print a[x,y];
		}
	}
}

J'entends d'ici pousser les hauts cris car c'est trop compliqué, ou/et surtout, que vous n'avez pas été présenté à Mesdames les inconnues.
Donc, on reprend pas à pas:

• n est la dimension de la matrice carrée.
• Première boucle:
  On prend les diagonales une à une de 2 à 2n (j'avais prévenu).
  On appelle ind l'indice.
• Combien d'élément dans cette diagonale ?
  Cette variable est muette et existe uniquement pour éviter les répétitions.
  On l'appelle e.
  e = n - | ind - n - 1 |
• Soit la fonction valeur absolue est implantée dans votre langage, soit vous calculez la racine carrée du carré du nombre.
• Deuxième boucle:
  On prend les éléments successifs de la diagonale.
  On l'appelle lec, comme une tête de lecture.
• L'abscisse x est exactement égale à lec pour les lignes avant la diagonale.
  Après on ajoute un décalage d'abscisse, qui se déclenche pour les grandes valeurs de ind.
  Il est égal à (ind-e-1)/2.
• L'ordonnée y est complémentaire de x. (toujours).
  Donc y=ind-x.
• On affiche la donnée du tableau.
• La dernière chose que je n'ai pas expliquée est le sens de lecture.
  lec devrait aller de 1 à e dans un sens, et de e à 1 dans l'autre sens.
  Au lieu de multiplier lec par -1 et d'ajouter un terme qui est là, ou pas ( ce qui obligerait à utiliser 2 fois la parité), on ajoute (ou pas) le terme (e+1)-2*lec.

Cette boucle est dans un script awk (modification de fichier texte sous linux/unix):

Code :

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

1
2
3
4
5
6
$ cat diagonale5.txt 
1,1 2,1 3,1 4,1 5,1
1,2 2,2 3,2 4,2 5,2
1,3 2,3 3,3 4,3 5,3
1,4 2,4 3,4 4,4 5,4
1,5 2,5 3,5 4,5 5,5

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
$ ./lineariser.awk diagonale5.txt 
1,1
2,1
1,2
1,3
2,2
3,1
4,1
3,2
2,3
1,4
1,5
2,4
3,3
4,2
5,1
5,2
4,3
3,4
2,5
3,5
4,4
5,3
5,4
4,5
5,5

Autre exemple avec une dimension paire:

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
$ ./lineariser.awk diagonale4.txt 
1,1
2,1
1,2
1,3
2,2
3,1
4,1
3,2
2,3
1,4
2,4
3,3
4,2
4,3
3,4
4,4

Et enfin, exemple avec du texte:

Code :

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

1
2
3
4
$ cat diagonale3.txt
la fin des
justifie parfois moyens
aussi tordus efficaces.

Code :

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

1
2
3
4
5
6
7
8
9
10
$ ./lineariser.awk diagonale3.txt 
la
fin
justifie
aussi
parfois
des
moyens
tordus
efficaces.

Conclusion: Aucune condition n'est requise. Que du calcul.

[wiwaxia]

Bonjour,

Rien à redire aux instructions en soi légitimes, dont tu nous a donné la traduction; et l'algorithme fonctionne correctement, puisqu'il conduit aux matrices et listes attendues lorsque (n) vaut 3, 4 ou 5. Donc bravo, un trophée de plus pour la section du Forum.
Il découle de ceci:
1°) que l'émulation est une excellente chose

J'avais la flemme de faire les calculs concrets, mais devant votre courage à tous pour écrire du code, je vais le faire ...

2°) que l'algorithmique n'est pas incompatible avec l'humour

Code :

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

1
2
 $ ./lineariser.awk diagonale3.txt 
la			fin			justifie	aussi		parfois		des			moyens		tordus		efficaces

3°) ... mais aussi que les instructions les plus tordues (*) peuvent dissimuler les plus simples algorithmes
(*) soyons francs, ce n'est pas le cas ici
J'aperçois en effet dans le texte la fonction Abs(x) définie (quelle horreur !) par les instructions conditionnelles;

Code :

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

1
2
IF x<0 THEN Abs:= -x
       ELSE Abs:=  x ;

ce qui fait que la longueur (e) d'une diagonale, définie par la relation: e = n - | ind - n - 1 | relève aussi de consignes prohibées:

Code :

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

1
2
IF ind<(n + 1) THEN e:= ind - 1                               // e = n - (n + 1 - ind) = ind - 1 , variant de 1 à n - 1
               ELSE e:= 2*n + 1 - ind ;                       // e = n - (ind - n - 1) = 2*n + 1 - ind , variant de n à 1

et quelques lignes plus loin l'expression

Code :

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

x=(ind%2)*(e+1-2*lec)+lec+(ind-e-1)/2;

équivalente à

Code :

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

1
2
 IF Odd(ind) THEN x:= (1 + e + ind)/2 - lec    // x = e + 1 - 2*lec +lec + Ind/2 -(1 + e)/2 = (1 + e + ind)/2 - lec 
             ELSE x:= lec+(ind-e-1)/2;         // heureusement, (e) et (ind) sont toujours de parités opposées !  

On retrouve ainsi les deux conditions concernant la longueur et la parité de la rangée.

Conclusion: Aucune condition n'est requise. Que du calcul.

De même que Monsieur Jourdain faisait de la prose sans le savoir, qui recourt aux fonctions Abs(x) et (x MOD 2) insère à son insu des opérations logiques dans son calcul.

[wiwaxia]

Bonjour,

@anapurna
Hier soir, l'appel de Round(x) dans le calcul d'une fonction entière de variables entières m'a intrigué, mais j'ai d'abord mis cela sur le compte des nombreux mystères de la programmation.

... Etant curieux j'ai programmé la fonction définie plus haut ...
voici les codes utiles pour les curieux ^^

Code :

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

1
2
3
4
5
6
7
8
 
Function zz(n,i,j : Integer) :Integer;
begin
  if (i+j) < n Then
    Result := Round(((i+j)*(i+j+2+Power(-1,i+j))/2)-(power(-1,i+j)*i))
  else
    Result := Round(Power(n,2)-1-zz(Round(power(n,2)),n-1-i,n-1-j));
end;

C'est seulement ce matin que je me suis aperçu qu'on y était contraint, dès lors qu'intervenait aussi la fonction réelle power(x, y); un calcul plus simple ne serait-il pas possible, en n'utilisant que des entiers ? Par exemple:

Code :

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

1
2
3
4
5
6
7
 
 BEGIN
   s:= i + j; IF Odd(s) THEN u:= -1
                        ELSE u:= 1;
   t:= s + 2; Inc(t, u); 
   p:= s * t; q:= p DIV 2; Result:= q - u
 END;

Cordialement, W

[Flodelarab]

De même que Monsieur Jourdain faisait de la prose sans le savoir, qui recourt aux fonctions Abs(x) et (x MOD 2) dissimule à son insu des opérations logiques dans son calcul.

C'est pas vrai M'sieur.

Déjà pour la valeur absolue, j'avais répondu: "Tu calcules la racine carré du carré du nombre".

Pas d'alternative.

Et en quoi le reste de la division entière te défrise ? (ind%2)
Il n'y a aucune condition.
C'est juste que le reste de la division euclidienne ne peut prendre que 2 valeurs.
Où est l'alternative ?
Même processus pour tous les cas.

Si % te gêne, alors / te gêne. Et par extension +, *, -, /, %, etc te gênent.
N'est-ce pas ?

[picodev]

Bravo. C'est ce que j'ai dit dès mon premier message pour lequel j'ai reçu un joli pouce baissé.

Toutes vos solutions ont des conditions. Alors qu'aucune condition n'est nécessaire.

J;ai donné une implémentation de ta solution au message 11.
Maintenant dès que tu as une boucle for tu vas avoir une condition ^^

[wiwaxia]

Bonjour,

Que du calcul.
Symptomatique, cette réaction d'évitement !
"Que du calcul", entendre par là: on peut foncer sans réfléchir, y a pas de trucs ch mesquins du genre < si ... alors ... sinon ... > qui vous gâchent l'ambiance. Les lycéens présentent tous le même réflexe, lorsqu'ils sont par exemple confrontés à des valeurs absolues. J'avais le même comportement, à l'époque.
On peut comprendre que l'insertion de consignes de validité soit encombrante, et que l'on préfère programmer sur une (très) ancienne calculatrice dépourvue d'opérations logiques: F_(n) = (1/2)*(a_(n) + b_(n)) + ((-1)ⁿ /2)*(a_(n) - b_(n)) au lieu de

Code :

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

1
2
IF Odd(n) THEN F:= b(n)
          ELSE F:= a(n)

D'autres subterfuges (au départ tout aussi séduisants, j'en conviens) conduisent à des expressions analogues, relativement lourdes - elles peuvent compliquer singulièrement le contrôle des éventuelles erreurs et la recherche des cas où le calcul deviendrait difficile, voire impossible.
La formule citée plus haut peut même conduire à des résultats surprenants: essayez donc le cas suivant: a = 10¹⁰ et b = 10^-10 ...

Aucune condition n'est requise
F(x) = │x│ et la condition

Code :

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

1
2
 IF x<0 THEN F:= -x
        ELSE F:= x;

sont indissociablement liés par la définition même de la valeur absolue, et il est enfantin d'espérer que ces instructions logiques disparaîtront comme par magie en usant de travestissements comme Fx) = (x² )^1/2 ; c'est croire qu'un nouvel habillage supprimera ce qu'il y a à l'intérieur.
Il existe d'autres exemples de produits de fonctions élémentaires non exactement réciproques, comme G(x) = Arctan(tan(x)) ou (Hx) = Arccos(cos(x),) et dont le comportement est surprenant.
L'une d'entre elles a un rapport étroit avec le reste euclidien mod((x, a). Je ne dis cela pour personne, en particulier.

Soit par exemple la fonction Max(a, b) définie par:

Code :

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

 IF b>a THEN Max:= b ELSE Max:= a;

un programmeur animé d'une aversion particulière pour les instructions conditionnelles lui substituera une expression plus sympathique:
Max(a, b) = (1/2)*(a + b) + (1/2)*(a² + b² - 2*a*b)^1/2 , nettement plus simple, tout le monde en conviendra.
Et s'il entreprend de rechercher le plus grand volume d'un prisme oblique constructible sur 4 points dans un nuage qui en comporte (N), il lui faudra comparer (N⁴/24) termes: rapidité optimale garantie.

Petit exercice de géométrie analytique niveau seconde, garanti sans conditions - que du calcul !
C'est un sujet tout simple, non sans rapport avec le parcours en zig-zag d'un matrice carrée: déterminer les points d'intersection d'une droite d'équation (y = a*x + b) avec un carré de côté 2, centré à l'origine et d'arêtes parallèles aux axes du repère.
Un programmeur au raz des pâquerettes définirait les 4 côtés successifs par les conditions:

Code :

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

1
2
3
4
5
 
 IF ((-1< y) AND (y< 1)) THEN CASE n OF  1: x:= 1;
                                         3: x:= -1  END;
 IF ((-1<=x) AND (x<=1)) THEN CASE n OF  2: y:= 1;
                                         4: y:= -1  END;

On rougit de confusion devant une démarche aussi prosaïque.
Un puriste ennemi de toute compromission aura recours à l'équation polaire du carré: r = 1 / cos[(1/2)*Arcsin(sin(2*t))] .
Ouf ! Enfin deux équations, que du calcul ! Pas de conditions !

[Flodelarab]

Ah oui. D'accord. Les balises [mauvaisefoi] [/mauvaisefoi] ont été activées sans le dire.
On peut trouver des exemples grand-guignolesques à l'inverse.

La base

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
if e=1 then s=2
elif e=2 then s=4
elif e=3 then s=6
elif e=4 then s=8
elif e=5 then s=10
elif e=6 then s=12
elif e=7 then s=14
elif e=8 then s=16
elif e=9 then s=18
elif e=10 then s=20
elif e=11 then s=22
elif e=12 then s=24
elif e=13 then s=26
elif e=14 then s=28
elif e=15 then s=30
elif e=16 then s=32
elif e=17 then s=34
elif e=18 then s=36
elif e=19 then s=38

Donc là, c'est sûr que la personne a bien fait d'écrire ces conditions pour connaître tous les doubles. s=2*e eût été trop simple.

Quête de l'infini

Un exemple qui permet d'enchaîner élégamment avec un second, tout aussi idiot car limité. Il donne la quantité de chiffres et -1 s'il ne sait pas.

Code :

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

1
2
3
4
if e<10 then s=1
elif e<100 then s=2
elif e<1000 then s=3
else s=-1

Si on rentre un nombre trop grand par rapport aux conditions, il y a
bug/dépassement de capacités. Alors qu'un logarithme en base 10 donne le
nombre de chiffres nécessaire quelque soit la valeur en entrée.

[emna1987]

j'ai essayer le code suivant en pascal :

Code pascal :

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
program zigzag;
uses wincrt;
var
nbligne,nbcolonne,nblignemax,nbcolonnemax,i,j,taille,k:integer;
mat:array [1..3,1..3] of integer;
begin
nbligne:=1;
nbcolonne:=1;
nblignemax:=3;
nbcolonnemax:=3;
k:=1;
taille:=36;
mat[nbligne,nbcolonne]:=k;
while(taille<9) do
begin
k:=k+1;
if(nbligne=1) or(nbligne=nblignemax) and(nbcolonne mod 2=1) then
begin
nbcolonne:=nbcolonne+1;
mat[nbligne,nbcolonne]:=k;
end
else
if(nbcolonne=1) or(nbcolonne=nbcolonnemax) and (nbligne mod 2 =0) then
begin
nbligne:=nbligne+1;
mat[nbligne,nbcolonne]:=k;
end
else
if(nbcolonne mod 2=0) then
begin
repeat
nbligne:=nbligne+1;
nbcolonne:=nbcolonne-1;
mat[nbligne,nbcolonne]:=k;
k:=k+1;
until(nbcolonne=1);
end 
else
if(nbligne mod 2=1) then
begin
repeat
nbligne:=nbligne-1;
nbcolonne:=nbcolonne+1;
mat[nbligne,nbcolonne]:=k;
k:=k+1;
until(nbligne=1);
end;
end;
for i:=1 to 3 do
begin
for j:=1 to 3 do
write(mat[i,j]);
writeln;
end;
end.

mais il m'affiche le resultat
123
456
789
et non pas le resultat attendu
126
357
489

[Flodelarab]

1. La question n'est pas celle posée dans le premier message.
2. N'as-tu pas lu les réponses que les uns et les autres ont pris le temps de t'écrire ?
3. Pourquoi ton programme n'a qu'une matrice alors qu'elle devrait au minimum en comporter deux ? une pour l'entrée et une pour la sortie...

[emna1987]

nom c'est une seul matrice qu'on doit remplir sous forme de zigzag j'ai mentionnée la photo d'une matrice en zigzag pour montrer la direction empreinté pour remplir la matrice

[anapurna]

Quel langage as-tu utilisé ? Les instructions me sont familières ... Free Pascal peut-être ? Je ne m'y suis pas encore investi à fond. (*)

(*) Je viens d'apercevoir la fonction booléenne Odd(s) donc c'est du Pascal, vraisemblablement.

Oups je manque a tout mes devoirs, je vais donc te répondre avec un peu de retard ma transcription est en pascal objet ...
plus précisément en Delphi

[emna1987]

j'utilise pascal comme langage et turbo pascal 1.5 cmme environnement vraiemment j'ai passé beaucoup de temp et je commence a m'enerver car j'ai pas de plus a ajouter j'ai mis tout svp je serais très reconnaissante si je trouve la solution et marci d'avance

[Flodelarab]

La solution est déjà écrite. Il ne reste plus qu'à apprendre à lire et à relire la discussion.

[tbc92]

Oupsss !
Je croyais que c'était un exercice que tu avais eu dans un examen, le genre d'exercice qu'on doit résoudre en 15/20 minutes, comme mise en bouche avant un exercice plus sérieux.
J'ai fait complètement fausse route !

[wiwaxia]

... je vais donc te répondre avec un peu de retard ma transcription est en pascal objet ... plus précisément en Delphi

@anapurna
Merci pour l'info; je suis actuellement en voyage, et indisponible pour la participation au forum.

[Prof]

Bonjour.

Permettez-moi d'avoir une autre approche concernant le sujet proposé.

Le problème initial concerne visiblement les procédures de compression/décompression d'images JPEG.

Dans ces procédures, l'image est découpée en blocs de 8x8 pixels et le traitement s'effectue sur chacun de ces blocs.
Puis le codage se fait suivant un parcourt en zigzag.
voir https://fr.wikipedia.org/wiki/JPEG#C...RLE_et_Huffman

Les photos prises par les appareils photos font couramment plusieurs millions de pixels.
( une vingtaine de Mp pour les appareils actuels, le record étant détenu par le CANON EOS 5DS avec 50 Mp )
On se retouve donc avec un nombre élevé de blocs à traiter ( plusieurs centaines de milliers ).

Or la rapidité d'exécution est primordiale, surtout dans la décompression car l'utilisateur souhaite un affichage rapide.
Il faut donc un algorithme simple et rapide pour le parcours en zigzag d'une matrice.

Comme on ne s'intéresse pas au cas d'une matrice carrée d'ordre n quelconque, mais à un cas particulier fixé, la meilleure solution est un " codage en dur ".
C'est-à-dire qu'on utilise une table de conversion, fixée une fois pour toutes.

Pour une matrice 8x8 dont les cases sont balayées de la manière habituelle : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
on utilisera la table de conversion : 1, 9, 2, 3, 10, 17, 18, 11, 4, 5, 12, ...

Et pour aller encore plus vite, on utilisera directement des adresses plutôt que calculer les adresses à partir des indices.

En Assembleur, on manipule naturellement les adresses.
Dans les langages évolués, le terme correspondant est "pointeur".
On va donc utiliser des pointeurs.

Utiliser une table de pointeurs est une opération courante en langage C.
Cela l'est un peu moins en Pascal, mais les pointeurs font partie du langage Pascal.

Voici donc un programme en Pascal qui remplit une matrice avec des entiers puis la lit en zigzag.
( pour simplifier l'exemple, j'ai pris une matrice 3x3, mais il est facile de généraliser à une matrice 8x8 )

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
Program Zigzag;
 
const N = 3;
      table : array[1..N*N] of integer = (1,4,2,3,5,7,8,6,9);  { table de conversion }
 
var   A : array[1..N,1..N] of integer;              { A est une matrice }
      T : array[1..N*N] of ^integer;                { T est une table d'adresses }
      i,j,k : integer;
 
begin
  for i := 1 to N do                                { initialisation de la table T }
      for j := 1 to N do T[(i-1)*N+j] := @A[i,j];
 
  randomize;
  for i := 1 to N do                                { remplissage de la matrice A }
      for j := 1 to N do A[i,j] := random(100);
 
  for i := 1 to N do                                { affichage de la matrice A }
      begin
         for j := 1 to N do write(A[i,j]:4);
         writeln;
      end;
  writeln;
 
  for k := 1 to N*N do write(T[table[k]]^:4);       { lecture en zigzag de la matrice A }
 
  writeln;                                          { pause }
  readln;
end.

Et la sortie écran :

Code :

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

1
2
3
4
5
6
7
 
 
  34  65  63
  36  89  70
   4  60   9
 
  34  36  65  63  89   4  60  70   9

[wiwaxia]

Bonjour,

Merci pour le programme, qui constitue une occasion motivante de se familiariser un peu mieux avec les pointeurs, que pour ma part je n'utilise que rarement, contraint et forcé.

Et je retiens la possibilité d'accélérer l'exécution des programmes très lourds ...

... Et pour aller encore plus vite, on utilisera directement des adresses plutôt que calculer les adresses à partir des indices.

... je suis curieux de voir ce que cela peut donner.

Tu présentes assez bien le lien particulier qui existe entre les matrices zig-zag et le traitement des images JPEG; ces explications sont difficiles à trouver sur la Toile, parce que l'on passe souvent sans transition d'une vague mention dans un texte sommaire à l'article de fond, de niveau professionnel.

Ceci dit, je n'ai toujours pas compris pourquoi le traitement de l'image est plus rapide par un balayage aller-retour en diagonale, plutôt que selon les lignes ou les colonnes ...

[Prof]

Bonjour.

Ceci dit, je n'ai toujours pas compris pourquoi le traitement de l'image est plus rapide par un balayage aller-retour en diagonale, plutôt que selon les lignes ou les colonnes ...

Parce que les ( quelques ) termes non nuls de la matrice quantifiée se trouvent en haut à gauche.
C'est une conséquence de la méthode suivie : DCT suivie de la quantification, en partant du coin supérieur gauche.

( voir le lien donné dans mon précédent post, puis remonter de quelques lignes dans l'article de Wikipédia )

En balayant en zigzag on a une séquence de quelques termes non nuls suivis de plusieurs dizaines de 0.
On peut alors comprimer facilement cette séquence, d'où le gain de place.

[souviron34]

Et je retiens la possibilité d'accélérer l'exécution des programmes très lourds ...

... je suis curieux de voir ce que cela peut donner.

Le principe est extrêmement simple et fortement utilisé dans tous les algos durs en calcul (comme par exemple en génétique), et devient encore plus puissant quand il y a des boucles imbriquées (matrices à plusieurs dimensions)

Calculer une adresse se fait par : adresse de base + (indice de l'élément * taille du type de l'élément) : table[i] = adresse de départ + i * taille_du_type.

Donc pour calculer UNE adresse on fait une multiplication et une addition. Donc quand on veut passer de l'élément i à l'élément i+1 on en fait 2 de chaque (plus une addition).

Si maintenant on se sert d'un pointeur (qui est le type "adresse") alors pour passer de i à i+1 on ne fait qu'une seule addition... Et comme la multiplication est plus longue que l'addition, non seulement on divise le nombre d'opérations par 2, mais même un peu plus que 2..

Par exemple, si on a une boucle sur un tableau d'entiers 2D :

Code C :

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

1
2
3
4
5
for ( i = 0 ;  i < DY ; i++ ) {
  for ( j = 0 ; j < DX ; j++ ) {
       table[i][j] = 0 ;
  }
}

Chaque itération sera équivalente à : table[i][j] = adresse de base de table[i] + j * taille d'un entier

Or l'adresse de base de table[i] sera : adresse de base du tableau + i * (DX * taille d'un entier) (par exemple)

Donc l'adressage d'un élément table[i][j] s'effectue par 2 additions et 2 multiplications.

Si maintenant on procède comme suit :

Code C :

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

1
2
3
4
5
6
7
8
tab = table  ;  /* (ou table[0][0]) */

for ( i = 0 ;  i < DY ; i++ ) {
  for ( j = 0 ; j < DX ; j++ ) {
       *tab = 0 ;   /*  l'étoile devant "tab" designe qu'on affecte le contenu de ce qui est pointé par l'adresse */
       tab = tab + 1 ;    /* qu'on peut écrire *tab++ = 0 ; */
  }
}

On voit qu'on ne fait qu'une seule addition à chaque fois.. On gagne donc 2 multiplications et une addition à chaque élément...

Quand DX et DY deviennent très grands, ou qu'on passe de multiples fois dans cette boucle (par exemple quand on cherche une minimisation du type Simplex) on voit bien qu'on gagne un facteur gigantesque...

Et quand on a plus que 2 dimensions c'est encore plus flagrant... Alors là j'ai présenté un exemple simple qui est "continu". Mais même si il faut affecter à chaque intérieur de boucle, on gagne à chaque fois un étage d'addition/multiplication...

Par exemple :

Code C :

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

1
2
3
4
5
6
7
for ( i = 1 ;  i < DY ; i++ ) {
  for ( j = 0 ; j < DX ; j++ ) {
      for ( k = 0 ; k < DZ ; k++ ) {
           table[i][j][k] = table[i][j][k] + table[i-1][j][k]  ;
      }
  }
}

Chaque référence à table[x][y][z] fera 3 multiplications et 3 additions. Dans le cas ci-dessus, pour donc affecter un élément de la table, on fera : 9 multiplications et 10 additions....

Si maintenant on écrit :

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
li1 = table[0][0][0]  ;  /* ligne précédente */
li = table[1][0][0]  ;   /* ligne actuelle */
 
for ( i = 1 ;  i < DY ; i++ ) {
  for ( j = 0 ; j < DX ; j++ ) {
      for ( k = 0 ; k < DZ ; k++ ) {
           *li = *li + *li1  ;
 
           li = li++ ;
           li1 = li1++ ;
     }
  }
}

Dans ce cas, on n'a que 3 additions.... à chaque élément... **

Imagine les gains....

(dans le cas cité on va 6 fois plus vite : DX*DY*DZ*19 vs DX*DY*DZ*3 !!!!)

Par exemple j'ai vu un programme passer de 10 heures de runtime à 2 minutes juste en faisant ça sur la fonction de fond qui etait appelée à chaque fois..

Alors bien sûr le code est moins lisible "mathématiquement", mais on profite de l'avantage tellement que le jeu en vaut la chandelle (et les programmeurs qui développent ou maintiennent ces applis, si ils documentent correctement (par exemple en mettant la formule mathématique en commentaires) rendent la lecture (en général) compréhensible)..





** : et même si c'est un peu plus compliqué et qu'il y a des indices plus compliqués (j-1, j-2 par exemple), on peut quand même les mettre sous forme de pointeurs dans l'étage j, et on gagne donc tous les calculs dans les boucles intérieures... Le principe est de remonter tout calcul d'adresse possible le plus haut possible dans la hiérarchie des boucles...