Entfernen von Elementen aus Listen: Hinten wegnehmen ist besser als vorne!

Teil 2 einer Serie über performantes Programmieren mit Bezug auf Operations Research. In diesem Beitrag wird gezeigt, wieso es besser ist Elemente hinten an eine Liste anzufügen, als vorn zu insertieren.

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.

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.

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

Nehmen wir an, wir haben eine Liste liste = [1,2,3,4] aus der wir das erste Element (1) entfernen wollen. Dies gelingt uns in Python mit liste.pop(0), in anderen Programmiersprachen gibt es äquivalente Methoden.

In einem solchen Fall “rutschen” alle verbleibenden Elemente um eins nach vorne. Damit mit liste[0], liste[1] und liste[2] dann anschließend die Zahlen 2, 3 und 4 adressiert werden können, muss nach dem entfernen der Zahl 1 eine interne Re-Nummerierung der verbleibenden Elemente vorgenommen werden. Aus diesem Grund ist die Zeitkomplexität in einem solchen Fall O(n) (mit n= Anzahl Elemente in der Liste).

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

Beispiel

Das nachfolgende Beispiel, illustriert den zeitlichen Unterschied.

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

Während das Entfernen von 100.000 Elementen (von vorne) rund eine Sekunde benötigt, dauert das Entfernen von hinten lediglich 0.01 Sekunden.