Quelle est la syntaxe idiomatique pour ajouter à une courte liste python?

543

list.append()est le choix évident pour ajouter à la fin d'une liste. Voici une explication raisonnable pour les disparus list.prepend(). En supposant que ma liste est courte et que les problèmes de performances sont négligeables,

list.insert(0, x)

ou

list[0:0] = [x]

idiomatique?

hurrymaplelad
la source

Réponses:

784

La s.insert(0, x)forme est la plus courante.

Chaque fois que vous le voyez, il peut être temps d'envisager d'utiliser un collections.deque au lieu d'une liste.

Raymond Hettinger
la source
9
"Chaque fois que vous le voyez, il est peut-être temps d'envisager d'utiliser un collections.deque au lieu d'une liste." Pourquoi est-ce?
Matt M.
6
@MattM. Si vous insérez au début d'une liste, python doit déplacer tous les autres éléments d'un espace vers l'avant, les listes ne peuvent pas "faire de l'espace au premier plan". collections.deque (file d'attente à double extrémité) prend en charge la "création d'espace à l'avant" et est beaucoup plus rapide dans ce cas.
fejfo
266

Si vous pouvez suivre la voie fonctionnelle, ce qui suit est assez clair

new_list = [x] + your_list

Bien sûr, vous ne l'avez pas inséré xdans your_list, plutôt vous avez créé une nouvelle liste avec xpré-ajouté.

Nil Geisweiller
la source
45
Comme vous le constatez, cela ne précède pas une liste. Il crée une nouvelle liste. Cela ne satisfait donc pas du tout la question.
Chris Morgan
113
Bien qu'il ne réponde pas à la question, il le complète, et c'est le but de ce site Web. Appréciez le commentaire et vous avez raison, mais lorsque les gens le recherchent, il est utile de le voir.
dave4jr
2
De plus, si vous souhaitez ajouter une liste à une liste, l'utilisation de l'insertion ne fonctionnera pas comme prévu. mais cette méthode fait!
gota
90

Quelle est la syntaxe idiomatique pour ajouter à une courte liste python?

Vous ne voulez généralement pas ajouter de manière répétitive à une liste en Python.

Si c'est court et que tu ne le fais pas beaucoup ... alors ok.

list.insert

Le list.insertpeut être utilisé de cette façon.

list.insert(0, x)

Mais cela est inefficace, car en Python, un list est un tableau de pointeurs, et Python doit maintenant prendre chaque pointeur de la liste et le déplacer vers le bas d'un pour insérer le pointeur sur votre objet dans le premier emplacement, donc ce n'est vraiment efficace pour des listes assez courtes, comme vous le demandez.

Voici un extrait de la source CPython où cela est implémenté - et comme vous pouvez le voir, nous commençons à la fin du tableau et déplaçons tout par le bas pour chaque insertion:

for (i = n; --i >= where; )
    items[i+1] = items[i];

Si vous voulez un conteneur / une liste efficace pour ajouter des éléments, vous voulez une liste liée. Python a une liste doublement liée, qui peut être insérée au début et à la fin rapidement - elle s'appelle a deque.

deque.appendleft

A collections.dequepossède de nombreuses méthodes d'une liste. list.sortest une exception, ce qui rend dequedéfinitivement pas entièrement Liskov substituable à list.

>>> set(dir(list)) - set(dir(deque))
{'sort'}

Le a dequeégalement une appendleftméthode (ainsi que popleft). Il deques'agit d'une file d'attente à double extrémité et d'une liste à double liaison - quelle que soit la longueur, il faut toujours autant de temps pour préparer quelque chose. En grande notation O, O (1) par rapport au temps O (n) pour les listes. Voici l'utilisation:

>>> import collections
>>> d = collections.deque('1234')
>>> d
deque(['1', '2', '3', '4'])
>>> d.appendleft('0')
>>> d
deque(['0', '1', '2', '3', '4'])

deque.extendleft

La extendleftméthode deque , qui préfère itérativement:

