python - Pandas DataFrame 的嵌套（双）行迭代
问题描述
您好我正在尝试找到迭代问题的矢量化（或更有效）解决方案，其中我找到的唯一解决方案需要对具有多个循环的 DataFrame 进行逐行迭代。实际的数据文件很大，所以我目前的解决方案实际上是不可行的。如果您想看一下，我在最后包含了线分析器输出。真正的问题非常复杂，所以我将尝试用一个简单的例子来解释这个问题（我花了很长时间来简化它:)）：
假设我们有一个机场，有两个并排的着陆跑道。每架飞机降落（到达时间），在其中一个跑道上滑行一段时间，然后起飞（起飞时间）。一切都存储在 Pandas DataFrame 中，按到达时间排序，如下所示（参见EDIT2以获得更大的数据集进行测试）：
PLANE STRIP ARRIVAL DEPARTURE
0 1 85.00 86.00
1 1 87.87 92.76
2 2 88.34 89.72
3 1 88.92 90.88
4 2 90.03 92.77
5 2 90.27 91.95
6 2 92.42 93.58
7 2 94.42 95.58
寻找两种情况的解决方案：
1.建立一个事件列表，其中一次在一个带上存在多个平面。不包括事件的子集（例如，如果存在有效的 [3,4,5] 案例，则不显示 [3,4]）。该列表应存储实际 DataFrame 行的索引。请参阅函数 findSingleEvents() 了解这种情况的解决方案（运行大约 5 毫秒）。
2.建立一个事件列表，其中每个条带上一次至少有一个平面。不计算事件的子集，仅记录具有最大平面数的事件。（例如，如果有 [3,4,5] 情况，则不显示 [3,4]）。不要计算在单个条带上完全发生的事件。该列表应存储实际 DataFrame 行的索引。请参阅函数 findMultiEvents() 了解这种情况的解决方案（运行大约 15 毫秒）。
工作代码：
import numpy as np
import pandas as pd
import itertools
from __future__ import division
data = [{'PLANE':0, 'STRIP':1, 'ARRIVAL':85.00, 'DEPARTURE':86.00},
{'PLANE':1, 'STRIP':1, 'ARRIVAL':87.87, 'DEPARTURE':92.76},
{'PLANE':2, 'STRIP':2, 'ARRIVAL':88.34, 'DEPARTURE':89.72},
{'PLANE':3, 'STRIP':1, 'ARRIVAL':88.92, 'DEPARTURE':90.88},
{'PLANE':4, 'STRIP':2, 'ARRIVAL':90.03, 'DEPARTURE':92.77},
{'PLANE':5, 'STRIP':2, 'ARRIVAL':90.27, 'DEPARTURE':91.95},
{'PLANE':6, 'STRIP':2, 'ARRIVAL':92.42, 'DEPARTURE':93.58},
{'PLANE':7, 'STRIP':2, 'ARRIVAL':94.42, 'DEPARTURE':95.58}]
df = pd.DataFrame(data, columns = ['PLANE','STRIP','ARRIVAL','DEPARTURE'])
def findSingleEvents(df):
events = []
for row in df.itertuples():
#Create temporary dataframe for each main iteration
dfTemp = df[(row.DEPARTURE>df.ARRIVAL) & (row.ARRIVAL<df.DEPARTURE)]
if len(dfTemp)>1:
#convert index values to integers from long
current_event = [int(v) for v in dfTemp.index.tolist()]
#loop backwards to remove elements that do not comply
for i in reversed(current_event):
if (dfTemp.loc[i].ARRIVAL > dfTemp.DEPARTURE).any():
current_event.remove(i)
events.append(current_event)
#remove duplicate events
events = map(list, set(map(tuple, events)))
return events
def findMultiEvents(df):
events = []
for row in df.itertuples():
#Create temporary dataframe for each main iteration
dfTemp = df[(row.DEPARTURE>df.ARRIVAL) & (row.ARRIVAL<df.DEPARTURE)]
if len(dfTemp)>1:
#convert index values to integers from long
current_event = [int(v) for v in dfTemp.index.tolist()]
#loop backwards to remove elements that do not comply
for i in reversed(current_event):
if (dfTemp.loc[i].ARRIVAL > dfTemp.DEPARTURE).any():
current_event.remove(i)
#remove elements only on 1 strip
if len(df.iloc[current_event].STRIP.unique()) > 1:
events.append(current_event)
#remove duplicate events
events = map(list, set(map(tuple, events)))
return events
print findSingleEvents(df[df.STRIP==1])
print findSingleEvents(df[df.STRIP==2])
print findMultiEvents(df)
验证输出：
[[1, 3]]
[[4, 5], [4, 6]]
[[1, 3, 4, 5], [1, 4, 6], [1, 2, 3]]
显然，这些既不是高效也不是优雅的解决方案。使用我拥有的巨大 DataFrame，运行它可能需要几个小时。我考虑了很长时间的矢量化方法，但无法提出任何可靠的方法。欢迎任何指示/帮助！我也对基于 Numpy/Cython/Numba 的方法持开放态度。
谢谢！
PS：如果您想知道我将如何处理列表：我将为EVENT每个 分配一个数字EVENT，并通过合并上面的数据构建一个单独的数据库，并将EVENT数字作为单独的列，用于其他用途。对于案例 1，它看起来像这样：
EVENT PLANE STRIP ARRIVAL DEPARTURE
0 4 2 90.03 92.77
0 5 2 90.27 91.95
1 5 2 90.27 91.95
1 6 2 92.42 95.58
编辑：修改了代码和测试数据集。
EDIT2：使用下面的代码生成一个 1000 行（或更多）长的 DataFrame 用于测试目的。（根据@ImportanceOfBeingErnest 的建议）
import random
import pandas as pd
import numpy as np
data = []
for i in range(1000):
arrival = random.uniform(0,1000)
departure = arrival + random.uniform(2.0, 10.0)
data.append({'PLANE':i, 'STRIP':random.randint(1, 2),'ARRIVAL':arrival,'DEPARTURE':departure})
df = pd.DataFrame(data, columns = ['PLANE','STRIP','ARRIVAL','DEPARTURE'])
df = df.sort_values(by=['ARRIVAL'])
df = df.reset_index(drop=True)
df.PLANE = df.index
编辑3：
已接受答案的修改版本。接受的答案无法删除事件的子集。修改后的版本满足规则“（例如，如果存在有效的 [3,4,5] 情况，则不显示 [3,4]）”
def maximal_subsets_modified(sets):
sets.sort()
maximal_sets = []
s0 = frozenset()
for s in sets:
if not (s > s0) and len(s0) > 1:
not_in_list = True
for x in maximal_sets:
if set(x).issubset(set(s0)):
maximal_sets.remove(x)
if set(s0).issubset(set(x)):
not_in_list = False
if not_in_list:
maximal_sets.append(list(s0))
s0 = s
if len(s0) > 1:
not_in_list = True
for x in maximal_sets:
if set(x).issubset(set(s0)):
maximal_sets.remove(x)
if set(s0).issubset(set(x)):
not_in_list = False
if not_in_list:
maximal_sets.append(list(s0))
return maximal_sets
def maximal_subsets_2_modified(sets, d):
sets.sort()
maximal_sets = []
s0 = frozenset()
for s in sets:
if not (s > s0) and len(s0) > 1 and d.loc[list(s0), 'STRIP'].nunique() == 2:
not_in_list = True
for x in maximal_sets:
if set(x).issubset(set(s0)):
maximal_sets.remove(x)
if set(s0).issubset(set(x)):
not_in_list = False
if not_in_list:
maximal_sets.append(list(s0))
s0 = s
if len(s0) > 1 and d.loc[list(s), 'STRIP'].nunique() == 2:
not_in_list = True
for x in maximal_sets:
if set(x).issubset(set(s0)):
maximal_sets.remove(x)
if set(s0).issubset(set(x)):
not_in_list = False
if not_in_list:
maximal_sets.append(list(s0))
return maximal_sets
# single
def hal_3_modified(d):
sets = np.apply_along_axis(
lambda x: frozenset(d.PLANE.values[(d.PLANE.values <= x[0]) & (d.DEPARTURE.values > x[2])]),
1, d.values
)
return maximal_subsets_modified(sets)
# multi
def hal_5_modified(d):
sets = np.apply_along_axis(
lambda x: frozenset(d.PLANE.values[(d.PLANE.values <= x[0]) & (d.DEPARTURE.values > x[2])]),
1, d.values
)
return maximal_subsets_2_modified(sets, d)
解决方案
我使用而不是迭代重写了解决方案DataFrame.apply，并且尽可能使用 numpy 数组进行优化。我使用frozenset它们是因为它们是不可变的和可散列的，因此Series.unique可以正常工作。Series.unique在 type 的元素上失败set。
另外，我发现d.loc[list(x), 'STRIP'].nunique()它比d.loc[list(x)].STRIP.nunique(). 我不知道为什么，但我在下面的解决方案中使用了更快的语句。
简单的英语算法：
对于每一行，创建一组低于（或等于）其 Departure 大于当前 Arrival 的当前索引的索引。这会产生一个集合列表。
返回不是其他集合子集的唯一集合（对于第二种算法，另外过滤两个STRIPs 都被集合引用）
（更新）第二次改进：
通过下拉到 numpy 层并使用np.apply_along_axis而不是使用 df.apply 进行了 1 个小改进。这是可能的，因为PLANE总是等于数据帧索引，我们可以访问底层矩阵df.values
我发现返回最大子集的列表理解有了重大改进
[list(x) for x in sets if ~np.any(sets > x)]
上面是一个 O(n^2) 顺序操作。在小型数据集上，这非常快。然而，在更大的数据集上，此语句成为瓶颈。为了优化这一点，首先对 进行排序sets，然后再次循环遍历元素以找到最大子集。排序后，检查 elem[n] 不是 elem[n+1] 的子集就足以确定 elem[n] 是否是最大子集。排序过程将两个元素与<操作进行比较
时间：
虽然与 OP 的尝试相比，我的原始实现显着提高了性能，但该算法是指数排序的，如下图所示。
我只介绍findMultiEvents, hal_2&的时间hal_5。findSinglEvents, hal_1&的相对性能hal_3同样具有可比性。
滚动下方查看基准测试代码。
请注意，当很明显它们的效率降低了指数因子时，我停止了findMumtiEvents基准hal_2测试
执行
改进的实施：
def maximal_subsets(sets):
sets.sort()
maximal_sets = []
s0 = frozenset()
for s in sets[::-1]:
if s0 > s or len(s) < 2:
continue
maximal_sets.append(list(s))
s0 = s
return maximal_sets
def maximal_subsets_2(sets, d):
sets.sort()
maximal_sets = []
s0 = frozenset()
for s in sets[::-1]:
if s0 > s or len(s) < 2 or d.loc[list(s), 'STRIP'].nunique() < 2:
continue
maximal_sets.append(list(s))
s0 = s
return maximal_sets
# single
def hal_3(d):
sets = np.apply_along_axis(
lambda x: frozenset(d.PLANE.values[(d.PLANE.values <= x[0]) & (d.DEPARTURE.values > x[2])]),
1, d.values
)
return maximal_subsets(sets)
# multi
def hal_5(d):
sets = np.apply_along_axis(
lambda x: frozenset(d.PLANE.values[(d.PLANE.values <= x[0]) & (d.DEPARTURE.values > x[2])]),
1, d.values
)
return maximal_subsets_2(sets, d)
原始实现：
# findSingleEvents
def hal_1(d):
sets = d.apply(
lambda x: frozenset(
d.index.values[(d.index.values <= x.name) & (d.DEPARTURE.values > x.ARRIVAL)]
),
axis=1
).unique()
return [list(x) for x in sets if ~np.any(sets > x) and len(x) > 1]
# findMultiEvents
def hal_2(d):
sets = d.apply(
lambda x: frozenset(
d.index.values[(d.index.values <= x.name) & (d.DEPARTURE.values > x.ARRIVAL)]
),
axis=1
).unique()
return [list(x) for x in sets
if ~np.any(sets > x) and
len(x) > 1 and
d.loc[list(x), 'STRIP'].nunique() == 2]
输出：
输出与 OP 的实现相同。
hal_1(df[df.STRIP==1])
[[1, 3]]
hal_1(df[df.STRIP==2])
[[4, 5], [4, 6]]
hal_2(df)
[[1, 2, 3], [1, 3, 4, 5], [1, 4, 6]]
hal_3(df[df.STRIP==1])
[[1, 3]]
hal_3(df[df.STRIP==2])
[[4, 5], [4, 6]]
hal_5(df)
[[1, 2, 3], [1, 3, 4, 5], [1, 4, 6]]
测试系统详情：
os: windows 10
python: 3.6 (Anaconda)
pandas: 0.22.0
numpy: 1.14.3
基准代码：
import random
def mk_random_df(n):
data = []
for i in range(n):
arrival = random.uniform(0,1000)
departure = arrival + random.uniform(2.0, 10.0)
data.append({'PLANE':i, 'STRIP':random.randint(1, 2),'ARRIVAL':arrival,'DEPARTURE':departure})
df = pd.DataFrame(data, columns = ['PLANE','STRIP','ARRIVAL','DEPARTURE'])
df = df.sort_values(by=['ARRIVAL'])
df = df.reset_index(drop=True)
df.PLANE = df.index
return df
dfs = {i: mk_random_df(100*(2**i)) for i in range(0, 10)}
times, times_2, times_5 = [], [], []
for i, v in dfs.items():
if i < 5:
t = %timeit -o -n 3 -r 3 findMultiEvents(v)
times.append({'size(pow. of 2)': i, 'timings': t})
for i, v in dfs.items():
t = %timeit -o -n 3 -r 3 hal_5(v)
times_5.append({'size(pow. of 2)': i, 'timings': t})
for i, v in dfs.items():
if i < 9:
t = %timeit -o -n 3 -r 3 hal_2(v)
times_2.append({'size(pow. of 2)': i, 'timings': t})
推荐阅读
- python - “make”命令权限被拒绝
- python - 不断增长的堆栈 Tkinter（切换帧时）
- r - 使用 R 中的嵌套 for 循环更快地替代成对比较
- scala - 如何创建一个不调用底层对象构造函数的 ScalaMock 存根？
- typescript - 用数字键入参数 | 枚举，用于文档目的
- python - 使用 for 循环简化几行代码？
- oracle - 查看结果的总和/除值
- java - Android连接Mysql数据库
- ios - 如何将 AVAudioRecorder 给出的数据重新解释为 const char *？
- spring-cloud-config - 如何从 spring-cloud-config-server 返回自定义键值对？