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

Question

可能重复:
在Python Flatten(不规则的)列表列表中展平浅表列表

编辑:问题不是如何做到 - 这已经在其他问题中讨论过 - 问题是,这是最快的方法？

我之前找到了解决方案,但我想知道最快的解决方案是什么来压缩包含其他任意长度列表的列表.

例如:

[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递归限制的限制,因为它不是递归的.不过,我确信这几乎不会发挥作用.

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