Discussion :

[sepas]

Bonjour,

J'ai une collection de taille importante (plusieurs centaines d'éléments) dans laquelle je dois sélectionner des éléments tirés au hasard.
Comme cette opération doit être répétée très souvent, elle est susceptible de peser sur les performances du logiciel.
Quel algorithme utiliseriez-vous avec quel type de collection si vous vouliez optimiser cette opération ?

[Nico02]

Salut,

je vois pas trop en quoi quelques appels à Random.nextInt() peuvent peser sur les performances d'un appli ?

Essayons un petit cas de test.

Disons que tes éléments sont stockés dans une ArrayList d'Integer et que j'ajoute des éléments au fur et à mesure dans la liste, puis j'en affiche un au hasard à chaque fois.

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
 
Random rand = new Random();
 
ArrayList<Integer> list = new ArrayList<Integer>();
 
long time = System.currentTimeMillis();
 
for(int i=0;i<10000;i++)
{
	list.add( i );
	System.out.println( list.get( rand.nextInt( list.size()  ) ) );
}
 
System.out.println( "temps d'éxécution : " + ( System.currentTimeMillis() - time ) + "ms" );
 
---> temps d'éxécution : 886ms

Après à voir aussi selon ce que tu as comme éléments à stocker e surtout sur quoi tu te bases pour y accéder mais bon là il faut plus d'infos.

[sepas]

Ce n'est pas les appels à Random qui pèsent, mais l'accès aux éléments de la collection.
Si on compare ArrayList et LinkedList :

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
		int size = 10000;
		Random rand = new Random(); 
		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		LinkedList<Integer> linkedList = new LinkedList<Integer>();
		for(int i=0;i<size;i++) {
			arrayList.add(rand.nextInt());
			linkedList.add(rand.nextInt());
		}
		long time1 = System.currentTimeMillis();
		for(int i=0;i<10000;i++) {
			arrayList.get(rand.nextInt(size-1));
		}
		System.out.println( "Temps d'exécution 1 : " + ( System.currentTimeMillis() - time1 ) + "ms" );
		long time2 = System.currentTimeMillis();
		for(int i=0;i<10000;i++) {
			linkedList.get(rand.nextInt(size-1));
		}
		System.out.println( "Temps d'exécution 2 : " + ( System.currentTimeMillis() - time2 ) + "ms" );

Je trouve :
Temps d'exécution 1 : 2ms
Temps d'exécution 2 : 62ms

Le type de collection à utiliser doit donc être réfléchi.
Ma question est : Y a t-il une autre façon de ranger ces éléments dans une collection et d'y accéder pour accélérer encore les tirages au sort ?

[dinobogan]

Pour accéder le plus rapidement possible à un élément via sa position dans une liste, utilise un ArrayList.
Quelles sont tes contraintes sur la structure de stockage à utiliser ?

[sepas]

A priori, une fois la liste initialisée, il ne devrait pas y avoir d'ajouts ou de retraits, ou alors pas souvent, donc de ce côté là j'ai pas de souci.
En revanche, en plus des tirages au sort, j'aurais besoin fréquemment d'une copie complète de liste mélangée au hasard (à l'aide de Collections.shuffle()).
Là encore, ArrayList semble plus performant.

Enfin, j'aurai sans doute aussi besoin de pouvoir accéder aux éléments par leur nom, et je pensais donc à une HashMap<String,Object>.
Le problème c'est que la HashMap n'est pas adaptée aux tirages au sort.
La solution serait alors de maintenir deux collections contenant les mêmes objets:
- ArrayList pour les tirages au sort,
- HashMap pour les accès par le nom.
Qu'est-ce que tu en penses ?

[tchize_]

Ca me semble correct. Quoi que si la Collection ne change plus une fois chargée, un tableau me semblerait plus approprié qu'un ArrayList. C'est beaucoup plus facile à copier et à mélanger