如何 vectorize/optimize 依赖于先前行的计算

Question

我正在做一些运行时非常重要并且我们正在处理的数据很大的事情，但基本上问题归结为优化求解序列 x，其中 x1 已知且 x = ax+b 来自前一行。例如，起始状态：

最终状态将如下所示：

因为 3*1+2 = 5, 5*3+1 = 16, 等等

我尝试计算它的数学结果，结果是：

b0 = x1
xi = sum(n=0 to i-1)(bn*product(m=n+1 to i-1)(am)

例如，对于第 3 行，您最终会得到：

x3 = a1*a2*b0 + b1*a2 + b2 = 3*1*3 + 2*3 + 1 = 9 + 6 + 1 = 16

但在计算上，这似乎比通过遍历行来计算每个 x 更糟糕，就像这样：

for i in range(2,len(df)):
    df.x[i] = df.x[i-1]*df.a[i-1]+df.b[i-1]

是否有更简单的方法来解决我所缺少的这个问题，或者我只是在处理一个计算量大的操作，我将不得不承担迭代的成本？如果 a 项不存在，则可以通过 cumsum 处理 bn 部分，例如：

df['b_cumsum'] = x1+cumsum(df.b)

但我在尝试包含 a 项时最终碰壁了，尤其是因为即使在每个总和项中我们最终也需要这么多不同的产品集。

谢谢。

Answer 1

当我运行进入我无法向量化的函数时，但它需要高效，我使用 numba。这是一个即时编译 (JIT) 模块。大多数时候，这甚至比原生 pandas 方法更快：

from numba import njit

@njit
def calculation(arr):
    result = np.empty(arr.shape[0])
    for idx, row in enumerate(arr):
        if idx == 0:
            result[idx] = row[2]
        else:
            row = arr[idx-1]
            result[idx] = result[idx-1] * row[0] + row[1]
    
    return result

df['x'] = calculation(df.to_numpy())

print(df)

   a  b      x
0  1  2    3.0
1  3  1    5.0
2  2  2   16.0
3  4  8   34.0
4  1  9  144.0

注意：你想计时的时候。不要在第一个运行上计时，因为它还没有编译。首先运行一次，然后在第二次运行.

计时

Answer 2

你可以先计算一个重新缩放的 x: x' = x/cumprod( a) 使用匹配的 b' = b/cumprod(a)

这可以通过向量化操作来完成，就像从 x' 到 x:

的反向转换一样

ab = np.array([[1, 2],
               [3, 1],
               [2, 2],
               [4, 8],
               [1, 9]])

scale = ab.T[0].cumprod()
xp = 3+(ab.T[1]/scale).cumsum()
x = xp*scale
x
array([  5.,  16.,  34., 144., 153.])

如何 vectorize/optimize 依赖于先前行的计算

How to vectorize/optimize calculations that rely on prior rows

python

optimization

numpy

vectorization

pandas