Assoziative Arrays

Inhalt

5. Assoziative Arrays#

Beispiel 1: Stell dir vor, du wolltest eine Vokabeltrainer-App entwickeln. Wer damit lernt, muss zu einer deutschen Vokabel die englische Übersetzung nennen. Das Programm überprüft dann die Antwort. Klar ist: Wir brauchen dazu eine Datenstruktur, die uns ermöglicht schnell zu überprüfen, ob die englische Benutzereingabe zur deutschen Vokabel passt.

Beispiel 2: In einem altmodischen Telefonbuch wurde jedem Namen eine Telefonnummer zugeordnet. Das nutzt heute (fast) niemand mehr, aber deine Kontaktliste im Smartphone speichert ebenfalls eine solche Zuordnung: Wenn du “Heini” eintippst, ist diesem String eine Telefonummer (und meist noch viele andere Informationen über deinen Kumpel Heini) zugeordnet. Auch hierfür ist es entscheidend, dass der dem Schlüssel “Heini” zugeordnete Wert (z.B. 0172-1234567) blitzschnell gefunden werden kann.

Übung 1: Überlege, mit welcher bereits bekannten Datenstruktur du ein Wörterbuch implementieren würdest:

Python-Liste
Verkettete Liste
Stack
Warteschlange

Antwort anzeigen

Ein Wörterbuch enthält 1. sehr viele Einträge und muss 2. sehr schnell auf jeden einzelnen zugreifen können. Wegen 2. würde sich ein Array anbieten, denn dies ist die einzige Datenstruktur, die einen direkten Zugriff (d.h. in konstanter Zeit unabhängig von der Größe des Arrays) auf jedes Element erlaubt. Allerdings funktioniert das nicht, weil man nicht genau weiß, wo im Array ein bestimmtes Wort gespeichert ist.

Möglich wäre eine alphabetisch sortierte Liste, die dann mithilfe der binären Suche recht schnell durchsucht werden kann. Eine äquivalente Lösung wäre die Verwendung eines binären Suchbaums, der genauso schnell durchsucht werden kann.

Beide Lösungen sind möglich (in Java gibt es z.B. die Klasse TreeMap), aber sie erfordern, dass man die Liste immer sortiert hält bzw. den Suchbaum immer balanciert.

5.1. Assoziative Arrays in Python: Dictionaries#

In einer Liste wird immer einer Position ein Wert zugeordnet, z.B.: namen[17] = "Bibi", d.h. an der Position 17 wird der Wert “Bibi” gespeichert. In einer zweiten Liste für Telefonnummern kann man dann z.B. telefonnummern[17] = "0711-1234" zuordnene, d.h. an der Position 17 wird der Wert “0711-1234” gespeichert.

Das ist oft aber nur eine umständliche Behelfslösung für das, was man eigentlich benötigt. Denn wenn man z.B. die Telefonummer von “Heinz” sucht, muss man erst die Position von “Heinz” in der Liste namen suchen und dann an der gleichen Position in der Liste telefonnummern nachsehen. Das ist umständlich und fehleranfällig!

In einem Dictionary wird jedem Schlüssel ein Wert zugeordnet.

telefonbuch["Heinz"] = "0711-1234"

bedeutet, das für den Schlüssel “Heinz” der Wert “0711-1234” gespeichert wird.

Will man die Telefonnummer von “Heinz” in einem Dictionary suchen, so fragt man einfach nach dem Wert, der dem Schlüssel “Heinz” zugeordnet ist, sozusagen dem Wert an der Position “Heinz”:

tel_heinz = telefonbuch["Heinz"]

Das ist einfacher, weniger fehleranfällig und - mit der richtigen Implementierung - sogar viel schneller!

Wie du siehst, ist die Syntax für das Schreiben und Lesen in einem Dictionary ist fast die gleiche wie bei einer Liste:

telefonbuch = dict()   # leeres Dictionary anlegen
telefonbuch = {}       # Alternative Schreibweise, legt ebenfalls ein leeres Dictionary an

# Man kann beim Erstellen des Dictionarys auch schon Einträge anlegen:
telefonbuch = {"Bibi": "0761-1234", "Tina": "0721-5678"}   # Dictionary mit Einträgen anlegen

telefonbuch["Amadeus"] = "0761-9999"  # Dem Schlüssel "Amadeus" wird der Wert "0761-9999" zugeordnet

