QuickSort trop lent

Question

Bonjour,
je viens d'implémenter le Quicksort en java. Le problème est que lorsque je l'exécute sur mon pc sous windows vista pour trier 10000 valeurs il met 4 ms (normal!) alors que lorsque je l'exécute sur mon autre pc tournant sous ubuntu il met pour la même chose de 40 à 200 ms. 
Pourriez-vous m'expliquer comment une telle "lenteur" est possible ? 
J'ajoute que lors de l'exécution aucun autre programme ne tourne. 
Merci beaucoup.

cs_heavenboy · Answer

re
j'ajoute tout de même mon fichier source : 

public class JSort 
{
    public final static int QUICKSORT=0;
    public final static int FUSIONSORT=1;
    private int Ipivot;
    private long tempsAvant,tempsApres;
    private int tableauTrier [];
    public JSort(int typeSort,int t [])
    {
        switch(typeSort)
        {
            case 0 : tempsAvant = System.currentTimeMillis();
                     triRapide(t,t.length-1); 
                     tempsApres = System.currentTimeMillis();
                     tableauTrier=t.clone();
                     break; 
            case 1 :    [...]                      break; 

        }
    }
        
    public int [] getSortArray()
    {
        return tableauTrier;
    }
    
    public static void  displayArrayOfInt(int [] tableau)
    {
        for(int i=0;i<tableau.length;i++)
        {
            System.out.print(tableau[i]+ "  ");
        }
        System.out.println();
    }
    
    private void triRapide(int [] t,int nb)
    {
        triRapideRecursif(t,0,nb);
    }
    
    private void triRapideRecursif(int [] t,int d,int f)
    {
            if(d<f)
            {
                partitionner(t,d,f,Ipivot);
                triRapideRecursif(t,d,Ipivot-1);
                triRapideRecursif(t,Ipivot+1,f);
            }
    }
    
    private void partitionner(int [] t,int debut, int fin, int indicePivot)
    {
        int i,j,pivot;
        pivot=t[debut];
        i=debut;
        j=fin;
        while(i<=j)
        {
            if(t[i]<=pivot)
                i=i+1;
            else
                if(t[j]>pivot)
                    j=j-1;
                else
                {
                    int intermediaire=t[i];
                    t[i]=t[j];
                    t[j]=intermediaire;
                }
        }
        Ipivot=j;
        int intermediare=t[debut];
        t[debut]=t[j];
        t[j]=intermediare;
    }

    public long getTimeOfSort()
    {
        return tempsApres-tempsAvant;
    }
    
    public static int [] getRandomArray(int nombreElements,int borneSup)
    {
        int  [] tabl = new int [nombreElements];
        Random x= new Random();
        if(borneSup==0)
        {
            borneSup=1;
        }
        for(int i=0;i<nombreElements;i++)
        {
            tabl[i]= x.nextInt(borneSup);
        }
        return tabl;
    }

public static void main(String[] args) 
    {
       
       int t[] = JSort.getRandomArray(10000,10);
        JSort js = new JSort(JSort.QUICKSORT,t);
        System.out.println(js.getTimeOfSort());
       js.displayArrayOfInt(js.getSortArray());
    }

merci de me répondre.

elvis36 · Answer

Bizarre sur ma machine ton code s'effectue très rapidement... Si tu veux je peux te passer un code perso sur le un tri QuickSort pour que tu le testes...

cs_heavenboy · Answer

salut
oui pourquoi pas. 
merci

elvis36 · Answer

Voila mon code, dans le main tu peux modifier le nombre d'éléments du tableau (ici 20) et le nombre de tableau trié (ici 2000)... en espérant que ce prog te rende service...

import java.util.Random;
public class TestQuickSortStat{
  public static int NbEchanges=0;
  public static int NbComparaisons=0;
  public static int[] A;
    public static int partition(int m , int n){
      int i=m;
      int j=n;
      int x=A[j];
      while(i<j) {if(A[i]>x)
                    {A[j]=A[i];
                     j--;
                     A[i]=A[j];
                     NbEchanges++;
                    }
                   else i++;
                   NbComparaisons++;
                   A[j]=x;
                   NbEchanges++;
                 }
     affiche();
     return j;
    }
 
