优化字符串生成和测试

Question

我正在尝试运行模拟来测试随机二进制字符串之间的平均Levenshtein距离.

为了加快速度,我正在使用这个C扩展.

我的代码如下.

from Levenshtein import distance 
for i in xrange(20):
    sum = 0
    for j in xrange(1000):
        str1 =  ''.join([random.choice("01") for x in xrange(2**i)])
        str2 =  ''.join([random.choice("01") for x in xrange(2**i)])
        sum += distance(str1,str2)
    print sum/(1000*2**i)

我认为最慢的部分现在是字符串生成.可以用某种方式加速,还是有其他加速我可以试试？

我也有8个核心,但我不知道它会有多么困难.

不幸的是,由于C扩展,我不能使用pypy.

Answer 1

以下解决方案在运行时方面应该更好.

它使用2**i随机位(random.getrandbits)生成一个数字,将其转换为数字的二进制表示(bin)的字符串,将从第3个字符开始的所有内容都结束(因为结果bin是前缀'0b')并将结果字符串前缀为零有你想要的长度.

str1 = bin(random.getrandbits(2**i))[2:].zfill(2**i)

快速计时最大字符串长度为2**20:

from timeit import Timer
>>> t=Timer("''.join(random.choice('01') for x in xrange(2**20))", "import random")
>>> sorted(t.repeat(10,1))
[0.7849910731831642, 0.787418033587528, 0.7894113893237318, 0.789840397476155, 0.7907980049587877, 0.7908638883536696, 0.7911707057912736, 0.7935838766477445, 0.8014726470912592, 0.8228315074311467]
>>> t=Timer("bin(random.getrandbits(2**20))[2:].zfill(2**20)", "import random")
>>> sorted(t.repeat(10,1))
[0.005115922216191393, 0.005215130351643893, 0.005234282501078269, 0.005451850921190271, 0.005531523863737675, 0.005627284612046424, 0.005746794025981217, 0.006217553864416914, 0.014556016781853032, 0.014710766150983545]

这是平均150倍的加速.