# Das Telefonbuch enthält jetzt drei Schlüssel-Wert-Paare:
# "Bibi" -> "0761-1234"
# "Tina" -> "0721-5678"
# "Amadeus" -> "0761-9999"
print("Das Telefonbuch mit 3 Einträgen:", telefonbuch)

# Wir können über die Schlüssel auf die Werte zugreifen:
tinas_nummer = telefonbuch["Tina"]   # Der Wert zum Schlüssel "Tina" wird ausgelesen und in einer Variablen gespeichert
print("Tinas Nummer:", tinas_nummer) # Der Wert wird ausgegeben
print("Amadeus' Nummer:", telefonbuch["Amadeus"])        # Der Wert zum Schlüssel "Amadeus" wird ausgegeben

# Ein Schlüssel-Wert-Paar kann überschrieben werden:
print("Bibi bekommt eine neue Nummer. Bisherige Nummer:", telefonbuch["Bibi"])
telefonbuch["Bibi"] = "0761-9999"   # Der Wert zum Schlüssel "Bibi" wird überschrieben
print("Bibis neue Nummer:", telefonbuch["Bibi"])

# Prüfen, ob ein Schlüssel im Dictionary vorhanden ist mit dem Schlüsselwort "in":
if "Bibi" in telefonbuch:
    print("Bibis Nummer:", telefonbuch["Bibi"])

# Wir testen das mal mit einem Schlüssel, der nicht im Telefonbuch steht:
if "Karla" in telefonbuch:
    print("Karlas Nummer:", telefonbuch["Karla"])
else:
    print("Karla ist nicht im Telefonbuch")

# Löschen eines Schlüssel-Wert-Paares:
del telefonbuch["Bibi"]
print("Das Telefonbuch, nachdem Bibi gelöscht wurde:", telefonbuch)

# Mit der Methode get kannst du einen Wert zu einem Schlüssel auslesen. Wenn der Schlüssel nicht existiert, wird ein Standardwert zurückgegeben:   
# Bsp.: Weil Karla nicht im Telefonbuch steht, wird "Kein Eintrag vorhanden" ausgegeben:
print(telefonbuch.get("Karla", "Kein Eintrag für Karla vorhanden"))

# keys() gibt eine Liste aller Schlüssel zurück, values() eine Liste aller Werte.
# Über diese Listen kannst du dann mit einer Schleife iterieren:
for name in telefonbuch.keys():
    print("Name:", name, "Nummer:", telefonbuch[name])
for nummer in telefonbuch.values():
    print("Nummer:", nummer)
# Tipp: Wenn man einfach nur schreibt...
for name in telefonbuch:
    print("Name:", name, "Nummer:", telefonbuch[name])
# ...wird automatisch über die Schlüssel iteriert, d.h. wie mit keys().

Das Telefonbuch mit 3 Einträgen: {'Bibi': '0761-1234', 'Tina': '0721-5678', 'Amadeus': '0761-9999'}
Tinas Nummer: 0721-5678
Amadeus' Nummer: 0761-9999
Bibi bekommt eine neue Nummer. Bisherige Nummer: 0761-1234
Bibis neue Nummer: 0761-9999
Bibis Nummer: 0761-9999
Karla ist nicht im Telefonbuch
Das Telefonbuch, nachdem Bibi gelöscht wurde: {'Tina': '0721-5678', 'Amadeus': '0761-9999'}
Kein Eintrag für Karla vorhanden
Schlüssel im Telefonbuch: dict_keys(['Tina', 'Amadeus'])

5.2. Beispiel: Mini-Vokabeltrainer#

Führe die folgende Zelle mehrfach aus. Jedesmal wird eine zufällige Vokabel abgefragt.

Schaue dir nun den Code gründlich an, bis du verstehst, wie das Programm arbeitet.

# Mini-Vokabeltrainer
from random import choice

deutsch2englisch = {"Hund": "dog", "Katze": "cat", "Maus": "mouse", "Schwein": "pig", "Huhn": "chicken", "Pferd": "horse"}
deutsche_vokabeln = list(deutsch2englisch.keys())  # keys() liefert alle im Dictionary gespeicherten Schlüssel
deutsches_wort = choice(deutsche_vokabeln)

eingabe = input(f"Wie lautet das englische Wort für {deutsches_wort}? ")
richtige_antwort = deutsch2englisch[deutsches_wort]   # Beim Schlüssel deutsches_wort gespeicherten Wert abfragen

if eingabe == richtige_antwort:
    print("Well done! Your knowledge is impressive!")
else:
    print(f"Sorry, the correct answer is {richtige_antwort}.")

