Jaka jest najbardziej wydajna biblioteka kolekcji Java? [Zamknięte]

Jaka jest najbardziej wydajna biblioteka kolekcji Java?

Kilka lat temu dużo pracowałem nad Javą i odniosłem wtedy wrażenie, że znalezisko jest najlepszą (najbardziej wydajną) implementacją kolekcji Java. Kiedy jednak przeczytałem odpowiedzi na pytanie „ Najbardziej przydatne darmowe biblioteki Java? ”, Zauważyłem, że prawie się nie wspomina o tym skarbcu . Więc która biblioteka kolekcji Java jest teraz najlepsza?

AKTUALIZACJA: Aby wyjaśnić, przede wszystkim chcę wiedzieć, jakiej biblioteki użyć, gdy muszę przechowywać miliony wpisów w tabeli skrótów itp. (Potrzebuję niewielkiego czasu wykonywania i pamięci).

Z oględzin wygląda na to, że Trove jest tylko biblioteką kolekcji dla typów prymitywnych - to nie jest tak, że ma dodawać wiele funkcji w stosunku do zwykłych kolekcji w JDK.

Osobiście (i jestem stronniczy) uwielbiam Guavę (w tym dawny projekt Google Java Collections). Znacznie ułatwia wykonywanie różnych zadań (w tym zbieranie) w sposób przynajmniej w miarę efektywny. Biorąc pod uwagę, że operacje zbierania rzadko tworzą wąskie gardło w moim kodzie (z mojego doświadczenia), jest to „lepsze” niż API kolekcji, które może być bardziej wydajne, ale nie czyni mojego kodu tak czytelnym.

Biorąc pod uwagę, że nakładanie się Trove i guawy jest prawie zerowe, być może mógłbyś wyjaśnić, czego faktycznie szukasz w bibliotece kolekcji.

Pytanie dotyczy (teraz) przechowywania dużej ilości danych, które można przedstawić za pomocą typów prymitywnych, takich jak int Map. Niektóre odpowiedzi są moim zdaniem bardzo mylące. Zobaczmy, dlaczego.

Zmodyfikowałem test porównawczy z trove, aby mierzyć zarówno czas wykonywania, jak i zużycie pamięci. Dodałem również PCJ do tego benchmarku, który jest kolejną biblioteką kolekcji dla typów prymitywnych (używam tego intensywnie). „Oficjalny” test porównawczy skarbów nie porównuje IntIntMaps z Java Collection Map<Integer, Integer>, prawdopodobnie przechowywanie Integersi przechowywanie intsnie jest tym samym z technicznego punktu widzenia. Jednak użytkownik może nie przejmować się szczegółami technicznymi, za pomocą których chce przechowywać dane, które można przedstawićints efektywnie .

Najpierw odpowiednia część kodu:

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

Zakładam, że dane są prymitywne ints , co wydaje się rozsądne. Ale to oznacza karę wykonawczą dla narzędzia java, ze względu na automatyczne boksowanie, które nie jest konieczne dla prymitywnych frameworków kolekcji.

Wyniki działania ( gc()oczywiście bez wywołań) na WinXP, jdk1.6.0_10:

                      100000 operacji sprzedaży 100000 zawiera operacje 
kolekcje java 1938 ms 203 ms
trove 234 ms 125 ms
PCJ 516 ms 94 ms

Chociaż może się to już wydawać drastyczne, nie jest to powód, aby korzystać z takiej struktury.

Powodem jest wydajność pamięci. Wyniki dla mapy zawierającej 100000 intwpisów:

kolekcje java oscylują między 6644536 a 7168840 bajtów
skarb 1853296 bajtów
pcj 1866112 bajtów

Kolekcje Java wymagają ponad trzykrotnie większej ilości pamięci niż prymitywne struktury kolekcji. Oznacza to, że można przechowywać w pamięci trzy razy więcej danych, bez uciekania się do operacji we / wy dysku, co znacznie obniża wydajność środowiska wykonawczego. I to ma znaczenie. Przeczytaj artykuł o wysokiej skalowalności, aby dowiedzieć się, dlaczego.

