Was ist die effizienteste Java Collections-Bibliothek? [geschlossen]

Was ist die effizienteste Java Collections-Bibliothek?

Vor ein paar Jahren habe ich viel Java gemacht und hatte damals den Eindruck, dass Trove die beste (effizienteste) Implementierung von Java Collections ist. Aber als ich die Antworten auf die Frage " Die nützlichsten kostenlosen Java-Bibliotheken? " Lies, bemerkte ich, dass die Fundgrube kaum erwähnt wird. Welche Java Collections-Bibliothek ist jetzt die beste?

UPDATE: Zur Verdeutlichung möchte ich hauptsächlich wissen, welche Bibliothek ich verwenden soll, wenn ich Millionen von Einträgen in einer Hash-Tabelle usw. speichern muss (ich benötige eine kleine Laufzeit und einen kleinen Speicherbedarf).

Nach der Inspektion sieht es so aus, als ob Trove nur eine Bibliothek von Sammlungen für primitive Typen ist - es ist nicht so, dass es eine Menge Funktionen gegenüber den normalen Sammlungen im JDK hinzufügen soll.

Persönlich (und ich bin voreingenommen) liebe ich Guava (einschließlich des früheren Google Java Collections-Projekts). Dies erleichtert verschiedene Aufgaben (einschließlich Sammlungen) erheblich und ist zumindest einigermaßen effizient. Da Erfassungsvorgänge (meiner Erfahrung nach) selten einen Engpass in meinem Code darstellen, ist dies "besser" als eine Erfassungs-API, die zwar effizienter ist, meinen Code jedoch nicht als lesbar macht.

Angesichts der Tatsache, dass die Überlappung zwischen Trove und Guave so gut wie gleich Null ist, könnten Sie vielleicht klarstellen, wonach Sie tatsächlich in einer Sammlungsbibliothek suchen.

Die Frage ist (jetzt), wie viele Daten, die mit primitiven Typen wie dargestellt werden können int, in einer Karte gespeichert werden . Einige der Antworten hier sind meiner Meinung nach sehr irreführend. Mal sehen warum.

Ich habe den Benchmark von trove geändert , um sowohl die Laufzeit als auch den Speicherverbrauch zu messen. Ich habe diesem Benchmark auch PCJ hinzugefügt , eine weitere Sammlungsbibliothek für primitive Typen (ich verwende diese ausgiebig). Der "offizielle" Fundus-Benchmark vergleicht IntIntMaps nicht mit dem von Java Collection Map<Integer, Integer>. Wahrscheinlich ist das Speichern Integersund Speichern intsaus technischer Sicht nicht dasselbe. Ein Benutzer interessiert sich jedoch möglicherweise nicht für dieses technische Detail. Er möchte Daten, mit denen er darstellbar ist, intseffizient speichern.

Zuerst der relevante Teil des Codes:

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();
     }

Ich gehe davon aus, dass die Daten primitiv sind ints , was vernünftig erscheint. Dies impliziert jedoch eine Laufzeitstrafe für Java Util aufgrund des Auto-Boxing, das für die Frameworks für primitive Sammlungen nicht erforderlich ist.

Die Laufzeitergebnisse ( gc()natürlich ohne Aufrufe) unter WinXP, jdk1.6.0_10:

                      100000 Put-Operationen 100000 enthält Operationen 
Java-Sammlungen 1938 ms 203 ms
Fundgrube 234 ms 125 ms
pcj 516 ms 94 ms

Dies mag bereits drastisch erscheinen, ist jedoch nicht der Grund, ein solches Framework zu verwenden.

Der Grund ist die Speicherleistung. Die Ergebnisse für eine Karte mit 100000int Einträgen:

Java-Sammlungen pendeln zwischen 6644536 und 7168840 Bytes
Fundus 1853296 Bytes
pcj 1866112 Bytes

Java-Sammlungen benötigen im Vergleich zu primitiven Sammlungsframeworks mehr als das Dreifache des Speichers. Das heißt, Sie können dreimal so viele Daten im Speicher behalten, ohne auf Festplatten-E / A zurückgreifen zu müssen, wodurch die Laufzeitleistung um Größenordnungen verringert wird. Und das ist wichtig. Lesen Sie Highscalability , um herauszufinden, warum.

