Was ist die idiomatische Syntax für das Voranstellen einer kurzen Python-Liste?

543

list.append()ist die naheliegende Wahl, um am Ende einer Liste hinzuzufügen. Hier ist eine vernünftige Erklärung für das Fehlen list.prepend(). Angenommen, meine Liste ist kurz und Leistungsbedenken sind vernachlässigbar

list.insert(0, x)

oder

list[0:0] = [x]

idiomatisch?

Hurrymaplelad
quelle

Antworten:

784

Die s.insert(0, x)Form ist die häufigste.

Wann immer Sie es sehen, ist es möglicherweise an der Zeit, eine collection.deque anstelle einer Liste zu verwenden.

Raymond Hettinger
quelle
9
"Wann immer Sie es sehen, ist es möglicherweise an der Zeit, eine collection.deque anstelle einer Liste zu verwenden." Warum ist das?
Matt M.
6
@ MattM. Wenn Sie am Anfang einer Liste einfügen, muss Python alle anderen Elemente um ein Leerzeichen nach vorne verschieben. Listen können kein "Leerzeichen an der Vorderseite" erstellen. collection.deque (Double Ended Queue) unterstützt "Platz an der Vorderseite schaffen" und ist in diesem Fall viel schneller.
18.
265

Wenn Sie den funktionalen Weg gehen können, ist das Folgende ziemlich klar

new_list = [x] + your_list

Natürlich haben eingefügt Sie nicht xin your_list, sondern haben Sie eine neue Liste erstellt mit xihm preprended.

Nil Geisweiller
quelle
45
Wie Sie sehen, steht dies nicht vor einer Liste. Es wird eine neue Liste erstellt. Somit befriedigt es die Frage überhaupt nicht.
Chris Morgan
112
Obwohl es die Frage nicht befriedigt, rundet es sie ab, und das ist der Zweck dieser Website. Schätzen Sie den Kommentar und Sie haben Recht, aber wenn Leute danach suchen, ist es hilfreich, dies zu sehen.
Dave4JR
2
Wenn Sie einer Liste eine Liste voranstellen möchten, funktioniert die Verwendung von Einfügen nicht wie erwartet. aber diese Methode tut es!
Gota
90

Was ist die idiomatische Syntax für das Voranstellen einer kurzen Python-Liste?

Normalerweise möchten Sie einer Liste in Python nicht wiederholt voranstellen.

Wenn es kurz ist und du es nicht viel machst ... dann ok.

list.insert

Das list.insertkann auf diese Weise verwendet werden.

list.insert(0, x)

Dies ist jedoch ineffizient, da in Python a listein Array von Zeigern ist und Python nun jeden Zeiger in der Liste um eins nach unten verschieben muss, um den Zeiger auf Ihr Objekt im ersten Slot einzufügen. Dies ist also wirklich nur effizient für eher kurze Listen, wie Sie fragen.

Hier ist ein Ausschnitt aus der CPython-Quelle, in der dies implementiert ist. Wie Sie sehen können, beginnen wir am Ende des Arrays und verschieben bei jeder Einfügung alles um eins nach unten:

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

Wenn Sie einen Container / eine Liste wünschen, mit dem Elemente effizient vorangestellt werden können, möchten Sie eine verknüpfte Liste. Python hat eine doppelt verknüpfte Liste, die am Anfang und am Ende schnell eingefügt werden kann - sie heißt a deque.

deque.appendleft

A collections.dequehat viele Methoden einer Liste. list.sortist eine Ausnahme, die dequeLiskov definitiv nicht vollständig ersetzbar macht list.

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

Das dequehat auch eine appendleftMethode (sowie popleft). Es dequehandelt sich um eine Warteschlange mit zwei Enden und eine doppelt verknüpfte Liste - unabhängig von der Länge dauert es immer genauso lange, bis etwas angezeigt wird. In der großen O-Notation ist O (1) gegen die O (n) -Zeit für Listen. Hier ist die Verwendung:

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

deque.extendleft

Ebenfalls relevant ist die extendleftMethode der Deque , die iterativ Folgendes vorstellt:

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

Beachten Sie, dass jedem Element ein einzelnes vorangestellt wird, wodurch die Reihenfolge effektiv umgekehrt wird.

Leistung von listversusdeque

Zuerst richten wir mit einem iterativen Voranstellen ein:

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

und Leistung:

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

Die Deque ist viel schneller. Wenn die Listen länger werden, würde ich erwarten, dass eine Deque noch besser abschneidet. Wenn Sie Deques verwenden können, extendlefterzielen Sie auf diese Weise wahrscheinlich die beste Leistung.

Aaron Hall
quelle
57

Wenn jemand diese Frage wie ich findet, sind hier meine Leistungstests der vorgeschlagenen Methoden:

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

Wie Sie sehen können, ist die insertSlice-Zuweisung fast doppelt so schnell wie das explizite Hinzufügen und weist sehr enge Ergebnisse auf. Wie Raymond Hettinger feststellte, insertist dies eine häufigere Option, und ich persönlich bevorzuge diesen Weg, um der Liste voranzukommen.

Alexey Milogradov
quelle
11
Eine Sache, die bei diesem Test fehlt, ist die Komplexität. Während die ersten beiden Optionen eine konstante Komplexität aufweisen (sie werden nicht langsamer, wenn mehr Elemente in der Liste enthalten sind), weist die dritte eine lineare Komplexität auf (sie wird langsamer, abhängig von der Anzahl der Elemente in der Liste), da dies immer der Fall ist muss die ganze Liste kopieren. Mit mehr Elementen in der Liste kann das Ergebnis viel schlechter werden.
Dakkaron
6
@ Dakkaron Ich denke du liegst falsch. Nicht wenige Quellen zitieren die lineare Komplexität für list.insert, z. B. diese schöne Tabelle , und implizieren die vernünftige Erklärung, mit der der Fragesteller verknüpft ist. Ich vermute, dass CPython in den ersten beiden Fällen jedes Element im Speicher in der Liste neu zuordnet, sodass alle drei wahrscheinlich eine lineare Komplexität aufweisen. Ich habe mir den Code noch nicht angesehen oder selbst getestet. Es tut mir leid, wenn diese Quellen falsch sind. Collections.deque.appendleft hat die lineare Komplexität, von der Sie sprechen.
TC Proctor
@ Dakkaron nicht wahr, alle diese haben die gleiche Komplexität. Obwohl .insertund [0:0] = [0]Arbeit an Ort und Stelle , noch sie haben Neuzuweisung den gesamten Puffers.
juanpa.arrivillaga
Diese Benchmarks sind schlecht. Die anfängliche Liste sollte in einem separaten Einrichtungsschritt erstellt werden, der nicht Teil des Timings selbst ist. Und die letzte erstellt eine neue Liste mit einer Länge von 1000001, sodass im Vergleich zu den beiden anderen mutierenden In-Place-Versionen Äpfel und Orangen verwendet werden.
wim