История изменений
Исправление AntonI, (текущая версия) :
однопоточная питоновская (python2) реализация с хэшами
#!/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
проц Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
$ ./bench.py
generate strings 2.64825701714
generate hash 9.09323906898 1048093 1048575
search time 0.0179228782654
total time 11.7594189644
matches 0
один проход. Т.е. метапроговская реализация обгоняет мерррскую скриптуху всего лишь в три раза?! Ща на плюсах сделаю, если не лень будет.
Исходная версия AntonI, :
однопоточная питоновская (python2) реализация с хэшами
#!/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
проц Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
$ ./bench.py
generate strings 2.64825701714
generate hash 9.09323906898 1048093 1048575
search time 0.0179228782654
total time 11.7594189644
matches 0
один проход. Т.е. метапроговская реализация обгоняет мерррскую скриптуху всего лишь в три раза?! Ща на плюсах сделаю, если не лень будет.