Подтвердить что ты не робот

Альтернативы HashMap для эффективного хранения данных

В настоящее время у меня есть программа типа электронных таблиц, которая хранит свои данные в ArrayList из HashMaps. Вы, несомненно, будете потрясены, когда я скажу вам, что это не оказалось идеальным. Накладные расходы, по-видимому, используют в 5 раз больше памяти, чем сами данные.

Этот вопрос спрашивает об эффективных библиотеках коллекций, и ответ был использован Google Collections. Мое продолжение - ", какая часть?". Я читал документацию, но не чувствую, что это дает очень хорошее представление о том, какие классы подходят для этого. (Я также открыт для других библиотек или предложений).

Итак, я ищу что-то, что позволит мне хранить плотные данные типа электронных таблиц с минимальными издержками памяти.

  • В моих столбцах в настоящее время ссылаются объекты Field, строки по их индексам, а значения - объекты, почти всегда Strings
  • В некоторых столбцах будет много повторяющихся значений
  • Основными операциями являются обновление или удаление записей на основе значений определенных полей, а также добавление/удаление/объединение столбцов

Я знаю варианты, такие как H2 и Derby, но в этом случае я не хочу использовать встроенную базу данных.

РЕДАКТИРОВАТЬ. Если вы предлагаете библиотеки, я также был бы признателен, если бы вы могли указать мне конкретный класс или два в них, которые будут применяться здесь. В то время как документация Sun обычно включает в себя информацию о том, какие операции O (1), которые являются O (N) и т.д., Я не вижу многого в сторонних библиотеках, и ни одно описание каких классов лучше всего подходит для каких-либо.

4b9b3361

ОТВЕТЫ

Ответ 1

Итак, я предполагаю, что у вас есть карта Map<ColumnName,Column>, где столбец фактически похож на ArrayList<Object>.

Несколько возможностей -

  • Вы полностью уверены, что проблема памяти? Если вас просто беспокоит размер, было бы полезно подтвердить, что это действительно будет проблемой в текущей программе. Для заполнения JVM требуется огромное количество строк и карт.

  • Вы можете протестировать свой набор данных с различными типами карт в коллекциях. В зависимости от ваших данных вы также можете инициализировать карты с предустановленными комбинациями размера/коэффициента загрузки, которые могут помочь. Я испортил это в прошлом, вы можете получить 30% -ное сокращение памяти, если вам повезет.

  • Как хранить ваши данные в одной матричной структуре данных (существующая реализация библиотеки или что-то вроде обертки вокруг списка списков), с одной картой, которая сопоставляет столбцы столбцов столбцам матрицы?

Ответ 2

В некоторых столбцах будет много повторяющиеся значения

сразу предлагает мне возможное использование шаблона FlyWeight, независимо от решения, которое вы выбрали для своих коллекций.

Ответ 3

Коллекции Trove должны иметь особую заботу о занятом пространстве (я думаю, что у них также есть специализированные структуры данных, если вы придерживаетесь примитивных типов).. посмотрите .

В противном случае вы можете попробовать с коллекциями Apache.. просто выполните свои тесты!

В любом случае, если у вас есть много ссылок вокруг тех же элементов, попробуйте создать подходящий шаблон (например flyweight)

Ответ 4

Предполагая, что все ваши строки имеют большинство одинаковых столбцов, вы можете просто использовать массив для каждой строки, а Map < ColumnKey, Integer > для поиска, какие столбцы относятся к какой ячейке. Таким образом, у вас есть только 4-8 байт служебных данных на ячейку.

Если строки часто повторяются, вы можете использовать пул String для уменьшения дублирования строк. Пулы объектов для других неизменяемых типов могут быть полезны для сокращения потребляемой памяти.

EDIT:. Вы можете структурировать свои данные как на основе строк, так и на основе столбцов. Если его строки основаны (один массив ячеек на строку), добавляя/удаляя строку, это просто вопрос удаления этой строки. Если его столбцы основаны, вы можете иметь массив на столбец. Это может сделать обработку примитивных типов намного более эффективной. то есть вы можете иметь один столбец, который является int [], а другой, который является double [], его гораздо более общий для целого столбца с тем же типом данных, а не с тем же типом данных для целой строки.

