Quelle est la bibliothèque Java Collections la plus efficace?

Quelle est la bibliothèque Java Collections la plus efficace?

Il y a quelques années, j’ai fait beaucoup de Java et j’ai eu l’impression à l’époque que trove était la meilleure implémentation de Java Collections (la plus efficace). Mais quand je lis les réponses à la question ” Librairies Java gratuites les plus utiles? “, J’ai remarqué que Trove est à peine mentionné. Alors, quelle bibliothèque Java Collections est la meilleure maintenant?

MISE À JOUR: Pour clarifier, je veux surtout savoir quelle bibliothèque utiliser lorsque je dois stocker des millions d’entrées dans une table de hachage, etc.

D’après l’inspection, il semble que Trove n’est qu’une bibliothèque de collections pour les types primitifs – ce n’est pas comme si elle était censée append beaucoup de fonctionnalités aux collections normales du JDK.

Personnellement (et je suis partial), j’aime Guava (y compris l’ancien projet de collections Google Java). Cela rend les tâches les plus diverses (y compris les collections) beaucoup plus faciles, au moins raisonnablement efficaces. Étant donné que les opérations de collecte constituent rarement un goulot d’étranglement dans mon code (selon mon expérience), cela est “meilleur” qu’une API de collecte qui peut être plus efficace mais ne rend pas mon code lisible.

Étant donné que le chevauchement entre Trove et la goyave est quasiment nul, vous pourriez peut-être clarifier ce que vous recherchez dans une bibliothèque de collections.

La question est (maintenant) de stocker beaucoup de données, qui peuvent être représentées en utilisant des types primitifs comme int , dans une carte. Certaines des réponses ici sont très trompeuses à mon avis. Voyons pourquoi.

J’ai modifié le benchmark à partir de trove pour mesurer à la fois le temps d’exécution et la consommation de mémoire. J’ai également ajouté PCJ à ce benchmark, qui est une autre bibliothèque de collections pour les types primitifs (je l’utilise souvent). Le benchmark «officiel» de Trove ne compare pas IntIntMaps à la Map de Java Collection, stockant probablement des Integers et stockant ints n’est pas la même d’un sharepoint vue technique. Mais un utilisateur peut ne pas se soucier de ces détails techniques, il veut stocker les données représentables avec ints efficacement.

