Discussion :

[Nicool]

Je m'intéresse à deux classes: LinkedList et ArrayList (ou Vector si vous préférez, je crois qu'ArrayList est la nouvelle version de Vector).
Vu la façon dont elles fonctionnent, il me semble que:
-LinkedList est efficace pour la suppression/ajout d'un élément, mais pas pour l'accès à un élément.
-ArrayList est peu efficace pour supprimer/ajouter un élément (sauf si c'est en fin de liste/début de liste), mais très efficace pour accéder à un élément (car ArrayList est une sorte de tableau).

Ma question: quelle est la plus efficace de ces deux classe pour le tri de ses éléments, par exemple en utilisant Collection.sort() (si les élements sont tous de même classe implémentant l'interface Comparable)???

[Nicool]

personne n'a d'idée?

[spilliaert]

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
import java.util.*;
public class Sorttest {
 
	public static void main (String args[]){
 
		List<String> linkedstaff = new LinkedList<String>();
		for(int i=0;i<=100000;i++){
			linkedstaff.add(i+"sfxbhsqflnxhlnqsklfxnqksldfjhxnqlskdfjxhnqslkdfhxnqsldkfhxnqlskfxjhsnfx");
		}
		long linkstart=System.currentTimeMillis();
		Collections.sort(linkedstaff);
		System.out.println("LinkedList: "+(System.currentTimeMillis()-linkstart));
 
		ArrayList<String> arrayliststaff = new ArrayList<String>();
		for(int i=0;i<=100000;i++){
			arrayliststaff.add(i+"sfxbhsqflnxhlnqsklfxnqksldfjhxnqlskdfjxhnqslkdfhxnqsldkfhxnqlskfxjhsnfx");
		}
		long arraystart=System.currentTimeMillis();
		Collections.sort(linkedstaff);
		System.out.println("ArrayList: "+(System.currentTimeMillis()-arraystart));
 
}
 
 
}

Comme tu peux le constater, ArrayList se montre plus performant...(si c'est la vitesse que tu veux optimiser)
J'obtiens:

LinkedList: 188
ArrayList: 109

J'espère t'avoir aidé...

@+

Spilliaert

[Nicool]

Merci pour ton idée de programme test! (je ne savais pas comment utiliser une quelconque fonction d'horloge).
Par contre les listes que tu construis sont déjà classées et je me disais que cela pouvait influer sur les résultats.
J'ai donc remplacé "i" dans les xxxstaff.add(...) par des Maths.random()*1000 et cela confirme ton test, LinkedList est au moins deux fois moins rapide qu'arrayList.

Encore merci!

[g_rare]

je crois qu'ArrayList est la nouvelle version de Vector

Petite précision : la seule différence (fondamentale) entre ArrayList et Vector, c'est que "Vector est la version synchronisée de ArrayList".

[Nicool]

au temps pour moi!