Datenstrukturen in Python

Datenstrukturen in Python: 6 Dinge, die ich früher gewusst hätte

Ich hoffe, dass diese Tipps dir helfen, deine Arbeit mit Python-Datenstrukturen erheblich effizienter und effektiver zu gestalten. Indem du die Eigenschaften und die jeweilige Performance der verschiedenen Datenstrukturen besser verstehst, kannst du viel gezielter die richtige Struktur für deine spezifischen Anforderungen auswählen. Dadurch wirst du nicht nur die Laufzeit deines Programms optimieren, sondern auch den Speicherverbrauch minimieren, was insbesondere bei großen Datenmengen von enormer Bedeutung ist.

Es ist auch hilfreich, sich bewusst zu machen, dass Python eine Vielzahl an eingebauten Datenstrukturen bietet, die in vielen Fällen für die meisten Anwendungen ausreichend sind. Jedoch gibt es auch fortgeschrittenere Techniken und Module wie collections oder heapq, die dir zusätzliche Werkzeuge an die Hand geben, um noch effizienter zu arbeiten. Diese bewusste Auswahl kann den Unterschied ausmachen, wenn es um Skalierbarkeit und Performance geht.

Zusammengefasst: Die Wahl der richtigen Datenstrukturen in Python ist nicht nur eine theoretische Überlegung, sondern hat direkte Auswirkungen auf die Praktikabilität und Performance deiner Python-Anwendungen. Ich ermutige dich, dich mit den verschiedenen Optionen auseinanderzusetzen und die für deine spezifischen Anforderungen passende Struktur zu wählen, um die bestmögliche Effizienz zu erreichen. So wirst du in der Lage sein, sauberere, schnellere und speichereffizientere Code-Lösungen zu entwickeln.

Listen können als Stapel verwendet werden

Ein Stapel ist eine lineare Datenstruktur mit zwei Hauptoperationen – push und pop.

Das Hinzufügen eines Elements zu einem Stapel (push) bedeutet, dass das Element oben auf den Stapel gelegt wird.

Im Gegensatz dazu bedeutet das Entfernen eines Elements aus einem Stapel (pop), dass das oberste Element entfernt wird (und gleichzeitig dieses entfernte Element zurückgegeben wird).

Das Hinzufügen und Entfernen von Elementen aus einem Stapel folgt der First In, Last Out (FILO)-Regel — das erste hinzugefügte Element wird als letztes entfernt. Dies steht im Gegensatz zur First In, First Out (FIFO)-Regel, die beispielsweise bei Warteschlangen angewendet wird.

In Python gibt es keinen eingebauten Stapeltyp. Aber das ist kein Problem, denn wir können ganz einfach eine Liste verwenden, um einen Stapel effizient darzustellen. Eine Liste in Python bietet uns die Möglichkeit, Elemente am Ende hinzuzufügen oder zu entfernen, was genau dem Verhalten eines Stapels entspricht.

Um ein Element auf den Stapel zu legen, verwenden wir die Methode .append(), die es uns erlaubt, ein neues Element an das Ende der Liste hinzuzufügen, was dem push-Befehl entspricht. Um ein Element vom Stapel zu entfernen, verwenden wir die Methode .pop(), die das oberste Element entfernt und es gleichzeitig zurückgibt, was dem pop-Befehl entspricht.

Ein weiterer Vorteil von Listen als Stapel ist, dass diese Operationen sehr schnell sind — sie haben eine durchschnittliche Zeitkomplexität von O(1). Das bedeutet, dass sowohl das Hinzufügen als auch das Entfernen von Elementen in konstantem Zeitaufwand erfolgen, was sie zu einer idealen Wahl für Stapeloperationen in Python macht.

Die Verwendung einer Liste als Stapel ist besonders nützlich in vielen Algorithmen, wie zum Beispiel der Implementierung von Tiefensuche (Depth-First Search, DFS), dem Rückgängigmachen von Aktionen (Undo-Operationen) oder der Evaluation von Ausdrücken. Man kann sich also vorstellen, dass diese Technik sehr vielseitig und effektiv ist, um eine Vielzahl von Problemen in Python zu lösen.

