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

Collection et Stream Java Discussion :

Quick Sort ne fonctionne pas


Sujet :

Collection et Stream Java

  1. #21
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Points : 29 131
    Points
    29 131
    Billets dans le blog
    2
    Par défaut
    Quand tu fais tes mesures avec JUnit, tu mesures le temps d'exécution de la version par List y compris la conversion du tableau en List ? Cela joue : cette partie doit être conséquente pour la conversion d'un tableau de 1000000 de valeurs :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    private List<Integer> tabToList(final int[] tab) {
    		final List<Integer> liste = new ArrayList<>();
     
    		for (final int elt : tab) {
    			liste.add(elt);
    		}
     
    		return liste;
    	}
    Si c'est le cas, essayes juste de faire, pour voir : ça devrait déjà économiser en allocation et copie de tableaux :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    private List<Integer> tabToList(final int[] tab) {
    		final List<Integer> liste = new ArrayList<>(tab.length);
     
    		for (final int elt : tab) {
    			liste.add(elt);
    		}
     
    		return liste;
    	}
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  2. #22
    Rédacteur
    Avatar de thierryler
    Homme Profil pro
    Inscrit en
    Octobre 2007
    Messages
    4 078
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 078
    Points : 12 815
    Points
    12 815
    Par défaut
    Heu, tu peux redonner carrément le code de chaque méthode en les nommant (genre 1, 2, 3) pour qu'il n'y ait pas d’ambiguïté ? Si tu peux inclure les deux que j'ai données aussi...
    Thierry Leriche-Dessirier
    Consultant Java JEE Web Agile freelance
    Rédacteur pour Developpez
    Professeur de Génie Logiciel à l'ESIEA

    Site : http://www.icauda.com / Linked'in : http://www.linkedin.com/in/thierryler / Twitter : @ThierryLeriche

  3. #23
    Rédacteur
    Avatar de thierryler
    Homme Profil pro
    Inscrit en
    Octobre 2007
    Messages
    4 078
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 078
    Points : 12 815
    Points
    12 815
    Par défaut
    Pour l'instant, ça me donne ça :

    RapideTri : 1027 ms

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
     
    	public void trier(final int[] tab) {
     
    		trier(tab, 0, tab.length - 1);
     
    	}
     
    	private void trier(final int[] tab, final int gauche, final int droite) {
     
    		if (droite <= gauche) {
    			return;
    		}
     
    		// Je commence avec un pivot à gauche
    		int positionPivot = gauche;
     
    		// positionPivot = trier(tab, gauche, droite, positionPivot);
    		permuter(positionPivot, droite, tab);
     
    		// int j = gauche;
    		for (int i = gauche; i < droite; i++) {
    			if (tab[i] <= tab[droite]) {
    				permuter(i, positionPivot++, tab);
    				// positionPivot++;
    			}
    		}
    		permuter(droite, positionPivot, tab);
    		// positionPivot = j;
     
    		// tri recursif des sous-listes
    		// Bien entendu on ne tri pas le pivot
    		trier(tab, gauche, positionPivot - 1);
    		trier(tab, positionPivot + 1, droite);
    	}
    RapideViaListeTri : 8654 ms

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
     
    	public void trier(final int[] tab) {
     
    		final List<Integer> liste = tabToList(tab);
     
    		final List<Integer> result = trier(liste);
     
    		ecraser(result, tab);
     
    	}
     
    	private List<Integer> trier(final List<Integer> liste) {
     
    		if (liste == null || liste.isEmpty()) {
    			return new ArrayList<>();
    		}
     
    		// Choix du pivot a gauche
    		final int pivot = liste.get(0);
    		// pour ne pas traiter le pivot dans la boucle
    		liste.remove(0);
     
    		final List<Integer> listeGauche = new ArrayList<>();
    		final List<Integer> listeDroite = new ArrayList<>();
     
    		// Separation en deux sous listes
    		for (final int elt : liste) {
    			if (elt < pivot) {
    				listeGauche.add(elt);
    			} else {
    				listeDroite.add(elt);
    			}
    		}
     
    		final List<Integer> result = new ArrayList<>();
     
    		result.addAll(trier(listeGauche));
    		result.add(pivot);
    		result.addAll(trier(listeDroite));
     
    		return result;
    	}
     
    	private List<Integer> tabToList(final int[] tab) {
    		final List<Integer> liste = new ArrayList<>(tab.length);
     
    		for (final int elt : tab) {
    			liste.add(elt);
    		}
     
    		return liste;
    	}
     
    	private void ecraser(final List<Integer> from, final int[] to) {
    		int i = 0;
    		for (final int elt : from) {
    			to[i++] = elt;
    		}
    	}
    RapideViaListe2Tri : 809 ms

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
     
    	public void trier(final int[] tab) {
     
    		final List<Integer> liste = tabToList(tab);
     
    		final List<Integer> result = trier(liste);
     
    		ecraser(result, tab);
     
    	}
     
    	private List<Integer> trier(final List<Integer> liste) {
     
    		if (liste == null || liste.isEmpty()) {
    			return new ArrayList<>();
    		}
     
    		// Choix du pivot a gauche
    		final Integer pivot = liste.get(0);
     
    		final List<Integer> listeGauche = new ArrayList<>();
    		final List<Integer> listeCentre = new ArrayList<>();
    		final List<Integer> listeDroite = new ArrayList<>();
     
    		// Separation en deux sous listes
    		for (final Integer elt : liste) {
    			final int comp = elt.compareTo(pivot);
    			if (comp < 0) {
    				listeGauche.add(elt);
    			} else if (comp == 0) {
    				listeCentre.add(elt);
    			} else {
    				listeDroite.add(elt);
    			}
    		}
     
    		liste.clear();
     
    		liste.addAll(trier(listeGauche));
    		liste.addAll(listeCentre);
    		liste.addAll(trier(listeDroite));
     
    		return liste;
    	}
    Ce qui m'ennuie, c'est que RapideViaListe2Tri soit plus rapide que RapideTri sur mon ordi avec la liste de 1 000 000 éléments.

    Peut être que le fait que l'algo de RapideTri change l'ordre joue beaucoup...
    Thierry Leriche-Dessirier
    Consultant Java JEE Web Agile freelance
    Rédacteur pour Developpez
    Professeur de Génie Logiciel à l'ESIEA

    Site : http://www.icauda.com / Linked'in : http://www.linkedin.com/in/thierryler / Twitter : @ThierryLeriche

  4. #24
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Points : 29 131
    Points
    29 131
    Billets dans le blog
    2
    Par défaut
    Je redonnes le tout :

    La version adaptée, que tu as donnée, à partir de listes, donnant une version identifiée L1.R (Tri de liste méthode 1, avec test de liste Random), et une L1.F (Tri de liste méthode 1, avec test de liste lue dans un fichier rand_1000000.txt) si on change le commentaire.

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    public class TestQuickSortDeListe1 {
     
    	public static void main(String[] args) {
     
    		//List<Integer> list = createList(1000000); // Appelons celle la L1.R (R comme random)
    		List<Integer> list = readList(); // Appelons celle la L1.F (F comme fichier)
     
    		long time = System.currentTimeMillis();
    		try {
    			new TestQuickSortDeListe1().trier(list);
    		}
    		finally {
    			System.out.println(System.currentTimeMillis()-time+" ms");
    		}
     
    	}
     
    	private static List<Integer> createList(int nb) {
    		List<Integer> list = new ArrayList<>();
     
    		Random random = new Random(424242);
     
    		for(int i=0;i<1000000; i++) {
    			list.add(random.nextInt());
    		}
     
    		return list;
    	}
     
    	private static List<Integer> readList() {
    		return ReadListe.readList();
    	} 
     
    	private List<Integer> trier(final List<Integer> liste) {
     
    		if (liste == null || liste.isEmpty()) {
    			return new ArrayList<>();
    		}
     
    		// Choix du pivot a gauche
    		final Integer pivot = liste.get(0);
     
    		final List<Integer> listeGauche = new ArrayList<>();
    		final List<Integer> listeCentre = new ArrayList<>();
    		final List<Integer> listeDroite = new ArrayList<>();
     
    		// Separation en deux sous listes
    		for (final Integer elt : liste) {
    			final int comp = elt.compareTo(pivot);
    			if (comp < 0) {
    				listeGauche.add(elt);
    			} else if (comp == 0) {
    				listeCentre.add(elt);
    			} else {
    				listeDroite.add(elt);
    			}
    		}
     
    		liste.clear();
     
    		liste.addAll(trier(listeGauche));
    		liste.addAll(listeCentre);
    		liste.addAll(trier(listeDroite));
     
    		return liste;
    	}
     
    }
    La même en liste, donnant T1.R et T1.F

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    public class TestQuickSortDeTableay1 {
     
    	public static void main(String[] args) {
    		//Integer[] array = createArray(1000000); // T1.R
    		Integer[] array = readArray(); // T1.F
     
    		//System.out.println(Arrays.toString(array));
    		long time = System.currentTimeMillis();
    		try {
    			array = new TestQuickSortDeTableay1().trier(array);
    			//System.out.println(Arrays.toString(array));
    		}
    		finally {
    			System.out.println(System.currentTimeMillis()-time+" ms");
    		}
     
    	}
     
    	private static Integer[] createArray(int nb) {
    		Integer[] array = new Integer[nb];
     
    		Random random = new Random(424242);
     
    		for(int i=0;i<array.length; i++) {
    			array[i]=random.nextInt();
    		}
    		return array;
    	}
     
    	private static Integer[] readArray() {
    		return ReadListe.readArray(); 
    	}
     
    	public Integer[] trier(Integer[] array) {
    		if (array == null || array.length==0) {
    			return new Integer[0];
    		}
    		return trier(array, new Integer[array.length], 0, array.length);
    	}
     
    	private Integer[] trier(final Integer[] array, final Integer[] array2, final int debut, final int fin) {
     
    			// Choix du pivot a gauche
    			final int pivot = array[debut]; 
    			int posGauche = debut;
    			int posDroite = fin;
     
    			// Separation en deux sous listes
    			for (int index = debut+1; index < fin; index++) {
    				Integer elt = array[index];
    				final int comp = elt.compareTo(pivot);
    				if (comp < 0) {
    					array2[posGauche++]=elt;
    				} else if (comp> 0) {
    					array2[--posDroite]=elt;
    				}
    			} 
     
    			Arrays.fill(array2, posGauche, posDroite, pivot);  
     
    		 	if ( posGauche>debut ) {
    				trier(array2, array, debut, posGauche );
    				System.arraycopy(array, debut, array2, debut, posGauche-debut);
    			} 
    			if ( posDroite<fin ) {
    				trier(array2, array, posDroite, fin);
    				System.arraycopy(array, posDroite, array2, posDroite, fin-posDroite);
    			}
     
    			return array2;
    		}
     
    }
    L2.R & L2.F :

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    public class TestQuickSortDeListe2 {
     
    	public static void main(String[] args) {
     
    		List<Integer> list = createList(1000000);
    		//List<Integer> list = readList(); 
     
    		//System.out.println(list);
    		//System.out.println(Arrays.toString(array));
    		long time = System.currentTimeMillis();
    		try {
    			list = new TestQuickSortDeListe2().trier(list);
    			//System.out.println(Arrays.toString(array));
    		}
    		finally {
    			System.out.println(System.currentTimeMillis()-time+" ms");
    		}
    		//System.out.println(list);
     
    	}
    	private static List<Integer> createList(int nb) {
    		List<Integer> list = new ArrayList<>();
     
    		Random random = new Random(424242);
     
    		for(int i=0;i<1000000; i++) {
    			list.add(random.nextInt());
    		}
     
    		return list;
    	}
     
    	private static List<Integer> readList() {
    		return ReadListe.readList();
    	} 
    	public List<Integer> trier(List<Integer> list) {
    		if (list == null || list.isEmpty() ) {
    			return Collections.emptyList();
    		}
    		trier(list, 0, list.size()-1);
    		return list;
    	}
     
    	private int trier(List<Integer> list, int debut, int fin, int pivot) {
    		echanger(list, pivot, fin);
    		int j = debut;
    		for( int i=debut; i<fin; i++) {
    			if ( list.get(i).compareTo(list.get(fin))<=0 ) {
    		            echanger(list, i, j);
    		            j ++;
    			}
    		}
    		echanger( list, fin, j);
    		return j;
    	} 
     
    	protected int choixPivot(List<Integer> list, int debut, int fin) {
    		return debut;
    	}
     
    	private void echanger(List<Integer> list, int i1, int i2) {
    		Integer temp = list.get(i1);
    		list.set(i1, list.get(i2));
    		list.set(i2, temp);
    	}
     
    	private void trier(List<Integer> list, int debut, int fin) {
    		if ( debut<fin ) {
    			int pivot = choixPivot(list, debut, fin);
    			pivot = trier(list, debut, fin, pivot);
    			trier(list, debut, pivot-1);
    			trier(list, pivot+1, fin);
    		}
    	}
     
    }
    T2.R et T2.F :

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    public class TestQuickSortDeTableau2 {
     
    	public static void main(String[] args) {
     
    		//Integer[] array = createArray(1000000);
    		Integer[] array = readArray();
     
     
    		long time = System.currentTimeMillis();
    		try {
    			array = new TestQuickSortDeTableau2().trier(array); 
    		}
    		finally {
    			System.out.println(System.currentTimeMillis()-time+" ms");
    		}
     
    	}
     
    	private static Integer[] createArray(int nb) {
    		Integer[] array = new Integer[nb];
     
    		Random random = new Random(424242);
     
    		for(int i=0;i<array.length; i++) {
    			array[i]=random.nextInt();
    		}
    		return array;
    	}
     
    	private static Integer[] readArray() {
    		return ReadListe.readArray(); 
    	}
     
    	public Integer[] trier(Integer[] array) {
    		if (array == null || array.length==0) {
    			return new Integer[0];
    		}
    		trier(array, 0, array.length-1);
    		return array;
    	}
     
    	private int trier(Integer[] array, int debut, int fin, int pivot) {
    		echanger(array, pivot, fin);
    		int j = debut;
    		for( int i=debut; i<fin; i++) {
    			if ( array[i].compareTo(array[fin])<=0 ) {
    		            echanger(array, i, j);
    		            j ++;
    			}
    		}
    		echanger( array, fin, j);
    		return j;
    	} 
     
    	protected int choixPivot(Integer[] array, int debut, int fin) {
    		return debut;
    	}
     
    	private void echanger(Integer[] array, int i1, int i2) {
    		Integer temp = array[i1];
    		array[i1] = array[i2];
    		array[i2] = temp;
    	}
     
    	private void trier(Integer[] array, int debut, int fin) {
    		if ( debut<fin ) {
    			int pivot = choixPivot(array, debut, fin);
    			pivot = trier(array, debut, fin, pivot);
    			trier(array, debut, pivot-1);
    			trier(array, pivot+1, fin);
    		}
    	}
     
    }
    Et j'ajoutes la dernière version que tu as mises :


    Mais pour celle-ci, il me manque ton code d'implémentation de la méthode permuter().

    - RapideTri : RT.R et RT.F

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    public class RapideTri {
     
    public static void main(String[] args) {
     
    		//Integer[] array = createArray(1000000); // RT.R
    		int[] array = readArray(); // RT.F
     
     
    		long time = System.currentTimeMillis();
    		try {
    			 new RapideTri().trier(array); 
    		}
    		finally {
    			System.out.println(System.currentTimeMillis()-time+" ms");
    		}
     
    	}
     
    	private static Integer[] createArray(int nb) {
    		Integer[] array = new Integer[nb];
     
    		Random random = new Random(424242);
     
    		for(int i=0;i<array.length; i++) {
    			array[i]=random.nextInt();
    		}
    		return array;
    	}
     
    	private static int[] readArray() {
    		return ReadListe.readIntArray(); 
    	}
     
    	public void trier(final int[] tab) {
     
    		trier(tab, 0, tab.length - 1);
     
    	}
     
    	private void trier(final int[] tab, final int gauche, final int droite) {
     
    		if (droite <= gauche) {
    			return;
    		}
     
    		// Je commence avec un pivot à gauche
    		int positionPivot = gauche;
     
    		// positionPivot = trier(tab, gauche, droite, positionPivot);
    		permuter(positionPivot, droite, tab);
     
    		// int j = gauche;
    		for (int i = gauche; i < droite; i++) {
    			if (tab[i] <= tab[droite]) {
    				permuter(i, positionPivot++, tab);
    				// positionPivot++;
    			}
    		}
    		permuter(droite, positionPivot, tab);
    		// positionPivot = j;
     
    		// tri recursif des sous-listes
    		// Bien entendu on ne tri pas le pivot
    		trier(tab, gauche, positionPivot - 1);
    		trier(tab, positionPivot + 1, droite);
    	}
     
    	private void permuter(int positionPivot, int droite, int[] tab) {
    		// IL ME MANQUE CA !!!
     
    	}
     
    }
    - RapideViaListeTri ! : RTL.R et RTL.F


    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
     
    public class RapideViaListeTri {
     
    public static void main(String[] args) {
     
    		//List<Integer> list = createList(1000000); // RTL.R
    		List<Integer> list = readList(); // RTL.F
     
     
    		long time = System.currentTimeMillis();
    		try {
    			 new RapideViaListeTri().trier(list); 
    		}
    		finally {
    			System.out.println(System.currentTimeMillis()-time+" ms");
    		}
     
    	}
     
    	private static List<Integer> createList(int nb) {
    		List<Integer> list = new ArrayList<>();
     
    		Random random = new Random(424242);
     
    		for(int i=0;i<1000000; i++) {
    			list.add(random.nextInt());
    		}
     
    		return list;
    	}
     
    	private static List<Integer> readList() {
    		return ReadListe.readList();
    	} 
     
    	public void trier(final int[] tab) {
     
    		final List<Integer> liste = tabToList(tab);
     
    		final List<Integer> result = trier(liste);
     
    		ecraser(result, tab);
     
    	}
     
    	private List<Integer> trier(final List<Integer> liste) {
     
    		if (liste == null || liste.isEmpty()) {
    			return new ArrayList<>();
    		}
     
    		// Choix du pivot a gauche
    		final int pivot = liste.get(0);
    		// pour ne pas traiter le pivot dans la boucle
    		liste.remove(0);
     
    		final List<Integer> listeGauche = new ArrayList<>();
    		final List<Integer> listeDroite = new ArrayList<>();
     
    		// Separation en deux sous listes
    		for (final int elt : liste) {
    			if (elt < pivot) {
    				listeGauche.add(elt);
    			} else {
    				listeDroite.add(elt);
    			}
    		}
     
    		final List<Integer> result = new ArrayList<>();
     
    		result.addAll(trier(listeGauche));
    		result.add(pivot);
    		result.addAll(trier(listeDroite));
     
    		return result;
    	}
     
    	private List<Integer> tabToList(final int[] tab) {
    		final List<Integer> liste = new ArrayList<>(tab.length);
     
    		for (final int elt : tab) {
    			liste.add(elt);
    		}
     
    		return liste;
    	}
     
    	private void ecraser(final List<Integer> from, final int[] to) {
    		int i = 0;
    		for (final int elt : from) {
    			to[i++] = elt;
    		}
    	}
     
    }
    - RapideViaListe2Tri : RTL2.R et RTL2.F


    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    public class RapideViaListe2Tri {
     
    	public static void main(String[] args) {
     
    		// List<Integer> list = createList(1000000); // RTL2.R
    		List<Integer> list = readList(); // RTL2.F
     
    		long time = System.currentTimeMillis();
    		try {
    			new RapideViaListe2Tri().trier(list);
    		} finally {
    			System.out.println(System.currentTimeMillis() - time + " ms");
    		}
     
    	}
     
    	private static List<Integer> createList(int nb) {
    		List<Integer> list = new ArrayList<>();
     
    		Random random = new Random(424242);
     
    		for (int i = 0; i < 1000000; i++) {
    			list.add(random.nextInt());
    		}
     
    		return list;
    	}
     
    	private static List<Integer> readList() {
    		return ReadListe.readList();
    	}
     
    	public void trier(final int[] tab) {
     
    		final List<Integer> liste = tabToList(tab);
     
    		final List<Integer> result = trier(liste);
     
    		ecraser(result, tab);
     
    	}
     
    	private void ecraser(final List<Integer> from, final int[] to) {
    		int i = 0;
    		for (final int elt : from) {
    			to[i++] = elt;
    		}
    	}
     
    	private List<Integer> tabToList(final int[] tab) {
    		final List<Integer> liste = new ArrayList<>(tab.length);
     
    		for (final int elt : tab) {
    			liste.add(elt);
    		}
     
    		return liste;
    	}
     
    	private List<Integer> trier(final List<Integer> liste) {
     
    		if (liste == null || liste.isEmpty()) {
    			return new ArrayList<>();
    		}
     
    		// Choix du pivot a gauche
    		final Integer pivot = liste.get(0);
     
    		final List<Integer> listeGauche = new ArrayList<>();
    		final List<Integer> listeCentre = new ArrayList<>();
    		final List<Integer> listeDroite = new ArrayList<>();
     
    		// Separation en deux sous listes
    		for (final Integer elt : liste) {
    			final int comp = elt.compareTo(pivot);
    			if (comp < 0) {
    				listeGauche.add(elt);
    			} else if (comp == 0) {
    				listeCentre.add(elt);
    			} else {
    				listeDroite.add(elt);
    			}
    		}
     
    		liste.clear();
     
    		liste.addAll(trier(listeGauche));
    		liste.addAll(listeCentre);
    		liste.addAll(trier(listeDroite));
     
    		return liste;
    	}
    }
    Et, enfin, pour être complet, la classe de lecture du fichier :

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    public class ReadListe {
     
    	public static  List<Integer> readList() {
     
    		List<Integer> list = new ArrayList<>();
    		try (BufferedReader reader = new BufferedReader(new FileReader("values.txt"))) {
     
    			String line;
    			while( (line=reader.readLine())!=null ) {
    				list.add(Integer.valueOf(line));
    			}
     
    		}
    		catch (Throwable t) {
    			t.printStackTrace();
    		}
     
    		return list;
    	}
     
    	public static Integer[] readArray() {
     
    		List<Integer> list = readList();
     
    		return list.toArray(new Integer[list.size()]);
    	}
     
    	public static int[] readIntArray() {
    		List<Integer> list = readList();
     
    		int[] array = new int[list.size()];
    		int index=0;
    		for(Integer elm : list ) {
    			array[index++]=elm;
    		}
    		return array;
    	}
     
    }
    Je lance en attendant d'avoir la méthode permuter() les mesures sur les 2 dernières
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  5. #25
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Points : 29 131
    Points
    29 131
    Billets dans le blog
    2
    Par défaut
    Voici le tableau récap de mes résultats :

    result.html
    Nom : Result.PNG
