Convertir un tableau en pourcentage le plus rapidement possible

Bonjour,

à cause d'une fonction SetTimeout contraignante je dois réaliser une conversion de tableau en pourcentage dans un temp record :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

function percent(array) { var i, max=0; var newarray = new Array();   for (i=0; i<array.length; i++) max = max+array[i];   for (i=0; i<array.length; i++) newarray[i] = Math.floor((array[i]/ max) * 100 );   return newarray; } $grawdata=percent($grawdata);

---

comment rendre le temps d'execution de ce code le plus court possible.

Tu peux peut-être remplir max au fur et à mesure que tu remplis le tableau. Tu t’épargnes ainsi une boucle.
De toute façon du moment que tu as une contrainte de temps il y aura un moment où tu la dépasseras.

Après si tu calcules tes pourcentages au tout début du setTimeout tu n’as plus la contrainte.

Citation:

---

Envoyé par badaze

Tu peux peut-être remplir max au fur et à mesure que tu remplis le tableau. Tu t’épargnes ainsi une boucle.

---

Au début j'ai pensé pareil et ensuite je me suis rendu compte que max est la somme de tous les éléments du tableau et c'est cette somme qui est utilisée ensuite dans la deuxième boucle donc on ne peut pas la calculer au fur et à mesure...

A moins d'avoir mal compris ?

Non. Je parlais de sommer les valeurs dans max au moment de leur affectation dans le tableau.

Au début max = 0
j’insère 10 dans le tableau et somme 10 dans max (10)
j’insère 12 dans le tableau et somme 12 dans max (22)
etc...

Sauf que le tableau en question est à priori déjà rempli, la fonction le reçoit en argument et alors la première boucle fait la somme de tous les éléments de ce tableau et range le résultat dans "max" qui est ensuite utilisée dans la deuxième boucle...

Oui. Justement le but est de faire la somme au moment du remplissage du tableau.

Si je ne m’abuse le setTimeout est exécuté une seule fois. S’il faisait son calcul juste dans le setTimeout juste avant le code qui est normalement exécuté cela devrait résoudre son problème. Non ?

Problème intéressant :)

Pour tout problème d’optimisation, il y a trois points à considérer :

• Identifier les opérations les plus coûteuses
• Repérer les endroits critiques dans le code
• Connaître les astuces techniques

:arrow: Je vais commencer par le 3^e point car c’est quelque chose qu’on ne peut pas deviner. Étant donné qu’on connaît à l’avance la taille que doit avoir newarray, on peut le pré-allouer :

Code:

---

var newarray = new Array(array.length);

---

En ayant une certaine connaissance du fonctionnement des interpréteurs JS, on peut imaginer qu’une affectation « case par case » d’éléments d’un tableau peut mener, dans certains cas, à la situation catastrophique où l’interpréteur doit demander une nouvelle allocation de mémoire à chaque itération. Et l’allocation de mémoire est une opération coûteuse.

Même si ce cas a peu de chances de se produire, en faisant simplement une pré-allocation, on peut l’éviter complètement.

De manière un peu similaire, il est intéressant de donner une valeur à i dès sa déclaration, ainsi on donne à l’interpréteur une indication de son « type ». Ça a moins d’incidence que pour le tableau mais ça reste une petite optimisation et ça ne coûte pas grand chose.


:arrow: Le point 1 est une affaire d’intuition, et un peu de connaissance aussi. Pour l’utilisateur, JavaScript ne fait pas de distinction entre les différents types de nombres, ils sont tous Number. Cependant, en interne, ils sont stockés sous des formes différentes. i et array.length sont garantis être entiers, ils ont donc une représentation interne int ou similaire.

Pour les éléments du tableau, ça dépend de ce que contient array au départ. Dans tous les cas, au moment de la division array[i] / max, ils vont passer en double. Et les opérations sur les nombres flottants (FPU pour Floating Point Unit) sont plus coûteuses.

On a donc ici trois opérations qui coûtent plus cher que les autres :

• la division array[i] / max
• la multiplication par 100 du flottant obtenu juste avant
• le Math.floor

On peut économiser une opération FPU en déplaçant simplement la multiplication par 100 pour qu’elle se fasse avant la division. Si le contenu de array[i] est un entier, ça devient alors une opération de nombres entiers.

Code:

---

newarray[i] = Math.floor((array[i] * 100) / max);

---

:arrow: Le point 2 est le plus intéressant. Les endroits critiques, ici, sont ceux qui sont répétés dans les boucles for. Il s’agit donc de trois choses :

• le corps des boucles
• les tests i < array.length
• l’instruction d’itération i++

Il y a deux pratiques assez connues pour améliorer la performance de ces boucles. La première est simplement de mettre en variable array.length :

Code:

---

1 2 3 4 5

var length = array.length; … for (i = 0; i < length; i++) { … }

---

La seconde, plus surprenante, consiste à « boucler à l’envers » :

Code:

---

1 2 3

for (i = array.length; i--; ) { … }

---

Le test i-- sert en même temps à décrémenter la variable de boucle, et ainsi on économise une instruction.

Au final, voici le code que je propose :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

