優化字符串生成和測試

我試圖運行一個模擬來測試隨機二進制字符串之間的平均值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

優化字符串生成和測試

回答

相關問題