python - 这在 python : flat_array = sum( array_2d , [ ] 中如何工作)

Question

要在 python 中将二维数组转换为一维数组，我在 leetcode 上找到了这个方法。但是找不到它是如何一步一步逻辑地工作的？请解释。也有人在 leetcode 上说:“当数组大小变得非常大时，这可能是二次运行时复杂度”

这是真的吗？如果是，怎么做？

a = [[4,2,5],[1,8,2],[7,5,6]]
flat  = sum(a,[])
flat

输出:[4, 2, 5, 1, 8, 2, 7, 5, 6]

Answer 1

sum 是如何工作的？

在 Python 中，列表可以用运算符 + 连接:

>>> [1] + [2, 3]
[1, 2, 3]

Python 中的sum 函数类似于:

>>> def my_sum(iterable, start=0):
...     for v in iterable:
...         start = start + v
...     return start
...

所以对于sum(a, [])，可以理解如下操作:

>>> [] + [4, 2, 5] + [1, 8, 2] + [7, 5, 6]
[4, 2, 5, 1, 8, 2, 7, 5, 6]

但这不是一个好的做法，因为每次连接都会产生一个新列表，而不是在其中一个列表上进行连接:

>>> a = [1]
>>> b = [2, 3]
>>> c = a + b
>>> a, b, c
([1], [2, 3], [1, 2, 3])

这意味着每次连接需要 O(n + m) 时间(n 和 m 分别是两个列表的长度)，而不是 O(m) .对于长度为 n 的 m 个列表，第一次长度为 n 的列表将与另一个长度为 n 的列表连接，下一次长度为 2n 的列表将与长度为 n 的列表连接...最后，花费的总时间将是:

(n + n) + (2n + n) + ... + (mn + n) = (m^2 + 3m) * n / 2 = O(m^2 * n)

更好的做法

简单的方法就是每次都使用in place concatenate:

def concatenate(lists):
    result = []
    for lst in lists:
        result += lst
    return result

更简洁的方法是使用functools.reduce和 operator.iconcat :

>>> from functools import reduce
>>> from operator import iconcat
>>> reduce(iconcat, a, [])
[4, 2, 5, 1, 8, 2, 7, 5, 6]

您还可以使用 itertools.chain.from_iterable链接这些列表，然后使用 list构建:

>>> from itertools import chain
>>> list(chain.from_iterable(a))
[4, 2, 5, 1, 8, 2, 7, 5, 6]

或者使用嵌套列表comprehension :

>>> [val for lst in a for val in lst]
[4, 2, 5, 1, 8, 2, 7, 5, 6]

性能对比请引用:How do I make a flat list out of a list of lists?