python - 对数据框中所有行组合求和的更快方法

Question

我有一个包含 10,000 行的数据框，我试图将这些行的所有可能组合相加。根据我的计算，大约有 5000 万种组合。我将举一个小例子来简化我的数据的样子:

df = Ratio     Count     Score
     1         6         11
     2         7         12
     3         8         13
     4         9         14
     5         10        15

这是想要的结果:

results = Min Ratio     Max Ratio     Total Count     Total Score
          1             2             13              23
          1             3             21              36
          1             4             30              50
          1             5             40              65
          2             3             15              25
          2             4             24              39
          2             5             34              54
          3             4             17              27
          3             5             27              42
          4             5             19              29

这是我想出的代码来完成计算:

for i in range(len(df)):
    j = i + 1
    while j <= len(df):
        range_to_calc = df.iloc[i:j]
        total_count = range_to_calc['Count'].sum()
        total_score = range_to_calc['Score'].sum()
        new_row = {'Min Ratio': range_to_calc.at[range_to_calc.first_valid_index(),'Ratio'],
                   'Max Ratio': range_to_calc.at[range_to_calc.last_valid_index(),'Ratio'],
                   'Total Count': total_count,
                   'Total Score': total_score}
        results = results.append(new_row, ignore_index=True)
        j = j + 1

这段代码有效，但根据我运行几分钟后的估计，它需要 200 小时才能完成。我知道使用 numpy 会快很多，但我无法理解如何构建多个数组以添加在一起。 (我认为如果我只做 1+2、2+3、3+4 等会很容易，但要困难得多，因为我需要 1+2、1+2+3、1+2+3 +4 等)是否有更有效的方法来完成此计算，以便它可以在合理的时间内运行？谢谢!
P.S.:如果你想知道我想用 5000 万行的数据框做什么，我的最终结果实际上并不需要它。我最终希望将结果中每一行的总分除以其总计数以获得每个总计数的总分值，然后显示每个总计数的 1,000 个最高总分，以及每个相关的最小比率、最大值比率、总计数和总分。

Answer 1

首先，您可以改进算法 .然后，您可以使用 加快计算速度。 Numpy 矢量化/广播 .
以下是提高算法性能的有趣点:

append Pandas 的速度很慢，因为它重新创建了一个新的数据帧。你永远不应该在代价高昂的循环中使用它。相反，您可以将这些行附加到 Python 列表中，甚至可以直接添加 将项目写入预先分配的 Numpy 向量 .

计算部分和需要一个 O(n)您可以的时间 预先计算累积和 然后在恒定时间内找到部分和。

CPython 循环非常慢，但由于广播，可以使用 Numpy 对内部循环进行矢量化。

这是结果代码:

import numpy as np
import pandas as pd

def fastImpl(df):
    n = len(df)
    resRowCount = (n * (n+1)) // 2
    k = 0

    cumCounts = np.concatenate(([0], df['Count'].astype(int).cumsum()))
    cumScores = np.concatenate(([0], df['Score'].astype(int).cumsum()))
    ratios = df['Ratio'].astype(int)
    minRatio = np.empty(resRowCount, dtype=int)
    maxRatio = np.empty(resRowCount, dtype=int)
    count = np.empty(resRowCount, dtype=int)
    score = np.empty(resRowCount, dtype=int)

    for i in range(n):
        kStart, kEnd = k, k+(n-i)
        jStart, jEnd = i+1, n+1
        minRatio[kStart:kEnd] = ratios[i]
        maxRatio[kStart:kEnd] = ratios[i:n]
        count[kStart:kEnd] = cumCounts[jStart:jEnd] - cumCounts[i]
        score[kStart:kEnd] = cumScores[jStart:jEnd] - cumScores[i]
        k = kEnd
    assert k == resRowCount

    return pd.DataFrame({
        'Min Ratio': minRatio,
        'Max Ratio': maxRatio,
        'Total Count': count,
        'Total Score': score
    })

请注意，此代码给出的结果与问题中的代码相同，但原始代码并未给出问题中所述的预期结果。还要注意，由于输入是整数，为了性能，我强制 Numpy 使用整数(尽管算法也应该使用浮点数)。
此代码是 快几十万倍与大数据帧上的原始代码相比，它成功计算了 的数据帧0.7 秒内 10,000 行 .