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

Question

编辑：问题不是如何执行-这已经在其他问题中进行了讨论 -问题是，哪种方法最快？我之前已经找到了解决方案，但是我想知道最快的解决方案是将包含其他任意长度列表的列表展平。例如：[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

此函数应该能够快速平整嵌套的可迭代容器，而无需使用任何递归：

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