Dictionaries [KSR Wiki]

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
## Dictionaries

### Problem

Um mehrere Listen zu verknüpfen, müssen wir jeweils den passenden Eintrag in einer Liste in der anderen suchen. Beispielsweise möchten wir die Postleitzahl zu den Schweizer Gemeinden finden, nur leider sind die Postleitzahlen in einer anderen Datei gespeichert (`plz.csv`). Wenn wir jedes Mal die ganze Liste durchsuchen müssen, dauert dies ziemlich lange. Geht das auch schneller?

Wie wir wissen, können wir in einem (sortierten) Wörterbuch (Diktionär) effizient suchen:
  * Der Suchbereich wird fortlaufend halbiert (s.a. Binäre Suche in [[gf_informatik:suchen_und_sortieren_2023]])
  * Bei $n$ Einträgen benötigt die Suche nach einem Element nur $log_2(n)$ Zugriffe, also
    * $10$ Zugriffe für $1024$ Elemente,
    * $20$ Zugriffe für $1024\cdot1024 \approx 1Mio$,
    * $30$ Zugriffe für $1024\cdot1024\cdot1024 \approx 1Mia$


### Syntax

Es wäre schön, hätten wir eine Datenstruktur, die das für uns erledigt... zum Glück gibt es sie: **Dictionary** (oft *dict* abgekürzt).
    * Ein Dictionary stellt eine Sammlung von `Schlüssel : Wert` Paaren dar (oder `key : value`).
    * Erlaubt direkten Zugriff auf jedes Element mit dem gewünschten *Schlüssel*.
    * Jeder Schlüssel kann nur einmal vorkommen, Werte hingegen können mehrfach enthalten sein.
    * In Wirklichkeit benützen Dictionaries nicht binäre Suche, sondern eine noch schnellere Zugriffsart: [[wpde>Hashtabelle]].

Ein leeres Dictionary wird mit geschweiften Klammern erzeugt:
<code python>
zip_codes = {}
</code>
Alternativ können auch bereits Einträge von der Form `key : value` eingetragen werden:
<code python>
zip_codes = { 'Romanshorn' : 8590, 'Egnach' : 9322 }
</code>

Auf ein bestimmtes Element kann über *eckige* Klammern und den Schlüssel (*key*) zugegriffen werden. Die Syntax ist die gleiche wie beim Listenzugriff, nur verwenden wir statt dem *Index* den *Schlüssel*.
<code python>
plz = zip_codes['Romanshorn']
print(plz)
</code>

  8590

Ein neues Element kann mit derselben Syntax angelegt werden - ist der Schlüssel bereits vorhanden, wird der Wert überschrieben:
<code python>
zip_codes['Amriswil'] = 8580    # Legt ein neues Key-Value-Pair an.
zip_codes['Romanshorn'] = 8591  # Überschreibt den bestehenden Eintrag für Romanshorn
print(zip_codes)
</code>

  {'Romanshorn': 8591, 'Egnach': 9322, 'Amriswil': 8580}

Mit dem `in` Schlüsselwort kann herausgefunden werden, ob ein Schlüssel im Dictionary vorhanden ist:
<code python>
print('Romanshorn' in zip_codes)
</code>

  True

<code python>
print('St. Gallen' in zip_codes)
</code>

  False

Wir können eine `for`-Schleife über die Keys in einem Dictionary schreiben:
<code python>
for town in zip_codes:
    print(town)
</code>

  Romanshorn
  Egnach
  Amriswil

Möchten wir in der Schleife sowohl Key als auch Value haben, verwenden wir die `items()` Funktion:
<code python>
for town, plz in zip_codes.items():
    print(plz, town)
</code>

  8591 Romanshorn
  9322 Egnach
  8580 Amriswil

### Aufgabe 1: Dictionary Syntax

Schreibe Code wie die obigen Beispiele, um eine Sammlung von Postleitzahlen anzulegen.

Wie müsste man vorgehen, wenn wir sowohl ein Dictionary von Ortsnamen zu Postleitzahlen als auch umgekehrt von Postleitzahlen zu Ortsnamen haben möchten?

++++Antwort:|
Wir benötigen dafür zwei separate Dictionaries.
++++

### Aufgabe 2: CSV in ein Dictionary einlesen

Lies die Datei [[https://kantonsschuleromanshorn.sharepoint.com/:f:/s/FSInformatik/Ek-Hi_stH2RMjDa-wQN9jekBMeF_YD6rvhmibDlNglGWxw?e=Y3AX65|plz.csv]] ein und erstelle daraus ein Dictionary von Ortsnamen zu Postleitzahl.

Die Daten sehen so aus:
<code csv>
PLZ,Ort,Kanton
1000,Lausanne,Waadt
1005,Lausanne,Waadt
1008,Prilly,Waadt
1009,Pully,Waadt
...
</code>

Hinweise:
  * Die PLZ steht zuerst, also an `values[0]`
  * Der Ort ist an zweiter Stelle, also `values[1]`
  * Wir wollen ein **umgekehrtes** Dictionary von Ortsnamen zu PLZ. 
  * Ein Ortsnamen kann mehrere Postleitzahlen haben - wir möchten immer die kleinste behalten (also `1000` für Lausanne, nicht `1005`).

<nodisp 1>
++++Code|
<code python>
def load_zip_codes():
    zip_codes = {}
    with open('plz.csv', 'r') as infile:
        for line in infile:
            values = line.split(',')
            try:
                plz = int(values[0])
                town = values[1]
                if not town in zip_codes:
                    zip_codes[town] = plz
            except ValueError:
                pass
    return zip_codes
</code>
++++
</nodisp>


### Aufgabe 3: Zwei Datasets kombinieren

Kombiniere die Daten zu den Schweizer Gemeinden (aus [[gf_informatik:daten:processing#aufgabe_6|Data Processing A6]]) mit den Postleitzahl-Daten: Was ist PLZ der kleinsten Schweizer Gemeinde? Der flächenmässig grössten Gemeinde?

++++Antwort:|
  * 4535 Kammersrohr 32 Einwohner
  * 7550 Scuol 438.76 km²
++++

<nodisp 1>
++++Lösung:|
<code python>
smallest_town, smallest_pop = find_smallest_population()
largest_town, largest_area = find_largest_area()
zip_codes = load_zip_codes()
print(zip_codes[smallest_town], smallest_town, smallest_pop, "Einwohner")
print(zip_codes[largest_town], largest_town, largest_area, "km²")</code>
++++
</nodisp>

### Mehr zu Dictionaries

Du willst mehr über Dictionaries wissen und selber eines programmieren? [[dictionaries_tutorial|Schau hier]]!

### Nächstes Kapitel

Weiter mit [[gf_informatik:daten:processing:maps]].