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

Я ищу способ хранения отображения string- > 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

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

Ответ 1

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

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

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

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

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

Джон Скит упоминает, что 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 миллиона действительно не так много, но вы по-прежнему ощущаете накладные расходы "Object" и постоянный (un) бокс примитивов Integer в регулярном HashMap {String, Integer}, поэтому Trove имеет большой смысл здесь.

Однако я бы отметил, что если вы контролируете "7 символов", вы можете пойти еще дальше: если вы используете только символы ASCII или ISO-8859-1, ваши 7 символов будут вписываться в вдоль (*). В этом случае вы можете полностью уклониться от создания объектов и долго представлять свои 7 символов. Затем вы использовали Troove 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;
}

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

То, что вы ищете, это succinct-trie - a trie, который сохраняет свои данные почти в наименьшем объеме пространства теоретически возможным.

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

Между тем, если вы не возражаете JNI, есть несколько хороших родных библиотек succinct-trie, которые вы могли бы ссылаться.

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

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

Ответ 8

возможно, вы можете пойти с RadixTree?

Ответ 9

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

Ответ 10

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

Ответ 11

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

Ответ 12

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

public class MyKey implements Comparable<MyKey>
{
    char[7] keyValue;

    public MyKey(String keyValue)
    {
        ... load this.keyValue from the String keyValue.
    }

    public int compareTo(MyKey rhs)
    {
        ... blah
    }

    public boolean equals(Object rhs)
    {
        ... blah
    }

    public int hashCode()
    {
        ... blah
    }
}

Ответ 13

попробуйте этот

OptimizedHashMap<String, int[]> myMap = new OptimizedHashMap<String, int[]>();
for(int i = 0; i < 2000000; i++)
{
  myMap.put("iiiiii" + i, new int[]{i});
}
System.out.println(myMap.containsValue(new int[]{3}));
System.out.println(myMap.get("iiiiii" + 1));

public class OptimizedHashMap<K,V> extends HashMap<K,V>
{
    public boolean containsValue(Object value) {
    if(value != null)
    {
        Class<? extends Object> aClass = value.getClass();
        if(aClass.isArray())
        {
            Collection values = this.values();
            for(Object val : values)
            {
                int[] newval = (int[]) val;
                int[] newvalue = (int[]) value;
                if(newval[0] == newvalue[0])
                {
                    return true;
                }
            }
        }
    }
    return false;
}

Ответ 14

На самом деле HashMap и List слишком общие для такой конкретной задачи, как поиск int по zipcode. Вы должны использовать преимущества знаний, данные которых используются. Один из вариантов - использовать дерево префикса с листьями, которое сохраняет значение int. Кроме того, его можно обрезать, если (моя догадка) множество кодов с одинаковыми префиксами сопоставляются с одним и тем же целым числом.

Поиск int по zipcode будет линейным в таком дереве и не будет расти, если количество кодов увеличено, сравните с O (log (N)) в случае двоичного поиска.

Ответ 15

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

    int sum=0;
    for(int i=0;i<arr.length;i++){
        sum+=(int)arr[i];

    }

hash "sum", используя хорошо определенные хэш-функции. Вы должны использовать хеш-функцию на основе ожидаемых шаблонов ввода. например если вы используете метод разделения

    public int hasher(int sum){
       return sum%(a prime number);
    }

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

другой метод - взвешивать символы на основе их соответствующего положения.

Например: если вы используете вышеупомянутый метод, оба "abc" и "cab" будут помещены в одно и то же место. но если вам нужно, чтобы они хранились в двух разных местах, дайте весы для таких мест, как мы используем системы счисления.

     int sum=0;
     int weight=1;
     for(int i=0;i<arr.length;i++){
         sum+= (int)arr[i]*weight;
         weight=weight*2; // using powers of 2 gives better results. (you know why :))
     }

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

Ответ 16

Проблема связана с издержками памяти объектов, но с использованием некоторых трюков вы можете попытаться реализовать свой собственный хэшсет. Что-то вроде this. Как и другие, строки имеют довольно большие накладные расходы, поэтому вам нужно как-то "сжать" ее. Также старайтесь не использовать слишком много массивов (списков) в хэш-таблице (если вы используете цепочку хеш-таблицы), поскольку они также являются объектами и также имеют накладные расходы. Еще лучше открыть хэш-таблицу адресации.