优化字符串生成和测试

我试图运行一个模拟来测试随机二进制字符串之间的平均值Levenshtein distance。我使用C extension。优化字符串生成和测试

我的代码如下。

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个内核，但我不知道这将是多么困难。

不幸的是，我不能使用pypy因为C扩展名。

来源

2013-04-27 marshall

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

它产生与2**i随机比特（random.getrandbits）的数，将其转换为数字的二进制表示（bin）的字符串，需要一切与3ND字符到端开始（因为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上平均的系数的加速。

来源

2013-04-27 09:32:33 halex

非常感谢。 – marshall 2013-04-27 15:34:31

@marshall：你可以使用['b2a_bin（os.urandom（2 ** i/8））'（用Cython写的C扩展）]（https://gist.github.com/zed/ 3526111）。请参阅[乘以大数倍的随机（）（Python）]（http://stackoverflow.com/q/12161988/4279） – jfs 2013-04-28 01:52:49

@ J.F.Sebastian谢谢！ – marshall 2013-04-30 18:53:33

您可以使用Python/C API创建Python字符串，这比任何专门使用Python的方法快得多，因为Python本身是在Python/C中实现的。性能可能主要取决于随机数发生器的效率。如果你是一个合理的随机（3）实现的系统，如the one in glibc，高效实现随机字符串应该是这样的：

#include <Python.h> 

/* gcc -shared -fpic -O2 -I/usr/include/python2.7 -lpython2.7 rnds.c -o rnds.so */ 

static PyObject *rnd_string(PyObject *ignore, PyObject *args) 
{ 
    const char choices[] = {'0', '1'}; 
    PyObject *s; 
    char *p, *end; 
    int size; 
    if (!PyArg_ParseTuple(args, "i", &size)) 
     return NULL; 
    // start with a two-char string to avoid the empty string singleton. 
    if (!(s = PyString_FromString("xx"))) 
     return NULL; 
    _PyString_Resize(&s, size); 
    if (!s) 
     return NULL; 
    p = PyString_AS_STRING(s); 
    end = p + size; 
    for (;;) { 
     unsigned long rnd = random(); 
     int i = 31; // random() provides 31 bits of randomness 
     while (i-- > 0 && p < end) { 
     *p++ = choices[rnd & 1]; 
     rnd >>= 1; 
     } 
     if (p == end) 
     break; 
    } 
    return s; 
} 

static PyMethodDef rnds_methods[] = { 
    {"rnd_string", rnd_string, METH_VARARGS }, 
    {NULL, NULL, 0, NULL} 
}; 

PyMODINIT_FUNC initrnds(void) 
{ 
    Py_InitModule("rnds", rnds_methods); 
}

测试此代码哈莱克斯的基准测试显示，它的速度比280X原代码，和2.3倍比哈莱克斯的代码快（我的机器上）：

# the above code 
>>> t1 = Timer("rnds.rnd_string(2**20)", "import rnds") 
>>> sorted(t1.repeat(10,1)) 
[0.0029861927032470703, 0.0029909610748291016, ...] 
# original generator 
>>> t2 = Timer("''.join(random.choice('01') for x in xrange(2**20))", "import random") 
>>> sorted(t2.repeat(10,1)) 
[0.8376679420471191, 0.840252161026001, ...] 
# halex's generator 
>>> t3 = Timer("bin(random.getrandbits(2**20-1))[2:].zfill(2**20-1)", "import random") 
>>> sorted(t3.repeat(10,1)) 
[0.007007122039794922, 0.007027149200439453, ...]

添加C代码到一个项目是一个复杂，但对于关键的操作280X加速，它很可能是值得的。

为了进一步提高效率，请研究更快的RNG，并从不同的线程调用它们，以便并行化并行化随机数生成。后者将受益于无锁同步机制，以确保线程间通信不会妨碍快速生成过程。

来源

2013-04-27 09:43:25 user4815162342

看到你的C代码* *只比我的* pure * python解决方案快3倍，这真的很有趣。认为它会更好:) – halex 2013-04-27 10:00:16

@halex我也很惊讶！与往常一样，诀窍是利用Python的内建函数，比如'bin'。我怀疑3倍加速是由于使用更快（不太复杂）的RNG。 – user4815162342 2013-04-27 10:05:55

非常感谢。 – marshall 2013-04-27 15:55:43

优化字符串生成和测试

回答

相关问题