Wie kann ich einer kurzen Python-Liste etwas voranstellen?

Question

list.append() wird an das Ende einer Liste angehängt. Dies erklärt que list.prepend() gibt es aufgrund von Leistungsproblemen bei großen Listen nicht. Wie kann ich bei einer kurzen Liste einen Wert voranstellen?

Answer 1

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

Wann immer Sie es jedoch sehen, ist es vielleicht an der Zeit, den Einsatz eines collections.deque anstelle einer Liste. Das Voranstellen an eine Deque läuft in konstanter Zeit. Das Voranstellen an eine Liste läuft in linearer Zeit ab.

Answer 2

Dadurch wird eine neue Liste mit x vorangestellt, anstatt eine bestehende Liste zu ändern:

new_list = [x] + old_list

Answer 3

Was ist die idiomatische Syntax für das Voranstellen an eine kurze Python-Liste?

In der Regel möchte man in Python nicht wiederholt einer Liste vorangestellt werden.

Wenn die Liste kurz und du machst es nicht oft ... dann ist es okay.

list.insert

Die list.insert kann auf diese Weise verwendet werden.

list.insert(0, x)

Dies ist jedoch ineffizient, da in Python eine list ist ein Array von Zeigern, und Python muss nun jeden Zeiger in der Liste um eins nach unten verschieben, um den Zeiger auf Ihr Objekt in den ersten Slot einzufügen, so dass dies wirklich nur für recht kurze Listen effizient ist, wie Sie fragen.

Hier ein Ausschnitt aus dem CPython-Quelltext wo dies implementiert ist - und wie Sie sehen können, beginnen wir am Ende des Arrays und verschieben alles um eins nach unten für jede Einfügung:

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

Wenn Sie einen Container/eine Liste wollen, der/die effizient beim Voranstellen von Elementen ist, brauchen Sie eine verknüpfte Liste. Python hat eine doppelt verkettete Liste, die am Anfang und am Ende schnell eingefügt werden kann - sie heißt deque .

deque.appendleft

A collections.deque hat viele der Methoden einer Liste. list.sort ist eine Ausnahme und macht deque definitiv nicht vollständig Liskov-substituierbar für list .

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

Die deque hat auch eine appendleft Methode (wie auch die popleft ). Die Website deque ist eine Warteschlange mit zwei Enden und eine doppelt verknüpfte Liste - unabhängig von der Länge dauert es immer gleich lang, etwas vorzubereiten. In Big-O-Notation: O(1) gegenüber der O(n)-Zeit für Listen. Hier ist die Anwendung:

>>> 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 deque's extendleft Methode, die iterativ vorangestellt wird:

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

Beachten Sie, dass jedes Element einzeln vorangestellt wird, so dass sich die Reihenfolge der Elemente umkehrt.

Leistung von list gegen deque

Zunächst werden die Daten iterativ vorangestellt:

import timeit
from collections import deque

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

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

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

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

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

Und eine Funktion für die Analyse, so dass wir alle Vorgänge über eine Reihe von Verwendungen hinweg fair vergleichen können:

def compare_prepends(n, runs_per_trial):
    results = {}
    for function in (
        list_insert_0, list_slice_insert,
        list_add, deque_appendleft, deque_extendleft,
        ):
        shortest_time = min(timeit.repeat(
            lambda: function(n), number=runs_per_trial))
        results[function.__name__] = shortest_time
    ranked_methods = sorted(results.items(), key=lambda kv: kv[1])
    for name, duration in ranked_methods:
        print(f'{name} took {duration} seconds')

und Leistung (Anpassung der Anzahl der Durchläufe pro Versuch nach unten, um die längeren Laufzeiten von mehr Prepends zu kompensieren) repeat macht standardmäßig drei Versuche):

compare_prepends(20, 1_000_000)
compare_prepends(100, 100_000)
compare_prepends(500, 100_000)
compare_prepends(2500, 10_000)

>>> compare_prepends(20, 1_000_000)
deque_extendleft took 0.6490256823599339 seconds
deque_appendleft took 1.4702797569334507 seconds
list_insert_0 took 1.9417422469705343 seconds
list_add took 2.7092894352972507 seconds
list_slice_insert took 3.1809083241969347 seconds
>>> compare_prepends(100, 100_000)
deque_extendleft took 0.1177942156791687 seconds
deque_appendleft took 0.5385235995054245 seconds
list_insert_0 took 0.9471780974417925 seconds
list_slice_insert took 1.4850486349314451 seconds
list_add took 2.1660344172269106 seconds
>>> compare_prepends(500, 100_000)
deque_extendleft took 0.7309095915406942 seconds
deque_appendleft took 2.895373275503516 seconds
list_slice_insert took 8.782583676278591 seconds
list_insert_0 took 8.931685039773583 seconds
list_add took 30.113558700308204 seconds
>>> compare_prepends(2500, 10_000)
deque_extendleft took 0.4839253816753626 seconds
deque_appendleft took 1.5615574326366186 seconds
list_slice_insert took 6.712615916505456 seconds
list_insert_0 took 13.894083382561803 seconds
list_add took 72.1727528590709 seconds

Der Deque ist viel schneller. Je länger die Listen werden, desto besser ist die Leistung von Deques. Wenn Sie die deque's extendleft Auf diese Weise erhalten Sie wahrscheinlich die beste Leistung.

Wenn Sie Listen verwenden müssen, bedenken Sie, dass für kleine Listen, list.insert arbeitet schneller, aber bei größeren Listen wird das Einfügen mit der Slice-Notation schneller.

Listen nicht vorangestellt

Listen sind zum Anhängen gedacht, nicht zum Voranstellen. Wenn Sie eine Situation haben, in der diese Art von Voranstellen die Leistung Ihres Codes beeinträchtigt, wechseln Sie entweder zu einer Deque oder, wenn Sie Ihre Semantik umkehren und das gleiche Ziel erreichen können, kehren Sie Ihre Liste um und hängen Sie stattdessen an.

Vermeiden Sie es im Allgemeinen, dem eingebauten Python list Objekt.

Answer 4

Falls jemand diese Frage wie ich findet, hier sind 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, insert und Slice-Zuweisung sind fast doppelt so schnell wie das explizite Addieren und liegen in den Ergebnissen sehr nahe beieinander. Wie Raymond Hettinger notiert insert ist die gängigere Option, und ich persönlich bevorzuge diesen Weg, um der Liste voranzustellen.

Answer 5

Meiner Meinung nach ist die eleganteste und idiomatischste Art, in Python ein Element oder eine Liste einer anderen Liste voranzustellen, die Verwendung des Erweiterungsoperators * (auch Entpackungsoperator genannt),

# Initial list
l = [4, 5, 6]

# Modification
l = [1, 2, 3, *l]

Die Liste, die sich nach der Änderung ergibt, lautet [1, 2, 3, 4, 5, 6]

Ich mag es auch, zwei Listen einfach mit dem Operator + zu kombinieren, wie hier gezeigt,

# Prepends [1, 2, 3] to l
l = [1, 2, 3] + l

# Prepends element 42 to l
l = [42] + l

Ich mag den anderen üblichen Ansatz nicht, l.insert(0, value) da sie eine magische Zahl erfordert. Außerdem, insert() erlaubt nur das Voranstellen eines einzelnen Elements, aber der obige Ansatz hat die gleiche Syntax für das Voranstellen eines einzelnen Elements oder mehrerer Elemente.