function percent(array) { var max = 0; var newarray = new Array(array.length); var length = array.length; var i = length;   for ( ; i--; ) { max = max + array[i]; }   for (i = length; i--; ) { newarray[i] = Math.floor((array[i] * 100) / max); }   return newarray; } $grawdata = percent($grawdata);

---

Bonjour,
tu peux encore optimiser le nombre d'opérations math exécutées, les divisions étaient plus lentes que les multiplications. (pas fait de test pour savoir si c'est toujours vrai !)

Code:

---

1 2 3 4

var multiplicateur = 100 / max; for (i = length; i--; ) { newarray[i] = Math.floor((array[i] * multiplicateur); }

---

Bien vu ;)

Effectivement max ne change pas à cet endroit-là, on a donc une opération sur deux valeurs constantes et on peut la factoriser.

Salut,

@badaze : ça y est j'ai compris ce que tu voulais dire...

Sinon c'est bien vu de la part de Watilin et de NoSmoking.

Citation:

---

Envoyé par Watilin

Il y a deux pratiques assez connues pour améliorer la performance de ces boucles. La première est simplement de mettre en variable array.length :

Code:

---

1 2 3 4 5

var length = array.length; … for (i = 0; i < length; i++) { … }

---

---

Ca tombe bien, je me suis posé cette question plusieurs fois... Et je me disais que length était une simple propriété associée au tableau et donc qu'on pouvait la lire aussi rapidement que n'importe quelle variable mais si je comprend bien ce n'est pas le cas et il y aurait alors un certain calcul d'effectuer comme si on avait affaire à une méthode...

Si c'est bien le cas, pourquoi on écrit pas un truc comme ça : array.length() ? Ca permettrait de savoir que c'est une méthode et non une simple variable ?

Citation:

---

Envoyé par Beginner.

[…] je me suis posé cette question plusieurs fois... Et je me disais que length était une simple propriété associée au tableau et donc qu'on pouvait la lire aussi rapidement que n'importe quelle variable mais si je comprend bien ce n'est pas le cas et il y aurait alors un certain calcul d'effectuer comme si on avait affaire à une méthode...

Si c'est bien le cas, pourquoi on écrit pas un truc comme ça : array.length() ? Ca permettrait de savoir que c'est une méthode et non une simple variable ?

---

Tu m’as mis le doute et j’ai dû vérifier dans la spec, mais .length est bel et bien une propriété « ordinaire » (enfin presque, elle a un effet de bord quand on change sa valeur, mais ce n’est pas le sujet).

La valeur de .length est mise à jour au moment où on ajoute ou retire des éléments du tableau, elle n’a donc aucune raison de provoquer des opérations inhabituelles quand on y accède en lecture.

Par contre, comme toute propriété de tableau, et à plus forte raison toute propriété d’objet, son accès nécessite au moins un déréférencement de pointeur, pour trouver son emplacement en mémoire parmi les propriétés de l’objet array.

En fait, il pourrait s’agir d’une propriété quelconque d’un objet quelconque, ce serait la même situation. L’interpréteur (hors optimisation) doit faire deux opérations de mémoire :
:fleche: localiser l’objet (dans la portée)
:fleche: localiser la propriété (dans l’objet)

Alors qu’avec une variable, il n’y aura qu’une seule opération.

Pour donner une explication plus visuelle, dans une expression comme celle-ci :

Code:

---

obj.prop1.prop2.prop3. …

---

Il y aura, a priori, autant de déréférencements qu’il y a de noms « autour des points ».

Donc array.length demanderait (hors optimisation, encore une fois) une opération de plus que la variable length. Ça n’a pas l’air énorme, mais dans une boucle qui fait dix mille itérations, on économise dix mille opérations. Il n’y a pas de petite optimisation quand il s’agit de boucles :roll:

Cependant… Ta question m’a aussi poussé à trouver autre chose en faisant des petites recherches : aujourd’hui, V8, le moteur JavaScript utilisé entre autres dans Google Chrome et NodeJS, est capable de faire une optimisation appelée inline caching qui consiste à mettre en cache l’adresse d’une propriété. Peut-être que j’ai mal compris le truc, mais ça permettrait de réduire le coût de l’expression précédente à une seule opération mémoire. Pour revenir à notre cas, array.length aurait le même coût que la variable length. Je ne suis pas certain, donc si quelqu’un peut apporter plus d’infos, ce serait sympa ;)

Je ne sais pas ce qu’il en est des autres moteurs JavaScript.

Pour donner une conclusion à mon post qui commence à être plutôt long, je pense qu’il ne faut pas compter sur une hypothétique optimisation du moteur, alors qu’on peut la faire nous-mêmes et qu’elle ne coûte rien :)

Salut,

Merci bien pour cette réponse détaillée.

Bon. Bien.
Mais est-ce que la solution ne serait pas tout bêtement de faire les calculs quand le setTimeout se déclenche ?

Code:

---

1 2 3 4 5 6 7 8

function mafonction() { calcul_pourcentages(); Reste du code .... }   .... setTimeout(mafonction,5000);

---

Un grand Merci pour vos réponses !!!