Python 嵌套列表的内置求和

Question

当我完成leetcode 1313时，我发现了内置sum函数的特殊用法。

Leetcode 问题 1313

我们得到一个整数列表nums，表示用游程编码压缩的列表。

考虑每对相邻的元素[a, b] = [nums[2*i], nums[2*i+1]](其中 i >= 0)。对于每个这样的对，解压缩列表中都有值为 b 的 a 元素。

返回解压后的列表。

 

示例1:

Input: nums = [1,2,3,4]
Output: [2,4,4,4]
Explanation: The first pair [1,2] means we have freq = 1 and val = 2 so we generate the array [2].
The second pair [3,4] means we have freq = 3 and val = 4 so we generate [4,4,4].
At the end the concatenation [2] + [4,4,4,4] is [2,4,4,4].

有一个使用sum的解决方案

nums = [1,2,3,4]
g = ([b] * a for a, b in zip(nums[::2], nums[1::2]))
print(list(g))
g = ([b] * a for a, b in zip(nums[::2], nums[1::2]))
print(sum(g,[]))

输出:

[[2], [4, 4, 4]]
[2, 4, 4, 4]

我的问题

我不知道为什么 sum 在这种情况下可以处理嵌套列表。有人可以告诉我吗？或者其他一些类似的函数行为？

这是official guide对于内置sum。

Answer 1

简短回答

给定的代码片段运行连续的列表串联。

它是如何工作的

大致内置sum()函数的工作原理如下:

def sum(iterable, /, start=0):
    total = start
    for x in iterable:
        total = total + x
    return total

+ 运算符在左侧操作数上调用 __add__，以便 3 + 4 运行为 (3).__add__ (4)，整数的加法运算。同样，[10, 20] + [30, 40, 50] 运行为 [10, 20].__add__([30, 40, 50])，一个串联对列表的操作。

以下是给定示例中的效果:

>>> nums = [1,2,3,4]
>>> g = ([b] * a for a, b in zip(nums[::2], nums[1::2]))
>>> result = []
>>> x = next(g)
>>> result = result + x
>>> result
[2]
>>> x = next(g)
>>> result = result + x
>>> result
[2, 4, 4, 4]

为什么这不是一个好主意

连续的列表串联在每次添加后生成下一个列表，因此它们在 O(n**2) 处运行速度，这意味着这是一种二次算法，在给定大量输入时运行速度非常慢。

更好的方法

不必在每一步都构建新列表，只需 extend基本列表就位。它运行在 O(n)线速度:

>>> nums = [1,2,3,4]
>>> g = ([b] * a for a, b in zip(nums[::2], nums[1::2]))
>>> result = []                 # new list
>>> for x in g:
        result.extend(x)        # extend in-place

>>> result
[2, 4, 4, 4]

更好的方法

itertools module提供a tool for chaining together iterators 。这使得问题很快得到解决:

>>> nums = [1,2,3,4]
>>> g = ([b] * a for a, b in zip(nums[::2], nums[1::2]))
>>> list(chain.from_iterable(g))
[2, 4, 4, 4]

该解决方案简短、快速，即使在输入较大的情况下也能正常工作。