Z mojego doświadczenia wynika, że ​​duże zużycie pamięci jest największym problemem z wydajnością w Javie, co oczywiście skutkuje również gorszą wydajnością środowiska uruchomieniowego. Prymitywne struktury kolekcji mogą tu naprawdę pomóc.

A więc: nie, java.util nie jest odpowiedzią. A „dodawanie funkcjonalności” do kolekcji Java nie jest celem, gdy pytamy o wydajność. Również współczesne kolekcje JDK nie „wyprzedzają nawet wyspecjalizowanych kolekcji Trove”.

Zastrzeżenie: tutaj wzorzec jest daleki od ukończenia, ani też nie jest doskonały. Ma to na celu podkreślenie punktu, którego doświadczyłem w wielu projektach. Prymitywne kolekcje są wystarczająco przydatne, aby tolerować podejrzane API - jeśli pracujesz z dużą ilością danych.

Wiem, że to stary post i jest tu mnóstwo odpowiedzi. Ale powyższe odpowiedzi są powierzchowne i zbyt uproszczone, jeśli chodzi o sugerowanie biblioteki. Nie ma jednej biblioteki, która radziłaby sobie dobrze z różnymi przedstawionymi tutaj testami porównawczymi. Jedynym wnioskiem, jaki wyciągam, jest to, że jeśli zależy ci na wydajności i pamięci, a konkretnie do czynienia z typami prymitywnymi, bardziej niż warto przyjrzeć się alternatywom innym niż jdk.

Oto bardziej rzetelna analiza, jeśli chodzi o mechanikę testów porównawczych i uwzględnione biblioteki. To jest wątek na liście deweloperów mahoutów.

Biblioteki objęte programem to

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

Aktualizacja czerwiec 2015 : Niestety, oryginalne testy porównawcze nie są już dostępne, a poza tym są nieco przestarzałe. Oto całkiem niedawne testy porównawcze (styczeń 2015) wykonane przez kogoś innego. Nie jest tak obszerny, ani nie ma interaktywnych narzędzi eksploracyjnych, jak oryginalny link.

Jak zauważyli inni komentatorzy, definicja „efektywnego” rzuca szeroką sieć. Jednak nikt jeszcze nie wspomniał o bibliotece Javolution .

Niektóre z najważniejszych:

• Klasy Javolution są szybkie, bardzo szybkie (np. Wstawianie / usuwanie tekstu w O [Log (n)] zamiast O [n] dla standardowego StringBuffer / StringBuilder).
• Wszystkie klasy Javolution są trudne do spełnienia w czasie rzeczywistym i mają wysoce deterministyczne zachowanie (w zakresie mikrosekund). Ponadto (w przeciwieństwie do biblioteki standardowej), Javolution jest bezpieczny dla RTSJ (brak konfliktów pamięci lub wycieków pamięci, gdy jest używany z rozszerzeniem Java Real-Time).
• Klasy kolekcji w czasie rzeczywistym Javolution (mapa, lista, tabela i zestaw) mogą być używane zamiast większości standardowych klas kolekcji i zapewniają dodatkową funkcjonalność.
• Kolekcje Javolution zapewniają gwarancje współbieżności, aby ułatwić implementację algorytmów równoległych.

Dystrybucja Javolution zawiera zestaw testów porównawczych, dzięki czemu można zobaczyć, jak wypadają na tle innych bibliotek / wbudowanych kolekcji.

Niektóre biblioteki kolekcji do rozważenia:

• Kolekcje Java w java.util
• Trove
• Biblioteka kolekcji Google
• Kolekcje Apache Commons
• Biblioteka na dużą skalę od Cliff Click
• Biblioteka kolekcji Douga Lei - nie jest już obsługiwana iw większości przebudowana w JDK

Przede wszystkim sięgnąłbym po bibliotekę JDK. Obejmuje najczęstsze rzeczy, które musisz zrobić, i jest oczywiście już dostępny.

Kolekcje Google to prawdopodobnie najlepsza biblioteka wysokiej jakości poza JDK. Jest mocno używany i dobrze obsługiwany.