Однако в любом случае вы создаете данные, которые будут выбраны для изменения строки или столбца, а выполнение добавления/удаления другого типа приведет к восстановлению всего набора данных.

(Что-то я делаю, это данные на основе строк и добавление столбцов в конец, если предположить, что строка не достаточно длинная, столбец имеет значение по умолчанию, это позволяет избежать перестроения при добавлении столбца. Вместо удаления столбца, У меня есть средство игнорировать его)

Ответ 5

В Guava есть интерфейс Table и реализация на основе хэша. Похоже на естественную подгонку вашей проблемы. Обратите внимание, что это по-прежнему отмечено как бета.

Ответ 6

хранит свои данные в ArrayList из HashMaps
Ну, эта часть кажется ужасно неэффективной для меня. Пустой HashMap уже выделяет 16 * size of a pointer байты (16 означает начальную емкость по умолчанию), плюс некоторые переменные для хэш-объекта (14 + psize). Если у вас много редко заполненных строк, это может быть большой проблемой.

Один из вариантов - использовать один большой хеш с составным ключом (объединение строк и столбцов). Хотя, это не делает операции над целыми рядами очень эффективными.

Кроме того, поскольку вы не упоминаете операцию добавления ячейки, вы можете создавать хеши с только необходимым внутренним хранилищем (параметр initialCapacity).

Я мало знаю о коллекциях google, поэтому не могу помочь. Кроме того, если вы найдете какую-либо полезную оптимизацию, пожалуйста, напишите здесь! Было бы интересно узнать.

Ответ 7

Я экспериментировал с использованием SparseObjectMatrix2D проекта Colt. Мои данные довольно плотные, но их классы Matrix действительно не предлагают никакого способа их увеличить, поэтому я пошел с разреженной матрицей, установленной на максимальный размер.

Кажется, он использует примерно на 10% меньше памяти и загружает примерно на 15% быстрее для одних и тех же данных, а также предлагает некоторые умные методы манипуляции. Тем не менее, они заинтересованы в других вариантах.

Ответ 8

Chronicle Map может иметь накладные расходы менее 20 байт на запись (см. тест, подтверждающий это). Для сравнения, служебные данные java.util.HashMap варьируются от 37-42 байт с -XX:+UseCompressedOops до 58-69 байт без сжатых oops (ссылка).

Кроме того, Chronicle Map хранит ключи и значения с кучей, поэтому он не хранит заголовки объектов, которые не учитываются как служебные данные HashMap выше. Chronicle Map интегрирует с Chronicle-Values, библиотеку для генерации мухи реализаций интерфейсов, образец предложенный Брайаном Агньюем в другом ответе.

Ответ 9

Из вашего описания кажется, что вместо ArrayList из HashMaps вам скорее нужен (связанный) HashMap из ArrayList (каждый ArrayList будет столбцом).

Я бы добавил двойную карту от имени поля к номеру столбца и некоторые умные геттеры/сеттеры, которые никогда не бросали IndexOutOfBoundsException.

Вы также можете использовать ArrayList<ArrayList<Object>> (в основном зубчатую динамически растущую матрицу) и сохранить отображение в именах полей (столбцов) вне.

В некоторых столбцах будет много повторяющиеся значения

Я сомневаюсь, что это важно, особенно если они являются строками (они интернализованы), и ваша коллекция будет хранить ссылки на них.

Ответ 10

Почему бы вам не попробовать использовать реализацию кэша, например EHCache. Это оказалось очень эффективным для меня, когда я попал в ту же ситуацию.
Вы можете просто сохранить свою коллекцию в рамках реализации EHcache. Существуют такие конфигурации, как:

Maximum bytes to be used from Local heap.

После того, как байты, используемые вашим приложением, переполнены, настроенные в кеше, реализация кэша позаботится о записи данных на диск. Также вы можете настроить время, в течение которого объекты записываются на диск с использованием алгоритма Least Recent Used. Вы можете быть уверены, что избегаете ошибок в памяти, используя эти типы реализаций кеша. Это лишь незначительно увеличивает количество операций ввода-вывода вашего приложения.
Это просто взгляд птицы на конфигурацию. Существует множество конфигураций для оптимизации ваших требований.