Es ist nicht optimal, eine Liste als Warteschlange zu verwenden. Verwende stattdessen Deques.

Eine Warteschlange ist ähnlich wie ein Stapel — der Hauptunterschied besteht darin, dass sie nach der First In, First Out (FIFO)-Regel funktioniert. Eine Warteschlange hat zwei Hauptoperationen: enqueue und dequeue.

Das Hinzufügen eines Elements zu einer Warteschlange (enqueue) bedeutet, dass das Element am Ende der Warteschlange eingefügt wird.

Im Gegensatz dazu bedeutet das Entfernen eines Elements aus einer Warteschlange (dequeue), dass das Element an der Vorderseite der Warteschlange entfernt wird (und gleichzeitig dieses entfernte Element zurückgegeben wird).

Obwohl es möglich ist, eine Liste zu verwenden, um eine Warteschlange darzustellen, ist dies nicht optimal, insbesondere wenn die Warteschlange häufig Elemente entfernt.

Wenn wir ein Element in eine Liste einfügen, können wir die .append()-Methode verwenden, die eine konstante Laufzeit von O(1) hat, was sehr effizient ist.

Das Problem tritt jedoch auf, wenn wir ein Element aus der Warteschlange entfernen wollen. In diesem Fall müssen wir die .pop(0)-Methode verwenden, um das erste Element der Liste zu entfernen. Diese Operation hat jedoch eine lineare Laufzeit von O(n), weil Python alle anderen Elemente in der Liste verschieben muss, um die Lücke am Anfang zu schließen. Wenn die Warteschlange also viele Elemente enthält, kann diese Operation sehr ineffizient werden.

Eine bessere Lösung ist die Verwendung eines deque (Double-Ended Queue).

Ein deque ist eine doppelseitige Warteschlange, bei der das Hinzufügen und Entfernen von Elementen an beiden Enden (sowohl vorne als auch hinten) in konstanter Zeit O(1) durchgeführt werden kann. Dies bedeutet, dass das Einfügen eines Elements am Ende der Warteschlange ebenso schnell ist wie das Entfernen eines Elements von vorne.

Im Gegensatz zu einer Liste benötigt ein deque keine Verschiebung der anderen Elemente, wenn ein Element von vorne entfernt wird. Das macht es zu einer viel effizienteren Wahl für Warteschlangen, vor allem, wenn du viele dequeue-Operationen durchführen musst. Mit der collections.deque-Klasse in Python kannst du diese doppelseitige Warteschlange ganz einfach nutzen.

Die Verwendung eines deques ist also besonders nützlich, wenn du eine Warteschlange benötigst, bei der du sowohl Elemente am Anfang als auch am Ende schnell hinzufügen und entfernen musst, ohne dass sich die Performance bei größeren Datenmengen merklich verschlechtert. Dies ist der Fall in vielen Algorithmen und Datenverarbeitungsprozessen, wie etwa beim Aufbau von Warteschlangen für Verarbeitungsjobs oder in Szenarien, in denen Elemente dynamisch an beiden Enden eingefügt oder entfernt werden müssen.

Ein Deque ist tatsächlich eine doppelt verkettete Liste

Diese Implementierung wird uns im collections-Modul von Python verborgen, aber ich denke, es ist trotzdem gut zu wissen, wie sie funktioniert.

Ein Deque (Double-Ended Queue) ist im Wesentlichen eine doppelt verkettete Liste. Eine doppelt verkettete Liste ist wie eine normale verkettete Liste, aber jeder Knoten verfolgt sowohl den Verweis auf den nächsten Knoten als auch auf den vorherigen Knoten.

