Quelle est la bibliothèque de collections Java la plus efficace? [fermé]

Quelle est la bibliothèque de collections Java la plus efficace?

Il y a quelques années, j'ai fait beaucoup de Java et j'avais l'impression à l'époque que le trésor est la meilleure implémentation (la plus efficace) des collections Java. Mais quand j'ai lu les réponses à la question « Les bibliothèques Java gratuites les plus utiles? », J'ai remarqué que le trésor 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. (besoin d'un petit temps d'exécution et d'une petite empreinte mémoire).

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 ajouter beaucoup de fonctionnalités par rapport aux collections normales du JDK.

Personnellement (et je suis partial) j'adore Guava (y compris l'ancien projet Google Java Collections). Cela facilite grandement diverses tâches (y compris les collections), d'une manière au moins raisonnablement efficace. Étant donné que les opérations de collecte forment rarement un goulot d'étranglement dans mon code (d'après mon expérience), c'est "mieux" qu'une API de collections qui peut être plus efficace mais ne rend pas mon code aussi lisible.

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

La question est (maintenant) de stocker beaucoup de données, qui peuvent être représentées à l'aide de 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 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 beaucoup). Le benchmark «officiel» de trove ne compare pas IntIntMaps à Java Collection Map<Integer, Integer>, le stockage Integerset le stockage intsne sont probablement pas les mêmes d'un point de vue technique. Mais un utilisateur peut ne pas se soucier de ce détail technique, il souhaite stocker des données représentables avec intsefficacité.

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<Integer, Integer> map = new HashMap<Integer, Integer>(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 sont primitives ints , ce qui semble raisonnable. Mais cela implique une pénalité d'exécution pour java util, à cause de l'auto-boxing, qui n'est pas nécessaire pour les frameworks de collections primitives.

Les résultats d'exécution (sans gc() appels, bien sûr) sur WinXP, jdk1.6.0_10:

                      100000 opérations put 100000 contient des opérations 
collections java 1938 ms 203 ms
trove 234 ms 125 ms
pcj 516 ms 94 ms

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

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

les collections java oscille entre 6644536 et 7168840 octets
trove 1853296 octets
pcj 1866112 octets

Les collections Java ont besoin de plus de trois fois la mémoire par rapport aux frameworks de collection primitifs. C'est-à-dire que vous pouvez conserver trois fois plus de données en mémoire, sans recourir aux E / S de disque, ce qui réduit considérablement les performances d'exécution. Et cela compte. Lisez la haute évolutivité pour découvrir pourquoi.

D'après mon expérience, la consommation de mémoire élevée est le plus gros problème de performances avec Java, ce qui entraîne bien sûr également une dégradation des performances d'exécution. Les frameworks de collection primitifs peuvent vraiment aider ici.

Donc: Non, java.util n'est pas la réponse. Et «l'ajout de fonctionnalités» aux collections Java n'est pas le but lorsque l'on se questionne sur l'efficacité. De plus, les collections JDK modernes ne " surpassent pas même les collections spécialisées Trove".

Avertissement: le benchmark ici est loin d'être complet, ni parfait. Il vise à faire ressortir le point que j'ai vécu dans de nombreux projets. Les collections primitives sont suffisamment utiles pour tolérer une API louche - 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 simplifiées en termes de suggestion d'une bibliothèque. Il n'y a pas de bibliothèque qui fonctionne bien à travers les divers benchmarks présentés ici. La seule conclusion que je tire est que si vous vous souciez des performances et de la mémoire et que vous vous occupez spécifiquement des types primitifs, cela vaut la peine de regarder les alternatives non jdk.

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

Les bibliothèques couvertes sont

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

Mise à jour juin 2015 : Malheureusement, les benchmarks d'origine ne sont plus disponibles et en plus c'est un peu obsolète. Voici un benchmark assez récent (janvier 2015) réalisé par quelqu'un d'autre. Il n'est pas aussi complet et ne dispose pas d'outils d'exploration interactifs que le lien d'origine.

Comme d'autres commentateurs l'ont remarqué, la définition d '«efficace» jette un large filet. Cependant, personne n'a encore mentionné la bibliothèque Javolution .

Certains des 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 StringBuffer / StringBuilder standard).
• Toutes les classes Javolution sont conformes en temps réel et ont un comportement hautement déterministe (de l'ordre de la microseconde). De plus (contrairement à la bibliothèque standard), Javolution est RTSJ safe (pas de conflit de mémoire ou de fuite de mémoire lorsqu'il est utilisé avec l'extension Java Real-Time).
• Les classes de collection en temps réel de Javolution (carte, liste, table et ensemble) 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 de concurrence pour faciliter la mise en œuvre d'algorithmes parallèles.

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

Quelques bibliothèques de collection à considérer:

• Collections Java dans java.util
• Trove
• Collections Google bibliothèque
• Collections Apache Commons
• Lib à grande échelle de Cliff Click
• Bibliothèque des collections de Doug Lea - n'est plus prise en charge et principalement reconstruite en JDK

Je voudrais avant tout atteindre la bibliothèque de la collection JDK. Il couvre les tâches 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 très utilisé et bien pris en charge.

Apache Commons Collections est plus ancienne et souffre un peu du problème du "trop ​​de cuisiniers", mais contient également beaucoup de choses utiles.

Trove a des collections très spécialisées pour des cas comme les clés / valeurs primitives. Ces jours-ci, nous constatons 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 de concurrence très élevée, vous devez absolument consulter des éléments tels que NonBlockingHashMap dans la bibliothèque à grande échelle, qui est une implémentation sans verrouillage et peut piétiner ConcurrentHashMap si vous avez le bon cas d'utilisation.

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 dollars Stringsur une carte, consultez la page 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 java.util.concurrentpackage doivent être mentionnés, si vous prévoyez d'utiliser le HashMap dans plusieurs threads. une faible empreinte mémoire est évaluée, car cela fait partie de java standard.

Cela 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 chaîné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 chaînée O (n).

Mais quand j'ai lu les réponses à la question "Les bibliothèques Java gratuites les plus utiles?" J'ai remarqué que le trésor est à peine mentionné.

Cela ne semble pas être «le 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, il n'utilise pas les objets Map.Entry
• 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 objet sur un nouvel ensemble de ses attributs
• il a des types de collection primitifs
• pense qu'il a une forme d'itérateur interne

Cela dit, beaucoup a été fait pour améliorer les collections jdk depuis l'écriture de trove.

Ce sont les stratégies de hachage qui me plaisent cependant ... Google pour trove et lisez leur aperçu.

Si vous souhaitez stocker des millions d'enregistrements dans une table de hachage, il est probable que vous rencontriez des problèmes de mémoire. Cela m'est arrivé lorsque j'ai essayé de créer une carte avec 2,3 millions d'objets String, par exemple. Je suis allé avec BerkeleyDB , qui est très mature et fonctionne bien. Ils ont une API Java qui encapsule l'API Collections, de sorte que vous pouvez facilement créer des cartes arbitrairement grandes avec très peu d'espace mémoire. L'accès sera cependant plus lent (car il est stocké sur disque).

Question complémentaire : 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.