Является ли это подходящим использованием встроенной хэш-функции python?

Мне нужно сравнить большие порции данных на равенство, и мне нужно сравнивать много раз в секунду, быстро. Каждый объект гарантированно одинакового размера, и возможно/вероятно, что они могут лишь немного отличаться (в неизвестных позициях).

Из интерактивной сессии ниже я увидел, что использование оператора == для байтовых строк может быть медленнее, если различия находятся в конце строки, и может быть очень быстрым, если различия находятся в начале.

Я подумал, что можно как-то ускорить работу с помощью хэша, конечно, вычисление хэша md5 и сравнение намного медленнее, но встроенный хэш Python, похоже, значительно ускоряет работу.

Однако я понятия не имею о деталях реализации этого хэша, действительно ли он похож на хэш в том смысле, что я могу быть уверен, что если hash(a) == hash(b), то a == b очень вероятно? Я буду рад нескольким неправильным результатам, если столкновение хэшей будет достаточно редким (редким в том смысле, что для столкновения потребуется массив из 200 PS3 несколько часов)

In [1]: import hashlib

In [2]: with open('/dev/urandom') as f:
   ...:     spam = f.read(2**20 - 1)
   ...:     

In [3]: spamA = spam + 'A'

In [4]: Aspam = 'A' + spam

In [5]: spamB = spam + 'B'

In [6]: timeit spamA == spamB
1000 loops, best of 3: 1.59 ms per loop

In [7]: timeit spamA == Aspam
10000000 loops, best of 3: 66.4 ns per loop

In [8]: timeit hashlib.md5(spamA) == hashlib.md5(spamB)
100 loops, best of 3: 4.42 ms per loop

In [9]: timeit hashlib.md5(spamA) == hashlib.md5(Aspam)
100 loops, best of 3: 4.39 ms per loop

In [10]: timeit hash(spamA) == hash(spamB)
10000000 loops, best of 3: 157 ns per loop

In [11]: timeit hash(spamA) == hash(Aspam)
10000000 loops, best of 3: 160 ns per loop

15
задан wim 4 October 2011 в 10:55
поделиться