In einer normalen verketteten Liste gibt es nur einen Verweis auf das nächste Element, was bedeutet, dass du nur in eine Richtung (vorwärts) durch die Liste navigieren kannst. Bei einer doppelt verketteten Liste kannst du jedoch sowohl vorwärts als auch rückwärts durch die Liste gehen, weil jeder Knoten sowohl auf das nächste als auch auf das vorherige Element verweist.

Hier ist eine einfache Darstellung, wie ein Deque funktioniert:

Stell dir vor, du hast eine Liste von Knoten, und jeder Knoten hat zwei Verweise: einen auf den nächsten Knoten und einen auf den vorherigen Knoten. Wenn du ein Element am Anfang des deques hinzufügst oder entfernst, aktualisierst du einfach die Verweise der benachbarten Knoten. Dasselbe gilt für das Hinzufügen oder Entfernen von Elementen am Ende des deques.

Kurze Simulation eines deques:

  1. Hinzufügen eines Elements am Anfang (enqueue vorne):
    • Der neue Knoten wird der erste Knoten, und sein „nächster“ Verweis zeigt auf das ursprüngliche erste Element, das nun als zweites Element fungiert.
    • Der Verweis des ursprünglichen ersten Elements auf den vorherigen Knoten wird auf den neuen Knoten aktualisiert.
  2. Hinzufügen eines Elements am Ende (enqueue hinten):
    • Der neue Knoten wird der letzte Knoten, und sein „vorheriger“ Verweis zeigt auf das ursprüngliche letzte Element, das nun als zweitletztes Element fungiert.
    • Der Verweis des ursprünglichen letzten Elements auf das nächste Element wird auf den neuen Knoten aktualisiert.
  3. Entfernen eines Elements am Anfang (dequeue vorne):
    • Der erste Knoten wird entfernt, und der Verweis des „zweiten“ Knotens auf den vorherigen Knoten wird auf None gesetzt, da es nun das erste Element der Liste ist.
  4. Entfernen eines Elements am Ende (dequeue hinten):
    • Der letzte Knoten wird entfernt, und der Verweis des „vorletzten“ Knotens auf den nächsten Knoten wird auf None gesetzt, da es nun das letzte Element der Liste ist.

Die Möglichkeit, von beiden Enden der Liste effizient zu arbeiten, ist das, was deques so leistungsfähig macht.

Wenn dir also das nächste Mal ein Interviewer die Frage stellt „Wie denkst du, dass ein Deque implementiert wird?“, solltest du in der Lage sein, dies selbstbewusst zu beantworten. Du kannst darauf hinweisen, dass es sich um eine doppelt verkettete Liste handelt, bei der jeder Knoten sowohl auf das nächste als auch auf das vorherige Element verweist, was eine effiziente Operation an beiden Enden der Liste ermöglicht.

Liste vs. Tupel, Set vs. Frozenset und Dictionary vs. MappingProxy

Ein Objekt ist veränderlich (mutable), wenn wir seinen Zustand oder Wert nach seiner Erstellung ändern können. Zu den veränderlichen Datentypen in Python gehören beispielsweise Listen, Dictionaries, Sets und so weiter.

Im Gegensatz dazu ist ein Objekt unveränderlich (immutable), wenn wir seinen Zustand oder Wert nach seiner Erstellung nicht ändern können. Beispiele für unveränderliche Datentypen sind Ganzzahlen (Integers), Fließkommazahlen (Floats), None, Booleans und so weiter.

Wusstest du, dass Listen, Sets und Dictionaries ihre unveränderlichen Gegenstücke haben?

  • Ein Tupel ist eine unveränderliche Liste.
  • Ein Frozenset ist ein unveränderliches Set.
  • Ein MappingProxy ist ein unveränderliches Dictionary.

Der Hauptnachteil von unveränderlichen Datenstrukturen in Python ist, dass wir sie nicht mehr ändern können, nachdem sie erstellt wurden. Das bedeutet, dass wir keine Elemente hinzufügen, entfernen oder die Struktur der Sammlung ändern können.

