Somme intégrée à Python pour les listes imbriquées

Question

Quand j'ai terminé le leetcode 1313, j'ai trouvé un usage spécial de l'intégré. sum función.

Le problème du Leetcode 1313

On nous donne une liste nums d'entiers représentant une liste compressée avec un encodage de longueur de course.

Considérons chaque paire adjacente d'éléments [a, b] = [nums[2*i], nums[2*i+1]] (with i >= 0) .  Pour chaque paire de ce type, il existe a éléments ayant une valeur b dans la liste décompressée.

Retourne la liste décompressée.

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

Il existe une solution utilisant 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,[]))

Sortie :

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

Ma question

Je ne peux pas dire pourquoi sum peut traiter une liste imbriquée dans cette situation. Quelqu'un peut-il m'en parler ? Ou d'autres fonctions ayant le même comportement ?

Voici le guide officiel pour l'encastrement sum .

Answer 1

Réponse courte

Le fragment de code donné exécute des concaténations de listes successives.

Comment cela fonctionne

En gros, l'intégré somme() fonctionne comme suit :

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

En + appels des opérateurs __add__ sur l'opérande de gauche de sorte que 3 + 4 fonctionne comme (3).__add__(4) une opération d'addition sur les entiers. De même, [10, 20] + [30, 40, 50] fonctionne comme [10, 20].__add__([30, 40, 50]) une opération de concaténation sur des listes.

Voici comment cela se passe dans l'exemple donné :

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

Pourquoi ce n'est pas une bonne idée

Les concaténations de listes successives créent la liste suivante après chaque ajout, ce qui fait qu'elles s'exécutent à la vitesse de O(n**2) vitesse, ce qui signifie qu'il s'agit d'un algorithme quadratique qui tourne excessivement lentement lorsqu'on lui donne de grandes entrées.

Meilleur moyen

Au lieu de construire de nouvelles listes à chaque étape, il suffit de étendre la liste de base en place. Cela fonctionne à O(n) vitesse linéaire :

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

Encore mieux

En module itertools fournit un outil pour enchaîner les itérateurs . Le problème est ainsi résolu au plus vite :

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

Cette solution est courte, rapide et fonctionne bien même avec des entrées importantes.

Answer 2

sum(foo) utilise simplement la définition de + pour la valeur initiale. Par défaut, la valeur initiale est 0 Así que sum(g) échouerait pour une liste puisque l'addition de listes et d'ints n'est pas définie. En passant une valeur initiale explicite de [] ce qui oblige sum(foo, []) pour être égal à foo[0] + foo[1] + ... + foo[n-1] + [] comme observé.

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

L'exception à cette définition est que vous ne pouvez pas utiliser sum avec une liste de str même si vous spécifiez "" comme valeur initiale. Il s'agit d'une exception codée en dur, ce qui entraîne l'apparition d'un TypeError avec une suggestion d'utiliser str.join à la place.

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