各繰り返しが以前の反復の状態に依存するループをベクトル化または最適化する

Question

私はPythonで実装しているアルゴリズムを持っています。アルゴリズムは1.000.000回実行されるので、できるだけ最適化したいと考えています。アルゴリズムのベースは3つのリスト（energy,pointおよびvalList）と2つのカウンタpおよびeです。

2つのリストenergyとpointには、意思決定に基づいて0〜1の数値が含まれています。 pはポイントカウンタであり、eはエネルギーカウンタです。 Eneryのポイントを交換でき、各エネルギーのコストはvalListで定義されています（時間に依存します）。私はまた、他のものと貿易することができます。しかし、私は一度にすべてをトレードする必要があります。

アルゴリズムの概要：

1. energyの要素が閾値を超えているとpointの要素が別の閾値以下であるブール・リストを取得します。これはポイントのためにエネルギーを交換する決定です。対応するポイントのリストを取得します。これは、エネルギーのためにポイントを交換することを決定します。
2. それぞれのブールリストにあります。
3. 各アイテムのペア（pB、ポイントboolとeB、energy bool（エネルギーブールとポイントを交換する場合は、 ）を2つのブール値リストから削除します：pBがtrueでポイントがある場合は、すべてのポイントをeneryに交換したいと思います。 eBが真で、エネルギーがある場合、私はすべてのエネルギーをポイントに交換したいと思っています。

このは私が出ている実装です。（それを行うことができる場合）

start = time.time() 
import numpy as np 

np.random.seed(2) #Seed for deterministic result, just for debugging 

topLimit = 0.55 
bottomLimit = 0.45 

#Generate three random arrays, will not be random in the real world 
res = np.random.rand(500,3) #Will probably not be much longer than 500 
energy = res[:,0]   
point = res[:,1] 
valList = res[:,2] 

#Step 1: 
#Generate two bools that (for ex. energy) is true when energy is above a threashold 
#and point below another threshold). The opposite applies to point 
energyListBool = ((energy > topLimit) & (point < bottomLimit)) 
pointListBool = ((point > topLimit) & (energy < bottomLimit)) 

#Step 2: 
#Remove all 'true' that comes after another true since this is not valid 
energyListBool[1:] &= energyListBool[1:]^energyListBool[:-1] 
pointListBool[1:] &= pointListBool[1:]^pointListBool[:-1] 

p = 100 
e = 0 

#Step 3: 
#Loop through the lists, if point is true, I loose all p but gain p/valList[i] for e 
#If energy is true I loose all e but gain valList[i]*e for p 
for i in range(len(energyListBool)): 
    if pointListBool[i] and e == 0: 
     e = p/valList[i] #Trade all points to energy 
     p = 0 
    elif energyListBool[i] and p == 0: 
     p = valList[i]*e #Trade all enery to points 
     e = 0 

print('p = {0} (correct for seed 2: 3.1108006690739174)'.format(p)) 
print('e = {0} (correct for seed 2: 0)'.format(e)) 

end = time.time() 
print(end - start) 

は、私は何をしてstruggelingいforループをどのようにベクトル化されたので、私は使用することができますそれは私の心の中でおそらくもっと速くなるfor-loopの代わりに。

Answer 1

ベクター化では、n番目の計算ステップが以前のn-1ステップに依存してはならないため、不可能な現在の問題設定内です。しかし、時には、f(n) = F(f(n-1), f(n-2), ... f(n-k))といういわゆる「閉形式」を見つけることができます。つまり、f(n)の明示的な式はnに依存しませんが、それは別の研究上の問題です。

さらに、アルゴリズムの観点からは、アルゴリズムの複雑さが依然としてC*n = O(n)であるため、このようなベクトル化はあまり効果がありません。しかし、実際には「複雑度定数」Cが重要なので、それを減らす方法はいくつかあります。たとえば、C/C++でクリティカルループを書き直すのは大きな問題ではありません。