En ligne · Standard · [ Linéaire+ ] Algo De Tri, appel aux codeurs

[Sha]

Gràce aux conseils de Gfx j'ai pu profiler mon appli java pour trouver quelles étaient les procédures qui la ralentissaient. (J'utilise Hyades sous Eclipse)

Il s'avère que l'un des plus importants bottelnecks (ralentissements) est provoqué par un aglo de tri, qui me sert à classer dans l'ordre décroissant des valeurs de type double, dont le nombre peut aller de quelques-unes à plusieurs milliers.

N'étant pas un vrai programmeur et ayant suivi les conseils que j'ai pu trouver, j'utilise pour l'instant un algo de "tri a bulles", réputé rapide. Alors peut-être que ma version de l'algo est sous-optimale et peut-être même que ce n'est pas le bon algo, si vous pouviez m'aider je vous en serais reconnaissant

CODE

   private void triBulle(double[] valeurs) {
       int i;
       boolean permut = true;
       double tempVal = 0;
       int tempNdx = 0;

       for (i = 0; i < valeurs.length; i++) {
           posDec[i] = i;
       }
       while (permut == true) {
           permut = false;
           for (i = 0; i < (valeurs.length - 1); i++) {
               if (valeurs[i] < valeurs[i + 1]) {
                   tempVal = valeurs[i];
                   valeurs[i] = valeurs[i + 1];
                   valeurs[i + 1] = Math.abs(tempVal);
                   tempNdx = posDec[i];
                   posDec[i] = posDec[i + 1];
                   posDec[i + 1] = tempNdx;
                   permut = true;
               }
           }
       }
   }

Ce message a été modifié par Sha - 17/03/2005 17:19.

[Dude76]

[mode vieux souvenirs de licence]
tri bulle : complexité en N²
QuikSort : complexité en N² théorique, s'approche de N Log(N) dans la pratique.
Passer par des arbres binaire : complexité en N Log(N).
[/mode]

[Gfx]

Houlà Sha, fallait demander Regarde donc la classe Arrays, elle est bourrée de méthodes sort() qui utilisent un quicksort modifié et donc les performances sont très bonnes. En plus ça c'est totalement inutile dans ton algo :

CODE

for (i = 0; i < valeurs.length; i++) {
 posDec[i] = i;
}

De manière générale je le trouve bizarre le code de ton tri à bulle.

[Sha]

Ben oui mais si je demandais pour tout, comme y'en a des milliers de lignes
En tout cas merci encore

[PoP]

Fait gaffe Sha, c'est un coup à finir sur DailyWTF!
Rah merde, ça me fait penser que j'ai un dewoir sur les algos de tri en ADA à faire pour la fin du mois...fack!

[Sha]

Désolé mais j'ai bien besoin de la premièe boucle qi remplit le tableau posDec, mais peut-être est-ce parce que je n'utilise pas d'Array.sort. J'ai besoin de classer des indices, en plus de classer des valeurs. L'objectif est d'avoir un tableau qui contienne l'ordre décroissant d'un autre tableau, en fait.

Mais bon, j'ai résolu mon problème, car ce tri était appelé pour chaque itération de la boucle qui dessine les polygones de mon fond de carte... Au lieu d'une fois préalablement ! Je suis content, mon appli tourne bien plus rapidement

Encore une démonstration de la niaiserie de ma méthode de travail en programmation : j'imagine vaguement dans ma tête (jamais sur un schéma propre) l'organisation des classes et des appels, je code en vrac, je regarde si ça marche

Si cela vous intrigue, voilà le bestiau :

http://www.univ-tlse2.fr/geoprdc/scap/java/

Ce message a été modifié par Sha - 18/03/2005 9:47.

[PoP]

/mode clubic on
pfff, c'est nul, y'a qu'une carte...quelle appli de merde...


Ca ne requière pas 1.5 si?

Ce message a été modifié par PoP - 18/03/2005 12:05.

[Gfx]

Utilise quand même Ararys.sort() Et puis pour avoir l'ordre décroissant... il suffit de parcourir le tableau en sens inverse puisqu'il est trié

Ce message a été modifié par Gfx - 18/03/2005 12:33.

[Sha]

Pop> j'en sais trop rien, normalement ça doit tourner avec le 1.4, mais j'ai fat le build avec le sdk 1.5.1 sur la machine.

Gfx> oui dès que j'ai un peu de temps pour reprndre ce code un peu plus sérieursment j'essaie. Le problème c'est la motivation, un mois de boulôt et personne que ça intéresse ou presque.

[Gfx]

Un build sur un JDK 1.5 ne tournera pas sur un JDK 1.4 si tu n'as pas ajouté les flags -source 1.4 et -target 1.4 au compilateur.

[PoP]

Ah bah ils doivent y être alors, ça tourne sous 1.4.2