为什么 '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²).

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

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

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

[x for sub in a for x in sub]

这就是这样一个 anti-pattern，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）已经摊销了 constant-time 行为，因此总体而言，它将是 O(N)。

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

why 'functools.reduce' and 'itertools.chain.from_itertools' had different computation time when nested list merged

python

reduce

itertools

python-3.x

functools