快速压缩列表，同时通过循环完成较短的列表

Question

请注意，这不是this post的副本，因为我想压缩2个以上的列表（或者至少在没有显式循环的情况下，我不能轻易地将该文章推广到这里使用）

我想找到以特定方式合并列表列表的最佳性能（在速度方面）实现。输入是一个列表（或元组）的列表，按顺序排列，以便下一个列表的长度始终是上一个列表的倍数。例如：

a = ['A', 'B', 'C', 'D']
b = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
input_list = [a, b]

输出是以下内容的合并列表：

output = ['A', 'A', 'B', 'B', 'C', 'C', 'D', 'D', 'A', 'E', 'B', 'F', 'C', 'G', 'D', 'H']

也就是说，较短的列表（在本例中是a）都通过循环自身来扩展到最长的列表（在本例中是b），这样列表的长度就相等了。然后以垂直堆叠方式合并所有列表。你知道吗

目前，我有一个实现，基本上实现了以下功能：

step 1            step 2           step 3 
======            ========         ======
ABCD              ABCDABCD
ABCDEFGH -------> ABCDEFGH ------> AABBCCDDAEBFCGDH

它工作但效率不高：

def flatten_list(value):
    return sum(value, [])

def group(value):
    for idx in reversed(range(1, len(value))):
        multiplier = int(len(value[idx]) / len(value[idx - 1]))
        if multiplier > 1:
            value[idx - 1] = flatten_list([value[idx - 1] for i in range(multiplier)])
    return flatten_list(list(zip(*value)))

有没有更快的实施？性能对于我的应用程序来说是非常重要的，因为输入是巨大的。如有任何建议，我们将不胜感激！你知道吗

Answer 1

使用来自^{}的cycle、chain、islice：

list(chain(*islice(
    zip(*(cycle(l) for l in input_list)), 
    0, len(max(input_list, key=len)))))
# ['A', 'A', 'B', 'B', 'C', 'C', 'D', 'D', 'A', 'E', 'B', 'F', 'C', 'G', 'D', 'H']

或者，在其部分：

# generator producing cycles of each list
(cycle(l) for l in input_list)  
# zip these cycles together: ('A', 'A') -> ('B', 'B') -> infinitely
zip(*...)  
# take a slice of this iterable of tuples with the length of the longest list
islice(..., 0, len(max(input_list, key=len)))
# chain those tuples together into one list
list(chain(*...))   

或插图：

lists = [
                 #        chain--┐-----┐-----┐
                 #              ┌--┐  ┌--┐  ┌--┐     
                 #        | ┌-┐ | ┌-┐ | ┌-┐ | ┌-┐  | ┌-┐     
   [1],          # cycle: | |1|,| |1|,| |1|,| |1|, | |1|, ...
   [1, 2],       # cycle: | |1|,| |2|,| |1|,| |2|, | |1|, ...
   [1, 2, 3, 4], # cycle: | |1|,| |2|,| |3|,| |4|, | |1|, ...
]                #        | └-┘ | └-┘ | └-┘ | └-┘  | └-┘  
                 #        |  └--┘  └--┘  └--┘      |
                 #        | zip   zip   zip   zip  | zip  ...
                 #        |                        |    
                 #   islice start           islice stop
                 #   -->  [1,1,1,1,2,2,1,1,3,1,2,4]

它的时间复杂度是O(n)，其中n是输出列表的长度。在Python2中，您必须使用itertools.izip而不是zip，因为后者将试图构建一个无限列表。你知道吗

Answer 2

将^{}应用于比最长列表短的所有列表，并将它们压缩到一起，使结果变平。你知道吗

def special_zip(*lsts):
    max_len = max(map(len, lsts))
    cyclic = [lst if len(lst) == max_len else itertools.cycle(lst) for lst in lsts]
    return (el for grp in zip(*cyclic) for el in grp)

这应该是O（2n），其中n是列表长度的总和。如果您知道最长的列表，并且可以单独传递它，则这将成为O（n）。类似地，如果您知道需要多少输出（因为您可以将itertools.cycle应用于每个列表并从无限输出中提取）

Answer 3

使用^{} itertools recipe：

两个输入

import itertools as it


a = list("ABCD")
b = list("ABCDEFGH")

list(it.chain.from_iterable(roundrobin(zip(it.cycle(a), b))))
# ['A', 'A', 'B', 'B', 'C', 'C', 'D', 'D', 'A', 'E', 'B', 'F', 'C', 'G', 'D', 'H']

itertools.cycle()无限扩展较短的iterable。zip()在较短的iterable之后停止迭代。roundrobin处理iterable之间的元素交错。你知道吗

---

较长的输入

要处理两个以上的输入，我们需要循环除最后一个iterable外的所有输入：

def interleave(*inputs):
    *rest, last = inputs
    cycles = (it.cycle(x) for x in rest)
    return list(it.chain.from_iterable(mit.roundrobin(zip(*cycles, last))))

现在，对于两个或多个输入iterables，我们可以应用interleave函数：

p = list("ab")
q = list("abcd")
r = list("abcdef")

input_list_1 = [a, b]
input_list_2 = [p, q, r]


print(interleave(*input_list_1))
# ['A', 'A', 'B', 'B', 'C', 'C', 'D', 'D', 'A', 'E', 'B', 'F', 'C', 'G', 'D', 'H']
print(interleave(*input_list_2))
# ['a', 'a', 'a', 'b', 'b', 'b', 'a', 'c', 'c', 'b', 'd', 'd', 'a', 'a', 'e', 'b', 'b', 'f']

注意：您可以从the docs重新实现roundrobin配方，也可以安装第三方库来实现它，例如^{}。> pip install more_itertools，然后在Python中，from more_itertools import roundrobin。你知道吗