स्ट्रिंग को अनुकूलित करना और परीक्षण करना

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 कोर भी हैं लेकिन मुझे नहीं पता कि यह उन लोगों का कितना मुश्किल होगा।

दुर्भाग्य से मैं सी एक्सटेंशन के कारण pypy का उपयोग नहीं कर सकता।

Answer 1

रनटाइम के मामले में निम्नलिखित समाधान बेहतर होना चाहिए।

यह 2**i यादृच्छिक बिट्स (random.getrandbits) के साथ एक संख्या उत्पन्न करता है, संख्या के द्विआधारी प्रतिनिधित्व (bin) के एक स्ट्रिंग में बदल देता है, सब कुछ समाप्त करने के लिए 3nd चरित्र के साथ शुरुआत (क्योंकि bin का परिणाम '0b' साथ prepended है लेता है) और जेरोस के साथ परिणामस्वरूप स्ट्रिंग को अपनी इच्छित लंबाई रखने के लिए तैयार करता है। 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 औसतन का एक पहलू की एक speedup है यही कारण है कि।

Answer 2

आप पाइथन/सी एपीआई का उपयोग करके एक पायथन स्ट्रिंग बना सकते हैं, जो कि पाइथन का उपयोग करने वाली किसी विधि से काफी तेज़ होगा, क्योंकि पाइथन स्वयं पाइथन/सी में लागू होता है। प्रदर्शन मुख्य रूप से यादृच्छिक संख्या जनरेटर की दक्षता पर निर्भर करेगा। आप एक उचित यादृच्छिक (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); 
} 

परीक्षण halex के बेंचमार्क के साथ इस कोड से पता चलता है कि यह 280x की तुलना में तेजी है मूल कोड, और 2.3x halex के कोड की तुलना में तेजी (मेरी मशीन पर):

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

एक परियोजना के लिए सी कोड को जोड़ने में एक जटिलता है, लेकिन एक महत्वपूर्ण आपरेशन के एक 280x speedup के लिए, यह अच्छी तरह से इसके लायक हो सकता है ।

आगे दक्षता में सुधार के लिए, तेजी से आरएनजी में देखें, और यादृच्छिक संख्या पीढ़ी को समानांतर करने के लिए उन्हें अलग थ्रेड से कॉल करें। उत्तरार्द्ध को यह सुनिश्चित करने के लिए लॉक-फ्री सिंक्रनाइज़ेशन तंत्र से लाभ होगा कि अंतर-थ्रेड संचार अन्यथा तेज़ पीढ़ी की प्रक्रिया को कम नहीं करता है।