памяти эффективного разреженный массив в Java

(Есть несколько вопросов о время эффективного разреженных массивов, но я ищу для эффективности использования памяти.)памяти эффективного разреженный массив в Java

мне нужен эквивалент List<T> или Map<Integer,T>, которые

Может расти по требованию, просто устанавливая ключ, который больше, чем любой, с которым мы столкнулись раньше. (Может считаться, что ключи неотрицательны.)
Является примерно такой же эффективной для памяти, как и ArrayList<T>, в случае, если большинство индексов не являются null, то есть когда фактические данные не очень разрежены.
Когда индексы разрежены, потребляет пространство, пропорциональное числу индексов не null.
Использует меньше памяти, чем HashMap<Integer,T> (так как это автоблокирует ключи и, вероятно, не использует тип скалярного ключа).
Может получить или установить элемент в амортизированном журнале (N), где N - количество записей: не обязательно должно быть линейное время, бинарный поиск будет приемлемым.
Реализована в невирусной чистой Java-библиотеке с открытым исходным кодом (желательно в Maven Central).

Кто-нибудь знает о таком классе полезности?

Я бы ожидал, что коллекций Commons будет один, но это не похоже.

Я столкнулся с org.apache.commons.math.util.OpenIntToFieldHashMap, который выглядит почти правильно, за исключением значения типа FieldElement, который кажется безвозмездным; Я просто хочу T extends Object. Похоже, что было бы легко изменить исходный код на более общий, хотя я бы предпочел использовать бинарную зависимость, если она доступна.

источник

2012-09-27 Jesse Glick

Я бы попробовал trove коллекций, есть TIntObjectMap, который может работать по вашим намерениям.

источник

2012-09-27 16:49:08 Jack

Это выглядит хорошо. Я попытался адаптировать 'OpenIntToFieldHashMap' к родовому типу значений, который, похоже, работал с работой ~ 10 минут, но он работает только немного лучше, чем' TIntObjectMap'. –

Я сохранил свой тестовый чехол как jglick/inthashmap. Результаты:

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

источник

2012-09-27 17:08:52

Где я могу найти IntHashMap? – oleh

@oleh, вероятно, apache commons (?) – Karussell

Извините, 'IntHashMap' был моей адаптацией' OpenIntToFieldHashMap' из Commons Math. Поскольку это было едва лучше, чем 'TIntObjectMap', я отклонил этот подход. –

Я бы рассмотрел реализацию Android SparseArray для вдохновения. Вы можете посмотреть исходный код, загрузив исходный код AOSP здесь http://source.android.com/source/downloading.html

источник

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 действительно выглядит подходящим - амортизированное время выполнения недокументировано, но из проверки я предполагаю, что он логарифмичен и находится под ASL 2.0, и это нормально. К сожалению, это не в Центральной, о которой я знаю, и хотел бы, чтобы она была отделена от несвязанных вещей, таких как поддержка Android Bluetooth, которая находится в том же корневом источнике. –

Вот самодостаточная версия, которая использует весь необходимый код от андроида https://github.com/frostwire/frostwire-jlibtorrent/blob/b4b3f9a90d7a1dade864d7e3eaa88b616f200a9a/src/com/frostwire/jlibtorrent/SparseArray.java – Gubatron

Я предлагаю вам использовать OpenIntObjectHashMap из библиотеки Colt. Link

источник

2014-05-13 19:30:25 abhinav

Спасибо за отзыв , Это действительно имеет умеренное, но значительно меньшее потребление пространства, чем альтернативы. Я включил это в свой пересмотренный тестовый пример. –

памяти эффективного разреженный массив в Java

ответ

Смежные вопросы