python 条件组合

Question

我有 3 个列表

list1= [min_0,min_1...min_150] consists of minimum indexes which has usually has 50-150 elements,  
list2= [max_0,max_1...max_150] consists of maximum indexes which has usually has 50-150 elements,  
list3= [min_0,max_0,max_1,min_1 ...max_149,min_150]

list3 是 list1 和 list2 的联合，并且是有序的。 list3一般有200-300个元素。

我想使用 python.

的 itertools 从 list3 创建适合 2 个条件的 5 个元素 [x0,x1,x2,x3,x4] 组合

条件 1：x0、x2 和 x4 必须在 list1 和 x1, x3 必须在 list2 或 x0、x2、x4 必须在 list2 和 x1、x3必须在 list1

条件 2 : x4-x0 <=89

问题出在性能上。 (300,5) 的可能组合是 19,582,837,560 。我已经尝试将 list3 拆分为 n 个部分并获得了一些不错的性能，但在这种情况下，我错过了一些适合我条件的可能性。

我希望问题很清楚。我怎样才能获得最佳性能？谢谢。

Answer 1

为条件 1 使用一个函数。然后将它应用到条件 2。这样条件 1 就有了精确的用法。

Answer 2

为了避免数十亿次迭代，您需要简化组合域。使用集合会更容易。

所以假设您的 3 个列表实际上是集合：

set1 = set(list1)
set2 = set(list2)
set3 = set(list3)

您有两种模式要查找：

让我们开始第 1 部分：

elements of list3 where x0,x2,x4 are in list1 and x1,x3 are in list2

x0,x2,x4 将是 set3 & set1

中 3 个的组合

x1,x3 将是 set3 & set2

中 2 个的组合

5 个值元组将是这些组合的乘积：

part1 = { (x0,x1,x2,x3,x4) for x0,x2,x4 in combinations(set3&set1,3) 
                                        if x4-x0 <= 89
                           for x1,x3    in combinations(set3&set2,2) }

第二部分使用相同的方法，但使用其他列表中的 odd/even 个元素：

part2 = { (x0,x1,x2,x3,x4) for x0,x2,x4 in combinations(set3&set2,3) 
                                        if x4-x0 <= 89
                           for x1,x3    in combinations(set3&set1,2) }

结果是两部分的并集：

result = part1 | part2

根据数据，这可能仍然有数百万种组合，但这种方法将大大减少需要按条件过滤掉的无效组合的数量。

如果仍然不够快，您应该考虑编写自己的组合函数来优化在组合逻辑中应用 set3 过滤器和 x4-x0<89 条件。（即给出 (x0,x4,x2) 的 3 级嵌套循环跳过不符合条件的 x4 值，最好来自排序列表以允许短路）

请注意，如果您的任何列表包含重复值，您肯定需要编写自己的过滤和组合函数，以便在乘以 3 元组和 2 元组组合之前获得预先过滤的子集

[编辑]这里是一个如何编写自定义组合函数的例子。我把它变成了一个生成器，以避免创建一个包含一亿个元素的结果集。它只生成有效组合并尽早应用条件 2 以避免通过无效组合进行无用的迭代：

m = 150
n = 200
list1 = list(range(m))
list2 = list(range(m,2*m))
list3 = list(range(2,2*n,2))

def combine(L1,L2,L3):
    S3 =set(L3)
    inL1 = [x for x in L1 if x in S3]
    inL2 = [x for x in L2 if x in S3]
    for evens,odds in [(inL1,inL2),(inL2,inL1)]: # only generate valid combinations
        for p0,x0 in enumerate(evens[:-2]): 
            for p4,x4 in enumerate(evens[p0+2:],p0+2):
                if abs(x4-x0)>89: continue # short circuit condition 2 early
                for x2 in evens[p0+1:p4]:
                    for p1,x1 in enumerate(odds[:-1]):
                        for x3 in odds[p1+1:]:
                            yield (x0,x1,x2,x3,x4)
                                
print(sum(1 for _ in combine(list1,list2,list3))) # 230488170

230,488,170 个组合是在我的笔记本电脑上用 22 秒生成的。

以下是我示例中的前几个组合：

for combo in combine(list1,list2,list3): print(combo)
            
(2, 150, 4, 152, 6)
(2, 150, 4, 154, 6)
(2, 150, 4, 156, 6)
(2, 150, 4, 158, 6)
(2, 150, 4, 160, 6)
(2, 150, 4, 162, 6)
(2, 150, 4, 164, 6)
(2, 150, 4, 166, 6)
(2, 150, 4, 168, 6)
(2, 150, 4, 170, 6)
(2, 150, 4, 172, 6)
(2, 150, 4, 174, 6) ...
KeyboardInterrupt

如果您获得数亿个有效组合，您可能需要重新考虑处理数据的方式，因为您将运行陷入每个角落的性能和内存问题。

python 条件组合

python conditional combination

python

combinations