为什么'functools.reduce'和'itertools.chain.from_itertools'在嵌套列表合并时有不同的计算时间

Question

有时你应该嵌套合并到合并列表（它类似于np.flatten()）。当列表的列表如下所示时，您应该将其展平

a = [[j for j in range(0, 10)] for i in range(0, 10000)]

你有两种解决方案来解决它。itertools.chain.from_iterable和functools.reduce。

%timeit list(itertools.chain.from_iterable(a))
%timeit reduce(lambda x, y: x+y, a)

你认为哪一个更快，比其他东西快多少？

itertools.chain.from_iterable快 1000 倍或更多（当列表的长度较大时）。

如果有人知道为什么会发生这种情况，请告诉我。

始终感谢您的支持和帮助。

Answer 1

是的，因为列表串联（即使用 ）+是 O(N) 操作。当您这样做来逐步构建大小为 N 的列表时，它会变成 O(N ² )。

相反，usingchain.from_iterable将使用类型构造函数简单地迭代最终列表中的所有 N 项list，这将具有线性性能。

这就是为什么您不应该使用sum展平列表（注意，reduce(lambda x, y: x+y,...)只是sum）。

请注意，像这样展平嵌套列表的惯用方法是使用列表理解：

[x for sub in a for x in sub]

这是一种反模式，该sum方法阻止您对str对象执行此操作：

>>> sum(['here', 'is', 'some', 'strings'], '')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: sum() can't sum strings [use ''.join(seq) instead]

请注意，您的reduce/sum方法相当于：

result = []
for sub in a:
    result = result + sub

+这非常清楚地表明了循环中的昂贵。请注意，以下简单方法实际上具有 O(N) 行为，而不是 O(N ² )：

result = []
for sub in a:
    result += sub

这是因为my_list += something等价于my_list.extend(something)、 和.extend（与.append） 具有摊销常数时间行为，因此总体而言，它将是 O(N)。