>>> from collections import deque
>>> d2 = deque('def')
>>> d2.extendleft('cba')
>>> d2
deque(['a', 'b', 'c', 'd', 'e', 'f'])

Notez que chaque élément sera ajouté un à la fois, inversant ainsi efficacement leur ordre.

Performance de listversusdeque

D'abord, nous configurons avec un préfixe itératif:

import timeit
from collections import deque

def list_insert_0():
    l = []
    for i in range(20):
        l.insert(0, i)

def list_slice_insert():
    l = []
    for i in range(20):
        l[:0] = [i]      # semantically same as list.insert(0, i)

def list_add():
    l = []
    for i in range(20):
        l = [i] + l      # caveat: new list each time

def deque_appendleft():
    d = deque()
    for i in range(20):
        d.appendleft(i)  # semantically same as list.insert(0, i)

def deque_extendleft():
    d = deque()
    d.extendleft(range(20)) # semantically same as deque_appendleft above

et performance:

>>> min(timeit.repeat(list_insert_0))
2.8267281929729506
>>> min(timeit.repeat(list_slice_insert))
2.5210217320127413
>>> min(timeit.repeat(list_add))
2.0641671380144544
>>> min(timeit.repeat(deque_appendleft))
1.5863927800091915
>>> min(timeit.repeat(deque_extendleft))
0.5352169770048931

Le deque est beaucoup plus rapide. À mesure que les listes s'allongent, je m'attendrais à ce qu'un deque fonctionne encore mieux. Si vous pouvez utiliser deque, extendleftvous obtiendrez probablement les meilleures performances de cette façon.

Aaron Hall
la source
57

Si quelqu'un trouve cette question comme moi, voici mes tests de performance des méthodes proposées:

Python 2.7.8

In [1]: %timeit ([1]*1000000).insert(0, 0)
100 loops, best of 3: 4.62 ms per loop

In [2]: %timeit ([1]*1000000)[0:0] = [0]
100 loops, best of 3: 4.55 ms per loop

In [3]: %timeit [0] + [1]*1000000
100 loops, best of 3: 8.04 ms per loop

Comme vous pouvez le voir, l' insertattribution des tranches est presque deux fois plus rapide que l'ajout explicite et les résultats sont très proches. Comme l'a noté Raymond Hettinger,insert c'est une option plus courante et moi, personnellement, je préfère cette façon de préparer à la liste.

Alexey Milogradov
la source
11
Une chose qui manque à ce test est la complexité. Alors que les deux premières options ont une complexité constante (elle ne ralentit pas lorsqu'il y a plus d'éléments dans la liste), la troisième a une complexité linéaire (elle devient plus lente, selon la quantité d'éléments dans la liste), car elle a toujours doit copier toute la liste. Avec plus d'éléments dans la liste, le résultat peut empirer.
Dakkaron
6
@Dakkaron Je pense que vous vous trompez à ce sujet. Un certain nombre de sources citent la complexité linéaire de list.insert, par exemple ce joli tableau , et implicite par l'explication raisonnable à laquelle l'interrogateur a lié. Je soupçonne que CPython réalloue chaque élément en mémoire dans la liste dans les deux premiers cas, donc tous les trois ont probablement une complexité linéaire. Je n'ai pas réellement regardé le code ni testé moi-même, alors désolé si ces sources sont erronées. Collections.deque.appendleft a la complexité linéaire dont vous parlez.
TC Proctor
@Dkkaron n'est pas vrai, tous ces éléments ont une complexité équivalente. Bien .insertet le [0:0] = [0]travail en place , ils ont encore de réattribuer l'ensemble de la mémoire tampon.
juanpa.arrivillaga
Ces repères sont mauvais. La liste initiale doit être créée dans une étape de configuration distincte, ne faisant pas partie du timing lui-même. Et le dernier crée une nouvelle liste de 1000001 de long, donc la comparaison avec les deux autres versions mutantes sur place est celle des pommes et des oranges.
wim