嵌套(双)逐行迭代Pandas DataFrame
mar*_*ion 11 python loops vectorization dataframe pandas
您好我正在尝试找到迭代问题的矢量化(或更有效)解决方案,其中我发现的唯一解决方案需要逐行迭代具有多个循环的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 ms).
2.建立一个事件列表,每次在每个条带上至少有一个平面.不计算事件的子集,仅记录具有最大平面数的事件.(例如,如果有[3,4,5]个案,则不显示[3,4]).不要计算单个条带上完全发生的事件.该列表应存储实际DataFrame行的索引.有关此案例的解决方案,请参阅函数findMultiEvents()(运行大约15 ms).
工作守则:
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的approches持开放态度.
谢谢!
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
EDIT3:
修改后的答案版本.接受的答案无法删除事件子集.修改后的版本满足规则"(例如,如果有[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对类型为 的元素失败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})