D’abord la partie pertinente du code:

 new Operation() { private long usedMem() { System.gc(); return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory(); } // trove public void ours() { long mem = usedMem(); TIntIntHashMap ours = new TIntIntHashMap(SET_SIZE); for ( int i = dataset.size(); i-- > 0; ) { ours.put(i, i); } mem = usedMem() - mem; System.err.println("trove " + mem + " bytes"); ours.clear(); } public void pcj() { long mem = usedMem(); IntKeyIntMap map = new IntKeyIntOpenHashMap(SET_SIZE); for ( int i = dataset.size(); i-- > 0; ) { map.put(i, i); } mem = usedMem() - mem; System.err.println("pcj " + mem + " bytes"); map.clear(); } // java collections public void theirs() { long mem = usedMem(); Map map = new HashMap(SET_SIZE); for ( int i = dataset.size(); i-- > 0; ) { map.put(i, i); } mem = usedMem() - mem; System.err.println("java " + mem + " bytes"); map.clear(); } 

Je suppose que les données proviennent d’ ints primitifs, ce qui semble sain. Mais cela implique une pénalité d’exécution pour java util, à cause de l’auto-boxing, ce qui n’est pas nécessaire pour les frameworks de collections primitifs.

Les résultats de l’exécution (sans les appels gc() , bien sûr) sous WinXP, jdk1.6.0_10:

                       100000 opérations de mise 100000 contiennent des opérations 
 collections java 1938 ms 203 ms
 trove 234 ms 125 ms
 pcj 516 ms 94 ms

Bien que cela puisse sembler déjà radical, ce n’est pas la raison d’utiliser un tel cadre.

La raison en est la performance de la mémoire. Les résultats pour une carte contenant 100 000 entrées int :

 les collections Java oscillent entre 6644536 et 7168840 octets
 trove 1853296 octets
 pcj 1866112 octets

Java Collections nécessite plus de trois fois plus de mémoire que les systèmes de collecte primitifs. C’est-à-dire que vous pouvez conserver trois fois plus de données en mémoire, sans avoir recours au disque IO, ce qui réduit les performances d’exécution par des grandeurs. Et ça compte. Lisez highscalability pour savoir pourquoi.

D’après mon expérience, la consommation de mémoire élevée est le plus gros problème de performance avec Java, ce qui se traduit bien entendu par une performance d’exécution plus mauvaise. Les frameworks de collecte primitifs peuvent vraiment aider ici.

Donc: Non, java.util n’est pas la solution. Et “append des fonctionnalités” aux collections Java n’est pas le but lorsque vous posez des questions sur l’efficacité. Les collections JDK modernes ne surpassent pas non plus les collections spécialisées Trove.

Disclaimer: La référence ici est loin d’être complète et n’est pas parfaite. Il est destiné à faire comprendre le point que j’ai expérimenté dans de nombreux projets. Les collections primitives sont assez utiles pour tolérer les API de poisson – si vous travaillez avec beaucoup de données.

Je sais que c’est un ancien message et il y a une tonne de réponses ici. Mais, les réponses ci-dessus sont superficielles et trop simplifiées pour suggérer une bibliothèque. Il n’y a pas une seule bibliothèque qui réponde bien aux différents critères présentés ici. La seule conclusion que je tire est que si vous vous souciez de la performance et de la mémoire et que vous traitez spécifiquement les types primitifs, il est plus que intéressant de regarder les alternatives non jdk.

Voici une parsing plus solide, en termes de mécanique de référence et de bibliothèques couvertes. Ceci est un fil dans la liste de développement de mahout.

Les bibliothèques couvertes sont

  • HPPC
  • Trove
  • FastUtil
  • Mahout (Colt)
  • Collections Java

Mise à jour Juin 2015 : Malheureusement, les benchmarks originaux ne sont plus disponibles et en plus c’est un peu dépassé. Voici un benchmark assez récent (janvier 2015) effectué par quelqu’un d’autre. Ce n’est pas aussi complet ni les outils exploratoires interactifs comme lien original.

Comme d’autres commentateurs l’ont remarqué, la définition de «efficace» est très large. Cependant, personne n’a encore mentionné la bibliothèque Javolution .

Quelques points forts:

  • Les classes Javolution sont rapides, très rapides (par exemple, insertion / suppression de texte dans O [Log (n)] au lieu de O [n] pour le standard SsortingngBuffer / SsortingngBuilder).
  • Toutes les classes Javolution sont conformes en temps réel et ont un comportement hautement déterministe (de l’ordre de la microseconde). En outre (contrairement à la bibliothèque standard), Javolution est sécurisé RTSJ (pas de conflit de mémoire ni de fuite de mémoire lorsqu’il est utilisé avec l’extension Java Real-Time).
  • Les classes de collecte en temps réel de Javolution (map, list, table et set) peuvent être utilisées à la place de la plupart des classes de collection standard et fournissent des fonctionnalités supplémentaires.
  • Les collections Javolution fournissent des garanties d’access simultané pour faciliter la mise en œuvre des algorithmes parallèles.

La dissortingbution Javolution comprend une suite de tests afin que vous puissiez voir comment ils se comparent aux autres bibliothèques / collections intégrées.

Quelques librairies à considérer:

  • Collections Java dans java.util
  • Trove
  • Bibliothèque de collections Google
  • Collections Apache Commons
  • Librairie à grande échelle de Cliff Click
  • Les collections de Doug Lea lib – ne sont plus supscopes et la plupart du temps reconstruites dans JDK

Je voudrais avant tout atteindre la bibliothèque de collection JDK. Il couvre les choses les plus courantes que vous devez faire et est évidemment déjà disponible pour vous.

Google Collections est probablement la meilleure bibliothèque de haute qualité en dehors du JDK. Il est fortement utilisé et bien pris en charge.

Apache Commons Collections est plus ancien et souffre un peu du problème du “trop ​​de cuisiniers”, mais il a aussi beaucoup de choses utiles.

Trove possède des collections très spécialisées pour les cas tels que les clés / valeurs primitives. De nos jours, nous trouvons que sur les JDK modernes et avec les collections Java 5+ et les cas d’utilisation simultanés, les collections JDK surpassent même les collections Trove spécialisées.

Si vous avez des cas d’utilisation très concomitants, vous devez absolument vérifier des choses comme NonBlockingHashMap dans la librairie à grande échelle, qui est une implémentation sans verrou et peut ralentir ConcurrentHashMap si vous en avez besoin.

java.util

Désolé pour la réponse évidente, mais pour la plupart des utilisations, les collections Java par défaut sont plus que suffisantes.

Pour stocker des millions de Ssortingng dans une carte, consultez http://code.google.com/p/flatmap

Je suis développeur de happy-collections de happy-collections sur source-forge

  1. Collections basées sur des événements
  2. Non modifiable
  3. SortedList
  4. Cache

ConcurrentHashMap ainsi que le package java.util.concurrent doivent être mentionnés si vous prévoyez d’utiliser HashMap dans plusieurs threads. petite empreinte mémoire est affirmée, car cela fait partie de Java standard.

Dépend de la façon dont nous définissons “efficace”.

Chaque structure de données a son propre comportement Big-Oh pour la lecture, l’écriture, l’itération, l’empreinte mémoire, etc. Une liste liée dans une bibliothèque est susceptible d’être la même que toute autre. Et une carte de hachage sera plus rapide pour lire O (1) qu’une liste liée O (n).

Mais quand je lis les réponses à la question “Librairies Java gratuites les plus utiles?” J’ai remarqué que le trésor est à peine mentionné.

Cela ne semble pas “plus efficace”. Cela me semble “le plus populaire”.

Juste quelques commentaires – je n’en ai jamais entendu parler et je ne connais personne qui l’ait utilisé. Les collections intégrées au JDK, Google ou Apache Commons me sont bien connues.

Trove offre quelques avantages.

  • Plus petite empreinte mémoire, les objects Map.Entry ne sont pas utilisés
  • vous pouvez utiliser des stratégies de hachage à la place des clés pour les cartes, cela économise de la mémoire et signifie que vous n’avez pas besoin de définir une nouvelle clé chaque fois que vous souhaitez mettre en cache un object sur un nouvel ensemble d’atsortingbuts
  • il a des types de collection primitifs
  • pense qu’il a une forme d’iterator interne

Cela dit, beaucoup a été fait pour améliorer les collections jdk depuis la création de trove.

Ce sont les stratégies de hachage qui me rendent très attrayant … Google for trove et lisent leur aperçu.

Si vous souhaitez stocker des millions d’enregistrements dans une table de hachage, il y a de fortes chances que vous renconsortingez des problèmes de mémoire. Cela m’est arrivé lorsque j’ai essayé de créer une carte avec 2,3 millions d’objects Ssortingng, par exemple. Je suis allé avec BerkeleyDB , qui est très mature et performant. Ils disposent d’une API Java qui encapsule l’API Collections, de sorte que vous pouvez facilement créer des cartes arbitrairement grandes avec un encombrement mémoire très réduit. L’access sera plus lent (car il est stocké sur le disque).

Question de suivi : existe-t-il une bibliothèque décente (et efficace), bien entretenue pour les collections immuables? Clojure a un excellent support pour cela, et ce serait bien d’avoir quelque chose de similaire pour Java.