pamięci wydajny multivaluemap

Question

Witam Mam następujący problem: mam przechowywania łańcuchów i odpowiednią listę wartości całkowitych w MultiValueMap<String, Integer> mam przechowującej około 13 000 000 mln struny i jeden łańcuch może mieć do 500 lub więcej wartości. Dla każdej pojedynczej wartości będę mieć dostęp losowy na mapie. Najgorszy przypadek to 13 000 000 * 500 połączeń. Teraz prędkość mapy jest dobra, ale obciążenie pamięci staje się dość wysokie. A MultiValueMap<String, Integer> to nic innego niż HashMap/TreeMap<String, <ArrayList<Integer>>. Zarówno HashMap, jak i TreeMap mają sporo pamięci narzutowej. Nie będę modyfikował mapy po jej zakończeniu, ale potrzebuję jej, aby była szybka i jak najmniejsza dla losowego dostępu w programie. (Przechowuję go na dysku i ładuję go na starcie, zserializowany plik mapy zajmuje około 600mb, ale w pamięci to około 3gb?)

najbardziej wydajna pamięć to przechowywanie ciągu w posortowanej tablicy ciągów i mają odpowiednią dwuwymiarową tablicę int dla wartości. Zatem dostęp byłby wyszukiwaniem binarnym w tablicy łańcuchów i uzyskiwaniem odpowiednich wartości.

Teraz mam trzy sposoby, aby się tam dostać:

1. używam posortowane MultivalueMap (TreeMap) dla fazy tworzenia do przechowywania everything.After skończę z uzyskaniem wszystkich wartości, pojawia się napis array, wywołując map.keyset().toArray(new String[0]); Utwórz dwuwymiarową tablicę int i uzyskaj wszystkie wartości z multivaluemap. Pro: Jest łatwy w implementacji, jest nadal szybki podczas tworzenia. Con: Zajmuje jeszcze więcej pamięci podczas kopiowania z mapy na tablice.

2. Używam tablic lub może ArrayLists od początku i przechowywać wszystko tam Pro: najmniej narzut pamięci. Con: Byłoby to bardzo powolne, ponieważ musiałbym sortować/kopiować tablicę za każdym razem, gdy dodam nowy klucz, również musiałbym wdrożyć własne (prawdopodobnie nawet wolniejsze) sortowanie, aby zachować odpowiednią tablicę int w tej samej kolejności jak struny. Trudno wdrożyć

3. Używam Tablic i MultivalueMap jako bufora. Po zakończeniu programu 10% lub 20% fazy tworzenia, dodam wartości do Tablic i utrzymam je w porządku, a następnie rozpocznę nową Mapę. Pro: Proponuje się wystarczająco szybko i pamięć jest wystarczająco wydajna. Con: Trudne do wdrożenia.

Żadne z tych rozwiązań naprawdę nie wydaje mi się właściwe. Czy znasz jakieś inne rozwiązania tego problemu, być może implementacja mapy o dużej wydajności pamięci (MultiValue)?

Wiem, że mógłbym używać bazy danych, więc nie zawracaj sobie głowy umieszczaniem jej jako odpowiedzi. Chcę wiedzieć, jak mógłbym to zrobić bez korzystania z bazy danych.

Answer 1

W zależności od tego, które wartości całkowite przechowujesz na mapie, duża część narzutu pamięci sterty może być spowodowana przez oddzielne instancje Integer, które zajmują o wiele więcej pamięci RAM niż pierwotna wartość int.

Rozważ używanie Map od String do jednej z wielu IntArrayList implementacji pływających wokół (np Colt lub w Pierwotne kolekcje Java), które w zasadzie implementują listy poparte int tablicy, zamiast bycie wspieranym przez tablicę instancji Integer.

Answer 2

Można użyć compressed strings, aby znacznie zmniejszyć zużycie pamięci.

• Parameters to configure your JVM
• Comparison of its usage between various java versions

Ponadto istnieją other bardziej drastyczne rozwiązania (to wymaga pewnej powtórną implementację)

• Memory-disk based list implementation lub suggestions about NoSQL database.

Answer 3

Jeśli włączony do guawy za Multimap - Nie mam pojęcia, czy to możliwe dla danego zastosowania - może być w stanie używać Trove i dostać

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

