对于numpy数组最有效的哈希属性

我需要能够将numpy array存储在dict中用于缓存目的。哈希速度很重要。

array表示索引，所以对象的实际身份不重要，值重要。可变性不是一个问题，因为我只对当前值感兴趣。

为了在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提供了最好的性能。

虽然对只读缓冲区的哈希运算本身很快，但设置可写标志的开销实际上会使它变慢。

您可以简单地散列底层缓冲区，如果您将其设置为只读:

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

您可以尝试通过其Python绑定xxhash。对于大型数组，这比hash(x.tostring())要快得多。

示例ippython会话:

>>> 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那样返回一个布尔值数组。

如果你的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]

有点晚了，但是对于大型数组，我认为一个不错的方法是随机地对矩阵进行子采样并对样本进行散列:

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

你有什么样的数据?

数组大小
在数组

如果你的数组只包含索引的排列，你可以使用基本转换

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

并使用'10'作为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()

现在您可以使用数组(shape=(base_size，))来代替字典来访问值

相关内容

最新更新

热门标签：