Der Hauptvorteil von unveränderlichen Datenstrukturen ist jedoch, dass sie hashbar sind (mit Ausnahme des MappingProxy). Damit eine Datenstruktur als Schlüssel in einem Dictionary verwendet werden kann oder wir sie zu einem Set hinzufügen können, muss diese Datenstruktur hashbar sein. Hashbarkeit bedeutet, dass ein Objekt einen festen Hashwert hat, der sich nicht ändert, sobald das Objekt erstellt wurde.

Warum ist das wichtig?

Unveränderliche Datenstrukturen in Python wie Tupel, Frozensets und MappingProxies sind in der Lage, als Schlüssel in Dictionaries verwendet zu werden. Zum Beispiel kannst du ein Tupel als Schlüssel in einem Dictionary verwenden, während eine Liste als Schlüssel nicht funktioniert, weil Listen veränderlich sind und somit nicht hashbar sind. Ebenso können Tupel und Frozensets zu Sets hinzugefügt werden, was mit veränderlichen Datentypen wie Listen oder Sets nicht möglich ist.

Zusammenfassung:

  1. Veränderliche Datenstrukturen wie Listen, Sets und Dictionaries können nach ihrer Erstellung geändert werden, bieten jedoch keine Garantie für Hashbarkeit.
  2. Unveränderliche Datenstrukturen wie Tupel, Frozensets und MappingProxies sind hashbar, was sie für bestimmte Aufgaben wie als Dictionary-Schlüssel oder als Set-Elemente nützlich macht.
  3. Der Hauptvorteil der Unveränderlichkeit besteht darin, dass diese Strukturen in Sets und als Dictionary-Schlüssel verwendet werden können, was mit veränderlichen Strukturen nicht möglich ist.

In vielen Fällen spielt es eine große Rolle, ob eine Struktur unveränderlich oder veränderlich ist, da dies Auswirkungen auf die Performance und die Funktionsweise von Programmen haben kann. Wenn du also eine Datenstruktur brauchst, die als Schlüssel in einem Dictionary fungieren soll oder die zu einem Set hinzugefügt werden muss, solltest du ein unveränderliches Pendant wie ein Tupel oder Frozenset wählen.

Listen werden verwendet, um Heaps (Prioritätswarteschlangen) darzustellen

In einer Prioritätswarteschlange wird jedem Element eine Art Prioritätswert zugewiesen. Zu jedem Zeitpunkt wird das Element mit der höchsten Priorität als Nächstes aus der Warteschlange entfernt.

Im Wesentlichen handelt es sich bei einer Prioritätswarteschlange um eine Warteschlange, bei der die Reihenfolge der Elemente nicht nur durch die Reihenfolge ihres Eingangs bestimmt wird, sondern durch ihren Prioritätswert. Dies bedeutet, dass Elemente mit höherer Priorität immer vor denen mit niedrigerer Priorität verarbeitet werden, unabhängig davon, wann sie in die Warteschlange eingefügt wurden.

In Python verwenden wir Heaps, um Prioritätswarteschlangen zu implementieren. Ein Heap ist eine spezielle Art von Baumstruktur, bei der für jedes Element die Bedingung gilt, dass der Wert eines Knotens entweder größer oder kleiner ist als die Werte seiner Kinder (je nach Art des Heaps: Max-Heap oder Min-Heap). In einem Min-Heap ist das kleinste Element immer am Anfang, während in einem Max-Heap das größte Element immer am Anfang steht.

Das Interessante an Python ist, dass wir normale Listen verwenden können, um Heaps darzustellen, was eine sehr effiziente Implementierung der Prioritätswarteschlange ermöglicht. Um diese Funktionalität zu nutzen, verwenden wir das eingebaute Modul heapq, das eine Sammlung von Funktionen bietet, um mit Heaps zu arbeiten.

