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

Question

如何快速展开包含任意长度列表的列表？

例如，[1, 2, [3, 4, [5],[]], [6]] 应变为 [1,2,3,4,5,6]。

列表可以有任意多级。列表中的某些对象可能是字符串，在输出列表中不应被展开为单个字符。

- Ivy

---

这个答案来自于一个之前提出的问题，应该能够满足你的需求。（投票关闭为重复问题）。 - GreenMatt

@GreenMatt，只有当“问题”相同而不是答案时，它才是重复的。很明显，另一个问题只是针对单层嵌套，更简单的解决方案更加适合。 - Mark Ransom

请不要删除系统生成的“可能重复”的横幅。第二个链接中有您问题的答案。 - vaultah

不同意，答案可能是相同的，但问题需要适用于任意嵌套列表，因此不是重复的问题。 - Ivy

我很惊讶这个功能没有被包含在标准库中，比如itertools或其他什么地方。 - a06e

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

---

这只是yield的一个美妙应用。干得好！ - fabee

在Python 3.3及以上版本中，你可以使用yield from flatten(i)代替for j in flatten(i): yield j。 - jfs

无论如何，这是一个很好的解决方案。你也可以使用if isinstance(i, (list, tuple)):来实现。 - acushner

如果它是一个集合怎么办？我使用了 if hasattr(i, '__iter__'):。 - TayTay

字符串类型会在 hasattr(i, '__iter__') 中导致无限递归。我使用了过滤器 if hasattr(i, '__iter__') and not isinstance(i, str): 来排除这些情况。 - random8

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

如果进一步调整代码，使用enumerate返回的x而不是频繁访问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

---

@Mark 这是一次性编写的代码 :). 请注意警告未来的编辑者并继续你的生活。 - Kenan Banks

@Triptych，我不太明白你的评论。 - Mark Ransom

enumerate()非常简单易用，文档中也明确说明它是一种惰性操作（即返回一个迭代器，该迭代器会产生连续的索引值）。同时，iter()在列表上的行为（使用递增的索引和__getitem__()进行比较，并在每次迭代时与len()进行比较，即使长度发生变化也能正常工作）也有文档记录。因此，尽管它看起来有点像黑科技，但实际上除非语言本身发生了重大变化，否则它是相当安全的。 - kindall

使用range而不是enumerate也可以解决问题。 - Narayan Singh

我很惊讶这个没有更多的投票。我认为这是因为你必须仔细阅读才能理解它在做什么。 - Mad Physicist

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()

- Noctis Skytower