Python：非常に遅い実行ループ

Question

私はHMMとビタビアルゴリズムを使って誤植を提案するコードを書いています。テキストの各単語のある時点で、私は次のことをしなければならない。あなたはそれは計算に関与していると私は実行すると、それが実行するのに時間がかかりすぎる見ることができるように

#FYI Windows 10, 64bit, interl i7 4GRam, Python 2.7.3 
import numpy as np 
import pandas as pd 

for k in range(10000): 
    tempWord = corruptList20[k] #Temp word read form the list which has all of the words 
    delta = np.zeros(26, len(tempWord))) 
    sai = np.chararray(26, len(tempWord))) 
    sai[:] = '@' 

    # INITIALIZATION DELTA 
    for i in range(26): 
     delta[i][0] = #CALCULATION matrix read and multiplication each cell is different 
    # INITILIZATION END 

    # 6.DELTA CALCULATION 
    for deltaIndex in range(1, len(tempWord)): 
     for j in range(26): 
      tempDelta = 0.0 
      maxDelta = 0.0 
      maxState = '' 
      for i in range(26): 
       # CALCULATION to fill each cell involve in: 
        # 1-matrix read and multiplication 
        # 2 Finding Column Max 
        # logical operation and if-then-else operations 

    # 7. SAI BACKWARD TRACKING 
    delta2 = pd.DataFrame(delta) 
    sai2 = pd.DataFrame(sai) 

    proposedWord = np.zeros(len(tempWord), str) 
    editId = 0 
    for col in delta2.columns: 
     # CALCULATION to fill each cell involve in: 
       # 1-matrix read and multiplication 
       # 2 Finding Column Max 
       # logical operation and if-then-else operations 
     editList20.append(''.join(editWord)) 
#END OF LOOP 

（私は10,000語を持っていると仮定します）。 現在、

のPython 2.7.3を私のラップトップが盗まれたと私は、Windows 10、64、4GRamでこれを実行して私の質問：誰もが、私は最適化に使用できる任意のポイントを見ることができますか？ループを次のラウンドに移してメモリを解放する前に、ループで作成した行列を削除する必要がありますか？これは自動的に行われますか？

以下のコメント後

とxrange代わりにrangeを使用して性能が30％によってほとんど増加しました。今回の変更後、ここにスクリーンショットを追加しています。反復処理するために番号が取り込まリスト全体を構築rangeコメントで述べたように、rangeの挙動は2でのPython 2および3

間で変化

Answer 1

私はrangeの議論が大きく異なるとは思わない。 rangeがイテレータであるPython3では、繰り返しの前にリストに展開しても時間はあまり変わりません。

In [107]: timeit for k in range(10000):x=k+1 
1000 loops, best of 3: 1.43 ms per loop 

In [108]: timeit for k in list(range(10000)):x=k+1 
1000 loops, best of 3: 1.58 ms per loop 

numpyで

とpandasループをスピードアップする本当の鍵は、配列全体またはデータフレーム上で動作してコンパイル操作でそれらを交換することです。しかし、純粋なPythonでさえ、反復メカニズムではなく、反復の内容を合理化することに焦点を合わせます。

======================

for i in range(26): 
    delta[i][0] = #CALCULATION matrix read and multiplication 

マイナーチェンジ：delta[i, 0] = ...。これは、単一要素のアドレス指定の配列方法です。機能的にはそれはしばしば同じですが、その意図はより明確です。しかし、あなたはその列のすべてを一度設定することはできないと思いますか？

N = len(tempWord) 
delta = np.zeros(26, N)) 
etc 

====================

delta[:,0] = ... 

タイトなループでは、このような一時的な変数は、時間を節約することができます。これはタイトではないので、ここでは明快さを追加しています。

===========================

この1つの醜いネストされた3重ループ。 26ステップは大きいとは言えませんが、26 * 26 * Nは：

for deltaIndex in range(1,N): 
    for j in range(26): 
     tempDelta = 0.0 
     maxDelta = 0.0 
     maxState = '' 
     for i in range(26): 
      # CALCULATION 
       # 1-matrix read and multiplication 
       # 2 Finding Column Max 
       # logical operation and if-then-else operations 

これは配列操作で置き換えることに焦点を当てています。これは、反復メカニズムではなく、変更する必要がある3つのコメント行です。

================

はproposedWordリストではなく、配列がより速くなる可能性があることを確認します。小さなリスト演算は配列numpyの配列が作成オーバーヘッドを持っているので、配列1より高速であることがよくあります。

In [136]: timeit np.zeros(20,str) 
100000 loops, best of 3: 2.36 µs per loop 

In [137]: timeit x=[' ']*20 
1000000 loops, best of 3: 614 ns per loop 

「空の」リストを作成するときは、同じもののコピーだけでなく、要素が本当に独立していることに注意する必要があります。

In [159]: %%timeit      
x = np.zeros(20,str) 
for i in range(20): 
    x[i] = chr(65+i) 
    .....: 
100000 loops, best of 3: 14.1 µs per loop 

In [160]: timeit [chr(65+i) for i in range(20)] 
100000 loops, best of 3: 7.7 µs per loop 

Answer 2

、次いで反復リストの上にこれをタイトループで行うのは非常に高価です。

3では、rangeは、私が知る限り、開始番号、ステップ（数字間の距離）、および終了番号の3つの数字のみからなる単純なオブジェクトを作成します。簡単な数学を使うと、必然的に反復する必要がなく、範囲に沿って任意の点を計算できます。これは、リスト全体が介入されたときに、O（n）の代わりにO（1）に「ランダムアクセス」を行い、高価なリストの作成を防ぎます。

では、xrangeを使用して、リストの代わりに範囲オブジェクトを反復処理します。

（@Tom：回答を投稿する場合は削除します）

Answer 3

コードが不足しているために必要なことは正確には分かりませんが、numpyコードをベクトル化する方法を学ぶ必要があることは明らかです。これは100倍のスピードアップにつながります。

おそらく、すべての内部forループを取り除いて、ベクトル化された操作で置き換えることができます。

例えば、代わりに

for i in range(26): 
    delta[i][0] = #CALCULATION matrix read and multiplication each cell is differen 

のこの

delta[:, 0] = # Vectorized form of whatever operation you were going to do.