java - móviles - manual de programacion android pdf

Almacén de clave-valor eficiente en memoria de Java en la memoria

Question

Tengo una tienda de 111 millones de pares clave-valor (una clave puede tener múltiples valores, un máximo de 2/3) cuya clave son los enteros de 50 bits y los valores enteros de 32 bits (máximo). Ahora, mis requisitos son:

1. Inserción rápida de par (clave, valor) [que permite duplicados]
2. Recuperación rápida de valores / valores basados ​​en la clave.

Aquí se ofrece una buena solución basada en MultiMap. Sin embargo, quiero almacenar más pares de clave-valor en la memoria principal sin penalización de rendimiento. Estudié de artículos web que B + Tree, R + Tree, B Tree, Compact Multimap, etc. pueden ser una buena solución para eso. Alguien puede ayudarme:

¿Hay alguna biblioteca de Java que satisfaga todas mis necesidades de manera adecuada (antes mencionado / otros DS también son aceptables, no hay problema con eso)? En realidad, quiero una estructura de datos de biblioteca java eficiente para almacenar / recuperar pares clave-valor / valores, lo que requiere menos memoria y debe construirse en la memoria.

NB: Lo he intentado con HashMultiMap (Guava con algunas modificaciones con trove) mencionado por Louis Wasserman, Kyoto / Tokyo Cabinet, etc. Mi experiencia no es buena con las soluciones de disco. Así que por favor evita eso :). Otro punto es que, para elegir library / ds, un punto importante es: las claves son 50 bit (por lo que si asignamos 64bit) se perderán 14 bit y los valores 32 bit Int (máximo) - en su mayoría son 10-12-14 bits. Entonces, podemos ahorrar espacio allí también.

Answer 1

Basado en la solución de @Tom Anderson, eliminé la necesidad de asignar objetos y agregué una prueba de rendimiento.

import java.util.Arrays;
import java.util.Random;

public class LongIntParallelHashMultimap {
    private static final long NULL = Long.MIN_VALUE;

    private final long[] keys;
    private final int[] values;
    private int size;

    public LongIntParallelHashMultimap(int capacity) {
        keys = new long[capacity];
        values = new int[capacity];
        Arrays.fill(keys, NULL);
    }

    public void put(long key, int value) {
        if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL);
        if (size == keys.length) throw new IllegalStateException("map is full");

        int index = indexFor(key);
        while (keys[index] != NULL) {
            index = successor(index);
        }
        keys[index] = key;
        values[index] = value;
        ++size;
    }

    public int get(long key, int[] hits) {
        if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL);

        int index = indexFor(key);

        int hitIndex = 0;

        while (keys[index] != NULL) {
            if (keys[index] == key) {
                hits[hitIndex] = values[index];
                ++hitIndex;
                if (hitIndex == hits.length)
                    break;
            }
            index = successor(index);
        }

        return hitIndex;
    }

    private int indexFor(long key) {
        return Math.abs((int) (key % keys.length));
    }

    private int successor(int index) {
        index++;
        return index >= keys.length ? index - keys.length : index;
    }

    public int size() {
        return size;
    }

    public static class PerfTest {
        public static void main(String... args) {
            int values = 110* 1000 * 1000;
            long start0 = System.nanoTime();
            long[] keysValues = generateKeys(values);

            LongIntParallelHashMultimap map = new LongIntParallelHashMultimap(222222227);
            long start = System.nanoTime();
            addKeyValues(values, keysValues, map);
            long mid = System.nanoTime();
            int sum = lookUpKeyValues(values, keysValues, map);
            long time = System.nanoTime();
            System.out.printf("Generated %.1f M keys/s, Added %.1f M/s and looked up %.1f M/s%n",
                    values * 1e3 / (start - start0), values * 1e3 / (mid - start), values * 1e3 / (time - mid));
            System.out.println("Expected " + values + " got " + sum);
        }

        private static long[] generateKeys(int values) {
            Random rand = new Random();
            long[] keysValues = new long[values];
            for (int i = 0; i < values; i++)
                keysValues[i] = rand.nextLong();
            return keysValues;
        }

        private static void addKeyValues(int values, long[] keysValues, LongIntParallelHashMultimap map) {
            for (int i = 0; i < values; i++) {
                map.put(keysValues[i], i);
            }
            assert map.size() == values;
        }

        private static int lookUpKeyValues(int values, long[] keysValues, LongIntParallelHashMultimap map) {
            int[] found = new int[8];
            int sum = 0;
            for (int i = 0; i < values; i++) {
                sum += map.get(keysValues[i], found);
            }
            return sum;
        }
    }
}

huellas dactilares

Generated 34.8 M keys/s, Added 11.1 M/s and looked up 7.6 M/s

Ejecutar en un i7 de 3.8 GHz con la actualización 3 de Java 7.

Esto es mucho más lento que la prueba anterior porque está accediendo a la memoria principal, en lugar de a la caché al azar. Esto es realmente una prueba de la velocidad de tu memoria. Las escrituras son más rápidas porque pueden realizarse de forma asíncrona a la memoria principal.

Usando esta colección

final SetMultimap<Long, Integer> map = Multimaps.newSetMultimap(
        TDecorators.wrap(new TLongObjectHashMap<Collection<Integer>>()),
        new Supplier<Set<Integer>>() {
            public Set<Integer> get() {
                return TDecorators.wrap(new TIntHashSet());
            }
        });

