python - 向量化或优化循环，其中每次迭代都取决于前一次迭代的状态

Question

我有一个在 python 中实现的算法。该算法可能会执行 1.000.000 次，所以我想尽可能地优化它。该算法的基础是三个列表(energy、point 和 valList)和两个计数器 p 和 e.

energy 和 point 这两个列表包含 0 到 1 之间的数字，我根据这些数字做出决定。 p 是一个点计数器，e 是一个能量计数器。我可以用积分换取能量，每种能量的成本都在 valList 中定义(它取决于时间)。我也可以换一种方式。但我必须一次全部交易。

算法概要:

1. 获取一个 bool 列表，其中 energy 中的元素高于阈值，point 中的元素低于另一个阈值。这是一个用能量换取点数的决定。得到相应的点数列表，决定用点数换取能量
2. 在每个 bool 列表中。删除在另一个真值之后出现的所有真值(如果我用所有点交换能量，我不允许在点之后再次这样做)
3. 对于两个 bool 列表中的每个项目对(pB，point bool 和 eB，energy bool):如果 pB 为真并且我有分数，我想要用我所有的点数换取能量。如果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)

我正在努力解决的问题是如何(如果可以的话)对 for 循环进行矢量化，因此我可以使用它而不是 for 循环，在我看来这可能会更快。

Answer 1

在当前的问题设置中，这是不可能的，因为矢量化本质上要求您的第 n 计算步骤不应依赖于之前的 n-1 步骤。然而，有时可以找到所谓的递归“封闭形式” f(n) = F(f(n-1), f(n-2), ... f(n-k)) ，即找到不依赖于 n 的 f(n) 的显式表达式，但这是一个单独的研究问题。

此外，从算法的角度来看，这样的矢量化不会带来太多好处，因为您的算法的复杂度仍然是 C*n = O(n)。但是，由于“复杂性常量”C 在实践中确实很重要，因此有不同的方法可以降低它。例如，用 C/C++ 重写关键循环应该不是什么大问题。