在 Python 中展平任意嵌套列表的最快方法是什么？

Question

压平包含任意长度其他列表的列表的最快解决方案是什么？

例如 [1, 2, [3, 4, [5],[]], [6]] 会变成 [1,2,3,4,5,6] 。

可以有任意多个级别。一些列表对象可以是字符串，在输出列表中不能将其展平为它们的顺序字符。

原文由 Ivy 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这是一种对字符串友好的递归方法：

 nests = [1, 2, [3, 4, [5],['hi']], [6, [[[7, 'hello']]]]]

def flatten(container):
    for i in container:
        if isinstance(i, (list,tuple)):
            for j in flatten(i):
                yield j
        else:
            yield i

print list(flatten(nests))

回报：

 [1, 2, 3, 4, 5, 'hi', 6, 7, 'hello']

请注意，这并不能保证速度或开销使用，但说明了一个递归解决方案，希望会有帮助。

原文由 hexparrot 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

它 不必 是递归的。事实上，由于涉及函数调用的开销，迭代解决方案通常更快。这是我前一段时间写的迭代版本：

 def flatten(items, seqtypes=(list, tuple)):
    for i, x in enumerate(items):
        while i < len(items) and isinstance(items[i], seqtypes):
            items[i:i+1] = items[i]
    return items

还没有测试这个特定实现的性能，但它可能不是很好，因为所有的切片分配，最终可能会移动大量内存。尽管如此，不要假设它必须是递归的，或者以这种方式编写它更简单。

此实现确实具有“就地”展平列表而不是返回副本的优点，递归解决方案总是这样做。当内存紧张时，这可能很有用。如果你想要一个扁平化的副本，只需传入你想要扁平化的列表的浅表副本：

 flatten(mylist)                # flattens existing list
newlist = flatten(mylist[:])   # makes a flattened copy

此外，此算法不受 Python 递归限制的限制，因为它不是递归的。但是，我敢肯定这实际上永远不会发挥作用。

2021 年编辑：在我看来，使用 try / except 可能会更好地处理列表末尾的检查，因为它只会发生一次，并且从主循环可以提供性能优势。那看起来像：

 def flatten(items, seqtypes=(list, tuple)):
    try:
        for i, x in enumerate(items):
            while isinstance(items[i], seqtypes):
                items[i:i+1] = items[i]
    except IndexError:
        pass
    return items

通过进一步调整以使用 x 由 enumerate 返回，而不是访问 items[i] 比原来的速度快得多或显着版本最高，具体取决于列表的大小和结构。

 def flatten(items, seqtypes=(list, tuple)):
    try:
        for i, x in enumerate(items):
            while isinstance(x, seqtypes):
                items[i:i+1] = x
                x = items[i]
    except IndexError:
        pass
    return items

原文由 kindall 发布，翻译遵循 CC BY-SA 4.0 许可协议