Wie funktioniert das?

  • Um ein Element in einen Heap einzufügen, verwenden wir die Methode heapq.heappush(). Diese Methode fügt das Element so in die Liste ein, dass die Heap-Eigenschaft beibehalten wird.
  • Um das Element mit der höchsten Priorität zu entfernen (im Fall eines Min-Heaps ist das das kleinste Element), verwenden wir die Methode heapq.heappop(). Diese Methode entfernt das kleinste Element (oder das Element mit der höchsten Priorität) und passt die Heap-Eigenschaft an, sodass der Heap immer korrekt bleibt.

Warum Listen? Python-Listen sind sehr flexible und dynamische Datenstrukturen in Python , die es uns ermöglicht, die Heap-Operationen effizient zu implementieren. Die Operationen wie das Einfügen und Entfernen von Elementen haben eine durchschnittliche Zeitkomplexität von O(log n), was die Verwendung von Listen als Heaps sehr effizient macht.

Beispiel für eine Prioritätswarteschlange:

Stell dir vor, du musst Aufgaben in einer Anwendung verarbeiten, bei denen einige Aufgaben dringender sind als andere. Du könntest die Aufgaben in einer Prioritätswarteschlange speichern, wobei Aufgaben mit einer höheren Priorität immer zuerst bearbeitet werden. In diesem Fall könnten die Aufgaben als Tupel gespeichert werden, wobei der erste Wert die Priorität darstellt, z. B.:

import heapq

# Eine leere Liste als Heap erstellen
heap = []

# Aufgaben mit Priorität einfügen
heapq.heappush(heap, (2, 'Task A'))  # Priorität 2
heapq.heappush(heap, (1, 'Task B'))  # Priorität 1
heapq.heappush(heap, (3, 'Task C'))  # Priorität 3

# Die Aufgaben in der Reihenfolge der Priorität abrufen
while heap:
    priority, task = heapq.heappop(heap)
    print(f'Processing: {task} mit priority {priority}')

Ausgabe:

Processing: Task B mit priority 1
Processing: Task A mit priority 2
Processing: Task C mit priority 3

In diesem Beispiel haben wir Aufgaben mit verschiedenen Prioritäten in den Heap eingefügt, und der Heap stellt sicher, dass die Aufgabe mit der höchsten Priorität zuerst verarbeitet wird. Das heapq-Modul übernimmt die Verwaltung der Heap-Eigenschaft und stellt sicher, dass die Operationen effizient ablaufen.

Heaps sind eine ideale Wahl, wenn du eine Prioritätswarteschlange benötigst, da sie es ermöglichen, Elemente schnell nach ihrer Priorität zu verwalten.

  • Python verwendet Listen, um Heaps darzustellen, und das heapq-Modul hilft uns, diese Datenstruktur zu nutzen, um Elemente effizient hinzuzufügen und zu entfernen.
  • Mit Heaps können wir sicherstellen, dass das Element mit der höchsten Priorität immer zuerst verarbeitet wird, was in vielen Algorithmen und Anwendungen von großer Bedeutung ist, wie zum Beispiel bei der Dijkstra-Algorithmus oder bei Task-Scheduling-Systemen.

Listen können Binärbäume darstellen

Aber warum kann eine normale Python-Liste einen Heap darstellen?

Ein Heap ist ein spezieller Binärbaum. In einem Min-Heap ist jeder Elternknoten kleiner oder gleich seinen Kindern, während in einem Max-Heap jeder Elternknoten größer oder gleich seinen Kindern ist.

Da Listen in Python verwendet werden können, um einen Binärbaum darzustellen, können Listen auch verwendet werden, um Heaps darzustellen, da Heaps eine spezielle Form von Binärbäumen sind (aber dennoch Binärbäume in ihrer Struktur bleiben).

Wie funktioniert das?