Affichages : 87
Taille : 6,9 Ko

    A mon avis, toutes les implémentations sont fortement influencées par l'ordre initial : sinon on aurait pas ces inversions (plus rapide dans un cas, plus lent dans l'autre) et ces écarts.
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  6. #26
    Rédacteur
    Avatar de thierryler
    Homme Profil pro
    Inscrit en
    Octobre 2007
    Messages
    4 078
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 078
    Points : 12 815
    Points
    12 815
    Par défaut
    Ma fonction permuter est très simple :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    	public static void permuter(final int indexA, final int indexB, final int[] tab) {
    		final int temp = tab[indexA];
    		tab[indexA] = tab[indexB];
    		tab[indexB] = temp;
    	}
    Effectivement, le Quick Sort est hyper influencé par l'ordre initial dans la liste. Si on prend RapideViaListe2Tri (RTL2.R et RTL2.F), qui ne change pas l'ordre dans les sous-listes, on peut dire que le Quick sort sera en O(n ln n) sur une liste mélangée et en O(n²) sur une liste triée lorsqu'on choisi le pivot à gauche.

    Je suis surpris que ce soit T1 qui donne les meilleurs résultats chez toi, dans la mesure où ça manipule des objets et non des primitifs.

    Qui plus est, il faudrait tester avec des listes de 10 ou 100 millions d'éléments...

    J'ai remarqué que ça avait un impact positif mesurable de mettre les paramètres en "final".

    Au fait, je suis en Java 7 depuis Eclipse.

    Et pour info, ma méthode de lecture du fichier (que je n'inclus pas dans le chrono) :

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
     
    public static int[] readFromFile(final String fileName) {
    		logger.debug("readFromFile");
    		logger.debug("fileName: {}", fileName);
     
    		final File file = new File(fileName);
     
    		if (!file.exists()) {
    			logger.error("Le fichier n'existe pas");
    		}
     
    		final List<Integer> list = new LinkedList<>();
     
    		try (final FileReader fr = new FileReader(file);//
    				final BufferedReader br = new BufferedReader(fr);) {
     
    			for (String line = br.readLine(); line != null; line = br.readLine()) {
    				if (line.isEmpty()) {
    					continue;
    				}
     
    				if (line.startsWith("#")) {
    					continue;
    				}
     
    				list.add(Integer.valueOf(line));
    			}
     
    		} catch (Exception e) {
    			logger.error(e.getMessage(), e);
    		}
     
    		final int[] tab = new int[list.size()];
    		int i = 0;
    		for (final int elt : list) {
    			tab[i++] = elt;
    		}
     
    		return tab;
     
    	}
    Thierry Leriche-Dessirier
    Consultant Java JEE Web Agile freelance
    Rédacteur pour Developpez
    Professeur de Génie Logiciel à l'ESIEA

    Site : http://www.icauda.com / Linked'in : http://www.linkedin.com/in/thierryler / Twitter : @ThierryLeriche

  7. #27
    Rédacteur
    Avatar de thierryler
    Homme Profil pro
    Inscrit en
    Octobre 2007
    Messages
    4 078
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 078
    Points : 12 815
    Points
    12 815
    Par défaut
    J'ai essayé de reprendre le code du "sort" de Java 6 en ne prenant que la partie Quick sort mais je n'arrive pas à l'adapter :-(

    Pour info, Arrays.sort() de Java 6 utilise un tri par insertion pour moins de 7 éléments, un quick sort avec médiane de 3 de 7 à 40 éléments, et avec une médiane de 9 au dessus de 40. Mais dans l'algo, il suffit de zapper le choix du pivot en prenant à gauche pour zapper les médianes. Java 7 utilise un quick sort avec double pivot au dessus de 7 éléments.
    Thierry Leriche-Dessirier
    Consultant Java JEE Web Agile freelance
    Rédacteur pour Developpez
    Professeur de Génie Logiciel à l'ESIEA

    Site : http://www.icauda.com / Linked'in : http://www.linkedin.com/in/thierryler / Twitter : @ThierryLeriche

  8. #28
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Points : 29 131
    Points
    29 131
    Billets dans le blog
    2
    Par défaut
    Je suis personnellement très étonné entre les différences de mon temp pour T2 et ton temps pour RT : les différences me semblent minimes. Je n'ai pas ma machine de test sous la main : je teste dès que possible (je me doutais bien de l'implémentation de permuter, mais je voulais être sûr pour tester le même code). Je ne comprends toujours pas les rapports très importants entre les temps sur L2 et RTL2, mais pas du même ordre (1 à 10 pour L2, 1 à 3 pour RTL2), de même pour L1 et RTL, qui sont même inversés.

    Tu effectues tes tests avec Java 6 ? Tous mes tests sont faits sous Java 8 : il est possible que cela ait une influence non négligeable.
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  9. #29
    Rédacteur
    Avatar de thierryler
    Homme Profil pro
    Inscrit en
    Octobre 2007
    Messages
    4 078
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 078
    Points : 12 815
    Points
    12 815
    Par défaut
    Moi avec Java 7.

    Après d'une machine à l'autres... Mais sur une même machine, avec le même jeu de données, et en moyenne, ça devrait être différent.
    Thierry Leriche-Dessirier
    Consultant Java JEE Web Agile freelance
    Rédacteur pour Developpez
    Professeur de Génie Logiciel à l'ESIEA

    Site : http://www.icauda.com / Linked'in : http://www.linkedin.com/in/thierryler / Twitter : @ThierryLeriche

  10. #30
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Points : 29 131
    Points
    29 131
    Billets dans le blog
    2
    Par défaut
    Mise à jour des résultats avec les chronos de RT (en plus il y avait une erreur sur la ligne RTL2 : inversion des 2 colonnes, du coup c'est plus cohérent)

    result.html
    Nom : Result.PNG
Affichages : 100
Taille : 7,3 Ko
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  11. #31
    Rédacteur
    Avatar de thierryler
    Homme Profil pro
    Inscrit en
    Octobre 2007
    Messages
    4 078
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 078
    Points : 12 815
    Points
    12 815
    Par défaut
    Comment c'est possible que RTL2 soit plus rapide que L1 alors qu'il fait le même algo avec les étapes de passage en tableau en plus ?
    Thierry Leriche-Dessirier
    Consultant Java JEE Web Agile freelance
    Rédacteur pour Developpez
    Professeur de Génie Logiciel à l'ESIEA

    Site : http://www.icauda.com / Linked'in : http://www.linkedin.com/in/thierryler / Twitter : @ThierryLeriche

  12. #32
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Points : 29 131
    Points
    29 131
    Billets dans le blog
    2
    Par défaut
    Je suppose que T1 donne des meilleurs résultats parce qu'il n'y a pas d'allocation de tableaux que L1 alors que l'ajout des éléments dans l'ArrayList provoque nécessairement plus d'allocations au fur et à mesure que le tableau interne grandit.

    Par ailleurs, j'ai fait le test intéressant suivant :

    1) dans T1 j'ai modifié la ligne suivante :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    final int pivot = array[debut];
    en

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    final Integer pivot = array[debut];
    et j'obtiens les temps suivants :
    • Random list : 260 ms
    • Fichier : 140 ms


    Un gain de 50 % en enlevant l'autoboxing : il devient de moins en moins négligeable au fur et à mesure que la liste grandit.
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  13. #33
    Rédacteur
    Avatar de thierryler
    Homme Profil pro
    Inscrit en
    Octobre 2007
    Messages
    4 078
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 078
    Points : 12 815
    Points
    12 815
    Par défaut
    Oui l'autoboxing a un coût énorme, surtout dans la zone de cache des 128.

    D'ailleurs c'est pour ça que je travaille avec des int[] et non pas avec des Integer[].

    Instinctivement j'avais l'impression que bosser avec des int[], et donc ne jamais faire de boxing, serait plus rapide. Mais peut être que le déplacement (permutation) d'une référence de Integer coûte finalement moins cher qu'une permutation de int. Cela dit, dans le code de Arrays.sort(), le JDK travaille sur des int.

    Je pense qu'on peut appeler T3 ta nouvelle version sans l'autoboxing
    Thierry Leriche-Dessirier
    Consultant Java JEE Web Agile freelance
    Rédacteur pour Developpez
    Professeur de Génie Logiciel à l'ESIEA

    Site : http://www.icauda.com / Linked'in : http://www.linkedin.com/in/thierryler / Twitter : @ThierryLeriche

  14. #34
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Points : 29 131
    Points
    29 131
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par thierryler Voir le message
    Comment c'est possible que RTL2 soit plus rapide que L1 alors qu'il fait le même algo avec les étapes de passage en tableau en plus ?
    Non, à mon sens les temps sont sensiblement les mêmes : les différences sont dues aux autres activités concurrentes sur ma machine je suppose, d'autant plus que je n'avais pas fait les mesures au même moment dans l'après-midi. Je les ais relancées ce matin et j'obtiens des temps similaires en moyennne (dans les 800 ms pour la random list, 340ms pour le fichier).

    De quel passage de tableau parles-tu ?
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  15. #35
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Points : 29 131
    Points
    29 131
    Billets dans le blog
    2
    Par défaut Dernière mise à jour tableau
    J'ai ajouté T3 dans le tableau récap, et j'ai fait un T4, le même que T3 tout en int[]. J'ai fait quelques essais différents au niveau de la comparaison (par calcul de la différence, par !=...) et j'obtiens des temps sensiblement identiques, donc j'ai conservé cette forme :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    if (elt < pivot) {
        array2[posGauche++]=elt;
    } else if (elt > pivot) {
       array2[--posDroite]=elt;
    }
    result.html
    Nom : Result.PNG
