Альтернативы HashMap для хранения данных с высокой эффективностью памяти

Question

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

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

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

• Мои столбцы в настоящее время ссылаются на объекты поля, строки по их индексам, а значения объектов, почти всегда Струны
• Некоторые столбцы будут иметь много повторяющихся значений
• первичные операции должны обновить или удалить записи на основе значений определенных полей, а также добавление/удаление/объединение столбцов

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

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

Answer 1

Так что я предполагаю, что у вас есть карта Map<ColumnName,Column>, где столбец на самом деле что-то вроде ArrayList<Object>.

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

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

Answer 6

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

Answer 7

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

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

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

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

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

Answer 8

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

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

Answer 9

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

Maximum bytes to be used from Local heap. 

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

Answer 10

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

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