memoria multivaluemap eficiente

Question

Hola tengo el siguiente problema: Estoy almacenando cuerdas y una lista correspondiente de valores enteros en una MultiValueMap<String, Integer> Estoy almacenando cerca de 13 000 000 millones de cuerdas y una cadena puede tener hasta 500 o más valores. Por cada valor individual tendré acceso aleatorio en el Mapa. El peor de los casos son 13 000 000 * 500 llamadas al público. Ahora la velocidad del mapa es buena, pero la carga de la memoria es bastante alta. A MultiValueMap<String, Integer> no es nada más que un HashMap/TreeMap<String, <ArrayList<Integer>>. Tanto HashMap como TreeMap tienen mucha memoria por encima. No modificaré el mapa una vez que lo haya hecho, pero necesito que sea lo más rápido posible para el acceso aleatorio en un programa. (Lo estoy almacenando en el disco y lo estoy cargando al inicio, el archivo de mapa serializado ocupa unos 600 MB pero en la memoria es de aproximadamente 3 gb)

Lo más eficiente en cuanto a la memoria sería almacenar el String en una matriz ordenada y tienen una matriz int bidimensional correspondiente para los valores. Entonces el acceso sería una búsqueda binaria en la matriz de cadenas y obtener los valores correspondientes.

Ahora tienen tres maneras de llegar:

1. Puedo usar un MultivalueMap ordenados (TreeMap) para la fase de creación para almacenar everything.After he terminado con la obtención de todos los valores, me sale la cadena array llamando al map.keyset().toArray(new String[0]); Crea una matriz int bidimensional y obtén todos los valores del mapa de valores múltiples. Pro: es fácil de implementar, todavía es rápido durante la creación. Con: Ocupa más memoria aún durante la copia de Map a Arrays.

2. Uso Arrays o ArrayLists desde el principio y almaceno todo allí Pro: menos sobrecarga de memoria. Con: esto sería enormemente lento porque tendría que ordenar/copiar la matriz cada vez que agregue una nueva clave, también tendría que implementar mi propia clasificación (incluso más lenta) para mantener la matriz int correspondiente en el mismo orden como las cuerdas. Difícil de implementar

3. Utilizo Arrays y un MultivalueMap como búfer. Después de que el programa finalizó el 10% o el 20% de la fase de creación, agregaré los valores a las matrices y los mantendré en orden, luego comenzaré un nuevo mapa. Pro: Propaga lo suficientemente rápido y lo suficientemente eficiente desde el punto de vista de la memoria. Con: Difícil de implementar.

Ninguna de estas soluciones realmente me parece correcta. ¿Conoces otras soluciones a este problema, tal vez una implementación de mapas con memoria eficiente (MultiValue)?

Sé que podría estar utilizando una base de datos, así que no se moleste en publicarla como respuesta. Quiero saber cómo podría hacer esto sin usar una base de datos.

Answer 1

Dependiendo de los valores de enteros que almacene en su mapa, una gran cantidad de su sobrecarga de memoria puede ser causada por tener distintas instancias de entero, que ocupan mucha más memoria RAM que un valor int primitivo.

Considere el uso de un Map de String a uno de los muchos IntArrayList implementaciones que flotan alrededor (por ejemplo, en Colt o en primitivas colecciones de Java), que básicamente implementar una lista apoyada por una matriz int, en lugar de un ser respaldado por una matriz de instancias de entero.

Answer 2

Puede usar compressed strings para reducir drásticamente el uso de memoria.

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

Además, no son other soluciones más drásticas (sería requieren algún reimplementación):

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

Answer 3

Si pasa al Multimapa Guava - No tengo ni idea de si eso es posible para su aplicación - que podría ser capaz de utilizar Trove y obtener

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

que hará una ListMultimap que utiliza una HashMap para asignar a List valores respaldados por matrices int[], que deberían ser eficientes en la memoria, aunque pagará una pequeña penalización de a causa del boxeo. Es posible que pueda hacer algo similar para MultiValueMap, aunque no tengo idea de qué biblioteca es.

Answer 4

Primero, considere la memoria tomada por los enteros. Usted dijo que el rango será de aproximadamente 0-4000000. 24 bits es suficiente para representar 16777216 valores distintos. Si eso es aceptable, podría usar matrices de bytes para los enteros, con 3 bytes por entero, y guardar el 25%. Tendría que indexar en la matriz algo como esto:

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

¿Puede decir algo acerca de la distribución de los números enteros? Si muchos de ellos caben en 16 bits, podría usar una codificación con un número variable de bytes por número (algo como lo hace UTF-8 para representar caracteres).

A continuación, considere si puede guardar memoria en las cadenas. ¿Cuáles son las características de las cuerdas? ¿Cuánto tiempo típicamente serán? ¿Varias cadenas compartirán prefijos? Un esquema de compresión adaptado a las características de su aplicación podría ahorrar mucho espacio (como señaló falsarella). O bien, si muchas cadenas compartirán prefijos, almacenarlos en algún tipo de búsqueda podría ser más eficiente. (Hay un tipo de trie llamado "patricia" que podría ser adecuado para esta aplicación.) Como una ventaja, tenga en cuenta que la búsqueda de cadenas en un trie puede ser más rápido que buscar un mapa hash (aunque tendría que comparar para ver si eso es cierto en tu aplicación).

¿Todas las cadenas serán ASCII? Si es así, se desperdiciará el 50% de la memoria utilizada para Strings, ya que Java char es de 16 bits. De nuevo, en este caso, podría considerar el uso de matrices de bytes.

Si solo necesita buscar Cadenas, no iterar sobre las Cadenas almacenadas, también podría considerar algo poco convencional: cortar las Cadenas, y mantener solo el hash. Dado que diferentes String pueden hacer hash con el mismo valor, existe la posibilidad de que una Cadena que nunca fue almacenada, aún pueda ser "encontrada" por una búsqueda. Pero si usa suficientes bits para el valor hash (y una buena función hash), puede hacer que esa posibilidad sea tan infinitesimalmente pequeña que casi nunca pasará en la vida estimada del universo.

Finalmente, está la memoria para la estructura en sí misma, que contiene las cadenas y los enteros.Ya sugerí usar un trie, pero si decides no hacer eso, nada usará menos memoria que las matrices paralelas: una matriz ordenada de cadenas (en la que puedes hacer búsquedas binarias, como dijiste), y una matriz paralela de matrices de enteros. Después de realizar una búsqueda binaria para encontrar un índice en la matriz de cadenas, puede usar el mismo índice para acceder a la matriz de matriz de enteros.

Mientras construye la estructura, si decide que una búsqueda es una buena opción, la usaría directamente. De lo contrario, podría hacer 2 pases: uno para construir un conjunto de cadenas (luego colocarlas en una matriz y ordenarlas), y una segunda pasada para agregar las matrices de números enteros.

Answer 5

Si hay patrones para sus cadenas de teclas, especialmente las raíces comunes, entonces a a Trie podría ser un método eficaz para almacenar una cantidad significativamente menor de datos.

Aquí está el código para un TrieMap de trabajo.

NB: El consejo habitual en el uso de EntrySet para iterar a través de Map s ¿Se aplica no a Trie s. Son excepcionalmente ineficientes en un Trie así que por favor evite solicitar uno si es posible.

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