Meiner Erfahrung nach ist ein hoher Speicherverbrauch das größte Leistungsproblem bei Java, was natürlich auch zu einer schlechteren Laufzeitleistung führt. Primitive Collection Frameworks können hier wirklich helfen.

Also: Nein, java.util ist nicht die Antwort. Und "Hinzufügen von Funktionen" zu Java-Sammlungen ist nicht der Punkt, wenn es um Effizienz geht. Auch die modernen JDK-Sammlungen übertreffen nicht einmal die spezialisierten Trove-Sammlungen.

Haftungsausschluss: Der Benchmark hier ist bei weitem nicht vollständig und auch nicht perfekt. Es soll den Punkt nach Hause fahren, den ich in vielen Projekten erlebt habe. Primitive Sammlungen sind nützlich genug, um fischartige APIs zu tolerieren - wenn Sie mit vielen Daten arbeiten.

Ich weiß, dass dies ein alter Beitrag ist und es hier eine Menge Antworten gibt. Die obigen Antworten sind jedoch oberflächlich und in Bezug auf den Vorschlag einer Bibliothek zu stark vereinfacht. Es gibt keine Bibliothek, die über die verschiedenen hier vorgestellten Benchmarks hinweg gut abschneidet. Die einzige Schlussfolgerung, die ich daraus ziehen kann, ist, wenn Sie sich für Leistung und Gedächtnis interessieren und sich speziell mit primitiven Typen befassen. Es lohnt sich mehr als, sich die Nicht-JDK-Alternativen anzusehen.

Hier finden Sie eine fundiertere Analyse in Bezug auf die Benchmark-Mechanik und die abgedeckten Bibliotheken. Dies ist ein Thread in der Mahout-Entwicklerliste.

Die abgedeckten Bibliotheken sind

• HPPC
• Fundgrube
• FastUtil
• Mahout (Colt)
• Java-Sammlungen

Update Juni 2015 : Leider sind die ursprünglichen Benchmarks nicht mehr verfügbar und außerdem etwas veraltet. Hier ist ein relativ neuer (Januar 2015) Benchmark, der von jemand anderem durchgeführt wurde. Es ist weder so umfassend noch verfügt es über interaktive Erkundungswerkzeuge wie der ursprüngliche Link.

Wie andere Kommentatoren bemerkt haben, wirft die Definition von "effizient" ein weites Netz. Allerdings hat noch niemand die Javolution-Bibliothek erwähnt .

Einige der Highlights:

• Javolution-Klassen sind schnell, sehr schnell (z. B. Einfügen / Löschen von Text in O [Log (n)] anstelle von O [n] für Standard-StringBuffer / StringBuilder).
• Alle Javolution-Klassen sind in Echtzeit kompatibel und weisen ein stark deterministisches Verhalten auf (im Mikrosekundenbereich). Darüber hinaus ist Javolution (im Gegensatz zur Standardbibliothek) RTSJ-sicher (kein Speicherkonflikt oder Speicherverlust bei Verwendung mit der Java-Echtzeiterweiterung).
• Die Echtzeit-Erfassungsklassen von Javolution (Karte, Liste, Tabelle und Satz) können anstelle der meisten Standard-Erfassungsklassen verwendet werden und bieten zusätzliche Funktionen.
• Die Javolution-Sammlungen bieten Parallelitätsgarantien, um die Implementierung paralleler Algorithmen zu vereinfachen.

Die Javolution-Distribution enthält eine Benchmark-Suite, damit Sie sehen können, wie sie sich gegenüber anderen Bibliotheken / den integrierten Sammlungen behaupten.

Einige zu berücksichtigende Sammlungsbibliotheken:

• Java-Sammlungen in java.util
• Fundgrube
• Google Sammlungen Bibliothek
• Apache Commons-Sammlungen
• Hochwertige Bibliothek von Cliff Click
• Doug Leas Sammlungsbibliothek - wird nicht mehr unterstützt und größtenteils in JDK neu erstellt

Ich würde in erster Linie nach der JDK-Sammlungsbibliothek greifen. Es deckt die häufigsten Dinge ab, die Sie tun müssen, und steht Ihnen offensichtlich bereits zur Verfügung.

Google Collections ist wahrscheinlich die beste hochwertige Bibliothek außerhalb des JDK. Es wird stark genutzt und gut unterstützt.

