再帰方程式のための効率的なPythonの方法

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 [S]

5.66514706612 [S]

最後に私がループ全体機能をinserteすることを決定し、パフォーマンスを3倍向上させます。私は実際に100倍の性能向上を望んでいますが、それ以外のことは分かりません。線形アルゴリズムは二次ものに置き換えますときに何が起こるかだ

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

：どんなにそれが実行されますどのくらいの速、より良いアルゴリズムは常に（十分に大きな問題のために）勝っていないこれが私の最後の関数です。

fは線形時間で実行され、f2は行列 - ベクトルドット積の時間的複雑さのために矩形時間で実行されることは明らかです。

対数 - 対数プロットは明らかに（リニアf2にquadractic、fを指す）実行時間の違いを示しています

緑線（すなわち、時の最も右の部分numpy関数は通常、小さなオーバーヘッドを持つため、小さくない配列では無視されますが、小さな配列では実行時間が支配的になるため、直線として動作しません。

---

すでに高速アルゴリズムを使っているPythonでコードをスピードアップするために「標準」の方法は、コンパイルされたコードのために達すると拡張子を書くことです。 Cythonは、Pythonのソースコードに少数の型アノテーションを付けることでこれを可能にし、numpyの配列を理解します。

vecはダブルスの配列であり、auxは倍精度であり、iの整数です。これは400倍高速のC拡張を生成することができます。

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で始まるセルにその機能をコピーすることができます。それを構築してコンパイルする他の方法は、Cython documentationで説明されています。ちなみに、IPythonでは、文の前に%timeitと書くことでコードをタイムリミットすることもできます。本当に便利です。

完全に異なるオプションは、PyPy（JITに付属し、基本的なnumpyサポートを持つPython 2.7実装を使用することです）。 import numpyの場合はimport numpypyを置き換えてこの小さなスニペットを実行できますが、プログラム全体を実行できない可能性があります。それはCythonより遅いですが、コンパイラを再requiereしたり、コードに注釈をつけることはありません。