最適化文字列の生成とテスト

Question

私は、ランダム バイナリ文字列の間に平均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つのコアを持っていますが、それらを利用することがどれほど難しいかわかりません。

残念ながら、C拡張のためにpypyを使用することはできません。

Answer 1

以下の解決策は、実行時の面で優れているはずです。 binの結果は'0b'前に付加されているので

それは2**iランダムビット（random.getrandbits）で番号を生成し、数のバイナリ表現（bin）の文字列に変換し、（最後に3ND文字で始まるすべてのものを取ります）、結果の文字列の前に、希望の長さになるように0が付加されます。 2 ** 20のあなたの最大文字列長のための

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

クイックタイミング：

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倍の高速化です。

Answer 2

Python/C APIを使用してPython文字列を作成することができます。これは、Python自体がPython/Cで実装されているため、排他的にPythonを使用する方法よりもはるかに高速です。パフォーマンスは、主に乱数ジェネレータの効率に依存します。あなたは、このようなthe one in glibcとして合理的なランダム（3）実装、とのシステム上にある場合は、ランダムな文字列の効率的な実装は次のようになります。

#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を調べて、別のスレッドから呼び出すようにして、乱数生成を並列化して並列化します。後者は、スレッド間通信がそうでなければ高速の生成プロセスを妨げないことを保証するために、ロックフリー同期メカニズムの恩恵を受けるであろう。