我正在用Python编写一个类似于
我目前正在测试各种快速哈希方法:
我得到的是:0.8 MB/s ... 所以 Python 内置的
哪种解决方案可以让标准计算机上的哈希速度达到至少 10 MB/s?
使用Numba,速度有了巨大的提升:40.0 MB/s,但仍未进行哈希。至少我们不会被限制在3 MB/s。
rsync
的玩具工具。与许多类似的工具一样,它首先使用非常快的哈希作为滚动哈希,一旦找到匹配项,就会使用SHA256(但后者不是本文的重点:SHA256、MD5等作为滚动哈希太慢了)。我目前正在测试各种快速哈希方法:
import os, random, time
block_size = 1024 # 1 KB blocks
total_size = 10*1024*1024 # 10 MB random bytes
s = os.urandom(total_size)
t0 = time.time()
for i in range(len(s)-block_size):
h = hash(s[i:i+block_size])
print('rolling hashes computed in %.1f sec (%.1f MB/s)' % (time.time()-t0, total_size/1024/1024/(time.time()-t0)))
我得到的是:0.8 MB/s ... 所以 Python 内置的
hash(...)
函数在这里太慢了。哪种解决方案可以让标准计算机上的哈希速度达到至少 10 MB/s?
I tried with
import zlib ... h = zlib.adler32(s[i:i+block_size])
but it's not much better (1.1 MB/s)
I tried with
sum(s[i:i+block_size]) % modulo
and it's slow tooInteresting fact: even without any hash fonction, the loop itself is slow!
t0 = time.time() for i in range(len(s)-block_size): s[i:i+block_size]
I get: 3.0 MB/s only! So the simpe fact of having a loop accessing to a rolling block on
s
is already slow.
不要重复造轮子并编写自己的哈希函数/或使用自定义的Rabin-Karp算法,您会建议什么,首先加速此循环,然后作为哈希函数?
编辑:上述“有趣的事实”慢循环的(部分)解决方案:
import os, random, time, zlib
from numba import jit
@jit()
def main(s):
for i in range(len(s)-block_size):
block = s[i:i+block_size]
total_size = 10*1024*1024 # 10 MB random bytes
block_size = 1024 # 1 KB blocks
s = os.urandom(total_size)
t0 = time.time()
main(s)
print('rolling hashes computed in %.1f sec (%.1f MB/s)' % (time.time()-t0, total_size/1024/1024/(time.time()-t0)))
使用Numba,速度有了巨大的提升:40.0 MB/s,但仍未进行哈希。至少我们不会被限制在3 MB/s。
block = s[i:i+block_size]
不会复制,它只是对该块的引用/视图,这样对吗? - Basjnumpy
才能获得该行为。 - jasonharper