Apache Commons Collections ist älter und leidet ein wenig unter dem Problem "zu viele Köche", hat aber auch viele nützliche Dinge.

Trove hat sehr spezielle Sammlungen für Fälle wie primitive Schlüssel / Werte. Heutzutage stellen wir fest, dass in modernen JDKs und mit den Java 5+ -Sammlungen und gleichzeitigen Anwendungsfällen die JDK-Sammlungen sogar die spezialisierten Trove-Sammlungen übertreffen.

Wenn Sie Anwendungsfälle mit sehr hoher Parallelität haben, sollten Sie auf jeden Fall Dinge wie die NonBlockingHashMap in der High-Scale-Bibliothek überprüfen, die eine sperrenfreie Implementierung ist und auf ConcurrentHashMap stampfen kann, wenn Sie den richtigen Anwendungsfall dafür haben.

java.util

Entschuldigen Sie die offensichtliche Antwort, aber für die meisten Anwendungen sind die Standard- Java-Sammlungen mehr als ausreichend.

Informationen zum Speichern von Millionen Stringin einer Karte finden Sie unter http://code.google.com/p/flatmap

Ich bin Entwickler von Happy-Sammlungen aus Happy-Sammlungen auf Source-Forge

1. Ereignisbasierte Sammlungen
2. Nicht veränderbar
3. SortedList
4. Zwischenspeicher

ConcurrentHashMap sowie das java.util.concurrentPaket sollten erwähnt werden, wenn Sie die HashMap in mehreren Threads verwenden möchten. Es wird ein geringer Speicherbedarf angenommen, da dies Teil von Standard-Java ist.

Kommt darauf an, wie wir "effizient" definieren.

Jede Datenstruktur hat ihr eigenes Big-Oh-Verhalten zum Lesen, Schreiben, Iterieren, Speicherbedarf usw. Eine verknüpfte Liste in einer Bibliothek ist wahrscheinlich dieselbe wie jede andere. Und eine Hash-Map ist zum Lesen von O (1) schneller als eine verknüpfte Liste O (n).

Aber wenn ich die Antworten auf die Frage "Nützlichste kostenlose Java-Bibliotheken?" Lies. Mir ist aufgefallen, dass Fundgrube kaum erwähnt wird.

Das klingt nicht nach "am effizientesten". Es klingt für mich wie "am beliebtesten".

Nur ein paar Rückmeldungen - ich habe noch nie davon gehört und kenne niemanden, der es benutzt hat. In JDK, Google oder Apache Commons integrierte Sammlungen sind mir bekannt.

Trove bietet einige Vorteile.

• Bei geringerem Speicherbedarf werden keine Map.Entry-Objekte verwendet
• Sie können anstelle von Schlüsseln für Karten Hash-Strategien verwenden. Dies spart Speicher und bedeutet, dass Sie nicht jedes Mal einen neuen Schlüssel definieren müssen, wenn Sie ein Objekt in einem neuen Satz seiner Attribute zwischenspeichern möchten
• Es hat primitive Sammlungstypen
• Ich denke, es hat irgendeine Form von internem Iterator

Trotzdem wurde viel getan, um die JDK-Sammlungen zu verbessern, seit Trove geschrieben wurde.

Es sind die Hashing-Strategien, die es für mich attraktiv machen ... Google für Fundgrube und lesen Sie deren Übersicht.

Wenn Sie Millionen von Datensätzen in einer Hash-Tabelle speichern möchten, treten möglicherweise Speicherprobleme auf. Dies ist mir passiert, als ich zum Beispiel versucht habe, eine Karte mit 2,3 Millionen String-Objekten zu erstellen. Ich habe mich für BerkeleyDB entschieden , das sehr ausgereift ist und gute Leistungen erbringt. Sie verfügen über eine Java-API, die die Sammlungs-API umschließt, sodass Sie problemlos beliebig große Karten mit sehr geringem Speicherbedarf erstellen können. Der Zugriff ist jedoch langsamer (da er auf der Festplatte gespeichert ist).

Folgefrage : Gibt es eine anständige (und effiziente), gut gepflegte Bibliothek für unveränderliche Sammlungen? Clojure hat dafür eine hervorragende Unterstützung, und es wäre schön, etwas Ähnliches für Java zu haben.