Est-il plus rapide pour ajouter à une collection puis à les trier, ou ajouter à une collection triée?

Question

Si j'ai un Map comme ceci:

HashMap<Integer, ComparableObject> map;

et je veux obtenir une collection de valeurs triées à l'aide de ordre naturel, quelle méthode est la plus rapide?

(A)

Créer une instance d'un sortable collection comme ArrayList, ajouter les valeurs, puis de les trier:

List<ComparableObject> sortedCollection = new ArrayList<ComparableObject>(map.values());
Collections.sort(sortedCollection);

(B)

Créer une instance d'une collection ordonnée comme TreeSet, puis ajouter les valeurs:

Set<ComparableObject> sortedCollection = new TreeSet<ComparableObject>(map.values());

Notez que la collection n'est jamais modifié, de sorte que le tri ne doit avoir lieu qu'une fois.

Answer 1

TreeSet a log(n) le temps de la complexité guarantuee pour ajouter()/remove()/contains() éléments. Tri d'une liste de tableaux prend n*log(n) opérations, mais l'ajout/la récupération de données à partir de la liste ne prend que 1 de l'opération.

Donc, si vous êtes principalement de la récupération, et à ne pas trier souvent, ArrayList est le meilleur choix. Si vous triez souvent, mais de ne récupérer que beaucoup TreeSet serait un meilleur choix.

Answer 2

Théoriquement, le tri à la fin devrait être plus rapide. Le maintien triés etat à travers le processus pourrait impliquer d'autres temps CPU.

À partir de la CS des points de vue, les deux opérations sont NlogN, mais 1 devrait avoir le bas de la constante.

Answer 3

Pourquoi ne pas utiliser le meilleur des deux mondes? Si vous n'êtes jamais l'utiliser à nouveau, tri à l'aide d'un TreeSet et initialiser une liste de tableaux avec le contenu

List<ComparableObject> sortedCollection = 
    new ArrayList<ComparableObject>( 
          new TreeSet<ComparableObject>(map.values()));

---

EDIT:

J'ai créé un indice de référence (vous pouvez y accéder à pastebin.com/5pyPMJav) pour tester les trois approches (ArrayList + Collections.trier, TreeSet et mon meilleur des deux mondes avec une approche de la mine et gagne toujours. Le fichier de test crée une carte avec 10000 éléments, dont les valeurs ont volontairement terrible comparateur, et puis chacune des trois stratégies obtenir une chance pour une) trier les données et b) effectuer une itération sur elle. Voici quelques exemple de sortie (vous pouvez le tester vous-mêmes):

EDIT: j'ai ajouté un aspect que les journaux d'appels de Truc.compareTo ("Truc") et j'ai également ajouté une nouvelle Stratégie basée sur PriorityQueues qui est beaucoup plus rapide que les solutions précédentes (au moins dans le tri).

compareTo() calls:123490
Transformer ArrayListTransformer
    Creation: 255885873 ns (0.255885873 seconds) 
    Iteration: 2582591 ns (0.002582591 seconds) 
    Item count: 10000

compareTo() calls:121665
Transformer TreeSetTransformer
    Creation: 199893004 ns (0.199893004 seconds) 
    Iteration: 4848242 ns (0.004848242 seconds) 
    Item count: 10000

compareTo() calls:121665
Transformer BestOfBothWorldsTransformer
    Creation: 216952504 ns (0.216952504 seconds) 
    Iteration: 1604604 ns (0.001604604 seconds) 
    Item count: 10000

compareTo() calls:18819
Transformer PriorityQueueTransformer
    Creation: 35119198 ns (0.035119198 seconds) 
    Iteration: 2803639 ns (0.002803639 seconds) 
    Item count: 10000

Étrangement, mon approche donne de meilleurs résultats dans l'itération (j'aurais pensé qu'il n'y aurait pas de différences à la liste de tableaux approche dans l'itération, puis-je avoir un bug dans mon test?)

Disclaimer: je sais que c'est probablement une terrible de référence, mais elle aide à obtenir le point à travers vous et je n'ai certainement pas la manipuler pour faire mon approche de la victoire.

(Le code a une dépendance à apache commons / lang pour l'est égal à / hashcode / compareTo les constructeurs, mais il devrait être facile à refactoriser le code de sortie)

Answer 4

Assurez-vous de lire mon commentaire à propos de TreeSet en bas, si vous choisissez de mettre en œuvre B)

Si votre application seulement occasionnelle sortes mais parcourt beaucoup, je dirais que vous êtes mieux à l'aide d'une simple liste non triée. Trier le une fois, puis de bénéficier plus rapidement de l'itération. L'itération est particulièrement rapide sur un tableau de la liste.

Cependant, si vous voulez ordre de tri pour être garanti en tout temps ou vous êtes peut-être l'ajout / suppression d'éléments fréquemment, puis utiliser une collection triée et prendre le coup de l'itération.

Donc dans votre cas, je dirais), est la meilleure option. La liste est triée une fois, ne change pas et, par conséquent, les avantages d'être un tableau. Itération doit être très rapide, surtout si vous savez son une liste de tableaux et peut utiliser directement la liste de tableaux.get() au lieu d'un Itérateur.

Je voudrais aussi ajouter que TreeSet, par définition, est un Ensemble qui signifie que les objets sont uniques. Un TreeSet détermine l'égalité en utilisant compareTo sur votre Comparateur / Comparables. Vous pourriez facilement vous trouver les données manquantes si vous essayez d'ajouter deux objets dont compareTo renvoie une valeur de 0. par exemple l'ajout de "C", "A", "B", "A" à un TreeSet sera de retour "A", "B", "C"

Answer 5

Collections.sort utilise mergeSort qui a O(nlog n).

TreeSet a-Rouge-Noir l'arbre sous-jacent, les opérations de base a O(logn). Donc n d'éléments de a également O(nlog n).

Donc les deux sont même big O algorithme.