如何让我的Python程序运行更快？

Question

我正在读取一个.csv文件并创建一个pandas dataframe，该文件是股票文件。我只关心日期、公司和收盘价。我想让我的程序找到指定公司在指定日期范围内的最大利润，需要使用分而治之算法。我只会用for循环，但它运行时间太长了。.csv文件有20万行，请问如何加速程序运行？

import pandas as pd
import numpy as np
import math

def cleanData(file):
    df = pd.read_csv(file)
    del df['open']
    del df['low']
    del df['high']
    del df['volume']
    return np.array(df)
    
df = cleanData('prices-split-adjusted.csv')

bestStock = [None, None, None, float(-math.inf)]

def DAC(data):
    global bestStock

    if len(data) > 1:
        mid = len(data)//2
        left = data[:mid]
        right = data[mid:]
    
        DAC(left)
        DAC(right)
    
        for i in range(len(data)):
            for j in range(i+1,len(data)):
                if data[i,1] == data[j,1]:
                    profit = data[j,2] - data[i,2]
                    if profit > bestStock[3]:
                        bestStock[0] = data[i,0]
                        bestStock[1] = data[j,0]
                        bestStock[2] = data[i,1]
                        bestStock[3] = profit
                    
                    print(bestStock)
    print('\n')
    return bestStock
    
print(DAC(df))

- Anonomous

---

干得好！做得很棒！ - Johnny

导致系统性能缓慢的主要问题是：1）您手动迭代嵌套循环中的2列，而不使用利用快速ndarray函数的pandas操作；2）您使用递归调用，看起来漂亮简单，但速度较慢。尝试使用pandas函数例如groupby（“company”）。agg（...）获取公司最佳收益的新列。然后在这个新列上使用idxmax，以获取所有公司中获得最佳收益的公司的条目。 - SeaBean

我好像迷失了！代码是否能够到达嵌套的for循环（假设发布的代码没有缩进错误）？ - sai

@sai 是的，它确实可以。然而，嵌套循环逻辑（例如冒泡排序）正在执行所有任务。该代码并没有真正利用分治结果。 - SeaBean

Answer 1

我有两件事情需要您考虑（我的答案尽量不改变您的算法方法，即嵌套循环和递归函数，并首先解决低级问题）：

1. 除非你在调试，否则尽量避免在循环内使用print()。(在你的情况下.. print(bestStock) ..) I/O开销可能会累加，特别是如果你在大数据集上循环并经常打印到屏幕上。一旦你对你的代码满意，就注释掉它来运行完整的数据集，并仅在调试会话期间取消注释。你可以期望在不必在循环中打印到屏幕的情况下看到一些速度改善。

2. 如果你想要更多的"加速"方法，我发现在我的案例中（与你的类似，尤其是在搜索/排序问题中），只需将昂贵的部分（Python 'For'循环）切换到Cython （并静态定义变量类型..这是关键！提高速度），即使在优化实现之前，也可以使我获得几个数量级的速度提升。查看Cython https://cython.readthedocs.io/en/latest/index.html。如果这还不够，那么并行处理是你的下一个好朋友，这需要重新思考你的代码实现。

- aaronlhe

Answer 2

主要导致系统性能缓慢的问题包括：

1. 您手动循环遍历嵌套循环中的2列，而不使用利用快速ndarray函数的pandas操作；
2. 您使用递归调用，这看起来很美观简洁，但速度较慢。

将示例数据设置如下：

          Date  Company         Close
0   2019-12-31     AAPL     73.412498
1   2019-12-31       FB    205.250000
2   2019-12-31     NFLX    323.570007
3   2020-01-02     AAPL     75.087502
4   2020-01-02       FB    209.779999
...        ...      ...           ...
184 2020-03-30       FB    165.949997
185 2020-03-30     NFLX    370.959991
186 2020-03-31     AAPL     63.572498
187 2020-03-31       FB    166.800003
188 2020-03-31     NFLX    375.500000

189 rows × 3 columns

然后使用以下代码（如果列标签不同，请修改为您的标签）：

df_result = df.groupby('Company').agg(Start_Date=pd.NamedAgg(column='Date', aggfunc="first"), End_Date=pd.NamedAgg(column='Date', aggfunc="last"), bestGain=pd.NamedAgg(column='Close', aggfunc=lambda x: x.max() - x.iloc[0]))

输出结果：

        Start_Date    End_Date   bestGain
Company         
AAPL    2019-12-31  2020-03-31   8.387505
FB      2019-12-31  2020-03-31  17.979996
NFLX    2019-12-31  2020-03-31  64.209991

获取最大收益的条目：

df_result.loc[df_result['bestGain'].idxmax()]

输出结果：

Start_Date    2019-12-31 00:00:00
End_Date      2020-03-31 00:00:00
bestGain                64.209991
Name: NFLX, dtype: object

执行时间比较

使用缩小后的3只股票在3个月内的数据，利用pandas函数编写的代码（需要8.9毫秒）比手动迭代numpy数组并进行嵌套循环和递归调用的原始代码（需要16.9毫秒）快了约一半，即使大部分print()函数调用已经被删除。

