Многозначная карта с эффективным использованием памяти

Question

Привет У меня есть следующая проблема: я храню строки и соответствующий список целочисленных значений в MultiValueMap<String, Integer> Я храню около 13 000 000 миллионов строк, и одна строка может иметь до 500 или более значений.Для каждого значения у меня будет произвольный доступ на карте.Так что наихудший случай - 13 000 000 * 500 пут-коллов.Теперь скорость карты хорошая, но объем памяти увеличивается.MultiValueMap<String, Integer> - это ничто иное, как HashMap/TreeMap<String, <ArrayList<Integer>>.И HashMap, и TreeMap имеют довольно много памяти.Я не буду изменять карту, как только она будет сделана, но мне нужно, чтобы она была быстрой и как можно меньшей для произвольного доступа в программе.(Я сохраняю его на диске и загружаю при запуске, файл сериализованной карты занимает около 600 МБ, а в памяти - около 3 ГБ?)

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

Теперь у меня есть три способа добраться туда:

1. Я использую отсортированный MultivalueMap (TreeMap) для фазы создания, чтобы хранить все. После того, как я закончу с получением всех значений, я получаю строковый массив, вызывая map.keyset().toArray(new String[0]); Создаю двумерный массив int и получаю все значения из многозначной карты.Pro: Это легко реализовать, это все еще быстро при создании.Con: Это занимает еще больше памяти при копировании из Map в Arrays.

2. Я использую Arrays или, возможно, ArrayLists с самого начала и сохраняю там все Pro: минимум накладных расходов памяти.Con: это будет очень медленно, потому что мне придется сортировать / копировать массив каждый раз, когда добавляется новый ключ, а также мне нужно реализовать собственную (возможно, даже более медленную) сортировку, чтобы сохранить соответствующий массив int в том же порядке, какструны.Трудно реализовать

3. Я использую Массивы и MultivalueMap в качестве буфера.После того, как программа закончила 10% или 20% фазы создания, я добавлю значения в массивы и сохраню их в порядке, затем начну новую карту.Pro: Вероятно, все еще достаточно быстро и память достаточно эффективна.Против: Трудно реализовать.

Ни одно из этих решений на самом деле не подходит мне.Знаете ли вы какие-либо другие решения этой проблемы, возможно, реализацию карты с эффективным использованием памяти (MultiValue)?

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

Answer 1

Если вы переключились на мультикарту Guava - я понятия не имею, возможно ли это для вашего приложения - вы могли бы использовать Trove и получить

ListMultimap<String, Integer> multimap = Multimaps.newListMultimap(
  new HashMap<String, Collection<Integer>>(),
  new Supplier<List<Integer>>() {
    public List<Integer> get() {
      return new TIntListDecorator();
    }
  });

, что даст ListMultimap, который используетHashMap для сопоставления со List значениями, подкрепленными массивами int[], что должно быть эффективным с точки зрения памяти, хотя вы будете платить небольшой штраф speed из-за бокса.Возможно, вы сможете сделать нечто подобное для MultiValueMap, хотя я понятия не имею, из какой это библиотеки.

Answer 2

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

Вот код для работающей TrieMap.

Примечание: обычный совет по использованию EntrySet для итерации по Map s относится к не и применяется к Trie s.Они исключительно неэффективны в Trie, поэтому, пожалуйста, избегайте их запрашивать, если это вообще возможно.

/**
 * Implementation of a Trie structure.
 * 
 * A Trie is a compact form of tree that takes advantage of common prefixes
 * to the keys. 
 * 
 * A normal HashSet will take the key and compute a hash from it, this hash will
 * be used to locate the value through various methods but usually some kind
 * of bucket system is used. The memory footprint resulting becomes something
 * like O(n).
 * 
 * A Trie structure essentuially combines all common prefixes into a single key.
 * For example, holding the strings A, AB, ABC and ABCD will only take enough 
 * space to record the presence of ABCD. The presence of the others will be 
 * recorded as flags within the record of ABCD structure at zero cost.
 * 
 * This structure is useful for holding similar strings such as product IDs or
 * credit card numbers.
 *  
 */
