在没有 6 个 for 循环的情况下端到端连接 6 个部分的最有效方法

Question

我有 6 个列表（部分），sec1 到 sec6。我想加入他们，以形成一个列表。

示例：

sec1 = [[1,2,3],[4,5,6]]
sec2 = [[7,8,9], [6], [1,2]]

如果我加入这两个部分，我应该得到：

sec_join = [[1,2,3,7,8,9], [1,2,3,6], [1,2,3,1,2], [4,5,6,7,8,9], [4,5,6,6], [4,5,6,1,2]]

现在我有 6 个这样的部分，我想相应地加入它们。

注：len(sec_join) = len(sec1)*len(sec2)....*len(sec6)

我可以使用 6 个 for 循环来做到这一点

[[[[[[sec_join.append(x1 + x2 + x3 + x4 + x5 + x6) for x1 in sec1] for x2 in sec2] for x3 in sec3] for x4 in sec4] for x5 in sec5] for x6 in sec6]

但是上面的方法是O($n^6$)。是否有可能以更好的时间复杂度来做到这一点？

注意：在我的例子中，sec1...sec6 的元素是整数元组而不是整数，因此排序可能会很混乱。

编辑：

我知道它不能比 O($n^6$) 更复杂。尽管如此，除了 6 个 for 循环和列表综合之外，还有什么“pythonic”方法可以更快地完成它吗？使用任何库函数等？

Answer 1

使用标准库中的itertools：

from itertools import chain, product

sec1 = [[1,2,3],[4,5,6]]
sec2 = [[7,8,9], [6], [1,2]]

sec_join = [list(chain(*x)) for x in product(sec1, sec2)]

全部 6 次执行：

sec_join = [list(chain(*x)) for x in product(sec1, sec2, sec3, sec4, sec5, sec6)]

Answer 2

我认为列表连接比通过 chain 更快。

sec_join = sec1
for sec in sec2, sec3, sec4, sec5, sec6:
    sec_join = [head + tail
                for head in sec_join
                for tail in sec]

可以通过以不同方式组合来进一步加快速度，但我必须知道实际的列表大小。

这可能是最快的，如果您的列表大小大致相同，则可以最大限度地减少迭代次数：

sec_join = sec6
for sec in sec5, sec4, sec3, sec2, sec1:
    sec_join = [head + tail
                for head in sec
                for tail in sec_join]

一点基准：

134 ms myrtlecat
 46 ms Kelly

代码(Try it online!):

from itertools import chain, product

sec1 = [[1,2,3],[4,5,6]]*3
sec2 = [[7,8,9], [6], [1,2]]*3

def Kelly(sec1,sec2,sec3,sec4,sec5,sec6):
  sec_join = sec6
  for sec in sec5, sec4, sec3, sec2, sec1:
    sec_join = [head + tail
                for head in sec
                for tail in sec_join]
  return sec_join

def myrtlecat(sec1,sec2,sec3,sec4,sec5,sec6):
  return [list(chain(*x)) for x in product(sec1, sec2, sec3, sec4, sec5, sec6)]

from timeit import *

args = sec1,sec2,sec1,sec2,sec1,sec2
expect = myrtlecat(*args)
result = Kelly(*args)
print(result == expect)
for a in expect, result: print(len(a))
for func in [myrtlecat, Kelly]*3:
  t = min(repeat(lambda: func(*args), number=1))
  print('%3d ms' % (t * 1e3), func.__name__)

在没有 6 个 for 循环的情况下端到端连接 6 个部分的最有效方法

Most efficient way to join 6 sections end to end without 6 for loops

python

list

algorithm

time-complexity

list-comprehension