पुनरावर्ती समीकरणों के लिए कुशल पायथन तरीका

Question

मैं अपने कोड के एक टुकड़े में लूप को अनुकूलित करने की कोशिश कर रहा हूं। मैंने सोचा कि इसे एक और अधिक गड़बड़ तरीके से लिखना इसे तेज कर देगा, लेकिन अब धीमा है! समीकरण इनपुट के रूप में लेता है n लंबाई की एक numpy.array vec:

from numpy import * 

def f(vec): 
    n=len(vec) 
    aux=0 
    for i in range(n): 
     aux = aux + (1- aux)*vec[i] 
    return aux 

def f2(vec): 
    n=len(vec) 
    G=tril(array([-vec]*n),-1)+1    #numpy way! 
    aux=dot(G.prod(1),vec) 
    return aux 


if __name__ == '__main__': 
    import timeit 
    print(timeit.timeit("f(ones(225)+4)", setup="from __main__ import f\nfrom numpy import ones",number=1000)) 
    print(timeit.timeit("f2(ones(225)+4)", setup="from __main__ import f2\nfrom numpy import ones,tril,dot",number=1000)) 

0,429496049881 [एस]

5,66514706612 [एस]

अंत में मैं अपने पाश में पूरे समारोह inserte का फैसला किया, एक 3x प्रदर्शन बढ़ावा मिल रहा है। मैं वास्तव में 100x प्रदर्शन को बढ़ावा देने की तलाश में हूं, लेकिन मुझे नहीं पता कि और क्या करना है।

def CALC_PROB_LOC2(int nSectors, int nZones,double[:] beta, double[:] thetaLoc,np.ndarray[double, ndim=2] h, np.ndarray[double, ndim=2] p, np.ndarray[np.float64_t, ndim=3] U_nij, np.ndarray[double, ndim=2] A_ni): 
    cdef np.ndarray[double, ndim=3] Pr_nij =np.zeros((nSectors,nZones,nZones),dtype="d") 
    cdef np.ndarray[double, ndim=2] U_ni =np.zeros((nSectors,nZones),dtype="d") 
    #cdef np.ndarray[np.float64_t, ndim=1] A_ni_pos 
    cdef Py_ssize_t n,i,opt 
    cdef int aux_bool,options 
    cdef np.ndarray[np.float64_t, ndim=1] prob,attractor,optionCosts 
    cdef np.ndarray[np.float64_t, ndim=1] eq23,utilities 
    cdef double disu 
    cdef double eq22 
    cdef double aux17 
    for n in range(nSectors): 
     aux_bool=1 
     if n in [0,2,9,10,11,12,13,14,18,19,20]: 
      for i in xrange(nZones): 
       U_ni[n,i]=p[n,i]+h[n,i] 
       Pr_nij[n,i,i]=1 
      aux_bool=0 
     if aux_bool==1: 
      if beta[n]<=0: 
       for i in xrange(nZones): 
        U_ni[n,i]=U_nij[n,i,i] 
      else: 
       A_ni_pos=A_ni[n,:]>0 
       options=len(A_ni[n,:][A_ni_pos]) 
       attractor=A_ni[n,:][A_ni_pos] 
       if options>0: 
        for i in xrange(nZones): 
         optionCosts=U_nij[n,i,A_ni_pos] 
         disu=0 
         eq22=0 
         aux17=0 
         prob=np.ones(options)/options #default value 
         if beta[n]==0: 
          Pr_nij[n,i,A_ni_pos],U_ni[n,i]= prob,0 
         if options==1: 
          Pr_nij[n,i,A_ni_pos],U_ni[n,i]= prob,optionCosts 
         else: 
          if thetaLoc[n]<=0: 
           cmin=1 
          else: 
           cmin=(optionCosts**thetaLoc[n]).min() 
           if cmin==0: 
            cmin=100 
          utilities=optionCosts/cmin 
          eq23=-beta[n]*utilities 
          eq23=np.exp(eq23) 
          aux17=np.dot(attractor,eq23) 
          if aux17==0: 
           Pr_nij[n,i,A_ni_pos],U_ni[n,i]= 0*prob,0 
          else: 
           for opt in range(options): 
            eq22=eq22+(1-eq22)*eq23[opt] 
           prob=attractor*eq23/aux17 
           disu=cmin*(-np.log(eq22)/beta[n]) 
           Pr_nij[n,i,A_ni_pos],U_ni[n,i]= prob,disu 


    return Pr_nij,U_ni 