public class TrieMap<V> extends AbstractMap<String, V> implements Map<String, V> {


  /**
   * Map each character to a sub-trie.
   * 
   * Could replace this with a 256 entry array of Tries but this will handle
   * multibyte character sets and I can discard empty maps. 
   * 
   * Maintained at null until needed (for better memory footprint).
   * 
   */
  protected Map<Character, TrieMap<V>> children = null;

  /**
   * Here we store the map contents.
   */
  protected V leaf = null;

  /**
   * Set the leaf value to a new setting and return the old one.
   * 
   * @param newValue
   * @return old value of leaf.
   */
  protected V setLeaf(V newValue) {
    V old = leaf;
    leaf = newValue;
    return old;
  }

  /**
   * I've always wanted to name a method something like this.
   */
  protected void makeChildren () {
    if ( children == null ) {
      // Use a TreeMap to ensure sorted iteration.
      children = new TreeMap<Character, TrieMap<V>>();
    }
  }

  /**
   * Finds the TrieMap that "should" contain the key.
   * 
   * @param key 
   * 
   * The key to find.
   * 
   * @param grow 
   * 
   * Set to true to grow the Trie to fit the key.
   * 
   * @return 
   * 
   * The sub Trie that "should" contain the key or null if key was not found and
   * grow was false.
   */
  protected TrieMap<V> find(String key, boolean grow) {
    if (key.length() == 0) {
      // Found it!
      return this;
    } else {
      // Not at end of string.
      if (grow) {
        // Grow the tree.
        makeChildren();
      }
      if (children != null) {
        // Ask the kids.
        char ch = key.charAt(0);
        TrieMap<V> child = children.get(ch);
        if (child == null && grow) {
          // Make the child.
          child = new TrieMap<V>();
          // Store the child.
          children.put(ch, child);
        }
        if (child != null) {
          // Find it in the child.
          return child.find(tail(key), grow);
        }
      }
    }
    return null;

  }

  /**
   * Remove the head (first character) from the string.
   * 
   * @param s
   * 
   * The string.
   * 
   * @return 
   * 
   * The same string without the first (head) character.
   * 
   */
  // Suppress warnings over taking a subsequence
  private String tail(String s) {
    return s.substring(1, s.length());
  }

  /**
   * 
   * Add a new value to the map.
   * 
   * Time footprint = O(s.length).
   * 
   * @param s
   * 
   * The key defining the place to add.
   * 
   * @param value
   * 
   * The value to add there.
   * 
   * @return
   * 
   * The value that was there, or null if it wasn't.
   * 
   */
  @Override
  public V put(String key, V value) {
    V old = null;

    // If empty string.
    if (key.length() == 0) {
      old = setLeaf(value);
    } else {
      // Find it.
      old = find(key, true).put("", value);
    }

    return old;
  }

  /**
   * Gets the value at the specified key position.
   * 
   * @param o
   * 
   * The key to the location.
   * 
   * @return 
   * 
   * The value at that location, or null if there is no value at that location.
   */
  @Override
  public V get(Object o) {
    V got = null;
    if (o != null) {
      String key = (String) o;
      TrieMap<V> it = find(key, false);
      if (it != null) {
        got = it.leaf;
      }
    } else {
      throw new NullPointerException("Nulls not allowed.");
    }
    return got;
  }

  /**
   * Remove the value at the specified location.
   * 
   * @param o
   * 
   * The key to the location.
   * 
   * @return 
   * 
   * The value that was removed, or null if there was no value at that location.
   */
  @Override
  public V remove(Object o) {
    V old = null;
    if (o != null) {
      String key = (String) o;
      if (key.length() == 0) {
        // Its me!
        old = leaf;
        leaf = null;
      } else {
        TrieMap<V> it = find(key, false);
        if (it != null) {
          old = it.remove("");
        }
      }
    } else {
      throw new NullPointerException("Nulls not allowed.");
    }
    return old;
  }

  /**
   * Count the number of values in the structure.
   * 
   * @return 
   * 
   * The number of values in the structure.
   */
  @Override
  public int size() {
    // If I am a leaf then size increases by 1.
    int size = leaf != null ? 1 : 0;
    if (children != null) {
      // Add sizes of all my children.
      for (Character c : children.keySet()) {
        size += children.get(c).size();
      }
    }
    return size;
  }

