Dictionaries und Sets

Dictionaries

Liste (und Tuple) sind die wichtigsten Datenstrukturen für die Sammlung von gleichartigen Daten. Solche Sammlungen bezeichnet man auch nach dem englischen Begriff als Collections. Bei Listen dient eine Zahl (der Index), also die Position in der Liste, als Schlüssel, um auf die Daten zuzugreifen.

Es gibt eine Reihe von Problemen, bei denen sich eine Zahl als Schlüssel für das Wiederfinden der Daten nicht anbietet. Ein typisches Beispiel ist ein Wörterbuch, bei dem ein Wort als Schlüssel für den Zugriff auf die entsprechende Übersetzung dient, so wird man z. B. unter dem Schlüssel "go" die deutschen Begriffe "gehen", "fahren", "laufen" etc. finden. Ein solches Wörterbuch kann man nur schlecht mit Listen abbilden, insbesondere, wenn man die Einträge schnell finden möchte und nicht die ganze Liste durchsuchen will.

Das folgende Beispiel zeigt, wie kompliziert es wird, ein Wörterbuch mithilfe von Listen aufzubauen. Besonders störend ist die lineare Suche in der Liste (for entry in dictionary:), deren Laufzeit mit der Anzahl der gespeicherten Wörter linear zunimmt.

woerterbuch = [ ["go", [ "gehen", "fahren", "laufen" ] ],
                ["fly", [ "fliegen" ] ]
              ]

def search(dictionary, word):
    for entry in dictionary:
        if entry[0] == word:
            print(entry[1])

search(woerterbuch, "go")  # -> ['gehen', 'fahren', 'laufen']
search(woerterbuch, "fly") # -> ['fliegen']

Deswegen gibt es in allen modernen Programmiersprachen eine weitere Art von Collection, die speziell für die Speicherung unter einem nicht-numerischen Schlüssel konstruiert sind.

• Dictionaries (Wörterbücher) sind Sammlungen von Name-Wert-Paaren
• Andere Bezeichnungen
• assoziatives Array
• Hash
• Map
• Ein Wert wird mit einem Namen als Schlüssel abgelegt
• Der Name kann ein beliebiger Datentyp sein

d = {}
d['go'] = 'gehen'
d['fly'] = 'fliegen'
print(d['go']) # -> gehen

Anders als in einer Liste, werden die Elemente in einem Dictionary nicht über einen Index, sondern über einen Schlüssel (Key) adressiert. D. h. im Dictionary sind genaugenommen nicht einzelne Werte, sondern Key/Value-Paare abgelegt.

Man fügt ein neues Element, ähnlich wie bei den Listen, durch Angabe des Schlüssels in eckigen Klammern ein (d['go'] = 'gehen'). Analog liest man einen Wert aus dem Dictionary aus, indem man den Schlüssel in eckigen Klammern verwendet (d['go'])

Beachten Sie, dass auch Zahlen als Key in einem Dictionary verwendet werden können.

d = {}
d[1] = 'hallo'
d[3] = 'du'
print(d[1]) # -> hallo

Anders als bei einer Liste müssen diese numerischen Schlüssel nicht fortlaufend sein.

Während eine Liste durch eckige Klammern ([1, 2, 3]) und ein Tuple durch runde ((1, 2, 3)) gekennzeichnet wird, verwendet man beim Dictionary geschweifte Klammern ({'go': 'gehen'}), um es direkt im Quelltext anzulegen.

• Ein Literal gibt einen Wert direkt im Quelltext an, ohne ihn zu berechnen
• Dictionaries können über ein Literal auch direkt beschrieben werden

d1 = { 'go': 'gehen', 'fly': 'fliegen' }
d2 = { 1: 'eins', 2: 'zwei', 3: 'drei' }

d1['go'] # -> 'gehen'
d2[2] # -> 'zwei'

Allgemein ist die Syntax für Dictionary-Literale: { key1: value1, key2, value2, ... }. Der Schlüssel wird vom Wert durch einen Doppelpunkt (:) getrennt.