In einem Binärbaum hat jeder Knoten höchstens zwei Kindknoten. Bei der Verwendung einer Liste zur Darstellung eines Binärbaums wird eine bestimmte Indexierung genutzt, die es uns ermöglicht, Eltern- und Kindknoten durch einfache Berechnungen zu ermitteln.

  • Der Index 0 ist immer der Wurzelknoten des Baums.
  • Der Index 1 ist der linke Kindknoten des Wurzelknotens.
  • Der Index 2 ist der rechte Kindknoten des Wurzelknotens.
  • Der Index 3 und Index 4 sind die linken und rechten Kinder des Knotens an Index 1 (also des linken Kindes der Wurzel).
  • Der Index 5 und Index 6 sind die linken und rechten Kinder des Knotens an Index 2 (also des rechten Kindes der Wurzel).
  • Und so weiter.

Wenn ein Knoten weniger als zwei Kinder hat, setzen wir die entsprechenden Indizes in der Liste auf None, um das Fehlen eines Kindes zu kennzeichnen.

Ein Beispiel für die Repräsentation eines Binärbaums mit einer Liste:

Stell dir vor, du hast diesen Binärbaum:

       10
      /  \
     5    15
    / \   /
   3   7 12

Dieser Baum würde in einer Liste wie folgt dargestellt werden:

[10, 5, 15, 3, 7, 12, None]
  • Der Wurzelknoten 10 ist an Index 0.
  • Der linke Kindknoten 5 ist an Index 1, der rechte Kindknoten 15 an Index 2.
  • Der linke Kindknoten von 5 ist 3 (Index 3), der rechte Kindknoten von 5 ist 7 (Index 4).
  • Der linke Kindknoten von 15 ist 12 (Index 5), und da es keinen rechten Kindknoten für 15 gibt, setzen wir an Index 6 None ein.

Wie man die Indizes berechnet:

  • Der linke Kindknoten eines Knotens an Index i befindet sich immer an Index 2i + 1.
  • Der rechte Kindknoten eines Knotens an Index i befindet sich immer an Index 2i + 2.
  • Der Elternknoten eines Knotens an Index i befindet sich an Index (i - 1) // 2.

Beispiel:
Wenn du den linken Kindknoten des Knotens an Index 1 finden möchtest (also des Knotens 5), dann berechnest du 2 * 1 + 1 = 3, was den linken Kindknoten 3 ergibt. Ebenso, um den rechten Kindknoten von 5 zu finden, berechnest du 2 * 1 + 2 = 4, was den Knoten 7 ergibt.

Warum funktioniert das?

Die Struktur eines Binärbaums eignet sich hervorragend zur Darstellung in einer Liste, weil der Baum eine klare hierarchische Struktur hat, die mit den oben genannten Berechnungen leicht in einer flachen Liste abgebildet werden kann. Besonders in einem Heap, der eine sehr spezifische Struktur verlangt (je nach Min- oder Max-Heap), lässt sich diese Struktur mit einer Liste sehr effizient nachbilden.

Durch diese Indexierung und die hierarchische Struktur des Baums können wir die Elemente des Heaps oder des Binärbaums schnell ansprechen und bearbeiten, was besonders bei Algorithmen wie dem Sortieren mit Heaps oder der Durchführung von Prioritätswarteschlangen von Vorteil ist.

  • Listen können verwendet werden, um Binärbäume darzustellen, da die Indizes in einer Liste eine einfache Möglichkeit bieten, die hierarchische Struktur eines Baums abzubilden.
  • Indem wir die Positionen von Eltern- und Kindknoten mithilfe einfacher mathematischer Formeln berechnen, können wir eine effiziente und klare Repräsentation eines Binärbaums erstellen.
  • Für Heaps, die eine spezielle Form von Binärbäumen sind, verwenden wir ebenfalls Listen, um die Heap-Eigenschaften effizient zu verwalten.

Mehr zum Thema Python: Python Programmierung: Wie man einfach besseren Code schreibt oder 20 Programmierprojekt-Ideen: Sie werden 2025 zum Meister der Programmierung

VG WORT Pixel

Newsletter Anmeldung

Bleiben Sie informiert! Wir informieren Sie über alle neuen Beiträge (max. 1 Mail pro Woche – versprochen)