Quelle union est la plus efficace: List/HashSet

Question

J'écris un algorithme où j'ai besoin d'utiliser une collection, et l'action principale (et seulement) avec eux est l'union.

Je vais avoir environ 1 million objets, et je dois savoir quelle collection a la méthode syndicale plus efficace - La liste ou HashSet (ot peut-être autre chose?).

Merci d'avance.

Answer 1

Je devine que lorsque vous dites « Je vais utiliser distinct avec la liste », vous voulez dire quelque chose comme ceci:

List l = ... 
    Set result = Collectors.toSet(l.stream().distinct()).union(someOtherSet); 

par rapport à ceci:

HashSet h = ... 
    Set result = h.union(someOtherSet); 

Il est clair que la deuxième la version est plus efficace. Le premier doit produire un ensemble intermédiaire de la liste. Chaque fois que vous l'exécutez. La seule chose que le premier enregistre est de la mémoire (à long terme), puisque l'ensemble intermédiaire devient inaccessible après utilisation.

Et la première version peut être écrit plus simplement et plus efficacement:

List l = ... 
    Set result = new HashSet(l).union(someOtherSet); 

L'API List n'a pas de méthode distinct() et aucune méthode union().

---

Si vous utilisez réellement Collection.contains() pour effectuer l'union, alors HashSet() sera beaucoup plus rapide que toute mise en œuvre List standard. Comme @JBNizet déclare:

HashSet.contains est O (1). List.contains est O (n).

Par exemple:

Set result = new HashSet(); 
    for (Integer element: set1) { 
     if (set2.contains(element)) { 
      result.add(element); 
     } 
    } 
    // result now contains the union of set1 and set2. 

Code Presque identique fonctionne pour les listes. Mais il est beaucoup plus lent.

Vous avez demandé:

Ok, oui. Mais qu'en est-il de l'union?

Voir ci-dessus. Il s'agit de mettre en œuvre union en utilisant contains appels.

Qu'est-ce que c'est? O (?)

Voir les articles suivants:

• https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
• https://en.wikipedia.org/wiki/Big_O_notation

Ainsi, tous les deux syndicats sont les mêmes O (N) (n - taille de la deuxième collection)?

No.

• En utilisant HashSet: N x O(1) est O(N)
• liste à l'aide: N x O(N) est O(N^2)

Ou pour être plus précis:

• En utilisant HashSet: min(M, N) x O(1) est O(min(M, N))
• aide de la liste: N x O(M) est O(NM)

où N et M sont les dimensions des deux ensembles/listes. Vous pouvez modifier les performances du boîtier HashSet en itérant le plus petit des deux ensembles. comme indiqué ci-dessus.

---

Enfin, si le type d'élément est Integer alors Bitset pourrait être plus efficace que soit List ou HashSet. Et il pourrait utiliser un couple de plusieurs ordres de grandeur moins de mémoire! En fonction de la plage des entiers, et densité des ensembles.

---

C'est l'analyse Java. Je ne connais pas Scala mais les calculs sous-jacents et la complexité seront les mêmes.