Python built-in sum for nested list

Question

When I finished leetcode 1313, I find a special usage of built-in sum function.

The Leetcode Problem 1313

We are given a list nums of integers representing a list compressed with run-length encoding.

Consider each adjacent pair of elements [a, b] = [nums[2*i], nums[2*i+1]] (with i >= 0). For each such pair, there are a elements with value b in the decompressed list.

Return the decompressed list.

Example 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].

There is a solution using `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,[]))

Output:

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

My question

I can't tell why sum can deal with a nested list in this situation. Can any one tell me about it? Or some other functions behavior like this?

Here is the official guide for built-in sum.

Raymond Hettinger · Accepted Answer · 2020-02-02 03:20:37Z

Short-answer

The given code-fragment runs successive list concatenations.

How it works

Roughly the built-in sum() function works like this:

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

The + operator calls __add__ on the left-hand operand so that 3 + 4 runs as (3).__add__(4), an addition operation on integers. Likewise, [10, 20] + [30, 40, 50] runs as [10, 20].__add__([30, 40, 50]), a concatenation operation on lists.

Here's how it plays out in the given example:

>>> 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]

Why it is not a good idea

Successive list concatenations make next list after each addition, so they run at O(n**2) speed, meaning that this a quadratic algorithm that runs excessively slow when given large inputs.

Better way

Instead of building new lists at each step, just extend the base list in-place. This runs at O(n) linear speed:

>>> 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]

Even better way

The itertools module provides a tool for chaining together iterators. This makes short-work of the problem:

>>> 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]

This solution is short, fast and works well even with large inputs.

chepner · Accepted Answer · 2020-02-01 16:14:34Z

sum(foo) simply uses the definition of + for the initial value. By default, the initial value is 0, so sum(g) would fail for a list since addition of lists and ints isn't defined. By passing an explicit initial value of [], this forces sum(foo, []) to be equal to foo[0] + foo[1] + ... + foo[n-1] + [], as observed.

>>> sum([[1], [2]])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'list'
>>> sum([[1], [2]], [])
[1, 2]

The exception to this definition is that you cannot use sum with a list of str values, even if you specify "" as the initial value. This is a hard-coded exception, resulting in a TypeError with a suggestion to use str.join instead.

>>> sum(["foo", "bar"])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'str'
>>> sum(["foo", "bar"], "")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: sum() can't sum strings [use ''.join(seq) instead]

Collectives™ on Stack Overflow

Python built-in sum for nested list

The Leetcode Problem 1313

There is a solution using `sum`

My question

2 Answers 2

Short-answer

How it works

Why it is not a good idea

Better way

Even better way

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

The Leetcode Problem 1313

There is a solution using sum

My question

2 Answers 2

Short-answer

How it works

Why it is not a good idea

Better way

Even better way

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related

There is a solution using `sum`