pamięci efektywny rzadki tablicy w Javie

(Istnieje kilka pytań o czas efektywny nielicznych tablic ale szukam wydajności pamięci.)pamięci efektywny rzadki tablicy w Javie

muszę równowartość List<T> lub Map<Integer,T> który

Może rosnąć na żądanie, ustawiając klucz większy niż kiedykolwiek napotkany. (Można założyć, że klucze nie są nieujemne).
Jest tak wydajny pod względem pamięci, jak ArrayList<T> w przypadku, gdy większość wskaźników nie jest null, tj. Gdy rzeczywiste dane nie są bardzo rzadkie.
Gdy wskaźniki są rzadkie, zużywa przestrzeń proporcjonalną do liczby indeksów innych niż null.
Używa mniej pamięci niż HashMap<Integer,T> (ponieważ to autoboxuje klucze i prawdopodobnie nie korzysta z klucza skalarnego).
Może uzyskać lub ustawić element w dzienniku zamortyzowanym (N), gdzie N jest liczbą pozycji: nie musi być czasem liniowym, wyszukiwanie binarne byłoby dopuszczalne.
Zaimplementowane w niewirusowej, czystej bibliotece Javy (najlepiej w Maven Central).

Czy ktoś wie o takiej klasie użytkowej?

Spodziewałam się, że Commons Kolekcje będą miały jeden, ale nie wydaje się.

Natknąłem się na org.apache.commons.math.util.OpenIntToFieldHashMap, który wygląda niemal prawe, z wyjątkiem tego, że jest to typ FieldElement, który wydaje się być nieuzasadniony; Chcę tylko T extends Object. Wygląda na to, że łatwo byłoby zmienić jego kod źródłowy na bardziej ogólny, chociaż wolałbym używać zależności binarnej, jeśli jest dostępna.

Źródło

2012-09-27 Jesse Glick

Chciałbym spróbować z kolekcjami trove, jest TIntObjectMap, które mogą pracować dla twoich zamiarów.

Źródło

2012-09-27 16:49:08 Jack

To wygląda dobrze. Próbowałem dostosować 'OpenIntToFieldHashMap' do ogólnego typu wartości, który wydaje się działać z ~ 10min pracy, ale działa on tylko marginalnie lepiej niż' TIntObjectMap'. –

Zapisałem moją walizkę testową jako jglick/inthashmap. Wyniki:

HashMap size: 1017504 
TIntObjectMap size: 853216 
IntHashMap size: 846984 
OpenIntObjectHashMap size: 760472

Źródło

2012-09-27 17:08:52

Gdzie mogę znaleźć IntHashMap? – oleh

@oleh prawdopodobnie apache commons (?) – Karussell

Przepraszam, 'IntHashMap' było moją adaptacją' OpenIntToFieldHashMap' z Commons Math. Ponieważ było to niewiele lepsze niż 'TIntObjectMap', odrzuciłem to podejście. –

Będę szukał inspiracji w implementacji SparseArray Androida. Możesz wyświetlić źródło, pobierając kod źródłowy AOSP tutaj http://source.android.com/source/downloading.html

Źródło

2013-04-22 03:50:34

https://code.google.com/p/android-source-browsing/source/browse/core/java/android/util/SparseArray.java?spec=svn.platform--frameworks--base.58aff7debfdab8ca99dd6bfcfa0c7bebdf2d303b&repo=platform - framework - base & r = 58aff7debfdab8ca99dd6bfcfa0c7bebdf2d303b wygląda na odpowiedni - amortyzowany czas pracy jest nieudokumentowany, ale z inspekcji zgaduję, że jest logarytmiczny - i jest pod ASL 2.0, co jest w porządku. Niestety, nie znam tego w Central, i chciałbym, żeby był oddzielony od niepowiązanych ze sobą elementów, takich jak Android Bluetooth, który jest w tym samym źródłowym źródle. –

Oto samowystarczalne wersja, która wykorzystuje wszystkie niezbędne kod z android https://github.com/frostwire/frostwire-jlibtorrent/blob/b4b3f9a90d7a1dade864d7e3eaa88b616f200a9a/src/com/frostwire/jlibtorrent/SparseArray.java – Gubatron

Proponuję ci użyć OpenIntObjectHashMap z biblioteki Colt. Link

Źródło

2014-05-13 19:30:25 abhinav

Dzięki za cynk . Rzeczywiście ma on umiarkowanie, ale znacznie mniejsze zużycie przestrzeni niż alternatywy. Zawarłem to w moim zmienionym przypadku testowym. –

pamięci efektywny rzadki tablicy w Javie

Odpowiedz

Powiązane problemy