向量化或用Pandas计算元组的最长递增子序列的有效方法

Question

使用pandas/python，我想为每个DTE组计算元组的最长递增子序列，但要有效地计算13M行。现在，使用应用/迭代大约需要10个小时。

我的问题大致如下：

投标<11>

DTE	罢工	询价
1	100	10
1	200	16	17
1	300	17	18
1		400	11	12
1	500	12	13
1		600	13	14
2	100	10	30
2	200	15	20
2	300	16	21

找到最长递增子序列的算法的复杂性是多少？

本文提供了一种复杂度为O(n-logn(的算法。Upd：不起作用。您甚至不需要修改代码，因为在python中，比较适用于元组：assert (1, 2) < (3, 4)

>>> seq=[(10, 11), (16, 17), (17, 18), (11, 12), (12, 13), (13, 14)]
>>> subsequence(seq)
[(10, 11), (11, 12), (12, 13), (13, 14)]

由于每一行都必须引用前几行才能计算出此时最长的递增子序列，因此您似乎无法并行执行此操作？

可以，但您可以为每个DTE并行计算序列。您可以在.groupby()之后尝试类似pandarallel的并行聚合。

from pandarallel import pandarallel
pandarallel.initialize()
# just an example of usage:
df.groupby("DTE").parallel_apply(subsequence)

还要尝试去掉panda(速度相当慢(，并使用原始numpy数组和python结构。您可以使用O(n^2(算法计算LIS索引，然后使用df.iloc选择所需行