Proprietà più efficiente dell'hash per l'array numpy

Question

Devo essere in grado di memorizzare uno numpyarray in un dict per scopi di memorizzazione nella cache. La velocità hash è importante.

Il array rappresenta gli indici, quindi mentre l'identità effettiva dell'oggetto non è importante, il valore è. La mutabilità non è una preoccupazione, perché sono interessato solo al valore attuale.

Cosa devo fare per memorizzarlo in un dict?

Il mio approccio attuale è quello di utilizzare str(arr.data), che è più veloce di md5 nei miei test.

---

Ho incorporato alcuni esempi delle risposte per avere un'idea dei tempi relativi:

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 

sembrerebbe che per questo particolare caso d'uso (piccoli array di indicies), offre la arr.tostring la prestazione migliore.

Mentre l'hashing del buffer di sola lettura è veloce da solo, il sovraccarico dell'impostazione del flag scrivibile lo rende effettivamente più lento.

Answer 1

Si può semplicemente hash il buffer sottostante, se si rendono sola lettura:

>>> 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 

Per le matrici molto grandi, hash(str(a)) è molto più veloce, ma poi ci vuole solo una piccola parte della matrice in account.

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

Answer 2

Che tipo di dati hai?

• matrice a dimensione
• avete un indice più volte nella matrice

Se l'array consiste solo di permutazione degli indici è possibile utilizzare una base-conversione

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

e utilizzare "10" come hash_key via

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() 

Ora è possibile utilizzare un array (shape = (base_size,)) anziché un dict per accedere ai valori.

Answer 3

Arrivando in ritardo alla festa, ma per i grandi array, penso che un modo decente per farlo è quello di sottocampionare a caso la matrice e hash che del campione:

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) 

Penso che questo è meglio di facendo hash(str(a)), perché quest'ultimo potrebbe confondere gli array che hanno dati univoci nel mezzo ma zeri attorno ai bordi.

Answer 4

Si può provare xxhash tramite il suo Python binding. Per array di grandi dimensioni questo è molto più veloce di hash(x.tostring()).

Esempio IPython sessione:

>>> 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 

E tra l'altro, sui vari blog e risposte inviati ad Stack Overflow, vedrete persone che utilizzano sha1 o md5 come funzioni hash. Per motivi di prestazioni, di solito è non accettabile, poiché quelle funzioni di hash "sicure" sono piuttosto lente. Sono utili solo se la collisione dell'hash è una delle preoccupazioni principali.

Tuttavia, le collisioni di hash si verificano sempre. E se tutto ciò che serve è implementare __hash__ per gli oggetti data-array in modo che possano essere usati come chiavi nei dizionari o negli insiemi Python, penso che sia meglio concentrarsi sulla velocità di __hash__ e lasciare che Python gestisca la collisione dell'hash [1].

[1] Potrebbe essere necessario eseguire l'override di __eq__ per aiutare Python a gestire la collisione dell'hash. Si desidera che __eq__ restituisca un valore booleano anziché una serie di valori booleani come avviene per numpy.