20

データの大きなチャンクを比較して等しいかどうかを確認する必要があります。また、1秒あたりのペア数を高速で比較する必要があります。各オブジェクトは同じ長さであることが保証されており、未知の位置にわずかな違いがある可能性があります。

以下のタイミング==は、データの先頭近くに差がある場合は演算子の使用が非常に速く、差が終わりにある場合は大幅に遅くなることを示しています。

>>> import os
>>> s = os.urandom(1600*1200 - 1)
>>> Aimg = b"A" + s
>>> Bimg = b"B" + s
>>> img1 = s + b"1"
>>> img2 = s + b"2"
>>> %timeit Aimg == Bimg
61.8 ns ± 0.484 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
>>> %timeit img1 == img2
159 µs ± 2.83 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

私のユースケースでは、違いはバイトの中央または終わりの方にある可能性があります（コンテキスト：非圧縮の画像データです）。ハッシュまたはチェックサムを使用して処理を高速化する方法を探しました。md5の使用は遅くなりましたが、Pythonの組み込みhashは実際に物事をスピードアップしました。

>>> %timeit img1 == img2
160 µs ± 5.96 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit hash(img1) == hash(img2) and img1 == img2
236 ns ± 5.91 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

このハッシュの技術的な詳細に興味がありますが、それは十分にハッシュのようであり、そのときhash(a) == hash(b)はa == b非常に可能性が高いですか？ハッシュの衝突がかなりまれである場合、誤検知は許容されます。その意図は、平均的な場合の比較を高速化するための高速パスです。

4

1 に答える 1

35

Pythonのハッシュ関数は速度を重視して設計されており、64ビット空間にマッピングされます。誕生日のパラドックスのため、これは約50億のエントリで衝突が発生する可能性が高いことを意味します（ハッシュ関数は暗号化されていないため、おそらくはるかに早いです）。また、の正確な定義はhashPythonの実装次第であり、アーキテクチャ固有またはマシン固有の場合もあります。複数のマシンで同じ結果が必要な場合は使用しないでください。

md5は暗号化ハッシュ関数として設計されています。入力のわずかな摂動でさえ、出力を完全に変化させます。また、128ビット空間にマッピングされるため、特に衝突を探している場合を除いて、衝突が発生する可能性はほとんどありません。

衝突を処理できる場合（つまり、おそらくMD5やSHA2などの暗号化アルゴリズムを使用して、バケット内のすべてのメンバー間の同等性をテストできる場合）、Pythonのハッシュ関数は完全に問題ありません。

もう1つ、スペースを節約するために、データをディスクに書き込む場合は、データをバイナリ形式で保存する必要があります。（すなわちstruct.pack('!q', hash('abc'))/ hashlib.md5('abc').digest()）。

補足として：Pythonisと同等ではありません。==つまり==。

于 2011-10-04T10:45:07.313 に答える