QuickSort trop lent

cs_heavenboy
Messages postés
22
Date d'inscription
jeudi 21 mai 2009
Statut
Membre
Dernière intervention
1 décembre 2009
- 22 mai 2009 à 12:49
cs_heavenboy
Messages postés
22
Date d'inscription
jeudi 21 mai 2009
Statut
Membre
Dernière intervention
1 décembre 2009
- 28 mai 2009 à 19:02
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.

9 réponses

cs_heavenboy
Messages postés
22
Date d'inscription
jeudi 21 mai 2009
Statut
Membre
Dernière intervention
1 décembre 2009

22 mai 2009 à 16:21
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.
0
elvis36
Messages postés
34
Date d'inscription
mercredi 8 novembre 2006
Statut
Membre
Dernière intervention
8 juillet 2010

22 mai 2009 à 22:06
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...
0
cs_heavenboy
Messages postés
22
Date d'inscription
jeudi 21 mai 2009
Statut
Membre
Dernière intervention
1 décembre 2009

22 mai 2009 à 23:22
salut
oui pourquoi pas.
merci
0
elvis36
Messages postés
34
Date d'inscription
mercredi 8 novembre 2006
Statut
Membre
Dernière intervention
8 juillet 2010

23 mai 2009 à 09:45
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();
      }
}
 
   
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
cs_heavenboy
Messages postés
22
Date d'inscription
jeudi 21 mai 2009
Statut
Membre
Dernière intervention
1 décembre 2009

23 mai 2009 à 11:05
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.
0
elvis36
Messages postés
34
Date d'inscription
mercredi 8 novembre 2006
Statut
Membre
Dernière intervention
8 juillet 2010

23 mai 2009 à 15:37
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é...
0
cs_heavenboy
Messages postés
22
Date d'inscription
jeudi 21 mai 2009
Statut
Membre
Dernière intervention
1 décembre 2009

23 mai 2009 à 17:12
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.
0
elvis36
Messages postés
34
Date d'inscription
mercredi 8 novembre 2006
Statut
Membre
Dernière intervention
8 juillet 2010

23 mai 2009 à 21:45
Honnêtement je ne connait pas assez Ubuntu pour pouvoir t'aider... désolé...
0
cs_heavenboy
Messages postés
22
Date d'inscription
jeudi 21 mai 2009
Statut
Membre
Dernière intervention
1 décembre 2009

28 mai 2009 à 19:02
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.
0