Programmieren mit Listen: Anfügen ist besser als einfügen

TL;DR

Bei Verfahren wie z.B. Branch and Bound, bei denen regelmäßig Elemente aus Listen entnommen werden, sollte man diese Elemente am oberen Ende wegnehmen. Diese Herangehensweise ist signifikant schneller, da das zugrunde liegende Array nicht neu aufgebaut werden muss.

Ausgangslage

Bei der Implementierung von einer Vielzahl von Algorithmen greift man vermutlich zu Listen. Dies kann beispielsweise bei den folgenden Verfahren der Fall sein:

Branch and Bound
Nachbarschaftssuchen
Dynamische Programmierung

Hierbei werden Elemente meist sortiert zu Listen hinzugefügt (z.B. Knoten im Suchbaum) und regelmäßig wieder entfernt (z.B. wenn der nächstbeste Knoten in einem Suchbaum betrachtet wird). In einem solchen Fall macht es Sinn, über die Sortierung der betroffenen Liste nachzudenken und es tunlichst zu vermeiden, dass “gute” Elemente unten und schlechte oben liegen.

Die nachfolgenden Absätze werden anhand von Python erklärt. Die Implikationen gelten aber für viele Programmiersprachen, z.B. Java.

Implikation von list.pop() und list.pop(0)

Wenn wir in der Liste liste = [1,2,3,4] das erste Element (1) entfernen wollen, gelingt uns dies mit liste.pop(0).

Hier geschieht nun folgendes im Hintergrund:

liste=[1,2,3,4] wird als Array im Arbeitsspeicher angelegt. Die Zahlen 1,2,3 und 4 haben den Index 0,1,2,3 und 4 im Array.
liste.pop(0) entfernt das erste Element in der Liste.
In einem solchen Fall “rutschen” alle verbleibenden Elemente um eins nach vorne. Die Elemente des zugrunde liegenden Arrays werden dabei unbemerkt neu angeordnet: Die Indizes der Elemente 2,3 und 4 werden nun zu 0,1 und 2. Ist dies geschehen, könne die Elemente mit liste[0] (für 2), liste[1] (für 2) und liste[2] (für 3) abgerufen werden.
Dies benötigt für die Liste mit n verbleibenden Elementen O(n) Schritte. Im Beispiel also drei Schritte.

Entfernen wir jedoch das letzte Element (4) mit liste.pop() entfällt diese Re-Nummerierung, da die verbleibenden Elemente nicht verschoben werden. Die Komplexität ist in diesem Fall O(1).

Empfehlung

In Listen mit Millionen von Einträgen kann die re-indexierung laufzeitkritisch werden. Die folgende Branch-and-Bound Implementierung speichert den Suchbaum als sortierte Liste von Knoten. Knoten mit einer guten Bound haben einen kleinen Index, Knoten mit einer schlechten Bound haben einen großen Index. In jedem Schritt wird der “beste” Knoten entnommen (Best-First-Search) und gebranched.

suchbaum = [initialknoten]
while len(suchbaum) > 0:
    naechster_knoten = suchbaum.pop(0) # Entfernt den besten Knoten, um ihn zu branchen
    kinder_knoten = branch(naechster_knoten)
    # ... Update der besten Lösung, Pruning
    # ...
    sortiere_in_baum(kinder_knoten) # sortiert "gute" Knoten nach vorne

Hier wäre es also empfehlenswert, die sortiere_in_baum Funktion so zu schreiben, dass gute Knoten ans Ende der Liste sortiert werden. Den besten Knoten entfernt man dann mit

naechster_knoten = suchbaum.pop() # Entfernt den letzten Knoten (hier ohne "0")

Laufzeitreduktion

Das nachfolgende Beispiel illustriert den zeitlichen Unterschied. Hier wird eine Liste mit 100.000 Einträgen geleert indem immer das erste oder das letzte Element entfernt wird.

import time

# Von vorne entfernen
now = time.time()
liste = list(range(100000))
while len(liste) > 0:
    liste.pop(0)
print("Dauer von vorne: {}".format(time.time()-now))

# Von hinten entfernen
now = time.time()
liste = list(range(100000))
while len(liste) > 0:
    liste.pop()
print("Dauer von hinten: {}".format(time.time()-now))

Die Laufzeiten der beiden Varianten sind die folgenden:

# Ausgabe:
Dauer von vorne: 0.9369099140167236
Dauer von hinten: 0.012409210205078125