Najbardziej wydajna właściwość do mieszania dla numpy array

Question

Potrzebuję być w stanie przechowywać numpyarray w dict dla celów buforowania. Szybkość skrótu jest ważna.

Oznaczenie array oznacza, że ​​podczas gdy rzeczywista tożsamość obiektu nie jest ważna, wartość jest. Mutabliity nie jest problemem, ponieważ interesuje mnie tylko obecna wartość.

Co powinienem użyć, aby go zapisać w numerze dict?

Moje obecne podejście polega na użyciu str(arr.data), która jest szybsza niż md5 w moich testach.

---

mam włączone kilka przykładów z odpowiedziami, aby zorientować razy względna:

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 

Wydaje się, że w tym konkretnym przypadku (małe tablice indeksów), arr.tostring oferuje najlepsza wydajność.

Podczas mieszania bufor tylko do odczytu jest szybki sam, obciążenie związane z ustawianiem flagi zapisu powoduje jej spowolnienie.

Answer 1

Można po prostu hash bufor podstawowy, jeśli je tylko do odczytu:

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

W przypadku bardzo dużych tablic, hash(str(a)) jest dużo szybszy, ale to zajmuje tylko niewielką część tablicy do konto.

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

Answer 2

Jakie masz dane?

• tablica rozmiarów
• masz indeks kilkakrotnie w tablicy

Jeśli tablica składa się tylko z permutacji indeksów można użyć BASE-konwersja

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

i użyj "10" jako hash_key przez

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

Teraz możesz użyć tablicy (shape = (base_size,)) zamiast dyktatury, aby uzyskać dostęp do wartości.

Answer 3

Coming późno do partii, ale dla dużych tablic, myślę przyzwoity sposób to zrobić jest losowo podpróba matrycę i hash że próbki:

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) 

Myślę, że to lepsze niż robi hash(str(a)), ponieważ te ostatnie mogą mylić tablice, które mają unikalne dane w środku, ale zera wokół krawędzi.

Answer 4

Możesz spróbować xxhash poprzez jego Python binding. W przypadku dużych tablic jest to znacznie szybsze niż hash(x.tostring()).

Przykład ipython sesja:

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

A przy okazji, na różnych blogach i odpowiedzi zamieszczone na przepełnienie stosu, zobaczysz ludzi używając sha1 lub md5 jako funkcji skrótu. Ze względów wydajności jest to zwykle dopuszczalne z uwagi na to, że te "bezpieczne" funkcje skrótu są raczej wolne. Są użyteczne tylko wtedy, gdy kolizja hash jest jedną z najważniejszych kwestii.

Mimo to kolizje mieszania zdarzają się przez cały czas. A jeśli wszystko czego potrzebujesz to implementacja __hash__ dla obiektów macierzy danych, tak aby mogły być używane jako klucze w słownikach lub zestawach Pythona, myślę, że lepiej jest skoncentrować się na samej szybkości __hash__ i pozwolić Pythonowi radzić sobie z kolizją hashów [1].

[1] Konieczne może być również zastąpienie __eq__, aby pomóc Pythonowi w zarządzaniu kolizją haszów. Użytkownik chciałby, aby __eq__ zwrócił wartość logiczną, a nie tablicę zmiennych, jak jest to robione przez numpy.