Kolekcja Apache Commons jest starsza i trochę cierpi z powodu problemu „zbyt wielu kucharzy”, ale zawiera również wiele przydatnych rzeczy.

Trove ma bardzo wyspecjalizowane zbiory przypadków, takich jak prymitywne klucze / wartości. Obecnie okazuje się, że na nowoczesnych JDK oraz w przypadku kolekcji Java 5+ i jednoczesnych przypadków użycia, kolekcje JDK przewyższają nawet wyspecjalizowane kolekcje Trove.

Jeśli masz naprawdę wysokie przypadki użycia współbieżności, zdecydowanie powinieneś sprawdzić rzeczy takie jak NonBlockingHashMap w bibliotece o dużej skali, która jest implementacją wolną od blokad i może tupnąć na ConcurrentHashMap, jeśli masz do tego odpowiedni przypadek użycia.

java.util

Przepraszamy za oczywistą odpowiedź, ale w przypadku większości zastosowań domyślne kolekcje Java są więcej niż wystarczające.

Aby przechowywać miliony obiektów Stringna mapie, spójrz na http://code.google.com/p/flatmap

Jestem twórcą happy-collections z happy-collections na source-forge

1. Kolekcje oparte na wydarzeniach
2. Niemodyfikowalne
3. SortedList
4. Pamięć podręczna

ConcurrentHashMap, a także java.util.concurrentpakiet, należy wspomnieć, jeśli planujesz używać HashMap w wielu wątkach. zakłada się niewielkie zużycie pamięci, ponieważ jest to część standardowego oprogramowania java.

Zależy od tego, jak zdefiniujemy „efektywny”.

Każda struktura danych ma swoje własne zachowanie Big-Oh do czytania, pisania, iteracji, śladu pamięci itp. Połączona lista w jednej bibliotece prawdopodobnie będzie taka sama jak każda inna. Mapa skrótów będzie szybsza do odczytu O (1) niż połączona lista O (n).

Ale kiedy czytam odpowiedzi na pytanie „Najbardziej przydatne darmowe biblioteki Java?” Zauważyłem, że prawie się nie wspomina o tym skarbcu.

To nie brzmi jak „najbardziej wydajne”. Dla mnie brzmi to jak „najpopularniejszy”.

Tylko garść opinii - nigdy o tym nie słyszałem i nie znam nikogo, kto z niego korzystał. Kolekcje wbudowane w JDK, Google czy Apache Commons są mi dobrze znane.

Trove ma kilka zalet.

• mniejsze zużycie pamięci, nie używa obiektów Map.Entry
• możesz użyć strategii haszowania zamiast kluczy do map, oszczędza to pamięć i oznacza, że ​​nie musisz definiować nowego klucza za każdym razem, gdy chcesz buforować obiekt w nowym zestawie jego atrybutów
• ma prymitywne typy kolekcji
• myślę, że ma jakąś formę wewnętrznego iteratora

To powiedziawszy, wiele zrobiono, aby ulepszyć kolekcje jdk od czasu napisania trove.

To właśnie strategie haszowania sprawiają, że jest to dla mnie atrakcyjne ... Szukaj w Google i przeczytaj ich przegląd.

Jeśli chcesz przechowywać miliony rekordów w tabeli skrótów, prawdopodobnie napotkasz problemy z pamięcią. Zdarzyło mi się to na przykład, gdy próbowałem stworzyć mapę z 2,3 milionami obiektów typu String. Poszedłem z BerkeleyDB , który jest bardzo dojrzały i działa dobrze. Mają Java API, które otacza Kolekcje API, dzięki czemu można łatwo tworzyć dowolnie duże mapy z bardzo małym śladem pamięci. Dostęp będzie jednak wolniejszy (ponieważ jest przechowywany na dysku).

Pytanie uzupełniające : czy istnieje porządna (i wydajna), dobrze utrzymana biblioteka na niezmienne zbiory? Clojure ma do tego doskonałe wsparcie i byłoby miło mieć coś podobnego dla Javy.