Affichages : 87
Taille : 8,9 Ko
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  16. #36
    Rédacteur
    Avatar de thierryler
    Homme Profil pro
    Inscrit en
    Octobre 2007
    Messages
    4 078
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 078
    Points : 12 815
    Points
    12 815
    Par défaut
    Le T4 est carrément plus rapide là. Tu peux redonner le code complet ?
    Thierry Leriche-Dessirier
    Consultant Java JEE Web Agile freelance
    Rédacteur pour Developpez
    Professeur de Génie Logiciel à l'ESIEA

    Site : http://www.icauda.com / Linked'in : http://www.linkedin.com/in/thierryler / Twitter : @ThierryLeriche

  17. #37
    Rédacteur
    Avatar de thierryler
    Homme Profil pro
    Inscrit en
    Octobre 2007
    Messages
    4 078
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 078
    Points : 12 815
    Points
    12 815
    Par défaut
    Ca y est, j'ai enfin réussi à copier la version du JDK. J'ai un peu honte de ne pas y être arrivé plus tôt.

    Disons que c'est la version T5. Sur mon ordi elle explose les autres algo.

    Voici ce que ça donne :

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
     
    	public void trier(final int[] tab) {
    		if (tab.length == 0) {
    			return;
    		}
    		trier(tab, 0, tab.length);
    	}
     
    	private static void trier(final int tab[], final int gauche, final int taille) {
     
    		final int pivot = tab[gauche];
     
    		// Establish Invariant: v* (<v)* (>v)* v*
    		int g = gauche;
    		int g2 = g;
    		int d = gauche + taille - 1;
    		int d2 = d;
    		while (true) {
    			while (g2 <= d && tab[g2] <= pivot) {
    				if (tab[g2] == pivot) {
    					permuter(g++, g2, tab);
    				}
    				g2++;
    			}
    			while (d >= g2 && pivot <= tab[d]) {
    				if (tab[d] == pivot) {
    					permuter(d, d2--, tab);
    				}
    				d--;
    			}
    			if (g2 > d) {
    				break;
    			}
    			permuter(g2++, d--, tab);
    		}
     
    		// Swap partition elements back to middle
    		int s, n = gauche + taille;
    		s = Math.min(g - gauche, g2 - g);
    		decaler(tab, gauche, g2 - s, s);
    		s = Math.min(d2 - d, n - d2 - 1);
    		decaler(tab, g2, n - s, s);
     
    		// Recursively sort non-partition-elements
    		if (1 < (s = g2 - g)) {
    			trier(tab, gauche, s);
    		}
    		if (1 < (s = d2 - d)) {
    			trier(tab, n - s, s);
    		}
    	}
    Avec :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    	public static void decaler(final int tab[], int a, int b, int n) {
    		for (int i = 0; i < n; i++, a++, b++) {
    			permuter(a, b, tab);
    		}
    	}
    Thierry Leriche-Dessirier
    Consultant Java JEE Web Agile freelance
    Rédacteur pour Developpez
    Professeur de Génie Logiciel à l'ESIEA

    Site : http://www.icauda.com / Linked'in : http://www.linkedin.com/in/thierryler / Twitter : @ThierryLeriche

  18. #38
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Points : 29 131
    Points
    29 131
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par thierryler Voir le message
    Le T4 est carrément plus rapide là. Tu peux redonner le code complet ?
    Voilà :

    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
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    public class TestQuickSortDeTableau4 {
     
    	public static void main(String[] args) {
    		int[] array = createArray(1000000); // T4.R
    		//int[] array = readArray(); // T4.F
     
    		//System.out.println(Arrays.toString(array));
    		long time = System.currentTimeMillis();
    		try {
    			array = new TestQuickSortDeTableau4().trier(array);
    			//System.out.println(Arrays.toString(array));
    		}
    		finally {
    			System.out.println(System.currentTimeMillis()-time+" ms");
    		}
     
    	}
     
    	private static int[] createArray(int nb) {
    		int[] array = new int[nb];
     
    		Random random = new Random(424242);
     
    		for(int i=0;i<array.length; i++) {
    			array[i]=random.nextInt();
    		}
    		return array;
    	}
     
    	private static int[] readArray() {
    		return ReadListe.readIntArray(); 
    	}
     
    	public int[] trier(int[] array) {
    		if (array == null || array.length==0) {
    			return new int[0];
    		}
    		return trier(array, new int[array.length], 0, array.length);
    	}
     
    	private int[] trier(final int[] array, final int[] array2, final int debut, final int fin) {
     
    			// Choix du pivot a gauche
    			final int pivot = array[debut]; 
    			int posGauche = debut;
    			int posDroite = fin;
     
    			// Separation en deux sous listes
    			for (int index = debut+1; index < fin; index++) {
    				int elt = array[index];
    				//final int comp = elt-pivot;
    				if (elt < pivot) {
    					array2[posGauche++]=elt;
    				} else if (elt > pivot) {
    					array2[--posDroite]=elt;
    				}
    			} 
     
    			Arrays.fill(array2, posGauche, posDroite, pivot);  
     
    		 	if ( posGauche>debut ) {
    				trier(array2, array, debut, posGauche );
    				System.arraycopy(array, debut, array2, debut, posGauche-debut);
    			} 
    			if ( posDroite<fin ) {
    				trier(array2, array, posDroite, fin);
    				System.arraycopy(array, posDroite, array2, posDroite, fin-posDroite);
    			}
     
    			return array2;
    		}
     
    }
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  19. #39
    Rédacteur
    Avatar de thierryler
    Homme Profil pro
    Inscrit en
    Octobre 2007
    Messages
    4 078
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Octobre 2007
    Messages : 4 078
    Points : 12 815
    Points
    12 815
    Par défaut
    As-tu testé le T5 ?
    Thierry Leriche-Dessirier
    Consultant Java JEE Web Agile freelance
    Rédacteur pour Developpez
    Professeur de Génie Logiciel à l'ESIEA

    Site : http://www.icauda.com / Linked'in : http://www.linkedin.com/in/thierryler / Twitter : @ThierryLeriche

  20. #40
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 54
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Points : 29 131
    Points
    29 131
    Billets dans le blog
    2
    Par défaut La mise à jour avec le T5
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

Discussions similaires

  1. sort by ne fonctionne pas avec des subtables
    Par ekremyilmaz dans le forum JSF
    Réponses: 1
    Dernier message: 27/07/2010, 14h17
  2. Fonctionr sort() ne fonctionne pas ?
    Par EricStib dans le forum Général Python
    Réponses: 14
    Dernier message: 13/01/2009, 18h26
  3. Collections.sort ne fonctionne pas
    Par lex13 dans le forum Collection et Stream
    Réponses: 7
    Dernier message: 12/07/2007, 12h13
  4. Un Hint sur un PopupMenu ne fonctionne pas !!??
    Par momox dans le forum C++Builder
    Réponses: 6
    Dernier message: 26/05/2003, 17h48
  5. ca ne fonctionne pas (generateur auto-incrémentant)
    Par tripper.dim dans le forum SQL
    Réponses: 7
    Dernier message: 26/11/2002, 01h10

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