7

我正在尝试运行模拟来测试随机二进制字符串之间的平均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。

4

2 回答 2

6

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

它生成一个带有随机2**i位random.getrandbits的数字bin（有你想要的长度。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-27T09:32:33.070 回答
2

您可以使用 Python/C API 创建 Python 字符串，这将比任何专门使用 Python 的方法快得多，因为 Python 本身是在 Python/C 中实现的。性能可能主要取决于随机数生成器的效率。如果您使用的是具有合理 random(3) 实现的系统，例如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);
}

使用 halex 的基准测试此代码表明它比原始代码快 280 倍，比 halex 的代码（在我的机器上）快 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 代码添加到项目中是一件复杂的事情，但对于关键操作的 280 倍加速，这可能是值得的。

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

于 2013-04-27T09:43:25.630 回答