我正在读取.csv文件并创建pandas数据帧。这个档案是一个库存档案。我只对日期、公司和成交价格感兴趣。我想让我的程序找到最大利润与开始日期,结束日期和公司。它需要使用分治算法。我只知道如何使用循环,但它需要很长时间才能运行。.csv文件有200000行。我怎样才能让它跑得快?
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))
我有两件事需要你考虑(我的回答尽量不改变你的算法方法,即嵌套循环和递归函数,并首先处理底层结果):
-
除非您正在调试,否则请尝试避免在循环中打印()。(在您的情况下..打印(bestStock)..)I/O开销可能会增加,特别是如果你在大型数据集上循环并经常打印到屏幕上。一旦您对代码感到满意,请将其注释掉以在完整的数据集上运行,并仅在调试会话期间取消注释。在不需要循环打印到屏幕的情况下,您可以预期速度会有所提高。
-
如果你想要更多的"加速"方法,我发现,在我的案例中(类似于我经常遇到的问题,尤其是在搜索/排序问题中),只需将昂贵的部分(python"For"循环)切换到Cython(并静态定义变量类型……这是SPEEEEDDDDDD的关键!),即使在优化实现之前,我也能获得几个数量级的速度提升。检查Cythonhttps://cython.readthedocs.io/en/latest/index.html.如果这还不够,那么parrelism是你的下一个好朋友,这需要重新思考你的代码实现。
导致系统性能缓慢的主要问题是:
- 您可以在嵌套循环中手动迭代2列,而无需使用panda操作,后者使用快速ndarray函数
- 您使用递归调用,它看起来很好,很简单,但速度很慢
如下设置样本数据:
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.9ms),这大约是原始代码执行时间的一半,即使在删除了大多数print()函数调用后,也可以手动迭代带有嵌套循环和递归调用的numpy数组(需要16.9ms)。
删除了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)
熊猫编码方式中的新简化码:
%%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)
使用递归函数的解决方案:
递归函数的主要问题在于,您没有使用大小减小的数据的递归调用的结果。
要正确地使用递归函数作为一种分而治之的方法,您应该采取3个主要步骤:
- 将整个数据集划分为更小的部分,并通过递归调用处理较小的部分,每个调用取一个较小的部分
- 在每次递归调用中处理端点情况(大多数情况下最简单的情况)
- 合并较小部分的所有递归调用的结果
递归调用的美妙之处在于,您可以通过用两个更简单的步骤代替处理来解决复杂的问题:第一步是处理端点情况,在大多数情况下,您只能处理一个数据项(这通常很容易)。第二步是采取另一个简单的步骤来巩固缩减规模呼叫的结果。
你成功地迈出了第一步,但没有迈出其他两步。特别是,您没有利用较小工件的结果来简化处理。相反,您可以通过在二维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行现在假设目前没有股票中断。