Как я должен сопоставить строковые ключи со значениями в Java эффективным способом памяти?

Question

Я ищу способ сохранить отображение строки-> int.HashMap, конечно, является наиболее очевидным решением, но, поскольку я ограничен в памяти и мне нужно хранить 2 миллиона пар, ключи длиной 7 символов, мне нужно что-то, что эффективно использует память, скорость поиска является второстепенным параметром.

В настоящее время я иду по линии:

List<Tuple<String, int>> list = new ArrayList<Tuple<String, int>>();
list.add(...); // load from file
Collections.sort(list);

и затем для поиска:

Collections.binarySearch(list, key); // log(n), acceptable

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

Answer 1

Редактировать : Я только что видел, что вы упомянули, что String были британскими почтовыми индексами, поэтому я вполне уверен, что вы не ошибетесь, используя Trove TLongIntHashMap (кстати, Trove - это небольшая библиотека и она очень проста в использовании).

Редактировать 2 : Многим людям этот ответ кажется интересным, поэтому я добавляю к нему некоторую информацию.

Целью здесь является использование карты, содержащей ключи / значения, с эффективным использованием памяти, поэтому мы начнем с поиска коллекций с эффективным использованием памяти.

Следующий вопрос SO связан (но далеко не идентичен этому).

Какая библиотека Java Collections наиболее эффективна?

Джон Скит упоминает, что Trove является "просто библиотекой коллекций из примитивных типов" [sic] и что, действительно, он не добавляет много функциональности. Мы также можем увидеть несколько тестов ( the.duckman ) о памяти и скорости Trove по сравнению с коллекциями по умолчанию. Вот фрагмент кода:

                      100000 put operations      100000 contains operations 
java collections             1938 ms                        203 ms
trove                         234 ms                        125 ms
pcj                           516 ms                         94 ms

А также есть пример, показывающий, сколько памяти можно сохранить, используя Trove вместо обычной Java HashMap :

java collections        oscillates between 6644536 and 7168840 bytes
trove                                      1853296 bytes
pcj                                        1866112 bytes

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

Таким образом, наша цель теперь заключается в использовании Trove (видно, что, помещая миллионы и миллионы записей в обычный HashMap , ваше приложение перестает отвечать на запросы).

Вы упомянули 2 миллиона пар, ключи длиной 7 символов и отображение String / int.

2 миллиона - это на самом деле не так много, но вы все равно будете ощущать издержки «Объекта» и постоянное (не) упаковывание примитивов в Integer в обычном HashMap {String, Integer}, поэтому Trove создает много смысла здесь.

Однако я хотел бы отметить, что если у вас есть контроль над «7 символами», вы можете пойти еще дальше: если вы используете, скажем, только символы ASCII или ISO-8859-1, ваши 7 символов будут соответствовать вместе (*). В этом случае вы можете полностью избежать создания объектов и представлять своих 7 персонажей на длинной. Затем вы бы использовали Trove TLongIntHashMap и вообще обошли бы «Java-объект».

Вы специально указали, что ваши ключи имеют длину 7 символов, а затем прокомментировали, что они являются британскими почтовыми индексами: я бы отображал каждый почтовый индекс на длинный и сохранял огромный объем памяти, помещая в память пару ключей / значений, используя Trove.

Преимущество Trove в основном в том, что не выполняет постоянную упаковку / распаковку объектов / примитивов: во многих случаях Trove работает напрямую только с примитивами и примитивами.

(*) говорят, что вы используете не более 256 кодовых точек / символов, тогда он умещается в 7 * 8 == 56 бит, что достаточно мало, чтобы соответствовать длинному.

Пример метода для кодирования ключей String в long (предполагается, что для упрощения используются символы ASCII, один байт на символ - достаточно 7 бит):

long encode(final String key) {
    final int length = key.length();
    if (length > 8) {
        throw new IndexOutOfBoundsException(
                "key is longer than 8 characters");
    }
    long result = 0;
    for (int i = 0; i < length; i++) {
        result += ((long) ((byte) key.charAt(i))) << i * 8;
    }
    return result;
}

