散列为numpy数组的最有效属性

Question

我需要能够存储numpy array一个dict用于缓存的目的.哈希速度很重要.

该array代表indicies,所以在对象的真实身份并不重要,值.可变性不是一个问题,因为我只对当前价值感兴趣.

我应该散列什么才能将其存储在一个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

对于这个特定的用例(小型标记阵列),似乎可以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

您可以尝试xxhash通过其Python绑定.对于大型阵列,这比它快得多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

顺便说一句,在发布到Stack Overflow的各种博客和答案中,您会看到人们使用sha1或md5作为哈希函数.出于性能方面的原因,这通常是不接受的,因为那些"安全"的散列函数是相当缓慢的.只有当哈希冲突是最受关注的问题之一时,它们才有用.

然而,哈希冲突一直在发生.如果您只需要实现__hash__数据数组对象以便它们可以用作Python字典或集合中的键,我认为最好专注于__hash__自身的速度并让Python处理哈希冲突[1].

[1]您可能还需要覆盖__eq__,以帮助Python管理哈希冲突.你会想要__eq__返回一个布尔值,而不是一个布尔数组numpy.

Answer 3

如果你的np.array()代码很小并且处于紧密循环中，那么一种选择是完全跳过hash()并np.array().data.tobytes()直接用作你的字典键：

grid  = np.array([[True, False, True],[False, False, True]])
hash  = grid.data.tobytes()
cache = cache or {}
if hash not in cache:
    cache[hash] = function(grid)
return cache[hash]

Answer 4

来晚了，但对于大型数组，我认为一个不错的方法是随机对矩阵进行二次采样并对样本进行哈希处理：

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))，因为后者可能会混淆中间有唯一数据但边缘有零的数组。