Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Most efficient property to hash for numpy array

Tags:

python

numpy

I need to be able to store a numpy array in a dict for caching purposes. Hash speed is important.

The array represents indicies, so while the actual identity of the object is not important, the value is. Mutabliity is not a concern, as I'm only interested in the current value.

What should I hash in order to store it in a dict?

My current approach is to use str(arr.data), which is faster than md5 in my testing.


I've incorporated some examples from the answers to get an idea of relative times:

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 

It would appear that for this particular use case (small arrays of indicies), arr.tostring offers the best performance.

While hashing the read-only buffer is fast on its own, the overhead of setting the writeable flag actually makes it slower.

like image 424
sapi Avatar asked May 16 '13 14:05

sapi


People also ask

What makes NumPy faster?

Because the Numpy array is densely packed in memory due to its homogeneous type, it also frees the memory faster. So overall a task executed in Numpy is around 5 to 100 times faster than the standard python list, which is a significant leap in terms of speed.

Are NumPy arrays more efficient?

NumPy Arrays are faster than Python Lists because of the following reasons: An array is a collection of homogeneous data-types that are stored in contiguous memory locations. On the other hand, a list in Python is a collection of heterogeneous data types stored in non-contiguous memory locations.

Is appending to NumPy array faster than list?

array(a) . List append is faster than array append .


2 Answers

You can simply hash the underlying buffer, if you make it read-only:

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

For very large arrays, hash(str(a)) is a lot faster, but then it only takes a small part of the array into account.

>>> %timeit hash(str(a)) 10000 loops, best of 3: 55.5 us per loop >>> str(a) '[63 30 33 ..., 96 25 60]' 
like image 106
Fred Foo Avatar answered Oct 18 '22 03:10

Fred Foo


You can try xxhash via its Python binding. For large arrays this is much faster than hash(x.tostring()).

Example IPython session:

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

And by the way, on various blogs and answers posted to Stack Overflow, you'll see people using sha1 or md5 as hash functions. For performance reasons this is usually not acceptable, as those "secure" hash functions are rather slow. They're useful only if hash collision is one of the top concerns.

Nevertheless, hash collisions happen all the time. And if all you need is implementing __hash__ for data-array objects so that they can be used as keys in Python dictionaries or sets, I think it's better to concentrate on the speed of __hash__ itself and let Python handle the hash collision[1].

[1] You may need to override __eq__ too, to help Python manage hash collision. You would want __eq__ to return a boolean, rather than an array of booleans as is done by numpy.

like image 31
Cong Ma Avatar answered Oct 18 '22 01:10

Cong Ma