który dokona ListMultimap który wykorzystuje HashMap do mapowania na wartości List z macierzami int[], które powinny być wydajne pod względem pamięci, jednak zapłacisz niewielką karę z szybkością z powodu boksowania. Być może będziesz w stanie zrobić coś podobnego dla MultiValueMap, ale nie mam pojęcia, z której biblioteki pochodzi.

Answer 4

Po pierwsze, rozważ pamięć pobraną przez liczby całkowite. Powiedziałeś, że zakres będzie wynosił około 0-4000000. 24 bity wystarczają do reprezentowania 16777216 odrębnych wartości. Jeśli jest to dopuszczalne, możesz użyć tablic bajtowych dla liczb całkowitych z 3 bajtami na liczbę całkowitą i zaoszczędzić 25%. Będziesz musiał indeksować tablicę w następujący sposób:

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); 
} 

Czy możesz powiedzieć coś o dystrybucji liczb całkowitych? Jeśli wiele z nich mieści się w 16 bitach, możesz użyć kodowania ze zmienną liczbą bajtów na liczbę (coś w stylu UTF-8 do reprezentowania znaków).

Następnie zastanów się, czy możesz zapisać pamięć w Ciągach. Jakie są cechy Strings? Jak długo będą one zazwyczaj? Czy wiele ciągów ma wspólne prefiksy? Schemat kompresji dostosowany do charakterystyki twojej aplikacji może zaoszczędzić dużo miejsca (jak zauważyła falsarella). LUB, jeśli wiele ciągów podzieli się prefiksami, przechowywanie ich w jakimś typie wyszukiwania może być bardziej wydajne. (Jest taki typ triety zwany "patricia", który może być odpowiedni dla tej aplikacji.) Jako bonus, zauważ, że wyszukiwanie napisów w trie może być szybsze niż wyszukiwanie mapy haszującej (chociaż musisz wykonać test porównawczy aby sprawdzić, czy jest to prawdą w twojej aplikacji).

Czy wszystkie ciągi będą miały kod ASCII? Jeśli tak, 50% pamięci używanej dla Strings zostanie zmarnowane, ponieważ Java char ma 16 bitów. Ponownie, w tym przypadku można rozważyć użycie tablic bajtowych.

Jeśli potrzebujesz tylko spojrzeć na Strings, nie powtarzaj nad zapisanymi Strunami, możesz również rozważyć coś niekonwencjonalnego: haszować Struny i zachować tylko skrót. Ponieważ inny ciąg może mieszać do tej samej wartości, istnieje szansa, że ​​ciąg, który nigdy nie był przechowywany, może zostać "znaleziony" przez wyszukiwanie. Ale jeśli użyjesz wystarczającej ilości bitów do wartości mieszania (i dobrej funkcji mieszania), możesz sprawić, że ta szansa będzie tak mała, że ​​prawie na pewno nigdy nie stanie się w szacowanej długości życia wszechświata.

Wreszcie jest pamięć dla samej struktury, która zawiera ciągi i liczby całkowite.Już zasugerowałem użycie trie, ale jeśli zdecydujesz się tego nie robić, nic nie będzie zużywało mniej pamięci niż tablice równoległe - jedna posortowana tablica łańcuchów (którą możesz zrobić, tak jak powiedziałeś, binarne wyszukiwanie) i równoległy układ tablice liczb całkowitych. Po wykonaniu wyszukiwania binarnego w celu odnalezienia indeksu w tablicy String można użyć tego samego indeksu, aby uzyskać dostęp do tablicy tablic całkowitej.

Podczas budowania struktury, jeśli zdecydujesz, że wyszukiwanie jest dobrym wyborem, po prostu skorzystam z tego bezpośrednio. W przeciwnym razie możesz wykonać 2 przebiegi: jeden, aby zbudować zestaw łańcuchów (następnie umieścić je w tablicy i posortować), a drugi przejść, aby dodać tablice liczb całkowitych.

Answer 5

Jeśli istnieją wzorce dla twoich kluczy, szczególnie wspólnych korzeni, to może być skuteczną metodą przechowywania znacznie mniej danych.

Oto kod dla działającej aplikacji TrieMap.

Uwaga: zwykle porady na temat używania EntrySet iteracyjne całej Map s ma nie dotyczą Trie s. Są wyjątkowo nieefektywne w wersji Trie, więc należy unikać żądania, jeśli to w ogóle możliwe.

/** 
* 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; 
    } 
    } 
}