Der Zugriff auf die Elemente eines Dictionaries erfolgt über den jeweiligen Schlüssel. Damit stellt sich die Frage, welche Datentypen als Schlüssel in einem Dictionary zulässig sind.

• Der Schlüssel muss unveränderlich sein
• Jeder Schlüssel ist eindeutig
  ⇒ neue Werte mit demselben Schlüssel ersetzen die alten

d = {}
d['go'] = 'gehen'
d['fly'] = 'fliegen'
d['fly'] = 'Fliege' # ersetzt 'fliegen'
print(d) # {'go': 'gehen', 'fly': 'Fliege'}

Obwohl in Python häufig Strings als Schlüssel verwendet werden, kann jedes beliebige Objekt als Schlüssel in einem Dictionary verwendet werden. Generell sollte man aber – in allen Programmiersprache – als Schlüssel nur Objekte verwenden, die nicht verändert werden können, da es andernfalls vorkommen kann, dass das Objekt nicht wieder gefunden wird.

Wichtige Funktionen

Es gibt eine Reihe von Methoden und Funktionen für den Umgang mit Dictionaries.

• len(dict) Anzahl der gespeicherten Werte
• key in dict testet, ob ein Schlüssel vorhanden ist
• dict.key() liefert alle Schlüssel
• dict.values() liefert alle Werte
• dict.items() liefert eine Liste mit den Schlüssel-Wert-Paaren

d = {}
d['go'] = 'gehen'
d['fly'] = 'fliegen'
'go' in d # -> True
'gehen' in d # -> False
list(d.keys()) # -> ['go', 'fly']
list(d.values()) # -> ['gehen', 'fliegen']

Wenn man über ein Dictionary iterieren möchte, dann wäre der naive Weg, dies über die key-Methode zu machen:

d = { 'go': 'gehen', 'fly': 'fliegen' }
for key in d.keys():
    e = d[key]
    print(e)

gehen
fliegen

Dieser Weg ist aber nicht elegant, weil man einen unnötigen Zugriff über den Key erzeugt. Deswegen sollte man zum Iterieren über ein Dictionary die items()-Methode verwenden.

• Mit der for-Schleife kann man über ein Dictionary iterieren
• Man sollte die items()-Methode verwenden

d = { 'go': 'gehen', 'fly': 'fliegen', 'sleep': 'schlafen' }

for key, value in d.items():
    print(key, '->', value)

go -> gehen
fly -> fliegen
sleep -> schlafen

Sets

Die letzte Collection in Python wird durch Sets realisiert. Sie dienen dazu, Mengen von Objekten oder Werten abzubilden. Wie in einer mathematischen Menge auch, kann in einem Set jeder Wert nur ein mal enthalten sein, es sind keine Duplikate erlaubt.

Man kann Sets in Python entweder über {} als Literal angeben oder sie über die Funktion set aus einer Liste oder einer anderen Collection erzeugen.

# Set als Literal
s = { 1, 3, 2}
print(s) # -> {1, 2, 3}

# Set aus Liste
s = set([ 1, 2, 3, 1, 2 ])
print(s) # -> {1, 2, 3}

# Set aus Dictionary
s = set({'go': 'gehen', 'fly': 'fliegen' })
print(s) # -> {'fly', 'go'}

# Set aus Range
s = set(range(1, 5))
print(s) # -> {1, 2, 3, 4}

Sets entsprechen mathematischen Mengen

• Jedes Element kann nur einmal enthalten sein
  (→ Keys von Dictionaries)
• Reihenfolge der Elemente wird nicht erhalten

s = set(['a', 'b', 'c', 'a', 'c', 'd', 'b'])
print(s) # -> {'b', 'd', 'c', 'a'}

Will man ein leeres Set anlegen, dann kann dies nicht über {} erfolgen, weil dieses Literal eine leeres Dictionary erzeugt.

s = {}
print(type(s)) # -> <class 'dict'>

Deswegen muss man in diesem Fall die set()-Funktion verwenden.

s = set()
print(type(s)) # -> <class 'set'>

