如何展平具有以下内容的列表：基元数据类型、列表和生成器？

Question

我正在尝试扁平化包含原始数据类型、列表和生成器的数十万个列表。列表和生成器都有原始数据类型，所以在展平之后我将只有原始数据类型（浮点数、整数、字符串和布尔值）

例子 ：

list_1 = [1, 2, 3, 'ID45785', False, '', 2.85, [1, 2, 'ID85639', True, 1.8], (e for e in range(589, 591))]

我的代码：

flatten = []
for item in list_1:
    if isinstance(item, (str, bool, int, float)) :
        flatten.append(item)
    else:
        flatten.extend(list(item))

由于性能很重要，我想知道是否有更好的方法来实现扁平化？

Answer 1

一种更快的方法是避免使用全局变量：

def to_flatten3(my_list, primitives=(bool, str, int, float)):
    flatten = []
    for item in my_list:
        if isinstance(item, primitives):
            flatten.append(item)
        else:
            flatten.extend(item)
    return flatten

他们的时间是：

list_1 = [1, 2, 3, 'ID45785', False, '', 2.85, [1, 2, 'ID85639', True, 1.8], (e for e in range(589, 591))]

%timeit to_flatten(list_1 * 100)
# 1000 loops, best of 3: 296 µs per loop
%timeit to_flatten1(list_1 * 100)
# 1000 loops, best of 3: 255 µs per loop
%timeit to_flatten2(list_1 * 100)
# 10000 loops, best of 3: 183 µs per loop
%timeit to_flatten3(list_1 * 100)
# 10000 loops, best of 3: 168 µs per loop

请注意，这不会展平任意嵌套的输入，而只会展平单个嵌套级别。

要展平任意嵌套的输入，可以使用：

def flatten_iter(items, primitives=(bool, int, float, str)):
    buffer = []
    iter_items = iter(items)
    while True:
        try:
            item = next(iter_items)
            if isinstance(item, primitives) or not hasattr(item, '__iter__'):
                yield item
            else:
                buffer.append(iter_items)
                iter_items = iter(item)
        except StopIteration:
            if buffer:
                iter_items = buffer.pop()
            else:
                break

或者：

def flatten_recursive(
        items,
        primitives=(bool, int, float, str)):
    for item in items:
        if isinstance(item, primitives) or not hasattr(item, '__iter__'):
            yield item
        else:
            for subitem in flatten_recursive(item, primitives):
                yield subitem

两者都较慢，但对于更深的嵌套可以正常工作（to_flatten3()与原始方法一样，的结果不是平坦的）：

list_2 = [list_1, [[[[1], 2], 3], 4], 5]
print(to_flatten3(list_2))
# [1, 2, 3, 'ID45785', False, '', 2.85, [1, 2, 'ID85639', True, 1.8], <generator object <genexpr> at 0x7f1c92dff6d0>, [[[1], 2], 3], 4, 5]
print(list(flatten_iter(list_2)))
# [1, 2, 3, 'ID45785', False, '', 2.85, 1, 2, 'ID85639', True, 1.8, 1, 2, 3, 4, 5]
print(list(flatten_recursive(list_2)))
# [1, 2, 3, 'ID45785', False, '', 2.85, 1, 2, 'ID85639', True, 1.8, 1, 2, 3, 4, 5]

（请注意，这里已经使用了生成器表达式，因此不会产生任何对象。）

在时间上，这里提出的迭代解决方案慢了大约 3 倍，而对于测试输入，递归解决方案慢了大约 2 倍，它只有一个嵌套级别（并且to_flatten3()也可以正常工作）：

%timeit list(flatten_iter(list_1 * 100))
# 1000 loops, best of 3: 450 µs per loop
%timeit list(flatten_recursive(list_1 * 100))
# 1000 loops, best of 3: 291 µs per loop

当输入具有更多嵌套级别时，时序为：

%timeit list(flatten_iter(list_2 * 100))
# 1000 loops, best of 3: 953 µs per loop
%timeit list(flatten_recursive(list_2 * 100))
# 1000 loops, best of 3: 714 µs per loop

并且递归解决方案再次比迭代解决方案更快（对于测试输入大约快 30%）。

虽然通常情况下，迭代方法在 Python 中执行得更快，因为它避免了昂贵的函数调用，但在建议的解决方案中，递归函数调用的成本被try/except子句和重复使用iter().

Cython 可以稍微改善这些时间。