5.3. Übungen zu Dictionaries#

5.3.1. Aufgabe: Artikel und Preise#

Unten siehst du ein Dictionary, das Produkte (als Schlüssel) und deren Preise (als Werte) enthält.

a) Schreibe eine Funktion preis_fuer, die als Parameter einen Produktnamen übergeben bekommt und den Preis des Produkts zurückgibt. Falls das Produkt nicht im Dictionary ist, soll eine Fehlermeldung angezeigt werden.

b) Wenn ein Artikelname unbekannt ist, soll einfach 0.0 zurückegeliefert werden. (Es gibt mehrere Möglichkeiten, das zu erreichen. Schaue dir die Code-Beispiele zum Telefonbuch weiter oben an.)

c) Angenommen, Gurken würden, genau wie Äpfel, 0,50 Euro kosten. Ist das ein Problem? Falls ja, welche Fehlermeldung erwartest du?

preis_dict = {
    "Apfel": 0.5,
    "Banane": 0.3,
    "Kirschen": 1.2,
    "Pfirsich": 0.8,
    "Gurke": 0.6,
    "Erdbeeren": 2.5
}

def preis_fuer(artikel: str) -> float:
    ...  # Hier fehlt dein Code!

# Teste deine Funktion mit diesen Beispielen:
print(preis_fuer("Banane"))  # Sollte 0.3 ausgeben
print(preis_fuer("Kirschen"))  # Sollte 1.2 ausgeben
print(preis_fuer("Erdbeeren"))  # Sollte 2.5 ausgeben

5.3.2. Aufgabe: Häufigkeit von Buchstaben zählen#

Schreibe ein Programm, das einen String liest und daraus ein Dictionary erstellt, das die Häufigkeit jedes Buchstabens im Satz zählt.

Tipp, falls du nicht weiterkommst:

Du musst unterscheiden, ob du einen Buchstaben das erste Mal siehst oder er schon früher vorkam.

satz = "ChatGPT tut sich sehr schwer damit, den Buchstaben 'r' in Wörtern zu zählen."

buchstaben = dict()   # leeres Dictionary anlegen

# Hier fehlt dein Code!

# Test: Wie oft kommt der Buchstabe 'r' im Satz vor? 
print(buchstaben["r"])   # Ergebnis sollte 5 sein

Lösung:

5.3.3. Aufgaben: Kontodaten#

Für eine Banking-App hast du die Klasse Konto entwickelt (s. unten). Da du damit rechnest, bald Millionen von Kunden zu betreuen, muss deine App blitzschnell von der Kontonummer auf alle Kontendaten zugreifen können.

a) Ergänze den untenstehenden Code entsprechend.

b) Ein Kunde kann mehrere Konten besitzen. Wie würdest du vorgehen, um über den Namen des Kunden auf alle seine Konten zugreifen zu können.

class Konto:
    def __init__(self, kontonummer: int, vorname: str, nachname: str, kontostand: float):
        self.kontonummer = kontonummer
        self.vorname = vorname
        self.nachname = nachname
        self.kontostand = kontostand

# Mehrere Konten anlegen
konten = [Konto(123456, "Max", "Mustermann", 1000.0), 
          Konto(789012, "Erika", "Musterfrau", 2000.0), 
          Konto(345678, "Moritz", "Musterkind", 3000.0),
          Konto(901234, "Eva", "Musterfrau", 4000.0)]

# AUFGABE: Erweitere das Programm so, dass man über die Kontonummer auf ein Konto zugreifen kann.

konten_dict = dict()  # leeres Dictionary anlegen

# Hier fehlt dein Code!


# Test: Kontostand von Konto mit Kontonummer 789012 ausgeben
# Erwartetes Ergebnis: 2000.0

      # Ergänze den Testcode hier selbst

2000.0

Lösung:

5.3.4. Aufgabe: Mini-Vokabeltrainer reloaded#

Weiter oben hast du (hoffentlich!) den Code des Vokabeltrainers genau studiert. Programmiere ihn jetzt nach - natürlich möglichst ohne nochmal nachzuschauen.

# Deine Version des Vokabeltrainers

...

5.4. Wie arbeiten Dictionaries intern?#

Gute Frage - schön, dass du dich dafür interessierst… Leider haben wir in diesem Schuljahr nicht genügend Zeit, um uns das genauer anzuschauen 😿

Aber keine Sorge: Im Abi kommt das Thema auch nicht dran, so dass wir es hier guten Gewissens weglassen können!