Wichtig für die Arbeit mit Sets ist, dass die Werte keine Ordnung haben. Ordnung bedeutet in diesem Zusammenhang, dass die Elemente innerhalb der Collection in einer festen Reihenfolge abgelegt sind, die sich aus der Reihenfolge des Einfügens ergibt. Wenn eine Ordnung vorhanden ist, kann man den gespeicherten Objekten stabile Indices zuordnen, jedes Objekt bekommt einen Index, der über die Zeit stabil bleibt. Hält die Collection keine Ordnung, können die Elemente nicht indiziert werden und bei aufeinanderfolgenden Iterationen können die Objekte in unterschiedlicher Sequenz ausgegeben werden. Insbesondere kommen die Elemente in einer anderen Reihenfolge heraus, als man sie hineingesteckt hat.

• Iteration über Sets efolgt mit for-Schleife

s = { 'A', 'B', 'C', 'D'}

for e in s:
    print(e) # -> D A B C

Wichtige Funktionen

Es gibt eine Reihe von Methoden und Funktionen für den Umgang mit Sets.

• len(s) Anzahl der gespeicherten Werte
• key in s testet, ob ein Schlüssel vorhanden ist
• s.add(x) fügt Element x hinzu
• s.update(list) fügt mehrere Elemente aus der Liste list hinzu
• s.discard(x) entfernt das Element x
• s.remove(x) entfernt das Element x
  gibt Fehler, wenn es nicht vorhanden war
• s.pop() liefert ein zufälliges Element aus dem Set und entfernt es
• s.clear() löscht das Set

s = { 'A', 'B', 'C', 'D'}
print('E' in s) # -> False

s.add('E')
print(s) # -> {'A', 'C', 'B', 'E', 'D'}

s.update([ 'F', 'G', 'H' ])
print(s) # -> {'H', 'A', 'F', 'C', 'G', 'B', 'E', 'D'}

s.discard('H')
print(s) # -> {'A', 'F', 'C', 'G', 'B', 'E', 'D'}

s.remove('H') # KeyError 'H'

e = s.pop()
print(e) # -> A
print(s) # -> {'F', 'C', 'G', 'B', 'E', 'D'}

s.clear()
print(s) # -> set()

Bei einem leeren Set wird set() und nicht {} ausgegeben, damit es nicht zu Verwechselungen mit einem Leeren Dictionary kommt.

Mengenoperationen

• s1.union(s2) Vereinigungsmenge
• s1.intersection(s2) Schnittmenge
• s1.difference(s2) Differenzmenge
• s1.symmetric_difference(s2) Symmetrische Differenz

a = { 'A', 'B', 'C', 'D' }
b = { 'C', 'D', 'E', 'F' }

print(a.union(b)) # -> {'A', 'F', 'C', 'B', 'E', 'D'}
print(a.intersection(b)) # -> {'D', 'C'}
print(a.difference(b)) # -> {'A', 'B'}
print(a.symmetric_difference(b)) # -> {'F', 'B', 'E', 'A'}

Anstatt der hier genannten Methoden kann man auch spezielle Operatoren auf Sets anwenden:

• s1 | s2 Vereinigungsmenge
• s1 & s2 Schnittmenge
• s1 - s2 Differenzmenge
• s1 ^ s2 Symmetrische Differenz

a = { 'A', 'B', 'C', 'D' }
b = { 'C', 'D', 'E', 'F' }

print(a | b) # -> {'A', 'F', 'C', 'B', 'E', 'D'}
print(a & b) # -> {'D', 'C'}
print(a - b) # -> {'A', 'B'}
print(a ^ b) # -> {'F', 'B', 'E', 'A'}

Dass man Operatoren, die normalerweise für Zahlen benutzt auch für Sets anwenden kann, wird durch ein Sprachfeature ermöglicht, das man als operator overloading bezeichnet.

Es gibt auch die Methoden isdisjoint(), issubset() und issuperset(), um zwei Sets miteinander zu vergleichen.

Set Comprehension

• Sets können ähnlich wie Listen über Set Comprehensions erzeugt werden

s = { x for x in 'python rocks'  if x not in 'aeiou ' }

print(s)
# {'h', 's', 'y', 'n', 'p', 'r', 't', 'c', 'k'}