75

我需要能够将 a 存储numpy array在 a 中以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提供了最佳性能。

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

4

5 回答 5

63

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

>>> 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]'
于 2013-05-16T15:58:25.890 回答
35

你可以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

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

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

[1] 你可能也需要重写__eq__，以帮助 Python 管理哈希冲突。您可能希望__eq__返回一个布尔值，而不是像numpy.

于 2015-08-05T09:58:42.927 回答
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))，因为后者可能会混淆中间有唯一数据但边缘为零的数组。

于 2014-04-25T18:47:24.923 回答
4

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

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]
于 2020-04-10T08:46:30.417 回答
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()

现在您可以使用数组 (shape=(base_size, )) 而不是 dict 来访问这些值。

于 2013-05-16T15:32:05.133 回答