Python встроенная сумма для вложенного списка

Question

Когда я закончил leetcode 1313, я обнаружил специальное использование встроенной функции sum.

Проблема Leetcode 1313

Нам дан список nums целых чисел, представляющих список, сжатый с использованием кодировки длин серий.

Рассмотрим каждую смежную пару элементов [a, b] = [nums[2*i], nums[2*i+1]] (with i >= 0). Для каждой такой пары в распакованном списке есть a элементов со значением b.

Возвращает распакованный список.

Пример 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 может иметь дело с вложенным списком в этой ситуации. Кто-нибудь может рассказать мне об этом? Или некоторые другие функции ведут себя следующим образом?

Вот официальное руководство для встроенного sum.

Answer 1

Краткий ответ

Данный фрагмент кода выполняет последовательные конкатенации списков.

Как это работает

Грубо говоря, встроенная сумма ( ) функция работает следующим образом:

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), что означает, что это алгоритм квадратичного c, который работает чрезмерно медленно при наличии больших входных данных.

Лучший способ

Вместо создания новых списков на каждом шаге, просто расширить базовый список на месте. Это работает на 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 предоставляет инструмент для создания цепочек вместе итераторы . Это облегчает проблему:

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

Это решение короткое, быстрое и хорошо работает даже при больших входах.

Answer 2

sum(foo) просто использует определение + для начального значения. По умолчанию начальное значение равно 0, поэтому sum(g) завершится ошибкой для списка, поскольку добавление списков и целых не определено. Передав явное начальное значение [], это заставляет sum(foo, []) быть равным foo[0] + foo[1] + ... + foo[n-1] + [], как отмечено.

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

Исключением из этого определения является то, что вы не можете использовать sum с список значений str, даже если вы указали "" в качестве начального значения. Это жестко закодированное исключение, приводящее к TypeError с предложением использовать вместо него str.join.

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