python - functions - La propiedad más eficiente de hash para numpy array

pip install numpy

Question

Necesito poder almacenar una array numpy en un dict para propósitos de caché. La velocidad del hash es importante.

La array representa indicios, por lo tanto, aunque la identidad real del objeto no es importante, el valor sí lo es. La mutablidad no es una preocupación, ya que solo estoy interesado en el valor actual.

¿Qué debería hash para almacenarlo en un dict ?

Mi enfoque actual es usar str(arr.data) , que es más rápido que md5 en mi prueba.

He incorporado algunos ejemplos de las respuestas para tener una idea de los tiempos relativos:

In [121]: %timeit hash(str(y))
10000 loops, best of 3: 68.7 us per loop

In [122]: %timeit hash(y.tostring())
1000000 loops, best of 3: 383 ns per loop

In [123]: %timeit hash(str(y.data))
1000000 loops, best of 3: 543 ns per loop

In [124]: %timeit y.flags.writeable = False ; hash(y.data)
1000000 loops, best of 3: 1.15 us per loop

In [125]: %timeit hash((b*y).sum())
100000 loops, best of 3: 8.12 us per loop

Parece que para este caso de uso particular (pequeñas matrices de indicios), arr.tostring ofrece el mejor rendimiento.

Mientras que el hash del búfer de solo lectura es rápido por sí mismo, la sobrecarga de establecer el indicador de escritura realmente lo hace más lento.

Answer 1

¿Qué tipo de información tienes?

• array-size
• ¿Tiene un índice varias veces en la matriz

Si su matriz solo consiste en permutación de índices, puede usar una conversión de base

(1, 0, 2) -> 1 * 3**0 + 0 * 3**1 + 2 * 3**2 = 10(base3)

y usa ''10'' como hash_key vía

import numpy as num

base_size = 3
base = base_size ** num.arange(base_size)
max_base = (base * num.arange(base_size)).sum()

hashed_array = (base * array).sum()

Ahora puede usar una matriz (shape = (base_size,)) en lugar de una dict para acceder a los valores.

Answer 2

Llegando tarde a la fiesta, pero para arreglos grandes, creo que una buena manera de hacerlo es submuestrear aleatoriamente la matriz y hash esa muestra:

def subsample_hash(a):
    rng = np.random.RandomState(89)
    inds = rng.randint(low=0, high=a.size, size=1000)
    b = a.flat[inds]
    b.flags.writeable = False
    return hash(b.data)

Creo que esto es mejor que hacer hash(str(a)) , porque este último podría confundir las matrices que tienen datos únicos en el medio pero ceros alrededor de los bordes.

Answer 3

Puede probar xxhash través de su enlace de Python . Para arreglos grandes, esto es mucho más rápido que hash(x.tostring()) .

Ejemplo de sesión de IPython:

>>> import xxhash
>>> import numpy
>>> x = numpy.random.rand(1024 * 1024 * 16)
>>> h = xxhash.xxh64()
>>> %timeit hash(x.tostring())
1 loops, best of 3: 208 ms per loop
>>> %timeit h.update(x); h.intdigest(); h.reset()
100 loops, best of 3: 10.2 ms per loop

Y, por cierto, en varios blogs y respuestas publicadas en , verá gente usando sha1 o md5 como funciones hash. Por razones de rendimiento, esto generalmente no es aceptable, ya que esas funciones hash "seguras" son bastante lentas. Son útiles solo si la colisión hash es una de las principales preocupaciones.

Sin embargo, las colisiones hash suceden todo el tiempo. Y si todo lo que necesita es implementar __hash__ para los objetos de matriz de datos para que puedan usarse como claves en los diccionarios o conjuntos de Python, creo que es mejor concentrarse en la velocidad de __hash__ y dejar que Python maneje la colisión hash [1].

[1] También es posible que necesites anular __eq__ para ayudar a Python a gestionar la colisión hash. __eq__ que __eq__ devolviera un booleano, en lugar de una matriz de booleanos, como lo hace numpy .

Answer 4

Simplemente puede hash el búfer subyacente, si lo hace de solo lectura:

>>> a = random.randint(10, 100, 100000)
>>> a.flags.writeable = False
>>> %timeit hash(a.data)
100 loops, best of 3: 2.01 ms per loop
>>> %timeit hash(a.tostring())
100 loops, best of 3: 2.28 ms per loop

Para arreglos muy grandes, hash(str(a)) es mucho más rápido, pero solo toma una pequeña parte de la matriz en cuenta.

>>> %timeit hash(str(a))
10000 loops, best of 3: 55.5 us per loop
>>> str(a)
''[63 30 33 ..., 96 25 60]''