Answer 1

कि जब एक रेखीय एल्गोरिदम एक द्विघात से परिवर्तित कर दिया जाता है क्या होता है:: कोई फर्क नहीं पड़ता कि यह कैसे तेजी से मार डाला है, बेहतर एल्गोरिथ्म हमेशा (एक समस्या काफी बड़ा के लिए) जीतता है यह मेरा अंतिम कार्य है।

यह बहुत स्पष्ट है कि quadractic समय में f2 रन क्योंकि है कि एक मैट्रिक्स वेक्टर डॉट उत्पाद के समय जटिलता है रैखिक समय में f रन, और।

एक लॉग-लॉग साजिश स्पष्ट रूप से समय से चल रहा है में अंतर (रेखीय f को संदर्भित करता है, f2 को quadractic) दिखाता है:

हरे रंग की रेखा के दाएँ अधिकांश भाग (यानी, जब यह एक सीधी रेखा के रूप में व्यवहार नहीं करता है) समझाया जा सकता है क्योंकि numpy कार्यों में आमतौर पर एक उच्च ओवरहेड होता है जो छोटे अक्षरों के लिए नगण्य है लेकिन छोटे होने पर चलने वाले समय पर हावी है।

---

कि पहले से ही एक तेजी से एल्गोरिथ्म का उपयोग कर रहा है "मानक" जिस तरह से अजगर में कोड तेजी लाने के लिए संकलित कोड के लिए तक पहुँचने और एक विस्तार लिखने के लिए है। Cython आपको कुछ प्रकार की एनोटेशन के साथ पायथन स्रोत कोड को एनोटेट करके ऐसा करने देता है, और यह numpy arrays को समझता है।

कि vec Cython की कसौटी पर युगल की एक सरणी है, aux एक डबल और i एक पूर्णांक है, यह एक सी विस्तार जो मेरे लिए तेजी से 400 गुना है उत्पन्न करने में सक्षम है।

def f(double[:] vec): 
    n = len(vec) 
    cdef double aux = 0 
    cdef int i 
    for i in range(n): 
     aux = aux + (1- aux)*vec[i] 
    return aux 

आप IPython का उपयोग करने की है, तो आप सिर्फ %load_ext cythonmagic चलाने के लिए और फिर एक सेल लाइन %%cython लगाया जाता है करने के लिए है कि समारोह कॉपी इसे आज़माने के लिए कर सकते हैं। इसे बनाने और संकलित करने के अन्य तरीकों को साइथन documentation में समझाया गया है। वैसे, आईपीथन आपको समय-समय पर बयान से पहले %timeit लिखकर कोड का समय देता है, यह वास्तव में आसान है।

PyPy का उपयोग करने के लिए एक पूरी तरह से अलग विकल्प है, एक पायथन 2.7 कार्यान्वयन जो कि एक जेआईटी के साथ आता है और इसमें कुछ बुनियादी संख्यात्मक समर्थन है। यह import numpy के लिए import numpypy को प्रतिस्थापित करके इस छोटे स्निपेट को चला सकता है, लेकिन यह संभव है कि यह आपके पूरे कार्यक्रम को चलाने में सक्षम नहीं होगा। यह साइथन की तुलना में धीमी गति से है लेकिन यह एक कंपाइलर की आवश्यकता नहीं है और न ही कोड को एनोटेट कर रहा है।