Ejecutando la misma prueba con 50 millones de entradas (que usaron alrededor de 16 GB) y -mx20g el siguiente resultado.

 Generated 47.2 M keys/s, Added 0.5 M/s and looked up 0.7 M/s

Para las entradas de 110 M, necesitará alrededor de 35 GB de memoria y una máquina 10 veces más rápida que la mía (3,8 GHz) para realizar 5 millones de adiciones por segundo.

Answer 2

¿Hay alguna biblioteca de Java que satisfaga todas mis necesidades adecuadamente?

AFAIK no. O al menos, no uno que minimice la huella de memoria.

Sin embargo, debería ser fácil escribir una clase de mapa personalizada que esté especializada para estos requisitos.

Answer 3

Es una buena idea buscar bases de datos, porque problemas como estos son para lo que están diseñados. En los últimos años, las bases de datos de valores clave se hicieron muy populares, por ejemplo, para los servicios web (palabra clave "NoSQL"), por lo que debería encontrar algo.

La elección de una estructura de datos personalizada también depende de si desea utilizar un disco duro para almacenar sus datos (y qué tan seguro debe ser) o si se perdió por completo al salir del programa.

Si la implementación manual y todo el DB se ajusta con facilidad a la memoria, implementaría un hashmap en C. Cree una función hash que proporcione una dirección de memoria (bien dispersa) desde un valor. Insertar allí o al lado si ya está asignado. Asignar y recuperar es entonces O (1). Si lo implementa en Java, tendrá la sobrecarga de 4 bytes para cada objeto (primitivo).

Answer 4

Si debe usar Java, implemente su propio hashmap / hashmap. Una propiedad importante de su tabla es usar una lista enlazada para manejar colisiones. Por lo tanto, cuando realiza una búsqueda, puede devolver todos los elementos en la lista.

Answer 5

No creo que haya nada en el JDK que pueda hacer esto.

Sin embargo, implementar tal cosa es una simple cuestión de programación. Aquí hay una tabla hash abierta con sondeo lineal, con claves y valores almacenados en matrices paralelas:

public class LongIntParallelHashMultimap {

    private static final long NULL = 0L;

    private final long[] keys;
    private final int[] values;
    private int size;

    public LongIntParallelHashMultimap(int capacity) {
        keys = new long[capacity];
        values = new int[capacity];
    }

    public void put(long key, int value) {
        if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL);
        if (size == keys.length) throw new IllegalStateException("map is full");

        int index = indexFor(key);
        while (keys[index] != NULL) {
            index = successor(index);
        }
        keys[index] = key;
        values[index] = value;
        ++size;
    }

    public int[] get(long key) {
        if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL);

        int index = indexFor(key);
        int count = countHits(key, index);

        int[] hits = new int[count];
        int hitIndex = 0;

        while (keys[index] != NULL) {
            if (keys[index] == key) {
                hits[hitIndex] = values[index];
                ++hitIndex;
            }
            index = successor(index);
        }

        return hits;
    }

    private int countHits(long key, int index) {
        int numHits = 0;
        while (keys[index] != NULL) {
            if (keys[index] == key) ++numHits;
            index = successor(index);
        }
        return numHits;
    }

    private int indexFor(long key) {
        // the hashing constant is (the golden ratio * Long.MAX_VALUE) + 1
        // see The Art of Computer Programming, section 6.4
        // the constant has two important properties:
        // (1) it is coprime with 2^64, so multiplication by it is a bijective function, and does not generate collisions in the hash
        // (2) it has a 1 in the bottom bit, so it does not add zeroes in the bottom bits of the hash, and does not generate (gratuitous) collisions in the index
        long hash = key * 5700357409661598721L;
        return Math.abs((int) (hash % keys.length));
    }

    private int successor(int index) {
        return (index + 1) % keys.length;
    }

    public int size() {
        return size;
    }

}

Tenga en cuenta que esta es una estructura de tamaño fijo. Tendrá que crearlo lo suficientemente grande como para contener todos sus datos: 110 millones de entradas para mí ocupan 1,32 GB. Cuanto más grande lo hagas, en exceso de lo que necesitas para almacenar los datos, más rápido serán las inserciones y las búsquedas. Descubrí que para 110 millones de entradas, con un factor de carga de 0,5 (2,64 GB, el doble de espacio que se necesita), tardó 403 nanosegundos en buscar una clave, pero con un factor de carga de 0,75 (1,76 GB, una un tercer espacio más de lo que se necesita), tomó 575 nanosegundos. Disminuir el factor de carga por debajo de 0.5 generalmente no hace mucha diferencia, y de hecho, con un factor de carga de 0.33 (4.00 GB, tres veces más espacio de lo necesario), obtengo un tiempo promedio de 394 nanosegundos. Entonces, aunque tenga 5 GB disponibles, no lo use todo.

Tenga en cuenta también que cero no está permitido como una clave. Si esto es un problema, cambie el valor nulo para que sea otra cosa, y prellene la matriz de claves con eso en la creación.

Answer 6

Podría ser que estoy atrasado en responder esta pregunta, pero la búsqueda elástica resolverá su problema.