  /**
   * Is the tree empty?
   * 
   * @return 
   * 
   * true if the tree is empty.
   * false if there is still at least one value in the tree.
   */
  @Override
  public boolean isEmpty() {
    // I am empty if I am not a leaf and I have no children 
    // (slightly quicker than the AbstaractCollection implementation).
    return leaf == null && (children == null || children.isEmpty());
  }

  /**
   * Returns all keys as a Set.
   * 
   * @return 
   * 
   * A HashSet of all keys.
   * 
   * Note: Although it returns Set<S> it is actually a Set<String> that has been
   * home-grown because the original keys are not stored in the structure 
   * anywhere.
   */
  @Override
  public Set<String> keySet() {
    // Roll them a temporary list and give them a Set from it.
    return new HashSet<String>(keyList());
  }

  /**
   * List all my keys.
   * 
   * @return 
   * 
   * An ArrayList of all keys in the tree.
   * 
   * Note: Although it returns List<S> it is actually a List<String> that has been
   * home-grown because the original keys are not stored in the structure 
   * anywhere.
   * 
   */
  protected List<String> keyList() {
    List<String> contents = new ArrayList<String>();

    if (leaf != null) {
      // If I am a leaf, a null string is in the set.
      contents.add((String) "");
    }

    // Add all sub-tries.
    if (children != null) {
      for (Character c : children.keySet()) {
        TrieMap<V> child = children.get(c);
        List<String> childContents = child.keyList();
        for (String subString : childContents) {
          // All possible substrings can be prepended with this character.
          contents.add((String) (c + subString.toString()));
        }
      }
    }

    return contents;
  }

  /**
   * Does the map contain the specified key.
   * 
   * @param key
   * 
   * The key to look for.
   * 
   * @return 
   * 
   * true if the key is in the Map.
   * false if not.
   */
  public boolean containsKey(String key) {
    TrieMap<V> it = find(key, false);
    if (it != null) {
      return it.leaf != null;
    }
    return false;
  }

  /**
   * Represent me as a list.
   * 
   * @return 
   * 
   * A String representation of the tree.
   */
  @Override
  public String toString() {
    List<String> list = keyList();
    //Collections.sort((List<String>)list);
    StringBuilder sb = new StringBuilder();
    Separator comma = new Separator(",");
    sb.append("{");
    for (String s : list) {
      sb.append(comma.sep()).append(s).append("=").append(get(s));
    }
    sb.append("}");
    return sb.toString();
  }

  /**
   * Clear down completely.
   */
  @Override
  public void clear() {
    children = null;
    leaf = null;
  }

  /**
   * Return a list of key/value pairs.
   * 
   * @return 
   * 
   * The entry set.
   */
  public Set<Map.Entry<String, V>> entrySet() {
    Set<Map.Entry<String, V>> entries = new HashSet<Map.Entry<String, V>>();
    List<String> keys = keyList();
    for (String key : keys) {
      entries.add(new Entry<String,V>(key, get(key)));
    }
    return entries;
  }

  /**
   * An entry.
   * 
   * @param <S>
   * 
   * The type of the key.
   * 
   * @param <V> 
   * 
   * The type of the value.
   */
  private static class Entry<S, V> implements Map.Entry<S, V> {

    protected S key;
    protected V value;

    public Entry(S key, V value) {
      this.key = key;
      this.value = value;
    }

    public S getKey() {
      return key;
    }

    public V getValue() {
      return value;
    }

    public V setValue(V newValue) {
      V oldValue = value;
      value = newValue;
      return oldValue;
    }

    @Override
    public boolean equals(Object o) {
      if (!(o instanceof TrieMap.Entry)) {
        return false;
      }
      Entry e = (Entry) o;
      return (key == null ? e.getKey() == null : key.equals(e.getKey()))
              && (value == null ? e.getValue() == null : value.equals(e.getValue()));
    }

    @Override
    public int hashCode() {
      int keyHash = (key == null ? 0 : key.hashCode());
      int valueHash = (value == null ? 0 : value.hashCode());
      return keyHash ^ valueHash;
    }

