Python #23 – Datenstrukturen

In diesem Beitrag möchte ich dir die Datenstrukturen „Set“, „Queue“ und „Priority Queue“ aus Python3 genauer vorstellen.
Im nachfolgenden findest du zu jeder dieser Datenstruktur ein Beispiel sowie die Vor-&Nachteile aufgezeigt.

In den Beiträgen

habe ich bereits einige dieser Datenstrukturen vorgestellt und ausführlich mit Beispielen erläutert.

Hier möchte ich nun auf das Set sowie die Priority Queue eingehen.

Set

Ein leeres Set definiert man über die Schreibweise:

mySet = set()

wobei man jedoch ein Set auch gleich bei der initalisierung befüllen kann. Hier nutzt man die geschweifte Klammer (wie bei einem Dictionary):

mySet = {"Max", "Monika", "Stefan", "Birgit"}

Vor- & Nachteile

Vorteil

Die Einträge sind einmalig im Set, d.h. es können keine Elemente hinzugefügt werden welche bereits existieren.

Python3 - Set, hinzufügen von Elementen
Python3 – Set, hinzufügen von Elementen

Nachteil

Bei einem Set geht die Sortierung verloren, d.h. die Reihenfolge in welche man die Einträge mit der Funktion „add“ hinzufügt garantiert NICHT das dieses auch so im Set abgelegt wird.

Python3 - unsortiertes Set
Python3 – unsortiertes Set

In der Grafik erkennt man sehr gut dass, das Set mit den Namen Max, Moritz, Stefan, Klaus befüllt wird und beim auslesen die Reihenfolge Stefan, Max, Moritz, Klaus ist.

Beispiel – zählen der Städte in Niedersachsen

Im nachfolgenden Beispiel durchlaufen wir die GeoIP Datendank und filtern diese nach allen Städten in Europa & Deutschland & Niedersachsen. Die Stadt wird in ein Set aufgenommen, somit erhalten wir eine Aufzählung aller Namen welche nur einmal vorkommen.

#Bibliothek zum verarbeiten von CSV Dateien
import csv

#initialisieren eines leeren Sets 
citys = set()

#öffnen der Datei 
with open("../data/dbip07.csv",'r', encoding='utf-8') as file:
    #CSV Reader erstellen, die Werte sind mit einem Komma getrennt 
    #sollte einmal ein Wert ein Komma enthalten so wird dieses in doppelte
    #anführungszeichen gesetzt.
    namesReader = csv.reader(file, delimiter=',', quotechar='"')
    #entspacken der Liste in einzelne Werte
    for ip_start, ip_end, continent, country, stateprov, city, latitude, longitude in namesReader:
        #Wenn der Datensatz die Werte enthält...
        if continent == 'EU' and country == 'DE' and stateprov == 'Lower Saxony':
            #Stadt in das Set einfügen
            citys.add(city)

#ausgeben der Länge / Anzahl des Sets
print(len(citys))

Würden die Daten statt in ein Set in eine Liste aufgenommen werden so wären deutlich mehr Daten in der Datenstruktur vorhanden denn zu einigen Städten gibt es mehr IP Bereiche.

Queue

Eine Queue ist eine Liste welche optimiert ist um Daten an diese anzuhängen und vom Anfang zu entfernen. Quasi kann man sich eine Queue als eine Art Warteschlange vorstellen wo man von vorne immer ein Element entfernt. Um eine Queue erstellen zu können, müssen wir das Modul „queue“ in unser Programm importieren.

import queue

Die Queue bietet zum entnehmen des ersten Elementes die Funktion „get“ und zum hinzufügen die Funktion „put“.

Beispiel

Wie bereits erwähnt kann man sich die Queue als eine Warteschlange vorstellen, nun wollen wir das Beispiel aufgreifen und uns ein Wartezimmer als Queue erstellen. Wer also als erstes kam wird auch aus der Queue als erstes entnommen.

from queue import Queue

wartezimmer = Queue()
wartezimmer.put("Max Mustermann")
wartezimmer.put("Sabine Bauer")
wartezimmer.put("Moritz Mueller")
wartezimmer.put("Erika Meier")

print(wartezimmer.get())

print(wartezimmer.get())

print(wartezimmer.get())

print(wartezimmer.get())

Mit der Funktion „put“ fügen wir als erstes nach einander die Personen dem Wartezimmer (unserer Queue) hinzu. Danach entnehmen wir diese der Queue mit der Funktion „get“. Dabei rückt dann das nächste eine Stelle nach vorne und somit können wir das nächste Element auch wieder mit „get“ entnehmen usw.

Wenn die Queue leer ist und wir mit „get“ versuchen“ diesem Objekt etwas zu entnehmen wird kein Fehler geworfen es wird ein leeres Objekt (nicht vom Typ None) geliefert.

Die Anzahl der verbleibenden Elemente einer Queue kann man mit der Funktion „qsize“ auslesen und somit ermitteln wann diese leer ist.

Wenn du mehr über das Modul Queue erfahren möchtest so kannst du auf der Seite https://docs.python.org/3/library/queue.html weiterführende Informationen finden.

Priority Queue

Die Priority Queue erweitert die Queue um die Möglichkeit den Daten eine Priorität zu geben. Der Vorteil dabei ist, das unsere Queue nach dieser Prioriät sortiert wird und wir somit die Einträge nach diesem Wert automatisch entnehmen.

Die Funktion „put“ erwartet ein Tupel, wobei an erster Stelle eine Zahl (positiv wie auch negativ) erwartet wird und an zweiter Stelle ein beliebiger anderer Datentyp.

from queue import PriorityQueue

class Test():
    pass
    
pq = PriorityQueue()

pq.put((-1, 1))
pq.put((-10, "Test"))
pq.put((-15, 1.5))

test = Test()
pq.put((10, test))

print(pq.get())
print(pq.get())
print(pq.get())
print(pq.get())

Auf der Konsole werden die Daten wie folgt ausgegeben:

(-15, 1.5)
(-10, 'Test')
(-1, 1)
(10, <__main__.Test object at 0x000001C5CF680B38>)

Greifen wir also unser Wartezimmer auf und schauen uns das Beispiel einmal mit einer Priority Queue an. Denn im Wartezimmer wird nicht nur entschieden nach FIFO („First In First Out“) sondern auch nach schwere der Krankheit.

from queue import PriorityQueue

simulant = 100
schnupfen = 80
schlecht = 15
ganzSchlecht = 1

wartezimmer = PriorityQueue()
wartezimmer.put((simulant,"Max Mustermann"))
wartezimmer.put((ganzSchlecht,"Sabine Bauer"))
wartezimmer.put((schnupfen,"Moritz Mueller"))
wartezimmer.put((schlecht,"Erika Meier"))
wartezimmer.put((simulant,"Jochen Braun"))

print(wartezimmer.get())

print(wartezimmer.get())

print(wartezimmer.get())

print(wartezimmer.get())

print(wartezimmer.get())

Wir befüllen nun unsere Priority Queue mit unseren Wartenden jedoch vergeben wir zusätzlich die Prioritäten welche ich als Variablen zunächst definiert habe. Dabei gilt je kleiner die Zahl desto höher ist die Priorität.

Wenn wir das Programm ausführen so werden die Datensätze wie folgt ausgegeben:

(1, 'Sabine Bauer')
(15, 'Erika Meier')
(80, 'Moritz Mueller')
(100, 'Jochen Braun')
(100, 'Max Mustermann')

Wir sehen also unsere beiden Simulanten werden laut unserer Priority Queue ganz zum Schluß behandelt.

 

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.