您的代码中DAC()函数内的print()已被删除：

%%timeit
"""
def cleanData(df):
    # df = pd.read_csv(file)
    del df['Open']
    del df['Low']
    del df['High']
    del df['Volume']
    return np.array(df)
"""    
# df = cleanData('prices-split-adjusted.csv')
# df = cleanData(df0)
df = np.array(df0)

bestStock = [None, None, None, float(-math.inf)]

def DAC(data):
    global bestStock

    if len(data) > 1:
        mid = len(data)//2
        left = data[:mid]
        right = data[mid:]
    
        DAC(left)
        DAC(right)
    
        for i in range(len(data)):
            for j in range(i+1,len(data)):
                if data[i,1] == data[j,1]:
                    profit = data[j,2] - data[i,2]
                    if profit > bestStock[3]:
                        bestStock[0] = data[i,0]
                        bestStock[1] = data[j,0]
                        bestStock[2] = data[i,1]
                        bestStock[3] = profit
                    
                    # print(bestStock)
    # print('\n')
    return bestStock
    
print(DAC(df))

[Timestamp('2020-03-16 00:00:00'), Timestamp('2020-03-31 00:00:00'), 'NFLX', 76.66000366210938]
16.9 ms ± 303 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

在pandas编程中的新简化代码：

%%timeit
df_result = df.groupby('Company').agg(Start_Date=pd.NamedAgg(column='Date', aggfunc="first"), End_Date=pd.NamedAgg(column='Date', aggfunc="last"), bestGain=pd.NamedAgg(column='Close', aggfunc=lambda x: x.max() - x.iloc[0]))
df_result.loc[df_result['bestGain'].idxmax()]

8.9 ms ± 195 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

- SeaBean

---

我删掉了打印语句，但使用导入的 .csv 文件时我的代码仍无法执行。虽然 Pandas 的方法确实有效，但有没有办法在递归函数内执行 Pandas 代码？我的问题要求使用递归函数。 - Anonomous

@JaredPino 递归函数解决方案已添加，以演示如何正确使用递归调用。代码在处理股票中断方面仍存在限制。您需要加以改进。这只是为了演示递归调用。 - SeaBean

Answer 3

使用递归函数的解决方案：

你的递归函数的主要问题在于没有利用减少数据量的递归调用的结果。

为了正确地将递归函数作为分而治之的方法使用，您应该执行三个主要步骤：

1. 将整个数据集划分为较小的部分，并通过递归调用处理每个较小的部分
2. 在每个递归调用中处理端点情况（大多数情况下是最简单的情况）
3. 合并所有减少大小调用的结果

递归调用的美妙之处在于，您可以通过用两个更轻松的步骤替换处理来解决复杂的问题：第一步是处理端点情况，其中您通常只能处理一个数据项（这通常很容易）。第二步只需要采取另一个简单的步骤来合并减小大小调用的结果。

你成功迈出了第一步，但没有迈出后面的两步。特别地，你没有利用较小块的结果简化处理过程。相反，每次调用都会循环2维numpy数组中的所有行来处理整个数据集。嵌套循环逻辑就像一个“冒泡排序”[时间复杂度为(n平方)而不是(n)]。因此，你的递归调用只是浪费时间而没有价值！建议修改你的递归函数如下:

def DAC(data):
    # global bestStock                 # define bestStock as a local variable instead
    bestStock = [None, None, None, float(-math.inf)]    # init bestStock

    if len(data) = 1:                  # End-point case: data = 1 row
        bestStock[0] = data[0,0]
        bestStock[1] = data[0,0]
        bestStock[2] = data[0,1]
        bestStock[3] = 0.0
    elif len(data) = 2:                # End-point case: data = 2 rows
        bestStock[0] = data[0,0]
        bestStock[1] = data[1,0]
        bestStock[2] = data[0,1]       # Enhance here to allow stock break 
        bestStock[3] = data[1,2] - data[0,2]
    elif len(data) >= 3:               # Recursive calls and consolidate results
        mid = len(data)//2
        left = data[:mid]
        right = data[mid:]
    
        bestStock_left = DAC(left)
        bestStock_right = DAC(right)

        # Now make use of the results of divide-and-conquer and consolidate the results
        bestStock[0] = bestStock_left[0]
        bestStock[1] = bestStock_right[1]
        bestStock[2] = bestStock_left[2]    # Enhance here to allow stock break 
        bestStock[3] = bestStock_left[3] if bestStock_left[3] >= bestStock_right[3] else bestStock_right[3] 
    
    # print(bestStock)
    # print('\n')
    return bestStock

这里我们需要处理两种端点情况：1行和2行。原因是对于只有1行的情况，我们无法计算增益，只能将增益设置为零。增益可以从2行开始计算。如果不将其拆分为这两个端点情况，则最终可能只会一直传播零增益。

以下是如何编写递归调用以利用它的演示。代码的限制仍需要进行微调。您必须进一步完善它以处理股票破裂案例。现在，2行和≥3行的代码假定目前没有股票破裂。

- SeaBean