    @Override
    public String toString() {
      return key + "=" + value;
    }
  }
}

Answer 3

Сначала рассмотрим память, занятую целыми числами.Вы сказали, что диапазон будет около 0-4000000.24 бита достаточно для представления 16777216 различных значений.Если это приемлемо, вы можете использовать байтовые массивы для целых чисел с 3 байтами на целое число и сэкономить 25%.Вам нужно будет индексировать в массиве что-то вроде этого:

int getPackedInt(byte[] array, int index) {
  int i = index*3;
  return ((array[i] & 0xFF)<<16) + ((array[i+1] & 0xFF) <<8) + (array[i+2] & 0xFF);
}
int storePackedInt(byte[] array, int index, int value) {
  assert value >= 0 && value <= 0xFFFFFF;
  int i = index*3;
  array[i]   = (byte)((value>>16) & 0xFF);
  array[i+1] = (byte)((value>>8)  & 0xFF);
  array[i+2] = (byte)(value & 0xFF);
}

Можете ли вы что-нибудь сказать о распределении целых чисел?Если многие из них уместятся в 16 бит, вы можете использовать кодировку с переменным числом байтов на число (что-то вроде UTF-8 для представления символов).

Далее, подумайте, можете ли вы сэкономить память наСтруны.Каковы характеристики струн?Как долго они обычно будут?Будет ли много строк иметь префиксы?Схема сжатия, адаптированная к характеристикам вашего приложения, может сэкономить много места (как указал falsarella).ИЛИ, если многие строки будут иметь общие префиксы, хранение их в некотором типе поиска может быть более эффективным.(Существует тип дерева, называемый «patricia», который может подойти для этого приложения.) В качестве бонуса обратите внимание, что поиск строк в дереве может быть быстрее , чем поиск по хеш-карте (хотя вы 'Мне нужно провести тестирование, чтобы увидеть, так ли это в вашем приложении).

Будут ли все строки ASCII?Если это так, 50% памяти, используемой для строк, будет потрачено впустую, поскольку Java char составляет 16 бит.Опять же, в этом случае вы можете рассмотреть возможность использования байтовых массивов.

Если вам нужно только искать строки, а не перебирать сохраненные строки, вы также можете рассмотреть что-то довольно необычное: хеширование строк и сохранение толькохешПоскольку разные строки могут хэшировать одно и то же значение, существует вероятность того, что строка, которая никогда не сохранялась, все равно может быть «найдена» при поиске.Но если вы используете достаточно битов для хеш-значения (и хорошей хеш-функции), вы можете сделать этот шанс настолько бесконечно малым, что он почти наверняка никогда не случится в течение предполагаемой продолжительности жизни вселенной.

Наконец, естьэто память для самой структуры, которая содержит строки и целые числа.Я уже предлагал использовать trie, но если вы решите не делать этого, ничто не будет использовать меньше памяти, чем параллельные массивы - один отсортированный массив строк (по которому вы можете выполнять бинарный поиск, как вы сказали) и параллельный массивмассивы целых чисел.После того, как вы выполните двоичный поиск, чтобы найти индекс в массиве String, вы можете использовать тот же индекс для доступа к массиву array-of-integer.

Если вы строите структуру, если вы решите, чтоSearch Trie - хороший выбор, я бы использовал это напрямую.В противном случае вы могли бы сделать 2 прохода: один для создания набора строк (затем поместить их в массив и отсортировать их), а второй - для добавления массивов целых чисел.

Answer 4

Вы можете использовать сжатые строки , чтобы значительно сократить использование памяти.

• Параметры для настройки вашей JVM
• Сравнение его использования между различными версиями Java

Кроме того, есть другие более радикальные решения (это потребует некоторой повторной реализации):

• Реализация списка на основе памяти или предложения по базе данных NoSQL .

Answer 5

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

Рассмотримиспользование Map из String в одной из множества IntArrayList реализаций, плавающих вокруг (например, в Colt или в примитивных коллекциях для Java ), которые в основном реализуютСписок, поддерживаемый массивом int , а не массивом экземпляров Integer.