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

Question

可能的重复：在 Python 中展平
浅表列表 在 Python 中
展平（不规则）列表列表

编辑：问题不在于如何去做——这已在其他问题中讨论过——问题是，哪种方法最快？

我以前找到过解决方案，但我想知道最快的解决方案是展平包含其他任意长度列表的列表。

例如：

[1, 2, [3, 4, [5],[]], [6]]

会成为：

[1,2,3,4,5,6]

可以有无限多个级别。一些列表对象可以是字符串，它们不能在输出列表中被展平为它们的连续字符。

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']

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

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 递归限制的限制，因为它不是递归的。但是，我敢肯定，这实际上永远不会发挥作用。

try2021 年编辑：在我看来，使用/处理对列表末尾的检查可能会更好，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返回的 byenumerate而不是访问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

Answer 3

这个函数应该能够在不使用任何递归的情况下快速扁平化嵌套的、可迭代的容器：

import collections

def flatten(iterable):
    iterator = iter(iterable)
    array, stack = collections.deque(), collections.deque()
    while True:
        try:
            value = next(iterator)
        except StopIteration:
            if not stack:
                return tuple(array)
            iterator = stack.pop()
        else:
            if not isinstance(value, str) \
               and isinstance(value, collections.Iterable):
                stack.append(iterator)
                iterator = iter(value)
            else:
                array.append(value)

大约五年后，我对此事的看法发生了变化，这可能更好用：

def main():
    data = [1, 2, [3, 4, [5], []], [6]]
    print(list(flatten(data)))


def flatten(iterable):
    iterator, sentinel, stack = iter(iterable), object(), []
    while True:
        value = next(iterator, sentinel)
        if value is sentinel:
            if not stack:
                break
            iterator = stack.pop()
        elif isinstance(value, str):
            yield value
        else:
            try:
                new_iterator = iter(value)
            except TypeError:
                yield value
            else:
                stack.append(iterator)
                iterator = new_iterator


if __name__ == '__main__':
    main()