speichereffiziente spärliche Array in Java

(Es gibt einige Fragen über zeiteffiziente spärliche Arrays, aber ich bin auf der Suche für die Speichereffizienz.)speichereffiziente spärliche Array in Java

Ich brauche das Äquivalent eines List<T> oder Map<Integer,T> die

Kann bei Bedarf wachsen, indem ein Schlüssel größer als zuvor festgelegt wird. (Kann davon ausgehen, Schlüssel sind nicht negativ.)
Ist etwa so speichereffizient wie ein ArrayList<T> in dem Fall, dass die meisten Indizes nicht null, d. H. Wenn die tatsächlichen Daten nicht sehr spärlich ist.
Wenn die Indizes spärlich sind, wird Platz verbraucht, der proportional zur Anzahl der Indizes ist, die nicht null sind.
Verwendet weniger Speicher als HashMap<Integer,T> (da dies die Schlüssel automatisch autoboxiert und wahrscheinlich nicht den skalaren Schlüsseltyp nutzt).
Kann ein Element in amortisierter Log (N) Zeit erhalten oder setzen, wobei N die Anzahl der Einträge ist: Es muss keine lineare Zeit sein, binäre Suche wäre akzeptabel.
Implementiert in einer nichtviralen Open-Source-Java-Bibliothek (vorzugsweise in Maven Central).

Kennt jemand solch eine Nutzungsklasse?

Ich hätte erwartet, dass Commons Collections eins haben, aber es scheint nicht zu sein.

Ich bin auf org.apache.commons.math.util.OpenIntToFieldHashMap gestoßen, das fast richtig aussieht, außer dem Werttyp ist ein FieldElement, der unentgeltlich scheint; Ich möchte nur T extends Object. Es sieht so aus, als ob es einfacher wäre, seinen Quellcode zu bearbeiten, um allgemeiner zu sein, obwohl ich lieber eine binäre Abhängigkeit verwenden würde, wenn eine verfügbar ist.

Quelle

2012-09-27 Jesse Glick

Ich würde versuchen mit trove Sammlungen, gibt es TIntObjectMap, die für Ihre Absichten arbeiten können.

Quelle

2012-09-27 16:49:08 Jack

Das sieht gut aus. Ich habe versucht, 'OpenIntToFieldHashMap' an einen generischen Werttyp anzupassen, der mit ~ 10min Arbeit funktioniert zu haben scheint, aber nur geringfügig besser als' TIntObjectMap' funktioniert. –

Ich habe meinen Testfall als jglick/inthashmap gespeichert. Die Ergebnisse:

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

Quelle

2012-09-27 17:08:52

Wo finde ich IntHashMap? – oleh

@oleh wahrscheinlich Apache commons (?) – Karussell

Sorry, 'IntHashMap' war meine Adaption von' OpenIntToFieldHashMap' von Commons Math. Da es kaum besser als "TIntObjectMap" war, habe ich diesen Ansatz abgelehnt. –

Ich würde Android SparseArray Implementierung für Inspiration betrachten. Sie können die Quelle anzeigen, indem Sie den Quellcode von AOSP hier herunterladen http://source.android.com/source/downloading.html

Quelle

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 --frameworks - base & r = 58aff7debfdab8ca99dd6bfcfa0c7bebdf2d303b scheint angemessen zu sein - die amortisierte Laufzeit ist undokumentiert, aber von der Inspektion her vermute ich, dass sie logarithmisch ist - und ist unter ASL 2.0, was in Ordnung ist. Leider ist es nicht in Central, die ich kenne, und würde es von nicht verwandten Dingen wie Android Bluetooth-Unterstützung, die alle in der gleichen Quelle root ist entkoppelt werden wollen. –

Hier ist eine in sich geschlossene Version, die für die Spitze von android https://github.com/frostwire/frostwire-jlibtorrent/blob/b4b3f9a90d7a1dade864d7e3eaa88b616f200a9a/src/com/frostwire/jlibtorrent/SparseArray.java – Gubatron

Ich werde vorschlagen, dass Sie OpenIntObjectHashMap von Colt Bibliothek verwenden. Link

Quelle

2014-05-13 19:30:25 abhinav

Dank all den notwendigen Code verwendet . Es hat tatsächlich einen moderat, aber signifikant geringeren Platzverbrauch als die Alternativen. Ich habe dies in meinen überarbeiteten Testfall aufgenommen. –

speichereffiziente spärliche Array in Java

Antwort

Verwandte Themen