Python ERWEITERTE Datentypen – Ist deque die bessere Liste?

Python hat mit Listen, Sets, Tupel und Dictionaries eine Reihe nützlicher Datenstrukturen direkt mit dabei.
Aber wusstest du, dass du auch noch Hilfe dabei kommst, die Typen so effizient wie möglich zu nutzen?
In dieser kleinen Serie möchte ich dir zeigen, welche das sind!
Deque bietet dabei eine paar schöne Möglichkeiten für Listen.

Listen sind einfach und kommen täglich zu Hauf zum Einsatz.
Aber was, wenn du viele Elemente gerade an den Anfang einer Liste einfügen möchtest?

In dem Beitrag verrate ich dir, wie auch hier die Laufzeit klein bleibt!

Mit dem collections Modul bekommst du mehrere Klassen, die dir dabei helfen sollen, die verschiedenen Typen in Python so effizient wie möglich zu nutzen.

Als Beispiel dient heute eine ToDo Liste.
Aufgaben können zur Liste hinzugefügt oder auch wieder entfernt werden.

Listen Geschwindigkeit

Kurz zur Erinnerung:
Listen sind veränderbare, geordnete Sequenzen.
Du kannst also einfach Elemente reinwerfen und sie bleiben an der Position, zu der du sie hinzugefügt hast.

import datetime
kategorien = ['Küche', 'Büro', 'Wohnzimmer']
start = datetime.datetime.now()
kategorien[0]
end = datetime.datetime.now()
print(end - start)
0:00:00.000039 

Aber was, wenn du Elemente am Anfang einfügen willst?
Dann werden Listen ganz schön langsam…

start = datetime.datetime.now()
kategorien.insert(0, 'Bad')
end = datetime.datetime.now()
print(end - start)
0:00:00.000172 

Kurzer Abstecher in “Big O”

Das liegt an der Performance der Operation. 
In der Softwareentwicklung wird die Auswirkung der Größe einer Operation auf die Zeit in der Big O Notation angegeben.

Zum Beispiel hat eine Operation mit O(1) einen konstanten Zeitverbrauch.
Das heißt egal wie groß die Operation ist, egal wie viele Elemente, die Operation braucht immer dieselbe Zeit.

Wenn Elemente zu dem Beginn einer Liste hinzugefügt werden sollen, ist das eine O(n) Operation.
Also je mehr Elemente (n) betroffen sind, desto langsamer wird die Operation.
Ist die Liste also bereits hunderte von Einträgen lang, dauert das Einfügen deutlich länger als bei den mickrigen 3 Einträgen.

Woran liegt das?
Listen behalten die Position.
Wird also an den Anfang etwas eingefügt, müssen alle Elemente um eine Position weiter geschoben werden.
Das heißt, jedes Element muss angefasst und mit einer Aktualisierung für den Index versehen werden.

Die Lösung bei Performance-Problemen

Da der Fall aber immer wieder vorkommt, gibt es in Python natürlich auch eine Lösung dafür.
Und die bekommst du im collections Modul über deque (“Deck“).

Mit deque kannst du Elemente mit einer O(1) Geschwindigkeit an den Anfang von Listen setzen!
Und so einfach gehts:

import datetime
from collections import deque
kategorien = deque(['Küche', 'Büro', 'Wohnzimmer'])
start = datetime.datetime.now()
kategorien.appendleft('Bad')
end = datetime.datetime.now()
print(end - start)
0:00:00.000047 

Mit deque() bekommst du also eine Liste, die Elemente am Anfang hinzufügen kann, ohne dass es eine Rolle spielt, wie viele Elemente schon in der Liste enthalten sind!

Doch nicht ganz…

Warum dann überhaupt noch Listen benutzen?
Wieso nicht deque() zum Standard machen?

Wo es Vorteile gibt, gibt es natürlich auch Nachteile:
Listen können mit einer Leistung von O(n) Elemente am Anfang hinzufügen.
Aber sie können mit einer Leistung von O(1) beliebige Elemente aus beliebig langen Listen entnehmen – durch den Zugriff über den Index.

Mit deque() geben wir den Vorteil auf zugunsten des schnellen zufügens.
Das heißt, mit deque kannst du zwar an beide Seiten der Listenelemente mit einer Leistung von O(1) hinzufügen – egal wie viele Elemente enthalten sind.
Aber das Herausziehen bestimmter Elemente hat dafür eine O(n) Leistung.

Zusammenfassung

Zusammengefasst heißt das: Überleg dir, was du brauchst!

Musst du viele Elemente zu großen Listen hinzufügen, ist deque() das Werkzeug der Wahl.
Hast du aber große Listen und musst über viele Zugriffe verschiedene Elemente entnehmen, ist die Standard-Liste deutlich schneller.

Kanntest du deque() schon? Schreib mir in den Kommentaren und lass mich wissen, wofür du es bisher eingesetzt hast!

Ressourcen

https://wiki.python.org/moin/TimeComplexity