इस पायथन कोड को कैसे गति दें?

Question

मैं निम्नलिखित छोटे अजगर विधि है कि दूर प्रदर्शन हॉटस्पॉट से मिल गया है (मेरे प्रोफाइलर के अनुसार,> निष्पादन समय यहां बीता का 95%) एक बहुत बड़ा कार्यक्रम में:

def topScore(self, seq): 
    ret = -1e9999 
    logProbs = self.logProbs # save indirection 
    l = len(logProbs) 
    for i in xrange(len(seq) - l + 1): 
     score = 0.0 
     for j in xrange(l): 
      score += logProbs[j][seq[j + i]] 
     ret = max(ret, score) 

    return ret 

कोड पायथन के ज्योथन कार्यान्वयन में चलाया जा रहा है, सीपीथन नहीं, अगर यह मायने रखता है। 1,000 तत्वों के क्रम पर seq एक डीएनए अनुक्रम स्ट्रिंग है। logProbs शब्दकोशों की एक सूची है, प्रत्येक स्थिति के लिए एक। लक्ष्य seq के बाद किसी भी लंबाई l (10-20 तत्वों के क्रम पर) का अधिकतम स्कोर प्राप्त करना है।

मुझे एहसास है कि यह लूपिंग व्याख्या ओवरहेड के कारण अक्षम है और स्थिर रूप से संकलित/JIT'd भाषा में बहुत तेजी से एक बिल्ली होगी। हालांकि, मैं भाषा स्विच करने के लिए तैयार नहीं हूँ। सबसे पहले, मुझे उपयोग की जाने वाली पुस्तकालयों के लिए एक जेवीएम भाषा की आवश्यकता है, और इस तरह के मेरे विकल्पों को बाधित करता है। दूसरा, मैं इस कोड थोक को निम्न स्तर की जेवीएम भाषा में अनुवाद नहीं करना चाहता हूं। हालांकि, अगर आवश्यक हो तो मैं इस हॉटस्पॉट को किसी और चीज में फिर से लिखना चाहता हूं, हालांकि मुझे कोई संकेत नहीं है कि इसे कैसे इंटरफ़ेस करना है या ओवरहेड क्या होगा।

इस विधि के एकल-थ्रेडेड धीमेपन के अलावा, मैं प्रोग्राम को समांतरता के संदर्भ में पिछले 4 CPUs को स्केल करने के लिए भी नहीं मिल सकता। यह देखते हुए कि मैंने अपने पूरे समय 10-लाइन हॉटस्पॉट में पोस्ट किया है, मैं यह नहीं समझ सकता कि बाधा क्या हो सकती है।

Answer 1

यदि topScore को उसी seq के लिए बार-बार कहा जाता है तो आप memoize इसके मूल्य को देख सकते हैं।

उदा। http://code.activestate.com/recipes/52201/

Answer 2

धीमा होने के कारण कुछ भी नहीं निकलता है। मैं इस तरह भीतरी पाश पुनर्लेखन सकता है:

score = sum(logProbs[j][seq[j+i]] for j in xrange(l)) 

या यहाँ तक कि:

seqmatch = zip(seq[i:i+l], logProbs) 
score = sum(posscores[base] for base, posscores in seqmatch) 

लेकिन मैं नहीं जानता कि है कि या तो अधिक समय की बचत होगी।

यह डीएनए बेस को पूर्णांक 0-3 के रूप में स्टोर करने के लिए मामूली रूप से तेज़ हो सकता है, और एक शब्दकोश के बजाय टुपल से स्कोर देख सकता है। संख्याओं को अक्षरों का अनुवाद करने पर एक प्रदर्शन हिट होगा, लेकिन केवल एक बार किया जाना है।

Answer 3

कारण यह धीमी गति से है, क्योंकि यह हे है (एन * एन)

maximum subsequence एल्गोरिथ्म आप इस

Answer 4

मैं किसी भी विचार मैं क्या कर रहा हूँ नहीं है बेहतर बनाने में मदद कर सकते हैं लेकिन शायद यह है

ret = -1e9999 
logProbs = self.logProbs # save indirection 
l = len(logProbs) 

scores = collections.defaultdict(int) 

for j in xrange(l): 
    prob = logProbs[j] 
    for i in xrange(len(seq) - l + 1): 
     scores[i] += prob[seq[j + i]] 


ret = max(ret, max(scores.values())) 

Answer 5

निश्चित रूप से एक 2 डी सरणी के बजाय शब्दकोशों की एक सूची के रूप में numpy और दुकान logProbs का उपयोग करें: अपने algo में तेजी लाने के कर सकते हैं। उपर्युक्त सुझाव के अनुसार सीईसी को 1 डी सरणी (लघु) पूर्णांक के रूप में भी स्टोर करें। यह मदद करेगा यदि आपको फ़ंक्शन कॉल करने पर हर बार इन रूपांतरणों को करने की आवश्यकता नहीं होती है (फ़ंक्शन के अंदर इन रूपांतरणों को करने से आपको अधिक बचत नहीं होगी)।

import numpy as np 
... 
print np.shape(self.logProbs) # (20, 4) 
print np.shape(seq) # (1000,) 
... 
def topScore(self, seq): 
ret = -1e9999 
logProbs = self.logProbs # save indirection 
l = len(logProbs) 
for i in xrange(len(seq) - l + 1): 
    score = np.sum(logProbs[:,seq[i:i+l]]) 
    ret = max(ret, score) 

return ret 

क्या आपको लगता है कि बाद निर्भर करता है इन 2 डेटा तत्वों की है जिस पर सबसे अधिक बार परिवर्तन:: आप उन दूसरे लूप को समाप्त कर सकते

logProbs आम तौर पर ही रहता है और आप कई डीएनए चलाना चाहते हैं इसके माध्यम से अनुक्रम, फिर 2 डी सरणी के रूप में अपने डीएनए अनुक्रमों को ढेर करने पर विचार करें। numpy 2 डी सरणी के माध्यम से बहुत तेज़ी से लूप कर सकते हैं ताकि यदि आपके पास प्रक्रिया के लिए 200 डीएनए अनुक्रम हैं, तो यह केवल एक से थोड़ा अधिक समय लेगा।

अंत में, यदि आपको वास्तव में गति की आवश्यकता है, तो scipy.weave का उपयोग करें। आपको लूप को तेज करने के लिए तेज़ सी की कुछ पंक्तियां लिखना एक बहुत ही आसान तरीका है। हालांकि, मैं scipy> 0.8 की सलाह देते हैं।

Answer 6

i loop के बाहर xrange(l) प्रीकंप्यूटिंग के बारे में क्या?

Answer 7

आप छोरों के बाहर सिर्फ self.logProbs की तुलना में अधिक उत्थापन की कोशिश कर सकते हैं:

def topScore(self, seq): 
    ret = -1e9999 
    logProbs = self.logProbs # save indirection 
    l = len(logProbs) 
    lrange = range(l) 
    for i in xrange(len(seq) - l + 1): 
     score = 0.0 
     for j in lrange: 
      score += logProbs[j][seq[j + i]] 
     if score > ret: ret = score # avoid lookup and function call 

    return ret 

Answer 8

मुझे शक है यह एक महत्वपूर्ण अंतर कर देगा, लेकिन आप को बदलने की कोशिश कर सकते:

for j in xrange(l): 
     score += logProbs[j][seq[j + i]] 

को

for j,lP in enumerate(logProbs): 
     score += lP[seq[j + i]] 

या यहां तक ​​कि seq loop के बाहर गणना को उछाल भी।