numpy配列のハッシュ処理に最も効率的なプロパティ

Question

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

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 

arr.tostringを提供しています、この特定のユースケース（なインデックスの小さな配列）のためにそれを表示されます最高のパフォーマンス。

読み取り専用バッファをハッシュするのは高速ですが、書き込み可能フラグを設定するオーバーヘッドは実際には遅くなります。

Answer 1

あなたはそれが読み取り専用にする場合は、単純に、基本となるバッファをハッシュすることができます：hash(str(a))がはるかに高速で、非常に大きなアレイの場合

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

を、しかし、それだけに、配列の小さな部分を取りますアカウント。

パーティーに遅刻

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

ベースconvertionを使用することができます

を使用し、hash_keyとして '10'を使用

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

dictの代わりに配列（shape =（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を使っている人が表示されます。パフォーマンス上の理由から、これは通常「」ではなく「」です。これらの「安全な」ハッシュ関数はかなり遅いためです。ハッシュコリジョンが最優先事項の1つである場合にのみ便利です。

しかし、ハッシュの衝突は常に発生します。そして、あなたが必要とするのは、データ配列オブジェクトのために__hash__を実装して、Pythonの辞書やセットのキーとして使うことができるならば、__hash__の速度に集中し、Pythonがハッシュ衝突を処理させる方が良いと思います。

[1] Pythonがハッシュ衝突を管理するのに役立つように、__eq__も無効にする必要があります。 numpyのように、__eq__にブール値の配列ではなくブール値を返すことをお勧めします。