我正在用Python编写一个类似玩具rsync的工具。像许多类似的工具一样，它将首先使用非常快的哈希作为滚动哈希，然后在找到匹配项后使用 SHA256(但后者在这里无关主题：SHA256、MDA5 等作为滚动哈希太慢了(。
我目前正在测试各种快速哈希方法：
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/秒 ...所以Python内置的hash(...)函数在这里太慢了。
哪种解决方案可以在标准计算机上实现至少 10 MB/s 的更快哈希？
我试过
import zlib ... h = zlib.adler32(s[i:i+block_size])但它也好不到哪里去(1.1 MB/s(
我试过
sum(s[i:i+block_size]) % modulo，也很慢有趣的事实：即使没有任何哈希设置，循环本身也很慢！
t0 = time.time() for i in range(len(s)-block_size): s[i:i+block_size]我得到：只有 3.0 MB/秒！因此，让循环访问
s上的滚动块的简单事实已经很慢了。
与其重新发明轮子并编写我自己的哈希/或使用自定义的 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 的速度被阻止。
而不是重新发明轮子并编写我自己的哈希/或使用自定义 拉宾-卡普算法，你会有什么建议，首先要加快速度 循环，然后作为哈希？
从这种心态开始总是很棒的，但似乎你没有想到滚动哈希。 哈希函数非常适合滚动的原因在于它能够重用以前的处理。
一些哈希函数允许非常计算滚动哈希 快速 - 仅根据旧的哈希值快速计算新哈希值 哈希值、从窗口中删除的旧值和新值 添加到窗口中。
来自同一维基百科页面
在没有 timeit 的情况下很难比较不同机器的性能，但我更改了您的脚本以使用带有素模的简单多项式哈希(使用 Mersene 素数会更快，因为模运算可以用二进制运算完成(：
import os, random, time
block_size = 1024 # 1 KB blocks
total_size = 10*1024*1024 # 10 MB random bytes
s = os.urandom(total_size)
base = 256
mod = int(1e9)+7
def extend(previous_mod, byte):
return ((previous_mod * base) + ord(byte)) % mod
most_significant = pow(base, block_size-1, mod)
def remove_left(previous_mod, byte):
return (previous_mod - (most_significant * ord(byte)) % mod) % mod
def start_hash(bytes):
h = 0
for b in bytes:
h = extend(h, b)
return h
t0 = time.time()
h = start_hash(s[:block_size])
for i in range(block_size, len(s)):
h = remove_left(h, s[i - block_size])
h = extend(h, s[i])
print('rolling hashes computed in %.1f sec (%.1f MB/s)' % (time.time()-t0, total_size/1024/1024/(time.time()-t0)))
显然，您在使用Numba时取得了相当大的改进，它也可以加快此代码的速度。 为了提取更多的性能，您可能需要编写一个 C(或其他低级语言如 Rust(函数来一次处理列表的很大一部分并返回一个带有哈希的数组。
我也在创建一个类似rsync的工具，但是当我在 Rust 中编写时，这个级别的性能不是我关心的问题。相反，我正在遵循 rsync 创建者的提示，并尝试并行化我能做的一切，这是在 Python 中完成的一项痛苦任务(如果没有 Jython 可能是不可能的(。
你会有什么建议，首先加速这个循环，然后作为哈希？
增加块大小。你的块大小越小，你每字节执行的python就越多，速度就越慢。
编辑：您的范围的默认步长为 1，并且您不会将i乘以block_size，因此您不是迭代 10*1024 个 1k 的非重叠块，而是迭代 1000 万个 - 1024 个大部分重叠的块
首先，你的慢循环。如前所述，您正在为流中的每个字节(较小的块大小(切一个新的块。这在 CPU 和内存上都是大量的工作。
更快的循环是将数据预先分块为并行位。
chunksize = 4096 # suggestion
# roll the window over the previous chunk's last block into the new chunk
lastblock = None
for readchunk in read_file_chunks(chunksize):
for i in range(0, len(readchunk), blocksize):
# slice a block only once
newblock = readchunk[i:blocksize]
if lastblock:
for bi in range(len(newblock)):
outbyte = lastblock[bi]
inbyte = newblock[bi]
# update rolling hash with inbyte and outbyte
# check rolling hash for "hit"
else:
pass # calculate initial weak hash, check for "hit"
lastblock = newblock
块大小应该是块大小的倍
数接下来，您依次计算整个块的"滚动哈希"，而不是以"滚动"方式逐字节更新哈希字节。这是非常慢的。上面的循环强制您在字节进出窗口时处理它们。尽管如此，我的试验显示吞吐量相当差(~3Mbps~ 编辑：对不起，这是 3MiB/s(，即使每个字节的算术运算数量适中。编辑：我最初有一个zip((，看起来很慢。在没有zip的情况下，我单独循环就获得了两倍多(上面的当前代码(
Python是单线程和解释的。我看到一个 CPU 挂钩，这就是瓶颈。为了更快，您需要多个线程(子进程(或中断 C，或两者兼而有之。我认为，简单地用 C 语言运行数学可能就足够了。(哈哈，"简单"(