Propriété la plus efficace à hacher pour le tableau numpy
Je dois pouvoir stocker un numpy array dans un dict à des fins de mise en cache. La vitesse de hachage est importante.
Le array représente des indices, donc alors que l'identité réelle de l'objet n'est pas importante, la valeur est. La mutabliité n'est pas une préoccupation, car je ne m'intéresse qu'à la valeur actuelle.
Que dois-je hacher pour le stocker dans un dict?
Mon approche actuelle consiste à utiliser str(arr.data), qui est plus rapide que md5 dans mes tests.
J'ai incorporé certains exemples des réponses pour avoir une idée des temps relatifs:
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
Il semblerait que pour ce cas d'utilisation particulier (petits tableaux d'indices), arr.tostring offre les meilleures performances.
Alors que le hachage du tampon en lecture seule est rapide, la surcharge de la définition de l'indicateur inscriptible le rend en fait plus lent.
4 réponses
Vous pouvez simplement hacher le tampon sous-jacent, si vous le faites en lecture seule:
>>> 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
Pour les très grands tableaux, hash(str(a)) est beaucoup plus rapide, mais il ne prend en compte qu'une petite partie du tableau.
>>> %timeit hash(str(a))
10000 loops, best of 3: 55.5 us per loop
>>> str(a)
'[63 30 33 ..., 96 25 60]'
, Vous pouvez essayer xxhash par l'intermédiaire de son binding Python. Pour les grands tableaux c'est beaucoup plus rapide que hash(x.tostring()).
Exemple de session 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
Et en passant, sur divers blogs et réponses postés sur Stack Overflow, vous verrez des gens utiliser sha1 ou md5 comme fonctions de hachage. Pour des raisons de performance, ceci n'est généralement pas acceptable, car ces fonctions de hachage "sécurisées" sont plutôt lentes. Ils ne sont utiles que si la collision de hachage est l'un des meilleurs préoccupation.
Néanmoins, les collisions de hachage se produisent tout le temps. Et si tout ce dont vous avez besoin est d'implémenter __hash__ pour les objets data-array afin qu'ils puissent être utilisés comme clés dans les dictionnaires ou les ensembles Python, je pense qu'il vaut mieux se concentrer sur la vitesse de __hash__ lui-même et laisser Python gérer la collision de hachage[1].
[1] vous devrez peut-être remplacer __eq__ aussi, pour aider Python à gérer la collision de hachage. Vous voudriez que __eq__ renvoie un booléen, plutôt qu'un tableau de booléens comme cela se fait par numpy.
Quel type de données avez-vous?
- Taille du tableau
- Avez-vous un index plusieurs fois dans le tableau
Si votre tableau consiste uniquement en une permutation d'indices, vous pouvez utiliser une conversion de base
(1, 0, 2) -> 1 * 3**0 + 0 * 3**1 + 2 * 3**2 = 10(base3)
Et utilisez ' 10 ' comme 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()
Maintenant, vous pouvez utiliser un tableau (de la forme=(base_size, )) au lieu d'un dict afin d'accéder aux valeurs.
Venant en retard à la fête, mais pour les grands tableaux, je pense qu'une façon décente de le faire est de sous-échantillonner aléatoirement la matrice et de hacher cet échantillon:
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)
Je pense que c'est mieux que de faire hash(str(a)), car ce dernier pourrait confondre les tableaux qui ont des données uniques au milieu mais des zéros sur les bords.