75

キャッシュの目的numpy arrayで a に aを格納できる必要があります。dictハッシュ速度は重要です。

はarray指標を表すため、オブジェクトの実際の ID は重要ではありませんが、値は重要です。現在の値のみに関心があるため、可変性は問題ではありません。

に格納するには、何をハッシュする必要があり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

35

Python bindingで試すことができxxhashます。大きな配列の場合、これは よりもはるかに高速です。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をハッシュ関数として使用している人を見かけます。これらの「安全な」ハッシュ関数はかなり遅いため、パフォーマンス上の理由から、これは通常は受け入れられません。これらは、ハッシュの衝突が最大の関心事の 1 つである場合にのみ役立ちます。

それにもかかわらず、ハッシュの衝突は常に発生します。また、データ配列オブジェクトを Python 辞書やセットのキーとして使用できるように実装するだけでよい場合は、それ自体の速度に集中して、ハッシュ衝突を Python に処理させる__hash__方がよいと思います[1]。__hash__

__eq__[1] 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 に答える