最有效的财产散列numpy阵列

Question

我需要能够存储numpyarray在dict为了缓存的目的。哈希速度很重要。

array表示指示，所以虽然对象的实际身份不重要，但值是。 Mutabliity不是一个问题，因为我只对目前的价值感兴趣。

我应该散列什么来存储它在dict？

我目前的做法是使用str(arr.data)，这比我测试中的md5快。

---

我已经采纳了一些答案的例子让相对时间的想法：

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 

这样看来，这个特定用例（indicies的小数组），arr.tostring提供最棒的表演。

虽然散列只读缓冲区本身很快，但设置可写入标志的开销实际上使其变慢。

Answer 1

你可以简单的哈希基础缓冲区，如果你把它只读：

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

对于非常大的阵列，hash(str(a))是快了不少，但随后只需要数组的一小部分进入帐户。

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

Answer 2

你有什么样的数据？

• 阵列尺寸
• 你有一个索引几次阵列

中如果阵列只包含索引的置换可以使用基本皈依

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

并使用'10'作为hash_key通过

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

现在您可以使用数组（形状=（base_size，））而不是字典来访问这些值。

Answer 3

即将迟到了，但对于大数组，我想一个体面的方式来做到这一点是随机子样本矩阵和散列该样本：

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) 

我认为这是优于做hash(str(a))，因为后者可能会混淆具有中间唯一数据但边缘零点的数组。

Answer 4

您可以尝试xxhash通过其Python binding。对于大型阵列，这比hash(x.tostring())快得多。

例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 

顺便说一下，张贴堆栈溢出各种博客和答案，你会使用sha1或md5哈希函数见人。出于性能原因，这通常是而不是，因为那些“安全”散列函数相当慢。只有散列冲突是最关心的问题之一，它们才有用。

尽管如此，哈希碰撞总是发生。如果您只需要为数据阵列对象实现__hash__，以便它们可以用作Python字典或集合中的键，我认为最好将注意力集中在__hash__本身的速度上，并让Python处理散列冲突[1]。

[1]您可能还需要覆盖__eq__，以帮助Python管理散列冲突。你会希望__eq__返回一个布尔值，而不是像numpy那样的布尔值数组。