IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

JavaScript Discussion :

Convertir un tableau en pourcentage le plus rapidement possible


Sujet :

JavaScript

  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    173
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2002
    Messages : 173
    Par défaut 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  2. #2
    Membre Expert
    Avatar de badaze
    Homme Profil pro
    Chef de projets info
    Inscrit en
    Septembre 2002
    Messages
    1 412
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Chef de projets info
    Secteur : Transports

    Informations forums :
    Inscription : Septembre 2002
    Messages : 1 412
    Par défaut
    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.

  3. #3
    Membre Expert
    Homme Profil pro
    Inscrit en
    Octobre 2011
    Messages
    2 910
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2011
    Messages : 2 910
    Par défaut
    Citation Envoyé par badaze Voir le message
    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 ?

  4. #4
    Membre Expert
    Avatar de badaze
    Homme Profil pro
    Chef de projets info
    Inscrit en
    Septembre 2002
    Messages
    1 412
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Chef de projets info
    Secteur : Transports

    Informations forums :
    Inscription : Septembre 2002
    Messages : 1 412
    Par défaut
    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...

  5. #5
    Membre Expert
    Homme Profil pro
    Inscrit en
    Octobre 2011
    Messages
    2 910
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2011
    Messages : 2 910
    Par défaut
    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...

  6. #6
    Membre Expert
    Avatar de badaze
    Homme Profil pro
    Chef de projets info
    Inscrit en
    Septembre 2002
    Messages
    1 412
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Chef de projets info
    Secteur : Transports

    Informations forums :
    Inscription : Septembre 2002
    Messages : 1 412
    Par défaut
    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 ?

  7. #7
    Expert confirmé
    Avatar de Watilin
    Homme Profil pro
    En recherche d'emploi
    Inscrit en
    Juin 2010
    Messages
    3 101
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : En recherche d'emploi

    Informations forums :
    Inscription : Juin 2010
    Messages : 3 101
    Par défaut
    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


    Je vais commencer par le 3e 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.


    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    newarray[i] = Math.floor((array[i] * 100) / max);

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    var length = array.length;
    …
    for (i = 0; i < length; i++) {}
    La seconde, plus surprenante, consiste à « boucler à l’envers » :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : 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
    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);
    La FAQ JavaScript – Les cours JavaScript
    Touche F12 = la console → l’outil indispensable pour développer en JavaScript !

  8. #8
    Modérateur

    Avatar de NoSmoking
    Homme Profil pro
    Inscrit en
    Janvier 2011
    Messages
    17 212
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Isère (Rhône Alpes)

    Informations forums :
    Inscription : Janvier 2011
    Messages : 17 212
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    var multiplicateur = 100 / max;
    for (i = length; i--; ) {
      newarray[i] = Math.floor((array[i] * multiplicateur);
    }

  9. #9
    Expert confirmé
    Avatar de Watilin
    Homme Profil pro
    En recherche d'emploi
    Inscrit en
    Juin 2010
    Messages
    3 101
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : En recherche d'emploi

    Informations forums :
    Inscription : Juin 2010
    Messages : 3 101
    Par défaut
    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.
    La FAQ JavaScript – Les cours JavaScript
    Touche F12 = la console → l’outil indispensable pour développer en JavaScript !

  10. #10
    Membre Expert
    Homme Profil pro
    Inscrit en
    Octobre 2011
    Messages
    2 910
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2011
    Messages : 2 910
    Par défaut
    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 Voir le message

    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 ?

  11. #11
    Expert confirmé
    Avatar de Watilin
    Homme Profil pro
    En recherche d'emploi
    Inscrit en
    Juin 2010
    Messages
    3 101
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations professionnelles :
    Activité : En recherche d'emploi

    Informations forums :
    Inscription : Juin 2010
    Messages : 3 101
    Par défaut
    Citation Envoyé par Beginner. Voir le message
    […] 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 :
    localiser l’objet (dans la portée)
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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

    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
    La FAQ JavaScript – Les cours JavaScript
    Touche F12 = la console → l’outil indispensable pour développer en JavaScript !

  12. #12
    Membre Expert
    Homme Profil pro
    Inscrit en
    Octobre 2011
    Messages
    2 910
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2011
    Messages : 2 910
    Par défaut
    Salut,

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

  13. #13
    Membre Expert
    Avatar de badaze
    Homme Profil pro
    Chef de projets info
    Inscrit en
    Septembre 2002
    Messages
    1 412
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Chef de projets info
    Secteur : Transports

    Informations forums :
    Inscription : Septembre 2002
    Messages : 1 412
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    function mafonction() {
       calcul_pourcentages();
       Reste du code ....
    }
     
    ....
    setTimeout(mafonction,5000);

  14. #14
    Membre confirmé
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    173
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2002
    Messages : 173
    Par défaut
    Un grand Merci pour vos réponses !!!

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 3
    Dernier message: 02/05/2007, 23h02
  2. Tri le plus rapide possible
    Par PadawanDuDelphi dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 04/10/2006, 19h19
  3. Lire un fichier le plus rapidement possible
    Par Rodrigue dans le forum SL & STL
    Réponses: 9
    Dernier message: 02/05/2006, 10h43
  4. Réponses: 10
    Dernier message: 12/01/2006, 21h22
  5. Permuter des valeurs, le plus rapidement possible?
    Par danje dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 27/09/2005, 21h51

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo