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

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

使用来自 itertools 的 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，因为后者会尝试构建无限列表。