このループスケールは

Question

二次の時間でない理由私は（5）とj不変はxrange [5ターンのためのアウターループのループを実行している間

t1=time.time() 

df1=train1[1,1:52] 
for i in xrange(40): 
    for j in xrange(52,551): 
     x=train1[i,(j-51):j] 
     df1=np.vstack((df1,x)) 

t2=time.time() 
t=t2-t1 

以下のコードを使用してnumpyのに行列を再配列してい]、それは< 1秒かかる。 10ターンでは、4秒かかります。 20ターン、約18秒かかります。 40ターン、〜85秒。

外部ループを直線的に増加させた場合でも、ループが2次時間でスケーリングされる理由を明確にしてください。

おかげ

PS：私はここに使用しています マトリックスは、ウィキペディアの競争のためKaggleのトレーニングセットに設定された訓練です。あなたは）（

Answer 1

を私はパンダのデータフレームに読み込まれているリンクからtrain_1.csvをダウンロードし.to_matrixを使用してnumpyの行列（すなわちtrain1）に変換することができます問題はvstackへの呼び出しがでdf1のコピーを作成することです各反復。シースのサイズdf1は、外側のループ範囲で線形に変化するので、二次ランタイムを取得します。コードのプロファイリング

はvstackによって呼び出され、ほとんどの時間をconcatenateに費やされていることを示しています。

In [13]: cProfile.run('q.proc()') 
     259486 function calls in 19.759 seconds 

    Ordered by: standard name 

    ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.001 0.001 19.759 19.759 <string>:1(<module>) 
    39920 0.030 0.000 0.036 0.000 numeric.py:534(asanyarray) 
    19960 0.031 0.000 15.037 0.001 shape_base.py:182(vstack) 
    19960 0.020 0.000 0.121 0.000 shape_base.py:237(<listcomp>) 
    39920 0.057 0.000 0.101 0.000 shape_base.py:63(atleast_2d) 
     1 4.720 4.720 19.758 19.758 temp.py:6(proc) 
     1 0.000 0.000 19.759 19.759 {built-in method builtins.exec} 
    39920 0.003 0.000 0.003 0.000 {built-in method builtins.len} 
    39920 0.006 0.000 0.006 0.000 {built-in method numpy.core.multiarray.array} 
    19960 14.886 0.001 14.886 0.001 {built-in method numpy.core.multiarray.concatenate} 
     2 0.000 0.000 0.000 0.000 {built-in method time.time} 
    39920 0.005 0.000 0.005 0.000 {method 'append' of 'list' objects} 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 

あなたはx年代のリストを作成し、ループの後に連結できます。

編集：train1をnp.random.rand(100,600)と定義しました。

Answer 2

私はちょうどより多くの時間をチェックして、あなたのコードを実行し、train1ためのランダム生成された行列使用して：私はこれを実行すると

import time 
import numpy as np 

t_total=time.time() 
train1=np.random.random((20, 550)) 
df1=train1[1,1:52] 
for i in range(5): 
    t1 = time.time() 
    tj = [] 
    for j in range(52,551): 
     t2 = time.time() 
     x=train1[i,(j-51):j] 
     df1=np.concatenate((df1,x),axis=0) 
     tj.append(time.time()-t2) 
    print("Time to loop on j:", time.time()-t1) 
    print("Average time for each j:", np.mean(tj)) 

print("Total time:", time.time()-t_total) 

を私は明らかに、すべてのループが長くなると長いことを示す、次の出力を取得します。

Time to loop on j: 0.009780406951904297 
Average time for each j: 1.9157577851e-05 
Time to loop on j: 0.02693343162536621 
Average time for each j: 5.33469932113e-05 
Time to loop on j: 0.06705927848815918 
Average time for each j: 0.000133752822876 
Time to loop on j: 0.08919048309326172 
Average time for each j: 0.000178138813179 
Time to loop on j: 0.11366486549377441 
Average time for each j: 0.000227188060661 
Total time: 0.3072977066040039 

私の推測では、次のとおりです。np.vstackは、単純マトリクス入力のサイズが大きくなるとより多くの時間を要し、それはあなたの実行時間が指数関数的に増加させているものです。しかし、この問題に対処するnumpyと同等のものを見つけることはできないようです...スタックしたいすべての配列をリストに格納し、最後にスタックを計算するという解決策があります：

import time 
import numpy as np 

t_total=time.time() 
train1=np.random.random((20, 550)) 
df1=[train1[1,1:52]] 
for i in range(5): 
    t1 = time.time() 
    tj = [] 
    for j in range(52,551): 
     t2 = time.time() 
     x=train1[i,(j-51):j] 
     df1.append(x) 
     tj.append(time.time()-t2) 
    print("Time to loop on j:", time.time()-t1) 
    print("Average time for each j:", np.mean(tj)) 
df1 = np.vstack(df1) 
print("Total time:", time.time()-t_total) 

と実行時間が、これは私を取得します。

Time to loop on j: 0.0005383491516113281 
Average time for each j: 7.99347260194e-07 
Time to loop on j: 0.0005192756652832031 
Average time for each j: 7.58734876981e-07 
Time to loop on j: 0.0005254745483398438 
Average time for each j: 7.73546452035e-07 
Time to loop on j: 0.0005245208740234375 
Average time for each j: 7.73546452035e-07 
Time to loop on j: 0.0005295276641845703 
Average time for each j: 7.80235550447e-07 
Total time: 0.008821249008178711 

多くの小さな配列を積み重ねることは、大きな配列、またはそのような何かを積み重ねるよりも簡単であると思われます。固定サイズのオブジェクトをリストに追加すると、リストのサイズにかかわらず固定コストが発生します。