Python按指定位规则筛选6元组合运行耗时久，如何优化提速？

原来的实现思路存在两个根本性的效率浪费，是耗时居高不下的主要原因：

• 无差别生成全量6元组合的逻辑完全反向：组合总量是C(n,6)的量级，只要列表x的元素数到200，全量组合数就接近1亿。原实现的结构大概是先把所有组合存在大列表里，再逐一遍历判断位规则，光生成、存储、遍历这些组合的开销，就占了90%以上的耗时。绝大多数组合从生成出来开始，就根本不可能符合位规则，纯属于无用计算。
• 逐组合嵌套判断的方式没有任何提前剪枝的逻辑：哪怕组合的第一个元素就不在允许的first列表里，也要等整体生成完再做判断；加上归属判断用的是列表查找，时间复杂度和列表长度正相关，冗余度极高。实际测试中x规模稍大时，这类写法跑到80多秒是非常典型的表现。

优化的核心是彻底放弃"先生成全量组合再筛选"的思路，从遍历的第一步就按位规则做剪枝，只生成符合约束的组合，完全跳过无效计算。
具体可分两步落地：

1. 提前把每一位的允许列表转换成哈希集合（set），把原来O(k)的列表归属判断降到O(1)，消除查找开销

   # 预转set，大幅加快in操作的速度
   s1, s2, s3, s4, s5, s6 = set(first), set(second), set(third), set(fourth), set(fifth), set(sixth)
   

2. 按组合的顺序规则（即itertools.combinations生成的元素顺序严格和原列表x的先后顺序对应），逐层嵌套索引遍历，每一层只要碰到不符合当前位规则的元素，立刻跳过进入下一轮，完全不进入后续的判断流程，根本不会生成不符合规则的组合。
   参考实现代码：

   y = []
   x_len = len(x)
   for i0, v0 in enumerate(x):
       # 第一层剪枝：第一位不符合规则直接跳过
       if v0 not in s1:
           continue
       # 从当前第一位的索引之后开始找第二位
       for i1 in range(i0 + 1, x_len):
           v1 = x[i1]
           if v1 not in s2:
               continue
           # 第二层剪枝：从第二位索引之后找第三位
           for i2 in range(i1 + 1, x_len):
               v2 = x[i2]
               if v2 not in s3:
                   continue
               # 第三层剪枝：从第三位索引之后找第四位
               for i3 in range(i2 + 1, x_len):
                   v3 = x[i3]
                   if v3 not in s4:
                       continue
                   # 第四层剪枝：从第四位索引之后找第五位
                   for i4 in range(i3 + 1, x_len):
                       v4 = x[i4]
                       if v4 not in s5:
                           continue
                       # 第五层剪枝：从第五位索引之后找第六位
                       for i5 in range(i4 + 1, x_len):
                           v5 = x[i5]
                           if v5 in s6:
                               y.append((v0, v1, v2, v3, v4, v5))
   

• 可以提前把每一位允许的元素在x中的位置单独整理成有序索引列表，把原来靠range逐位遍历的过程，替换成直接遍历预存的候选索引，能大幅减少无效的遍历次数
• 由于6层循环的代码量可控，这种直接写多层循环的方式比封装函数、用生成器的方式速度更快，没有额外的函数调用和生成器迭代的开销
• 因为全程不会生成全量组合的中间结果，内存占用也会比原来的实现低几个数量级，哪怕x的规模再大，也不会出现内存溢出的问题

内容的提问来源于stack exchange，提问作者91divoc