Answer 2

Используйте библиотеку Trove.

Библиотека Trove оптимизировала классы HashMap и HashSet для примитивов. В этом случае TObjectIntHashMap<String> отобразит параметризованный объект (String) на примитив int.

Answer 3

Прежде всего, вы измерили, что LinkedList действительно эффективнее памяти, чем HashMap, или как вы пришли к такому выводу? Во-вторых, LinkedList время доступа к элементу O(n), поэтому вы не можете выполнять эффективный бинарный поиск по нему. Если вы хотите сделать такой подход, вы должны использовать ArrayList, который даст вам огромный компромисс между производительностью и пространством. Однако, опять же, я сомневаюсь, что HashMap, HashTable или - в частности - TreeMap потребляли бы намного больше памяти, но первые два обеспечили бы постоянный доступ и логарифмическую карту дерева и предоставили бы более приятный интерфейс, который нормальный список. Я попытался бы сделать некоторые измерения, насколько велика разница в потреблении памяти.

ОБНОВЛЕНИЕ : Учитывая, как указал Адамски, что сами String, а не структура данных, в которой они хранятся, будут занимать больше всего памяти, было бы неплохо рассмотреть структуры данных, специфичные для строк, такие как попытки (особенно попытки Патриции ), которые могут уменьшить объем памяти, необходимый для строк.

Answer 4

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

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

А пока, если не возражаете, JNI , есть несколько хороших нативных кратких библиотек, на которые вы могли бы сослаться.

Answer 5

Вы смотрели на попытки .Я не использовал их, но они могут соответствовать тому, что вы делаете.

Answer 6

Может быть, вы можете пойти с RadixTree ?

Answer 7

Как пишет Эрик, используя библиотеку Trove, это хорошее место для начала, так как вы экономите место при хранении int примитивов, а не Integer s.

Однако вы все еще сталкиваетесь с хранением 2 миллионов строкэкземпляров.Учитывая, что это ключи на карте, их интернирование не принесет никакой пользы, поэтому следующее, что я хотел бы рассмотреть, - есть ли какая-то характеристика строк, которую можно использовать.Например:

• Если String s представляют предложения общих слов, вы можете преобразовать строку в класс Sentence и интернировать отдельные слова.
• ЕслиСтроки содержат только подмножество символов Unicode (например, только буквы AZ или буквы + цифры), вы можете использовать более компактную схему кодирования, чем Unicode в Java.
• Можно рассмотреть преобразование каждой строки в кодированный байт UTF-8.массив и обтекание это в классе: MyString.Очевидно, что компромисс здесь - это дополнительное время, затрачиваемое на поиск.
• Вы можете записать карту в файл, а затем отобразить в памяти часть или весь файл.
• Вы можетерассмотрим библиотеки, такие как Berkeley DB, которые позволяют вам определять постоянные карты и кэшировать часть карты в памяти.Это предлагает масштабируемый подход.

Answer 8

Пользовательское дерево будет иметь такую ​​же сложность O(log n), не беспокойтесь.Ваше решение разумно, но я бы выбрал ArrayList вместо LinkedList, потому что связанный список выделяет один дополнительный объект для каждого сохраненного значения, что в вашем случае составит много объектов.

Answer 9

Я думаю, что решение состоит в том, чтобы немного выйти за пределы Java. Если у вас есть столько значений, вы должны использовать базу данных. Если вы не хотите устанавливать Oracle, SQLite работает быстро и легко. Таким образом, данные, которые вам не нужны, сохраняются на диске, и все кэширование / хранение выполняется для вас. Настройка БД с одной таблицей и двумя столбцами совсем не займет много времени.

Answer 10

Используйте java.util.TreeMap вместо java.util.HashMap. Он использует красно-черное двоичное дерево поиска и не использует больше памяти, чем требуется для хранения заметок, содержащих элементы на карте. Никаких дополнительных блоков, в отличие от HashMap или Hashtable.