Ottimizzazione stringa generare e test

Question

Sto provando a eseguire una simulazione per testare la media Levenshtein distance tra stringhe binarie casuali .

Per accelerare sto usando questo C extension.

Il mio codice è come segue.

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) 

Penso che la parte più lenta sia ora la generazione di stringhe. Può essere accelerato in qualche modo o c'è qualche altra accelerazione che potrei provare?

Ho anche 8 core ma non so quanto sia difficile sfruttarli.

Sfortunatamente non posso usare pypy a causa dell'estensione C.

Answer 1

La seguente soluzione dovrebbe essere decisamente migliore in termini di tempo di esecuzione.

Si genera un numero con 2**i bit casuali (random.getrandbits), lo converte in una stringa di rappresentazione binaria del numero (bin), prende tutto iniziando con il carattere 3nd alla fine (perché il risultato di bin viene anteposto con '0b') e antepone la stringa risultante con zeri per ottenere la lunghezza desiderata.

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

tempistica rapida per la lunghezza massima della stringa di 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] 

Questo è un aumento di velocità di un fattore pari a 150 in media.

Answer 2

È possibile creare una stringa Python utilizzando l'API Python/C, che sarà significativamente più veloce di qualsiasi metodo che utilizza esclusivamente Python, poiché Python stesso è implementato in Python/C. Le prestazioni dipenderanno principalmente dall'efficienza del generatore di numeri casuali. Se siete su un sistema con un casuale (3) implementazione ragionevoli, come ad esempio the one in glibc, un'efficace attuazione della stringa casuale sarebbe simile a questa:

#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); 
} 

Testing questo codice con benchmark di halex dimostra che è 280x più veloce di il codice originale, e 2,3x più veloce di codice di Halex (sulla mia macchina):

# 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, ...] 

Aggiunta di codice C per un progetto è una complicazione, ma per un aumento di velocità 280x di un'operazione critica, potrebbe essere valsa la pena .

Per un ulteriore miglioramento dell'efficienza, esaminare gli RNG più veloci e richiamarli da thread separati per parallelizzare la generazione di numeri casuali in parallelo. Quest'ultimo trarrebbe vantaggio da un meccanismo di sincronizzazione privo di blocco per assicurarsi che la comunicazione tra thread non impoverisca il processo di generazione altrimenti veloce.