Optimisation de la vitesse d'insertion dans java.util.Map/Set

Question

Existe-t-il un moyen d'optimiser la vitesse des insertions dans une java.util.Collection en spécifiant l'ordre des éléments?

Par exemple

java.util.Set<String> set = java.util.TreeSet<String>(); 

sera cette solution:

set.add("A"); 
set.add("B"); 
set.add("C"); 
set.add("D"); 
set.add("E"); 

plus rapide que celui-ci (ordre aléatoire)?

set.add("E"); 
set.add("D"); 
set.add("C"); 
set.add("A"); 
set.add("B"); 

(et la même question pour les autres collections: HashMap, hastable ...)

Merci

Answer 1

temps d'insertion pour un red-black tree (qui est utilisé pour la mise en œuvre de Java TreeSet/TreeMap) est garanti le pire cas à O (log n). Cela pourrait être plus rapide si les éléments sont dans un ordre particulier, mais je ne suis pas sûr de ce que ce serait (probablement pré-triée serait le plus rapide?).

L'insertion dans une table de hachage est une opération O (1) (temps constant). La principale chose faite pour l'insertion est le calcul du hashcode. Edit: Starblue suggère pré-trié peut donner la pire des performances de sorte que vous pouvez essayer l'ordre aléatoire.

Answer 2

La réponse facile est "time it and see".

L'autre réponse est "cela n'aura pas d'importance". Cela semble être une micro-optimisation qui en vaut à peine la peine. Je pense que cela tombe dans la catégorie "The Sad Tragedy of Micro-Optimization Theater".

Answer 3

Il existe naturellement une énorme différence entre les collections basées sur le hachage et celles basées sur les arbres.

Les arborescences bénéficient de l'ordre des éléments pour l'insertion (par exemple, des comparaisons entre les chaînes), de sorte que lorsque vous avez des objets comparables (comme une chaîne), il est préférable de les utiliser. TreeSet/TreeMap/etc dans la collection standard est supposé être équilibré (arbre rouge-noir) donc l'ordre d'insertion n'a pas beaucoup d'importance. Si ce n'était pas équilibré, alors l'ordre d'insertion serait important puisque vous pourriez vous retrouver avec une chaîne au lieu d'un arbre.

Dans les tables de hachage, le facteur de chargement et la fonction de hachage déterminent tout, mais si vous traitez des chaînes, il est préférable de ne pas vous soucier du hachage.

Si vous avez besoin d'un ensemble de chaînes pour de nombreuses chaînes avec des chevauchements, un Trie peut être plus efficace en mémoire, mais je ne pense pas qu'il y en ait un dans la bibliothèque.

Answer 4

Non pour java.util.Map et java.util.Set, car il s'agit d'interfaces et il existe différentes implémentations.

Pour les implémentations concrètes, l'optimisation n'est pas rentable. Si vous avez des problèmes de performance, choisissez une implémentation mieux adaptée ou repensez ce que vous avez besoin de stocker et comment. L'insertion de 5000 nombres aléatoires dans un HashSet prend environ une milliseconde sur un ordinateur portable ordinaire, alors combien de millions d'éléments voulez-vous insérer pour rendre ce type d'optimisation utile?

Answer 5

Veillez à prendre en compte les caractéristiques de votre structure de données lorsque vous prenez des mesures d'optimisation. Pour un exemple extrême, l'insertion d'éléments dans un arbre binaire dans un ordre trié entraînerait une liste chaînée.