    public static void QuickSort(int m , int n)
      {if (m<n)
        {int p=partition(m,n);
         QuickSort(m , p-1);
         QuickSort(p+1 , n);
        }
      }

    public static Random generateur = new Random();
      public static void genere (){
        for (int i=0 ; i<A.length ; i++)
          {A[i]=generateur.nextInt(2000)-1000;}
      }

    public static void affiche(){
      for (int i=0 ; i<A.length ; i++)
        System.out.print(A[i] + " ");
      System.out.println();
    }
  
    public static void main (String[] args)
      {A=new int[20];
       for (int c=1 ; c<=2000 ; c++){
         genere();
         //affiche();
         QuickSort(0,A.length-1);
       }
       //affiche();
       System.out.println("Pour trier le tableau, il a fallu "+NbEchanges/2000+" échanges et "+NbComparaisons/2000+" Comparaisons.");
       affiche();
      }
}

cs_heavenboy · Answer

Bonjour
je viens d'essayer ton programme avec 10 000 valeurs dans un tableau à trier. Les résultats sont les mêmes que pour mon programme. Le tableau est bien trié mais dans des temps trop lent pour un QuickSort lorsque je l'exécute sur Ubuntu. Par contre sur Vista le temps est bien de 4ms (là pas de problème). 
J'ajoute que j'ai aussi essayé mon programme et le tien sur un autre PC tournant sur Ubuntu et que le QuickSort s'effectue en 4 ms (normal). 
Le problème n'a donc lieu que sur mon pc. 
J'ajoute qu'il est neuf (3 mois), que j'ai installé jdk 6 update 13 et le jre 6 update 13. 
Ce problème pourrait venir d'où ? Configuration java mauvaise ? ... ?
merci beaucoup.

elvis36 · Answer

Il y a de fortes chances que le problème vienne de la config... J'ai moi même Ubuntu sur mon PC mais je n'ai jamais fait tourner Java dessus...
Actuellement je tourne sous Vista mais j'ai le souvenir que sous XP il fallait rajouter une variable d’environnement

propriétés du système->avancé->variable d’environnement

La valeur de la variable est le dossier bin du jdk... Peut-être cherché de ce coté la a cette adresse : http://www.ubuntu-fr.org/

Lorsque j'ai des problème avec Ubuntu ce site est parfois d'une grande utilité...

cs_heavenboy · Answer

salut
oui, j'utilise beaucoup le site d'ubuntu aussi et justement je n'ai rien trouvé à propos de mon problème. Voici ma configuration java que j'obtiens grâce à la ligne de commande : sudo update-alternatives --config java
Voici le résultat (en gras la conf utilisée) : 

1         /usr/lib/jvm/java-6-sun/jre/bin/java
2         /usr/bin/gif-4.2
3         /usr/bin/gif-4.3
4         /usr/lib/jvm/java-gcj/jre/bin/java
5         /usr/lib/jvm/java-6-openjdk/jre/bin/java
6         /usr/lib/jvm/java-1.5.0-sun/jre/bin/java

J'ai essayé aussi avec le numéro 1, le résultat est le même. 
Je ne comprend vraiment pas d'où viens mon problème. 
merci.

elvis36 · Answer

Honnêtement je ne connait pas assez Ubuntu pour pouvoir t'aider... désolé...

cs_heavenboy · Answer

Salut
donc je me suis renseignais sur mon processeur, et il est performant. Je doute qu'il soit la cause de mon problème. De plus lorsque je lance mon programme implémenté en pascal, il trie dans des temps records. 
En outre, le problème semble bien venir de java. Ce que je ne comprends pas.
Si quelqu'un a une idée, elle est la bienvenue.
Je sais que la différence de temps semble dérisoir mais la compléxité de cette algorithme fait que cette différence augmentera de plus en plus en fonction du nombre de valeurs à trier. De plus, je fais tourner des programmes plus lourds que ça et j'aimerai qu'il soit à leur rapidité optimale.
Merci.

QuickSort trop lent

9 réponses

Votre réponse

Discussions similaires