История изменений

#!/usr/bin/python

import sys, random, time
s0 = ''.join(map(chr, range(97,123)))

r100, r20, r80 = range(100), range(20), range(20, 100)

t0 = time.time()
stable = [''.join(s0[int(random.random()*26)] for j in r100) for i in xrange(100000)]
t1 = time.time()
print 'generate strings', t1-t0

htable = {}
for I in xrange(len(stable)):
    s, h = stable[I], 0
    for k in r20: h |= ord(s[k])%2<<k
    for i in r80:
        htable.setdefault(h, []).append((I, i-20))
        h >>= 1; h |= ord(s[i])%2<<19
t2 = time.time()
print 'generate hash', t2-t1, len(htable), 0xfffff

matches = 0
for i in range(1000):
    h, s = 0, ''.join(s0[int(random.random()*26)] for j in r20)
    for k in r20: h |= ord(s[k])%2<<k
    for k, off in htable.get(h, []): matches += s==stable[k][off:off+20]
t3 = time.time()
print 'search time', t3-t2
print 'total time', t3-t0

print  'matches', matches

$ ./bench.py
generate strings 2.64825701714
generate hash 9.09323906898 1048093 1048575
search time 0.0179228782654
total time 11.7594189644
matches 0

#!/usr/bin/python

import sys, random, time
s0 = ''.join(map(chr, range(97,123)))

r100, r20, r80 = range(100), range(20), range(20, 100)

t0 = time.time()
stable = [''.join(s0[int(random.random()*26)] for j in r100) for i in xrange(100000)]
t1 = time.time()
print 'generate strings', t1-t0

htable = {}
for I in xrange(len(stable)):
    s, h = stable[I], 0
    for k in r20: h |= ord(s[k])%2<<k
    for i in r80:
        htable.setdefault(h, []).append((I, i))
        h >>= 1; h |= ord(s[i])%2<<19
t2 = time.time()
print 'generate hash', t2-t1, len(htable), 0xfffff

matches = 0
for i in range(1000):
    h, s = 0, ''.join(s0[int(random.random()*26)] for j in r20)
    for k in r20: h |= ord(s[k])%2<<k
    for k, off in htable.get(h, []): matches += s==stable[k][off:off+20]
t3 = time.time()
print 'search time', t3-t2
print 'total time', t3-t0

print  'matches', matches

$ ./bench.py
generate strings 2.64825701714
generate hash 9.09323906898 1048093 1048575
search time 0.0179228782654
total time 11.7594189644
matches 0