{
"cells": [
{
"cell_type": "markdown",
"id": "f161b54a-b628-40e3-85a4-c751a13d576d",
"metadata": {},
"source": [
"# Kapitel 10: Assoziative Datenfelder\n",
"[Chapter 10: Dictionaries](https://colab.research.google.com/github/AllenDowney/ThinkPython/blob/v3/chapters/chap10.ipynb)\n",
"\n",
"Dieses Kapitel behandelt einen weiteren eingebauten Datentyp, die sogenannten **assoziativen Datenfelder** (Englisch: *map, dictionary* oder *associative array*). Assoziative Datenfelder sind eines der besten Features von Python; sie sind die Bausteine vieler effizienter und eleganter Algorithmen. \n",
"\n",
"Wir werden assoziative Listen (Englisch: *dictionaries*) verwenden, um festzustellen, wie viele verschiedene Wörter ein Buch beinhaltet und um zu berechnen, wie oft diese Wörter jeweils vorkommen.\n",
"In den Übungen werden wir Wörterbücher nutzen, um Worträtsel zu lösen.\n",
"\n",
"### Ihre Lernziele:\n",
"\n",
"Beschreiben Sie in 2-3 Stichpunkten kurz was Sie im Seminar heute lernen wollen. Klicken Sie dazu doppelt auf diesen Text und bearbeiten Sie dann den Text:\n",
"\n",
"- \n",
"- \n",
"- \n",
"\n",
"\n",
"## Exkurs: Was mir an Python gefällt\n",
"\n",
"In dieser Rubrik, die immer am Anfang eines Kapitels steht, möchte ich Ihnen zeigen, wofür ich Python nutze und warum ich es mag. Sie werden vielleicht noch nicht verstehen, was ich genau mache, aber Sie sehen damit schon einmal die Möglichkeiten von Python und können später darauf zurückgreifen. Da dies auch ein Exkurs ist, können Sie diese Rubrik gerne auch erst einmal überspringen.\n",
"\n",
"Mit Hilfe von pydotplus ist es möglich, Graphen zu visualisieren, die auch direkt im Jupyter Notebook angezeigt werden können. Als Beispiel wird hier ein [Trie](https://de.wikipedia.org/wiki/Trie) erzeugt, der schnellen Zugriff auf die Präfixe einer Liste von Wörtern bildet (so etwas ermöglicht z.B. eine schnelle Wortvervollständigung bei der Eingabe von Wörtern auf der Handy-Tastatur ([siehe](https://towardsdatascience.com/implementing-a-trie-data-structure-in-python-in-less-than-100-lines-of-code-a877ea23c1a1))."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "06de232a-0b6c-40e9-9d1a-9bbbf74a8b3e",
"metadata": {},
"outputs": [],
"source": [
"!pip install pydotplus\n",
"from IPython.display import Image \n",
"import pydotplus\n",
"\n",
"# Der Quellcode für die Klasse `TrieNode` und die Funktion `add` stammt von der Webseite:\n",
"#https://towardsdatascience.com/implementing-a-trie-data-structure-in-python-in-less-than-100-lines-of-code-a877ea23c1a1\n",
"class TrieNode(object):\n",
" def __init__(self, char: str):\n",
" self.char = char\n",
" self.children = []\n",
" self.word = None\n",
" self.counter = 1\n",
"\n",
"def add(root, word):\n",
" node = root\n",
" for char in word:\n",
" found_in_child = False\n",
" # Search for the character in the children of the present `node`\n",
" for child in node.children:\n",
" if child.char == char:\n",
" # We found it, increase the counter by 1 to keep track that another\n",
" # word has it as well\n",
" child.counter += 1\n",
" # And point the node to the child that contains this char\n",
" node = child\n",
" found_in_child = True\n",
" break\n",
" # We did not find it so add a new chlid\n",
" if not found_in_child:\n",
" new_node = TrieNode(char)\n",
" node.children.append(new_node)\n",
" # And then point node to the new child\n",
" node = new_node\n",
" # Everything finished. Mark it as the end of a word.\n",
" node.word = word\n",
"\n",
"# fügt eine Liste von Wörtern hinzu\n",
"def add_words(root, words):\n",
" for word in words:\n",
" add(root, word)\n",
"\n",
"# wandelt den Baum in einen Graphen, also eine Menge von Knoten (vertices) und Kanten (edges) um\n",
"# Eingaben:\n",
"# - root: Wurzelknoten des Baums\n",
"# - vertices: (leere) Liste mit Knoten (jeder Knoten ist vom Typ TrieNode)\n",
"# - edges: (leere) Liste mit Kanten (jede Kante ist ein Tupel von ganzen Zahlen, die die Knoten-IDs repräsentieren)\n",
"def tree_to_graph(root, vertices, edges):\n",
" # Hinzufügen des Wurzelknotens\n",
" if len(vertices) == 0:\n",
" vertices.append(root)\n",
" # wir nummerieren die Knoten durch:\n",
" # jeder Knoten erhält als ID seine Position in der Liste (ab 1 zählend)\n",
" rootid = len(vertices)\n",
" # Hinzufügen der Kindknoten\n",
" for child in root.children:\n",
" vertices.append(child)\n",
" childid = len(vertices)\n",
" \n",
" # Kante zum Kindknoten hinzufügen\n",
" edges.append((rootid, childid))\n",
"\n",
" # Rekursion, falls Kindknoten vorhanden\n",
" if child.children:\n",
" tree_to_graph(child, vertices, edges)\n",
"\n",
"# erzeugt eine Zeichenkette in der Syntax for GraphViz (http://graphviz.org/)\n",
"def build_graph_string(vertices, edges):\n",
" # Konfiguration für Graph, Knoten und Kanten \n",
" s = \"\"\"\n",
"digraph G {\n",
" graph [rankdir=\"LR\"];\n",
" node [sep=\"+0.01,+0.01\", height=\"0\", width=\"0\", shape=\"box\", margin=\"0.05, 0.05\"];\n",
" edge [];\n",
" \"\"\"\n",
" # Hinzufügen der Knoten\n",
" for i, vertice in enumerate(vertices):\n",
" label = vertice.char\n",
" # Knoten, die ein Wort repräsentieren, sollen dieses zusätzlich enthalten\n",
" if vertice.word:\n",
" label += \" (\" + vertice.word + \")\"\n",
" s += ' ' + str(i + 1) + ' [label=\"' + label + '\"];\\n'\n",
" # Hinzufügen der Kanten\n",
" for v1, v2 in edges:\n",
" s += ' ' + str(v1) + ' -> ' + str(v2) + ';\\n'\n",
" s += \"}\"\n",
" return s\n",
" \n",
"\n",
"# Beispielwörter zum Visualisieren - ergänzen Sie die Liste oder probieren Sie andere Wörter\n",
"words = [\"Braten\", \"Brauerei\", \"Brause\", \"Brot\", \"Brett\", \n",
" \"Brei\", \"Brief\", \"Breite\", \"Brille\", \"Brand\", \"Bruder\", \n",
" \"Bruch\", \"Brust\", \"Bronze\", \"Brache\", \"Branche\", \n",
" \"Brandung\", \"Braten\", \"Bratsche\", \"Bremse\", \"Brenner\", \n",
" \"Brezel\", \"Brikett\", \"Brise\", \"Brocken\", \"Bronze\", \n",
" \"Brosche\", \"Brunnen\", \"Brut\"]\n",
"# Alternative: aus einer Datei einlesen\n",
"# words = []\n",
"# fin = open('top10000de.txt', encoding=\"latin1\")\n",
"# for line in fin:\n",
"# if line.startswith(\"Bra\"):\n",
"# words.append(line.strip())\n",
"\n",
"# Wörter zum Trie hinzufügen (in sortierter Reihenfolge, das liest sich leichter)\n",
"root = TrieNode('*')\n",
"add_words(root, sorted(words))\n",
"\n",
"# aus dem Trie einen Graph erzeugen\n",
"vertices = []\n",
"edges = []\n",
"tree_to_graph(root, vertices, edges)\n",
"\n",
"# die Zeichenkette für GraphViz erzeugen\n",
"graphdata = build_graph_string(vertices, edges)\n",
"\n",
"# den Graph zeichnen und anzeigen\n",
"graph = pydotplus.graph_from_dot_data(graphdata) \n",
"Image(graph.create_png())\n"
]
},
{
"cell_type": "markdown",
"id": "9a0b03e4-0e53-40b4-8850-5fa03078f99a",
"metadata": {},
"source": [
"## Herunterladen des unterstützenden Codes\n",
"Die folgende Zelle lädt eine Datei herunter und führt einen Code aus, der speziell für dieses Notebook verwendet wird. Sie müssen diesen Code nicht verstehen, aber Sie sollten die Zelle vor allen weiteren Zellen in diesem Notebook ausführen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e55de5cd",
"metadata": {
"id": "e55de5cd",
"tags": []
},
"outputs": [],
"source": [
"from os.path import basename, exists\n",
"\n",
"def download(url):\n",
" filename = basename(url)\n",
" if not exists(filename):\n",
" from urllib.request import urlretrieve\n",
"\n",
" local, _ = urlretrieve(url, filename)\n",
" print(\"Downloaded \" + str(local))\n",
" return filename\n",
"\n",
"download('https://github.com/AllenDowney/ThinkPython/raw/v3/thinkpython.py');\n",
"download('https://github.com/AllenDowney/ThinkPython/raw/v3/diagram.py');\n",
"\n",
"import thinkpython"
]
},
{
"cell_type": "markdown",
"id": "be7467bb",
"metadata": {
"id": "be7467bb"
},
"source": [
"## Ein assoziatives Datenfeld ist eine Abbildung\n",
"\n",
"Ein assoziatives Datenfeld ist wie eine Liste aber allgemeiner. In einer Liste müsse die Indexe ganze Zahlen sein, in einem assoziativen Datenfeld können sie von (fast) jedem Typ sein.\n",
"\n",
"Nehmen wir zum Beispiel an, wir erstellen folgendermaßen eine Liste mit Zahlenwörtern:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "20dd9f32",
"metadata": {
"id": "20dd9f32"
},
"outputs": [],
"source": [
"lst = ['null', 'eins', 'zwei']"
]
},
{
"cell_type": "markdown",
"id": "aa626f88",
"metadata": {
"id": "aa626f88"
},
"source": [
"Wir können eine ganze Zehl als Index verwenden, um das dazugehörige Wort zu erhalten:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9b6625c0",
"metadata": {
"id": "9b6625c0"
},
"outputs": [],
"source": [
"lst[1]"
]
},
{
"cell_type": "markdown",
"id": "c38e143b",
"metadata": {
"id": "c38e143b"
},
"source": [
"Aber nehmen wir einmal an, wir wollen das Ganze andersherum machen und stattdessen ein Wort eingeben, um die korrespondierende ganze Zahl zu bekommen.\n",
"Das können wir zwar nicht mit einer Liste, dafür aber mit einem assoziativen Datenfeld bewerkstelligen.\n",
"Wir beginnen damit, ein leeres assoziatives Datenfeld zu erstellen und es `zahlen` zuzuweisen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "138952d9",
"metadata": {
"id": "138952d9"
},
"outputs": [],
"source": [
"zahlen = {}\n",
"zahlen"
]
},
{
"cell_type": "markdown",
"id": "16fcaca0-50df-4da9-9fcb-f29e08844584",
"metadata": {},
"source": [
"Die geschweiften Klammern, `{}`, repräsentieren ein leeres assoziatives Datenfeld. Mit Hilfe von eckigen Klammern können wir Einträge hinzufügen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "007ef505",
"metadata": {
"id": "007ef505"
},
"outputs": [],
"source": [
"zahlen['null'] = 0"
]
},
{
"cell_type": "markdown",
"id": "1dbe12c3",
"metadata": {
"id": "1dbe12c3"
},
"source": [
"Diese Zuweisung fügt dem assoziativen Datenfeld ein **Element** (Englisch: *item*) hinzu, das die Verbindung zwischen einem **Schlüssel** (Englisch: *key*) und einem **Wert** (Englisch: *value*) darstellt.\n",
"In diesem Beispiel ist der Schlüssel die Zeichenkette `null` und der Wert ist die ganze Zahl `0`.\n",
"Wenn wir die assoziative Liste jetzt anzeigen sehen wir, dass sie ein Element enthält, das einen Schlüssel und einen Wert, getrennt durch einen Doppelpunkt, `:`, beinhaltet:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "753a8fbc",
"metadata": {
"id": "753a8fbc"
},
"outputs": [],
"source": [
"zahlen"
]
},
{
"cell_type": "markdown",
"id": "ad32c23d",
"metadata": {
"id": "ad32c23d"
},
"source": [
"Wir können so mehr Elemente hinzufügen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "835aac1e",
"metadata": {
"id": "835aac1e"
},
"outputs": [],
"source": [
"zahlen['eins'] = 1\n",
"zahlen['zwei'] = 2\n",
"zahlen"
]
},
{
"cell_type": "markdown",
"id": "278901e5",
"metadata": {
"id": "278901e5"
},
"source": [
"Jetzt enthält das assoziative Datenfeld drei Elemente.\n",
"\n",
"Um einen Schlüssel zu suchen und dessen korrespondierenden Wert zu erhalten, verwenden wir den Klammer-Operator:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c0475cee",
"metadata": {
"id": "c0475cee"
},
"outputs": [],
"source": [
"zahlen['zwei']"
]
},
{
"cell_type": "markdown",
"id": "df5724e6",
"metadata": {
"id": "df5724e6"
},
"source": [
"Wenn sich der Schlüssel nicht im assoziativen Datenfeld befindet, bekommen wir einen `KeyError`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "30c37eef",
"metadata": {
"id": "30c37eef",
"tags": []
},
"outputs": [],
"source": [
"%%expect KeyError\n",
"\n",
"zahlen['drei']"
]
},
{
"cell_type": "markdown",
"id": "4fe02bf1-5a4d-43ec-b03f-b3da561ef0ca",
"metadata": {},
"source": [
"Die Funktion `len` funktioniert auch mit assoziativen Datenfeldern; sie gibt die Anzahl der Schlüssel-Wert-Paare zurück:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1b4ea0c2",
"metadata": {
"id": "1b4ea0c2"
},
"outputs": [],
"source": [
"len(zahlen)"
]
},
{
"cell_type": "markdown",
"id": "58221e96",
"metadata": {
"id": "58221e96"
},
"source": [
"In mathematischer Sprache repräsentiert ein assoziatives Datenfeld eine **Zuordnung** (Englisch: *mapping*) von Schlüsseln zu Werten, man kann also sagen, dass jeder Schlüssel einem Wert **zugeordnet ist** (Englisch: *maps to*).\n",
"In diesem Beispiel ist jedes Zahlenwort der korrespondierenden ganzen Zahl zugeordnet.\n",
"\n",
"Die folgende Abbildung zeigt das Zustandsdiagramm für `Zahlen`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "eba36a24",
"metadata": {
"id": "eba36a24",
"tags": []
},
"outputs": [],
"source": [
"from diagram import make_dict, Binding, Value\n",
"\n",
"d1 = make_dict(zahlen, dy=-0.3, offsetx=0.37)\n",
"binding1 = Binding(Value('zahlen'), d1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9016bf4b",
"metadata": {
"id": "9016bf4b",
"tags": []
},
"outputs": [],
"source": [
"from diagram import diagram, adjust, Bbox\n",
"\n",
"width, height, x, y = [1.83, 1.24, 0.49, 0.85]\n",
"ax = diagram(width, height)\n",
"bbox = binding1.draw(ax, x, y)\n",
"# adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "b092aa61",
"metadata": {
"id": "b092aa61"
},
"source": [
"Assoziative Datenfelder werden durch Kästen dargestellt, die innen die Elemente enthalten und an denen außen das Wort `dict` steht.\n",
"Jedes Element wird durch einen Schlüssel und einen Pfeil, der auf einen Wert zeigt dargestellt.\n",
"Die Anführungszeichen weisen darauf hin, dass die Schlüssel hier keine Variablennamen, sondern Zeichenketten sind."
]
},
{
"cell_type": "markdown",
"id": "2a0a128a",
"metadata": {
"id": "2a0a128a"
},
"source": [
"## Assoziative Datenfelder erstellen\n",
"\n",
"Im vorherigen Abschnitt haben wir ein leeres assoziatives Datenfeld erstellt und nach und nach mit dem Klammer-Operator Elemente hinzugefügt.\n",
"Stattdessen hätten wir auch wie hier das gesamte assoziative Datenfeld auf einmal erstellen können:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "19dfeecb",
"metadata": {
"id": "19dfeecb"
},
"outputs": [],
"source": [
"zahlen = {'null': 0, 'eins': 1, 'zwei': 2}"
]
},
{
"cell_type": "markdown",
"id": "31ded5b2",
"metadata": {
"id": "31ded5b2"
},
"source": [
"Jedes Element besteht aus einem Schlüssel und einem Wert, getrennt durch einen Doppelpunkt.\n",
"Die Elemente selbst werden mit Kommata getrennt und in geschweifte Klammern eingeschlossen.\n",
"\n",
"Ein anderer Weg, ein assoziatives Datenfeld zu erstellen, ist, die `dict`-Funktion zu verwenden.\n",
"Wir können so ein leeres assoziatives Datenfeld so erstellen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "39b81034",
"metadata": {
"id": "39b81034"
},
"outputs": [],
"source": [
"leer = dict()\n",
"leer"
]
},
{
"cell_type": "markdown",
"id": "bfb215c9",
"metadata": {
"id": "bfb215c9"
},
"source": [
"Und wir können so eine Kopie eines assoziativen Datenfelds anfertigen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "88fa12c5",
"metadata": {
"id": "88fa12c5"
},
"outputs": [],
"source": [
"zahlen_kopie = dict(zahlen)\n",
"zahlen_kopie"
]
},
{
"cell_type": "markdown",
"id": "966c5539",
"metadata": {
"id": "966c5539"
},
"source": [
"Es ist oft sinnvoll, zuerst eine Kopie anzufertigen, bevor Operationen durchgeführt werden, die das assoziative Datenfeld verändern."
]
},
{
"cell_type": "markdown",
"id": "34d83f48-7e1e-4502-94e1-e6657327a651",
"metadata": {
"id": "2a948f62",
"tags": []
},
"source": [
"## Der `in`-Operator\n",
"\n",
"Der Operator `in` funktioniert ebenfalls mit assoziativen Datenfeldern; er sagt uns, ob etwas als *Schlüssel* in einem assoziativen Datenfeld enthalten ist:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "025cad92",
"metadata": {
"id": "025cad92"
},
"outputs": [],
"source": [
"'eins' in zahlen"
]
},
{
"cell_type": "markdown",
"id": "80f6b264",
"metadata": {
"id": "80f6b264"
},
"source": [
"Der `in`-Operator überprüft *nicht*, ob etwas als Wert auftaucht:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "65de12ab",
"metadata": {
"id": "65de12ab"
},
"outputs": [],
"source": [
"1 in zahlen"
]
},
{
"cell_type": "markdown",
"id": "00fe1dbc-51e7-461d-8af9-13a98e95ffc4",
"metadata": {},
"source": [
"Um zu sehen, ob etwas als Wert in einem assoziativen Datenfeld enthalten ist, können wir die Methode `values` verwenden, die uns eine Sammlung der Werte zurückgibt, und dann den Operator `in` verwenden: "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "87ddc1b2",
"metadata": {
"id": "87ddc1b2"
},
"outputs": [],
"source": [
"1 in zahlen.values()"
]
},
{
"cell_type": "markdown",
"id": "d787fd59-88c7-48de-aea5-ca3b5715137d",
"metadata": {},
"source": [
"Für assoziative Datenfelder nutzt Python eine Datenstruktur, die **Hash-Tabelle** (Englisch: *hash table*) genannt wird. Diese hat eine bemerkenswerte Eigenschaft: der Operator `in` benötigt ungefähr die gleiche Zeit, egal wie viele Einträge das assoziative Datenfeld enthält.\n",
"Das ermöglicht es uns, erstaunlich effiziente Algorithmen zu schreiben."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4849b563",
"metadata": {
"id": "4849b563",
"tags": []
},
"outputs": [],
"source": [
"download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');"
]
},
{
"cell_type": "markdown",
"id": "bba0522c",
"metadata": {
"id": "bba0522c"
},
"source": [
"Um das zu demonstrieren, werden wir zwei Algorithmen zum Finden von Wortpaaren, bei denen eines das andere rückwärts gelesen ergibt -- wie `stressed` und `desserts`-- vergleichen.\n",
"Wir beginnen damit, die Wortliste zu lesen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "830b1208",
"metadata": {
"id": "830b1208"
},
"outputs": [],
"source": [
"word_list = open('words.txt').read().split()\n",
"len(word_list)"
]
},
{
"cell_type": "markdown",
"id": "ab29fb8a",
"metadata": {
"id": "ab29fb8a"
},
"source": [
"Und hier ist `reverse_word` aus dem vorherigen Kapitel:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "49231201",
"metadata": {
"id": "49231201"
},
"outputs": [],
"source": [
"def reverse_word(word):\n",
" return ''.join(reversed(word))"
]
},
{
"cell_type": "markdown",
"id": "93f7ac1b",
"metadata": {
"id": "93f7ac1b"
},
"source": [
"Die folgende Funktion läuft in einer Schleife durch die Wörter der Liste.\n",
"Für jedes Wort dreht sie die Buchstaben um und überprüft, ob das umgedrehte Wort in der Wortliste enthalten ist:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a41759fb",
"metadata": {
"id": "a41759fb"
},
"outputs": [],
"source": [
"def too_slow():\n",
" count = 0\n",
" for word in word_list:\n",
" if reverse_word(word) in word_list:\n",
" count += 1\n",
" return count"
]
},
{
"cell_type": "markdown",
"id": "d4ebb84d",
"metadata": {
"id": "d4ebb84d"
},
"source": [
"Diese Funktion braucht über eine Minute um vollständig durchzulaufen.\n",
"Das Problem ist, dass der `in`-Operator am Anfang der Liste beginnt und jedes Wort einzeln überprüft.\n",
"Wenn er nicht findet, was er sucht -- was meistens der Fall ist -- muss er die Suche bis zum Ende der Liste fortsetzen. Falls die nächste Zelle Ihnen zu lange dauert, stoppen Sie diese gerne."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "33bcddf8",
"metadata": {
"id": "33bcddf8",
"tags": []
},
"outputs": [],
"source": [
"%time too_slow()"
]
},
{
"cell_type": "markdown",
"id": "2acb6c50",
"metadata": {
"id": "2acb6c50"
},
"source": [
"Außerdem befindet sich der `in`-Operator innerhalb der Schleife, deshalb läuft er für jedes Wort einmal durch.\n",
"Da in der Liste mehr als `100.000` Wörter stehen, und wir für jedes dieser Wörter mehr als `100.000` Wörter überprüfen, ist die Gesamtzahl der Vergleiche -- ungefähr -- die Anzahl der Wörter im Quadrat oder $O(n^2)$, also fast `13 Milliarden`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f2869dd0",
"metadata": {
"id": "f2869dd0"
},
"outputs": [],
"source": [
"len(word_list)**2"
]
},
{
"cell_type": "markdown",
"id": "5dbf01b7",
"metadata": {
"id": "5dbf01b7"
},
"source": [
"Mit einem assoziativen Datenfeld können wir diese Funktion wesentlich schneller machen.\n",
"Die folgende Schleife erstellt ein assoziatives Datenfeld, das die Wörter als Schlüssel enthält:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "300416d9",
"metadata": {
"id": "300416d9"
},
"outputs": [],
"source": [
"word_dict = {}\n",
"for word in word_list:\n",
" word_dict[word] = 1"
]
},
{
"cell_type": "markdown",
"id": "b7f6a1b7",
"metadata": {
"id": "b7f6a1b7"
},
"source": [
"Die Werte in `word_dict` sind alle `1`, sie könnten aber auch alles mögliche andere sein, da wir nie nach ihnen suchen werden -- wir werden dieses assoziative Datenfeld nur verwenden, um zu überprüfen, ob ein bestimmter Schlüssel existiert.\n",
"\n",
"Hier ist nun eine Version der vorherigen Funktion, die `word_list` durch `word_dict` ersetzt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9d3dfd8d",
"metadata": {
"id": "9d3dfd8d"
},
"outputs": [],
"source": [
"def much_faster():\n",
" count = 0\n",
" for word in word_dict:\n",
" if reverse_word(word) in word_dict:\n",
" count += 1\n",
" return count"
]
},
{
"cell_type": "markdown",
"id": "5f41e54c",
"metadata": {
"id": "5f41e54c"
},
"source": [
"Diese Funktion dauert weniger als ein Hundertstel einer Sekunde und ist damit etwa `10.000` Mal schneller als die vorherige Version:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "82b36568",
"metadata": {
"id": "82b36568",
"tags": []
},
"outputs": [],
"source": [
"%time much_faster()"
]
},
{
"cell_type": "markdown",
"id": "4cd91c99",
"metadata": {
"id": "4cd91c99"
},
"source": [
"Allgemein ist die Zeit, die es in Anspruch nimmt, ein Objekt in einer Liste zu finden, proportional zu der Länge dieser Liste.\n",
"Die Zeit, die benötigt wird um einen Schlüssel in einem assoziativen Datenfeld zu finden ist beinahe konstant -- unabhängig von der Anzahl der Elemente:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "aa079ed3",
"metadata": {
"id": "aa079ed3"
},
"outputs": [],
"source": [
"d = {'a': 1, 'b': 2}\n",
"d['a'] = 3\n",
"d"
]
},
{
"cell_type": "markdown",
"id": "b3bfa8a5",
"metadata": {
"id": "b3bfa8a5"
},
"source": [
"## Eine Sammlung von Zählern\n",
"\n",
"Nehmen wir an, wir erhalten eine Zeichenkette und sollen zählen, wie oft jeder einzelne Buchstabe darin vorkommt.\n",
"Ein assozaitives Datenfeld ist ein gutes Werkzeug für diese Aufgabe.\n",
"Wir beginnen mit einem leeren assoziativen Datenfeld:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7c21ff00",
"metadata": {
"id": "7c21ff00"
},
"outputs": [],
"source": [
"zaehler = {}"
]
},
{
"cell_type": "markdown",
"id": "34a9498a",
"metadata": {
"id": "34a9498a"
},
"source": [
"Nehmen wir nun an, wir gehen in einer Schleife durch die Buchstaben der Zeichenkette und sehen den Buchstaben `'a'` zum ersten Mal.\n",
"Wir können ihn folgendermaßen zum assoziativen Datenfeld hinzufügen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7d0afb00",
"metadata": {
"id": "7d0afb00"
},
"outputs": [],
"source": [
"zaehler['a'] = 1"
]
},
{
"cell_type": "markdown",
"id": "bca9fa11",
"metadata": {
"id": "bca9fa11"
},
"source": [
"Der Wert `1` zeigt an, dass wir den Buchstaben einmal gesehen haben.\n",
"Wenn wir den gleichen Buchstaben später noch einmal sehen, können wir so den Zähler inkrementieren:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ba97b5ea",
"metadata": {
"id": "ba97b5ea"
},
"outputs": [],
"source": [
"zaehler['a'] += 1"
]
},
{
"cell_type": "markdown",
"id": "274ea014",
"metadata": {
"id": "274ea014"
},
"source": [
"Jetzt ist der Wert, der mit `'a'` assoziiert ist `2`, weil wir den Buchstaben zweimal gesehen haben."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "30ffe9b4",
"metadata": {
"id": "30ffe9b4"
},
"outputs": [],
"source": [
"zaehler"
]
},
{
"cell_type": "markdown",
"id": "2ca8f99d",
"metadata": {
"id": "2ca8f99d"
},
"source": [
"Die folgende Funktion verwendet diese Features um zu zählen, wie oft jeder Buchstabe in einer Zeichenkette vorkommt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "36f95332",
"metadata": {
"id": "36f95332"
},
"outputs": [],
"source": [
"def wert_zaehlen(string):\n",
" zaehler = {}\n",
" for buchstabe in string:\n",
" if buchstabe not in zaehler:\n",
" zaehler[buchstabe] = 1\n",
" else:\n",
" zaehler[buchstabe] += 1\n",
" return zaehler"
]
},
{
"cell_type": "markdown",
"id": "735c758b",
"metadata": {
"id": "735c758b"
},
"source": [
"Bei jedem Schleifendurchlauf, bei dem `buchstabe` sich nicht im assoziativen Datenfeld befindet, erstellen wir ein neues Element mit dem Schlüssel `buchstabe` und dem Wert `1`.\n",
"\n",
"Wenn `buchstabe` sich schon im assoziativen Datenfeld befindet, inkrementieren wir den Wert, der mit `buchstabe` assoziiert ist.\n",
"\n",
"Hier ist ein Beispiel:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d6f1048e",
"metadata": {
"id": "d6f1048e"
},
"outputs": [],
"source": [
"zaehler = wert_zaehlen('brontosaurus')\n",
"zaehler"
]
},
{
"cell_type": "markdown",
"id": "8ac1fea4",
"metadata": {
"id": "8ac1fea4"
},
"source": [
"Die Elemente in `zaehler` zeigen, dass der Buchstabe `'b'` einmal vorkommt, `'r'` zweimal und so weiter."
]
},
{
"cell_type": "markdown",
"id": "54559337-6ae4-484f-ad81-a4b7059202c9",
"metadata": {},
"source": [
"### Schleifen und assoziative Datenfelder\n",
"\n",
"Wenn wir ein assoziatives Datenfeld in einer `for`-Schleife nutzen, durchlaufen wir alle Schlüssel des assoziativen Datenfeldes.\n",
"\n",
"Um das zu zeigen erstellen wir ein assoziatives Datenfeld, das die Buchstaben in `'banana'` zählt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "310e1489",
"metadata": {
"id": "310e1489"
},
"outputs": [],
"source": [
"zaehler = wert_zaehlen('banana')\n",
"zaehler"
]
},
{
"cell_type": "markdown",
"id": "fe263f3d",
"metadata": {
"id": "fe263f3d"
},
"source": [
"Die folgende Schleife gibt die Schlüssel aus, was hier die Buchstaben sind:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "da4ec7fd",
"metadata": {
"id": "da4ec7fd"
},
"outputs": [],
"source": [
"for schluessel in zaehler:\n",
" print(schluessel)"
]
},
{
"cell_type": "markdown",
"id": "bf1b7824",
"metadata": {
"id": "bf1b7824"
},
"source": [
"Um die Werte auszugeben können wir die `values` Methode verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "859fe1ad",
"metadata": {
"id": "859fe1ad"
},
"outputs": [],
"source": [
"for wert in zaehler.values():\n",
" print(wert)"
]
},
{
"cell_type": "markdown",
"id": "721135be",
"metadata": {
"id": "721135be"
},
"source": [
"Um die Schlüssel und Werte auszugeben, können wir in einer Schleife durch die Schlüssel gehen und die dazugehörigen Werte suchen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7242ab5b",
"metadata": {
"id": "7242ab5b"
},
"outputs": [],
"source": [
"for schluessel in zaehler:\n",
" wert = zaehler[schluessel]\n",
" print(schluessel, wert)"
]
},
{
"cell_type": "markdown",
"id": "efa1bce5",
"metadata": {
"id": "efa1bce5"
},
"source": [
"Im nächsten Kapitel werden wir eine etwas prägnantere Weise lernen, genau das Gleiche zu tun."
]
},
{
"cell_type": "markdown",
"id": "a160c0ef",
"metadata": {
"id": "a160c0ef"
},
"source": [
"### Listen und assoziative Datenfelder\n",
"\n",
"Listen können als Werte in einem assoziativen Datenfeld verwendet werden!\n",
"\n",
"Hier ist zum Beispiel ein assoziatives Datenfeld, das von de Zahl `4` auf eine Liste mit vier Buchstaben verweist:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "29cd8207",
"metadata": {
"id": "29cd8207"
},
"outputs": [],
"source": [
"d = {4: ['r', 'o', 'u', 's']}\n",
"d"
]
},
{
"cell_type": "markdown",
"id": "815a829f",
"metadata": {
"id": "815a829f"
},
"source": [
"Wir können eine Liste aber nicht als Schlüssel in einem assoziativen Datenfeld verwenden.\n",
"Folgendes passiert, wenn wir das versuchen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ca9ff511",
"metadata": {
"id": "ca9ff511",
"tags": []
},
"outputs": [],
"source": [
"%%expect TypeError\n",
"\n",
"buchstaben = list('abcd')\n",
"d[buchstaben] = 4"
]
},
{
"cell_type": "markdown",
"id": "2469b08a",
"metadata": {
"id": "2469b08a"
},
"source": [
"Ich habe vorhin schon erwähnt, dass assoziative Datenfelder Hash-Tabellen verwenden, weshalb die Schlüssel **hashbar** (Englisch: *hashable*) sein müssen.\n",
"\n",
"Ein **Hash** ist eine Funktion, die einen Wert (egal welcher Art) aufnimmt und eine ganze Zahl zurückgibt.\n",
"Assoziative Datenfelder verwenden diese ganzen Zahlen, auch **Hash-Werte** (Englisch: *hash values*) genannt, um Schlüssel zu lagern und zu suchen.\n",
"\n",
"Dieses System funktioniert nur, wenn ein Schlüssel unveränderbar ist, sein Hash-Wert also immer gleich bleibt.\n",
"Wenn aber ein Schlüssel veränderbar ist, könnte sich auch sein Hash-Wert verändern und das assoziative Datenfeld würde nicht funktionieren.\n",
"Deshalb müssen Schlüssel hashbar sein und veränderbare Datentypen wie Listen sind es nicht.\n",
"\n",
"Da assoziative Datenfelder veränderbar sind, können auch sie nicht als Schlüssel verwendet werden.\n",
"Aber sie *können* als Werte verwendet werden."
]
},
{
"cell_type": "markdown",
"id": "acfd2720",
"metadata": {
"id": "acfd2720",
"tags": []
},
"source": [
"## Akkumulation einer Liste\n",
"\n",
"Für viele Programmieraufgaben ist es nützlich, in einer Schleife durch eine Liste oder ein assoziatives Daetnfeld zu gehen, während man eine weitere erstellt.\n",
"Als Beispiel werden wir die Wörter in `word_dict` durchlaufen und eine Liste mit Palindromen erstellen -- also Wörtern, die von vorne und hinten gleich geschrieben werden, wie *noon* und *rotator*.\n",
"\n",
"Im vorherigen Kapitel wurden Sie in einer Übung darum gebeten, eine Funktion zu schreiben, die überprüft, ob ein Wort ein Palindrom ist.\n",
"Hier ist eine Lösung dazu, die `reverse_word` verwendet:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0647278e",
"metadata": {
"id": "0647278e"
},
"outputs": [],
"source": [
"def is_palindrome(word):\n",
" \"\"\"Check if a word is a palindrome.\"\"\"\n",
" return reverse_word(word) == word"
]
},
{
"cell_type": "markdown",
"id": "af545fcd",
"metadata": {
"id": "af545fcd"
},
"source": [
"Wenn wir in der Schleife durch die Wörter in `word_dict` laufen, können wir so die Anzahl der Palindrome ermitteln:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9eff9f2c",
"metadata": {
"id": "9eff9f2c"
},
"outputs": [],
"source": [
"count = 0\n",
"\n",
"for word in word_dict:\n",
" if is_palindrome(word):\n",
" count +=1\n",
"\n",
"count"
]
},
{
"cell_type": "markdown",
"id": "73c1ce1e",
"metadata": {
"id": "73c1ce1e"
},
"source": [
"Dieses Muster ist inzwischen bekannt:\n",
"\n",
"* Vor der Schleife wird `count` mit `0` initialisiert.\n",
"\n",
"* In der Schleife wird `count` inkrementiert, wenn `word` ein Palindrom ist.\n",
"\n",
"* Wenn die Schleife endet, enthält `count` die Gesamtzahl der Palindrome.\n",
"\n",
"Wir können ein ähnliches Muster verwenden, um eine Liste mit Palindromen zu machen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "609bdd9a",
"metadata": {
"id": "609bdd9a"
},
"outputs": [],
"source": [
"palindromes = []\n",
"\n",
"for word in word_dict:\n",
" if is_palindrome(word):\n",
" palindromes.append(word)\n",
"\n",
"palindromes[:10]"
]
},
{
"cell_type": "markdown",
"id": "be909f3b",
"metadata": {
"id": "be909f3b"
},
"source": [
"Das funktioniert folgendermaßen:\n",
"\n",
"* Vor der Schleife wird `palindromes` mit einer leeren Liste initialisiert.\n",
"\n",
"* Innerhalb der Schleife hängen wir `word` an das Ende von `palindromes` an, wenn es ein Palindrom ist.\n",
"\n",
"* Wenn die Schleife endet, ist `palindromes` eine Liste von Palindromen.\n",
"\n",
"In dieser Schleife wird `palindromes` als **Akkumulator** (Englisch: *accumulator*) verwendet, das ist eine Variabe, die während einer Berechnung Daten ansammelt oder akkumuliert.\n",
"\n",
"Nehmen wir jetzt einmal an, wir wollen nur Palindrome mit sieben oder mehr Buchstaben auswählen.\n",
"Wir können in einer Schleife durch `palindromes` gehen und eine Liste erstellen, die nur lange Palindrome enthält:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c2db1187",
"metadata": {
"id": "c2db1187"
},
"outputs": [],
"source": [
"long_palindromes = []\n",
"\n",
"for word in palindromes:\n",
" if len(word) >= 7:\n",
" long_palindromes.append(word)\n",
"\n",
"long_palindromes"
]
},
{
"cell_type": "markdown",
"id": "fa8ed275",
"metadata": {
"id": "fa8ed275"
},
"source": [
"In einer solchen Schleife durch eine Liste zu gehen, einige Elemente auszuwählen und andere auszulassen, nennt man **filtern** (Englisch: *filtering*)."
]
},
{
"cell_type": "markdown",
"id": "8ed50837",
"metadata": {
"id": "8ed50837",
"tags": []
},
"source": [
"## Memos\n",
"\n",
"Beim Durchlaufen der `fibonacci`-Funktion aus [Kapitel 6](seminar06.ipynb#Fibonacci), ist Ihnen vielleicht aufgefallen, dass die Laufzeit der Funktion länger wird, je größer das eingegebene Argument ist:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "13a7ed35",
"metadata": {
"id": "13a7ed35"
},
"outputs": [],
"source": [
"def fibonacci(n):\n",
" if n == 0:\n",
" return 0\n",
"\n",
" if n == 1:\n",
" return 1\n",
"\n",
" return fibonacci(n-1) + fibonacci(n-2)"
]
},
{
"cell_type": "markdown",
"id": "1b5203c2",
"metadata": {
"id": "1b5203c2"
},
"source": [
"Außerdem erhöht sich die Laufzeit schnell.\n",
"Um zu verstehen warum, betrachten Sie folgende Abbildung, die das **Aufrufdiagramm** (Englisch: *call graph*) für `fibonacci` mit `n=4` zeigt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7ed6137a",
"metadata": {
"id": "7ed6137a",
"tags": []
},
"outputs": [],
"source": [
"from diagram import make_binding, Frame, Arrow\n",
"\n",
"bindings = [make_binding('n', i) for i in range(5)]\n",
"frames = [Frame([binding]) for binding in bindings]"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a9374c39",
"metadata": {
"id": "a9374c39",
"tags": []
},
"outputs": [],
"source": [
"arrowprops = dict(arrowstyle=\"-\", color='gray', alpha=0.5, ls='-', lw=0.5)\n",
"\n",
"def left_arrow(ax, bbox1, bbox2):\n",
" x = bbox1.xmin + 0.1\n",
" y = bbox1.ymin\n",
" dx = bbox2.xmax - x - 0.1\n",
" dy = bbox2.ymax - y\n",
" arrow = Arrow(dx=dx, dy=dy, arrowprops=arrowprops)\n",
" return arrow.draw(ax, x, y)\n",
"\n",
"def right_arrow(ax, bbox1, bbox2):\n",
" x = bbox1.xmax - 0.1\n",
" y = bbox1.ymin\n",
" dx = bbox2.xmin - x + 0.1\n",
" dy = bbox2.ymax - y\n",
" arrow = Arrow(dx=dx, dy=dy, arrowprops=arrowprops)\n",
" return arrow.draw(ax, x, y)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "12098be7",
"metadata": {
"id": "12098be7",
"tags": []
},
"outputs": [],
"source": [
"from diagram import diagram, adjust, Bbox\n",
"\n",
"width, height, x, y = [4.94, 2.16, -1.03, 1.91]\n",
"ax = diagram(width, height)\n",
"\n",
"dx = 0.6\n",
"dy = 0.55\n",
"\n",
"bboxes = []\n",
"bboxes.append(frames[4].draw(ax, x+6*dx, y))\n",
"\n",
"bboxes.append(frames[3].draw(ax, x+4*dx, y-dy))\n",
"bboxes.append(frames[2].draw(ax, x+8*dx, y-dy))\n",
"\n",
"bboxes.append(frames[2].draw(ax, x+3*dx, y-2*dy))\n",
"bboxes.append(frames[1].draw(ax, x+5*dx, y-2*dy))\n",
"bboxes.append(frames[1].draw(ax, x+7*dx, y-2*dy))\n",
"bboxes.append(frames[0].draw(ax, x+9*dx, y-2*dy))\n",
"\n",
"bboxes.append(frames[1].draw(ax, x+2*dx, y-3*dy))\n",
"bboxes.append(frames[0].draw(ax, x+4*dx, y-3*dy))\n",
"\n",
"left_arrow(ax, bboxes[0], bboxes[1])\n",
"left_arrow(ax, bboxes[1], bboxes[3])\n",
"left_arrow(ax, bboxes[3], bboxes[7])\n",
"left_arrow(ax, bboxes[2], bboxes[5])\n",
"\n",
"right_arrow(ax, bboxes[0], bboxes[2])\n",
"right_arrow(ax, bboxes[1], bboxes[4])\n",
"right_arrow(ax, bboxes[2], bboxes[6])\n",
"right_arrow(ax, bboxes[3], bboxes[8])\n",
"\n",
"bbox = Bbox.union(bboxes)\n",
"# adjust(x, y, bbox)"
]
},
{
"cell_type": "markdown",
"id": "4ee2a87c",
"metadata": {
"id": "4ee2a87c"
},
"source": [
"Ein Aufrufdiagramm zeigt einen Satz an Funktionsrahmen, wobei Linien jeden Rahmen mit den Rahmen der Funktionen, die diese aufruft verbinden.\n",
"Ganz oben im Diagramm ruft `fibonacci` mit `n=4` `fibonacci` mit ` n=3` und `n=2` auf.\n",
"`fibonacci` mit `n=3` ruft wiederum `fibonacci` mit `n=2` und `n=1` auf. Und so weiter.\n",
"\n",
"Zählen Sie, wie oft `fibonacci(0)` und `fibonacci(1)` aufgerufen werden.\n",
"Diese Lösung ist sehr ineffizient und wird schlechter, je größer das Argument wird.\n",
"\n",
"Eine Lösung für dieses Problem ist es, einen Überblick über die schon berechneten Werte zu behalten, indem diese in einem assoziativen Datenfeld gespeichert werden.\n",
"Ein schon berechneter Wert, der für später aufbewahrt wird, wird **Memo** genannt.\n",
"Hier ist eine *memoisierte* Version von `fibonacci`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "28e443f5",
"metadata": {
"id": "28e443f5"
},
"outputs": [],
"source": [
"bekannt = {0:0, 1:1}\n",
"\n",
"def fibonacci_memo(n):\n",
" if n in bekannt:\n",
" return bekannt[n]\n",
"\n",
" res = fibonacci_memo(n-1) + fibonacci_memo(n-2)\n",
" bekannt[n] = res\n",
" return res"
]
},
{
"cell_type": "markdown",
"id": "d2ac4dd7",
"metadata": {
"id": "d2ac4dd7"
},
"source": [
"`bekannt` ist ein assoziatives Datenfeld, das sich die Fibonacci-Zahlen, die wir schon kennen merkt.\n",
"Es beginnt mit zwei Elementen: `0` wird `0` zugeordnet und `1` wird `1` zugeordnet.\n",
"\n",
"Jedes Mal wenn `fibonacci_memo` aufgerufen wird, überprüft es `bekannt`.\n",
"Wenn sich das Ergebnis schon dort befindet, kann es sofort zurückgegeben werden.\n",
"Andernfalls muss es den neuen Wert berechnen, zum assoziativen Datenfeld hinzufügen und zurückgeben.\n",
"\n",
"Nun können die beiden Funktionen verglichen werden: `fibonacci(40)` braucht etwa 30 Sekunden um durchzulaufen. `fibonacci_memo(40)` hingegen läuft innerhalb von 30 Mikrosekunden durch, ist also eine Million mal schneller.\n",
"In dem Notebook für dieses Kapitel können Sie sehen, woher diese Messwerte kommen:"
]
},
{
"cell_type": "markdown",
"id": "c6f39f84",
"metadata": {
"id": "c6f39f84",
"tags": []
},
"source": [
"Um zu messen, wie lange eine Funktion braucht, können wir `%time` verwenden, was eine von Jupyters eingebauten *magischen Methoden* ist.\n",
"Diese sind nicht Teil der Sprache von Python, daher funktionieren sie in anderen Programmierumgebungen eventuell nicht."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "af77c3bf-f3a8-4a7b-a57a-8301c7141943",
"metadata": {},
"outputs": [],
"source": [
"# nicht-memoisiert\n",
"%time fibonacci(40)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7316d721",
"metadata": {
"id": "7316d721",
"tags": []
},
"outputs": [],
"source": [
"# memoisiert\n",
"%time fibonacci_memo(40)"
]
},
{
"cell_type": "markdown",
"id": "ec969e51",
"metadata": {
"id": "ec969e51"
},
"source": [
"## Debugging\n",
"\n",
"Je größer die Datensätze werden, mit denen wir arbeiten, desto unpraktischer wird es auch, zum Debuggen den Output auszugeben und von Hand zu überprüfen:\n",
"\n",
"1. Input herunterskalieren: Wenn möglich, reduzieren Sie die Größe des Datensatzes. Wenn das Program zum Beispiel eine Textdatei liest, beginnen Sie mit den ersten zehn Zeilen oder mit dem kleinsten Beispiel, das Sie finden können. Sie können die Dateien entweder selbst bearbeiten, oder (besser) das Programm so anpassen, dass es nur die ersten `n` Zeilen liest.\n",
"\n",
" Wenn es einen Fehler gibt, reduzieren Sie `n`auf den kleinsten Wert, bei dem der Fehler vorkommt.\n",
" Während Sie Fehler finden und ausbessern, können Sie `n` nach und nach vergrößern."
]
},
{
"cell_type": "markdown",
"id": "1a62288b",
"metadata": {
"id": "1a62288b"
},
"source": [
"2. Prüfen Sie Zusammenfassungen und Datentypen: Anstatt den gesamten Datensatz auszugeben und zu prüfen, ziehen Sie in Erwägung, Zusammenfassungen der Daten auszugeben -- z. B. die Anzahl der Elemente in einem Wörterbuch oder die Gesamtsumme einer Liste von Zahlen.\n",
"\n",
" Eine häufige Ursache für Laufzeitfehler ist, dass einer der Werte nicht dem richtigen Datentyp entspricht. Um diese Art von Fehler zu beheben, reicht es oft aus, den Datentyp eines Wertes auszugeben."
]
},
{
"cell_type": "markdown",
"id": "c749ea3c",
"metadata": {
"id": "c749ea3c"
},
"source": [
"3. Schreiben Sie Selbstkontrollen: Manchmal können Sie Code schreiben, der automatisch auf Fehler prüft. Wenn Sie zum Beispiel den Durchschnitt einer Liste von Zahlen berechnen, können Sie prüfen, ob das Ergebnis weder größer als das größte Element in der Liste, noch kleiner als das kleinste ist. Dies nennt man eine „Plausibilitätsprüfung\" (Englisch: *sanity check*), weil damit \"verrückte\" (Englisch: *insane*) Ergebnisse erkannt werden.\n",
"\n",
" Eine andere Art der Prüfung vergleicht die Ergebnisse von zwei verschiedenen Berechnungen, um zu sehen, ob sie konsistent sind. Dies wird als „Konsistenzkontrolle“ bezeichnet."
]
},
{
"cell_type": "markdown",
"id": "749b91e9",
"metadata": {
"id": "749b91e9"
},
"source": [
"4. Formatieren Sie den Output: Die Formatierung des Debugging-Outputs kann die Erkennung von Fehlern erleichtern. Wir haben ein Beispiel hierfür in [Kapitel 6](seminar06.ipynb#Debugging) gesehen. Ein weiteres nützliches Werkzeug ist das `pprint`-Modul, das eine `pprint`-Funktion bietet, die eingebaute Datentypen in einem für Menschen besser lesbaren Format anzeigt (`pprint` steht für \"pretty print“).\n",
"\n",
" Auch hier gilt, dass die Zeit, die Sie mit der Erstellung von Strukturen verbringen, die Zeit, die Sie mit der Fehlersuche verbringen, reduzieren kann."
]
},
{
"cell_type": "markdown",
"id": "9820175f",
"metadata": {
"id": "9820175f"
},
"source": [
"## Glossar\n",
"\n",
"Legen wir uns eine Liste mit den wichtigsten Begriffen an, die wir im Kapitel 10 gelernt haben:\n",
"\n",
"- Assoziatives Datenfeld:\n",
"- Element:\n",
"- Schlüssel:\n",
"- Wert:\n",
"- Zuordnung:\n",
"- Hash-Tabelle:\n",
"- hashbar:\n",
"- Akkumulator:\n",
"- filtern:\n",
"- Aufrufdiagramm:\n",
"- Memo:\n",
"\n",
"Ergänzen Sie die Liste in eigenen Worten. Das ist eine gute Erinnerungs- und Übungsmöglichkeit."
]
},
{
"cell_type": "markdown",
"id": "906c1236",
"metadata": {
"id": "906c1236"
},
"source": [
"## Übung"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a4e34564",
"metadata": {
"tags": [
"remove-print"
]
},
"outputs": [],
"source": [
"# Diese Zelle weist Jupyter an, detallierte Debugging-Informationen auszugeben, wenn ein Laufzeitfehler\n",
"# passiert. Lassen Sie sie daher laufen, bevor Sie beginnen an den Aufgaben zu arbeiten.\n",
"\n",
"%xmode Verbose"
]
},
{
"cell_type": "markdown",
"id": "170f1deb",
"metadata": {
"id": "170f1deb"
},
"source": [
"### Fragen Sie einen Assistenten\n",
"\n",
"In diesem Kapitel habe ich beschrieben, dass die Schlüssel in einem assoziativen Datenfeld hashbar sein müssen und dafür eine kurze Erklärung gegeben. Wenn Sie dazu gerne mehr Details hätten, fragen Sie einen virtuellen Assistenten: \"Warum müssen in Python Schlüssel assoziativer Datenfelder hashbar sein?\".\n",
"\n",
"In dem oberen Abschnitt **Der `in`-Operator**, haben wir eine Liste mit Wörtern als Schlüssel in einem assoziativen Datenfeld gespeichert, um eine effiziente Version des `in`-Operators zu verwenden.\n",
"Wir hätten das Gleiche mit einem `set`, einem weiteren eingebauten Datentyp, erreichen können.\n",
"Fragen Sie einen virtuellen Assistenten: \"Wie erstelle ich in Python ein Set aus einer Liste mit Zeichenketten und überprüfe dann, ob eine Zeichenkette Teil dieses Sets ist?\"."
]
},
{
"cell_type": "markdown",
"id": "badf7d65",
"metadata": {
"id": "badf7d65"
},
"source": [
"### Aufgabe 1\n",
"\n",
"Assoziative Datenfelder haben eine Methode namens `get`, die einen Schlüssel und einen Standardwert aufnimmt.\n",
"Wenn der Schlüssel im assoziativen Datenfeld vorkommt, gibt `get` den entsprechenden Wert zurück; andernfalls wird der Standardwert zurückgegeben.\n",
"Hier ist zum Beispiel ein assoziatives Datenfeld, das von den Buchstaben in einer Zeichenkette auf die Häufigkeit von deren Vorkommen verweist:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "06e437d9",
"metadata": {
"id": "06e437d9"
},
"outputs": [],
"source": [
"zaehler = wert_zaehlen('brontosaurus')"
]
},
{
"cell_type": "markdown",
"id": "c3f6458d",
"metadata": {
"id": "c3f6458d"
},
"source": [
"Wenn wir einen Buchstaben suchen, der in dem Wort auftaucht, gibt `get` die Anzahl der Male zurück, die dieser vorkommt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "fc328161",
"metadata": {
"id": "fc328161"
},
"outputs": [],
"source": [
"zaehler.get('b', 0)"
]
},
{
"cell_type": "markdown",
"id": "49bbff3e",
"metadata": {
"id": "49bbff3e"
},
"source": [
"Wenn wir einen Buchstaben suchen, der nicht auftaucht, bekommen wir den Standardwert `0` zurück:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "674b6663",
"metadata": {
"id": "674b6663"
},
"outputs": [],
"source": [
"zaehler.get('c', 0)"
]
},
{
"cell_type": "markdown",
"id": "4ac3210f",
"metadata": {
"id": "4ac3210f"
},
"source": [
"Verwenden Sie `get`, um eine knappere, präzisere Version von `wert_zaehlen` zu schreiben.\n",
"Sie sollten dazu in der Lage sein, die `if`-Anweisung zu entfernen."
]
},
{
"cell_type": "markdown",
"id": "5413af6e",
"metadata": {
"id": "5413af6e"
},
"source": [
"### Aufgabe 2\n",
"\n",
"Welches ist das längste Wort, das Ihnen einfällt, in dem jeder Buchstabe nur einmal vorkommt?\n",
"Sehen wir einmal, ob wir ein längeres Wort als `unpredictably` finden können.\n",
"\n",
"Schreiben Sie eine Funktion namens `hat_duplikate`, die eine Folge -- wie eine Liste oder eine Zeichenkette -- als Parameter aufnimmt und `True` zurückgibt, wenn es in der Folge ein Element gibt, das mehr als einmal vorkommt."
]
},
{
"cell_type": "markdown",
"id": "9879d9e7",
"metadata": {
"id": "9879d9e7",
"tags": []
},
"source": [
"Hier ist als Starthilfe eine Struktur für die Funktion, die Doctests enthält:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1744d3e9",
"metadata": {
"id": "1744d3e9",
"tags": []
},
"outputs": [],
"source": [
"def hat_duplikate(t):\n",
" \"\"\"Überprüfen, ob ein Element in einer Folge mehr als einmal vorkommt.\n",
"\n",
" >>> hat_duplikate('banana')\n",
" True\n",
" >>> hat_duplikate('ambidextrously')\n",
" False\n",
" >>> hat_duplikate([1, 2, 2])\n",
" True\n",
" >>> hat_duplikate([1, 2, 3])\n",
" False\n",
" \"\"\"\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "061e2903",
"metadata": {
"id": "061e2903"
},
"outputs": [],
"source": [
"# Lösung hierhin schreiben"
]
},
{
"cell_type": "markdown",
"id": "d8c85906",
"metadata": {
"id": "d8c85906",
"tags": []
},
"source": [
"Sie können `doctest` verwenden, um Ihre Funktion zu testen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "62dcdf4d",
"metadata": {
"id": "62dcdf4d",
"tags": []
},
"outputs": [],
"source": [
"from doctest import run_docstring_examples\n",
"\n",
"def run_doctests(func):\n",
" run_docstring_examples(func, globals(), name=func.__name__)\n",
"\n",
"run_doctests(hat_duplikate)"
]
},
{
"cell_type": "markdown",
"id": "ce4df190",
"metadata": {
"id": "ce4df190",
"tags": []
},
"source": [
"Sie können diese Schleife verwenden, um die längsten Wörter ohne doppelte Buchstaben zu finden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a1143193",
"metadata": {
"id": "a1143193",
"tags": []
},
"outputs": [],
"source": [
"keine_wiederholung = []\n",
"\n",
"for wort in word_list:\n",
" if len(wort) > 12 and not hat_duplikate(wort):\n",
" keine_wiederholung.append(wort)\n",
"\n",
"keine_wiederholung"
]
},
{
"cell_type": "markdown",
"id": "afd5f3b6",
"metadata": {
"id": "afd5f3b6"
},
"source": [
"### Aufgabe 3\n",
"\n",
"Schreiben Sie eine Funktion namens `finde_wiederholungen`, die ein assoziatives Datenfeld aufnimmt, das von jedem Schlüssel auf einen Zähler verweist, wie das Ergebnis von `werte_zaehlen`.\n",
"Sie sollte das assoziative Datenfeld in einer Schleife durchlaufen und eine Liste von Schlüsseln zurückgeben, deren Zähler höher als `1` ist.\n",
"Sie können die folgende Skizze verwenden, um anzufangen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9ea333ff",
"metadata": {
"id": "9ea333ff"
},
"outputs": [],
"source": [
"def finde_wiederholungen(zaehler):\n",
" \"\"\"Erstellt eine Liste der Schlüssel mit Werten größer als 1.\n",
"\n",
" zaehler: assoziatives Datenfeld, das von Schlüsseln auf Zähler verweist\n",
"\n",
" Rückgabe: Liste mit Schlüsseln\n",
" \"\"\"\n",
" return []"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bbd6d241",
"metadata": {
"id": "bbd6d241"
},
"outputs": [],
"source": [
"# Lösung hierhin schreiben"
]
},
{
"cell_type": "markdown",
"id": "b9b0cbec",
"metadata": {
"id": "b9b0cbec",
"tags": []
},
"source": [
"Sie können die folgenden Beispiele verwenden, um Ihren Code zu testen.\n",
"Zuerst erstellen wir ein assoziatives Datenfeld, das von Buchstaben auf Zähler verweist:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ac983c6f",
"metadata": {
"id": "ac983c6f",
"tags": []
},
"outputs": [],
"source": [
"zaehler1 = wert_zaehlen('banana')\n",
"zaehler1"
]
},
{
"cell_type": "markdown",
"id": "3aa62942",
"metadata": {
"id": "3aa62942",
"tags": []
},
"source": [
"Das Ergebnis von `finde_wiederholungen` sollte `['a', 'n']` sein."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "214345d8",
"metadata": {
"id": "214345d8",
"tags": []
},
"outputs": [],
"source": [
"wiederholt = finde_wiederholungen(zaehler1)\n",
"wiederholt"
]
},
{
"cell_type": "markdown",
"id": "3eaf77f8",
"metadata": {
"id": "3eaf77f8",
"tags": []
},
"source": [
"Hier ist ein weiteres Beispiel, das mit einer Liste von Zahlen beginnt.\n",
"Das Ergebnis sollte `[1, 2]` sein:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "10e9d54a",
"metadata": {
"id": "10e9d54a",
"tags": []
},
"outputs": [],
"source": [
"zaehler1 = wert_zaehlen([1, 2, 3, 2, 1])\n",
"wiederholt = finde_wiederholungen(zaehler1)\n",
"wiederholt"
]
},
{
"cell_type": "markdown",
"id": "1c700d84",
"metadata": {
"id": "1c700d84"
},
"source": [
"### Aufgabe 4\n",
"\n",
"Nehmen Sie an, Sie lassen `wert_zaehlen` mit zwei verschiedenen Wörtern laufen und speichern die Ergebnisse in zwei assoziativen Datenfeldern:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c97e2419",
"metadata": {
"id": "c97e2419"
},
"outputs": [],
"source": [
"zaehler1 = wert_zaehlen('brontosaurus')\n",
"zaehler2 = wert_zaehlen('apatosaurus')"
]
},
{
"cell_type": "markdown",
"id": "deb14c7a",
"metadata": {
"id": "deb14c7a"
},
"source": [
"Jedes assoziative Daetnfeld verweist von einem Satz an Buchstaben zu der Anzahl wie viele Male diese auftauchen.\n",
"Schreiben Sie eine Funktion namens `zaehler_hinzu`, die zwei solcher assoziativer Datenfelder aufnimmt und ein neues zurückgibt, das alle Buchstaben und die Gesamtmenge der Male, die diese in einem der Wörter auftauchen enthält.\n",
"\n",
"Diese Aufgabe kann auf viele verschiedene Arten gelöst werden.\n",
"Sobald Sie eine funktionierende Lösung haben, fragen Sie einen virtuellen Assistenten nach anderen Lösungen."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6cf70355",
"metadata": {
"id": "6cf70355"
},
"outputs": [],
"source": [
"# Lösung hierhin schreiben"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6a729a14",
"metadata": {
"id": "6a729a14"
},
"outputs": [],
"source": [
"# Lösung hierhin schreiben"
]
},
{
"cell_type": "markdown",
"id": "f88110a9",
"metadata": {
"id": "f88110a9"
},
"source": [
"### Aufgabe 5\n",
"\n",
"Ein Wort ist \"ineinandergreifend\", wenn wir es in zwei Wörter aufteilen können, für die wir jeweils jeden zweiten Buchstaben verwenden.\n",
"Zum Beispiel ist `\"schooled\"` ein ineinandergreifendes Wort, weil wir es in `\"shoe\"` und `\"cold\"` aufspalten können.\n",
"\n",
"Um abwechselnd Buchstaben aus einer Zeichenkette auszuwählen, können Sie einen Slice-Operator verwenden, der drei Komponenten hat, die den Anfang, das Ende und die \"Schrittweite\" zwischen den Buchstaben angeben.\n",
"\n",
"Im folgenden Segment ist die erste Komponente `0`, also beginnen wir mit dem ersten Buchstaben.\n",
"Die zweite Komponente ist `None`, das bedeutet wir gehen die Zeichenkette bis zum Ende durch.\n",
"Und die dritte Komponente ist `2`, also sind zwei Schritte zwischen den Buchstaben, die wir auswählen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "56783358",
"metadata": {
"id": "56783358"
},
"outputs": [],
"source": [
"wort = 'schooled'\n",
"erstes = wort[0:None:2]\n",
"erstes"
]
},
{
"cell_type": "markdown",
"id": "d432332d",
"metadata": {
"id": "d432332d"
},
"source": [
"Statt `None` als zweite Komponente anzugeben, können wir den gleichen Effekt erzielen indem wir es einfach weglassen.\n",
"Das folgende Segment wählt zum Beispiel jeden zweiten Buchstaben aus und beginnt damit beim zweiten Buchstaben des Wortes:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "77fa8483",
"metadata": {
"id": "77fa8483"
},
"outputs": [],
"source": [
"zweites = wort[1::2]\n",
"zweites"
]
},
{
"cell_type": "markdown",
"id": "c8c4e3ba",
"metadata": {
"id": "c8c4e3ba"
},
"source": [
"Schreiben Sie eine Funktion namens `greift_ineinander`, die ein Wort als Argument aufnimmt und `True`zurückgibt, wenn dieses in zwei ineinandergreifende Wörter aufgeteilt werden kann."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e5e1030c",
"metadata": {
"id": "e5e1030c"
},
"outputs": [],
"source": [
"# Lösung hierhin schreiben"
]
},
{
"cell_type": "markdown",
"id": "2787f786",
"metadata": {
"id": "2787f786",
"tags": []
},
"source": [
"Sie können die folgende Schleife verwenden, um die ineinandergreifenden Wörter in der Wortliste zu finden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e04a5c73",
"metadata": {
"id": "e04a5c73"
},
"outputs": [],
"source": [
"# Lösung hierhin schreiben"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ced5aa90",
"metadata": {
"id": "ced5aa90"
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "aadee942-b8dd-4679-a331-e6023b569ad6",
"metadata": {},
"source": [
" Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). Rufen Sie dazu im Menü *File* den Punkt *Download as* → *Notebook* auf und nutzen Sie beispielsweise einen USB-Stick, E-Mail, Google Drive, Dropbox oder Ihre [HU-Box](https://box.hu-berlin.de/). \n"
]
},
{
"cell_type": "markdown",
"id": "3f98530e-bfe6-4319-9898-50940c840ba4",
"metadata": {},
"source": [
"\n",
"\n",
"Herzlichen Glückwunsch! Sie haben das 10. Kapitel geschafft!"
]
},
{
"cell_type": "markdown",
"id": "5cf853f4-5575-408c-8446-bc993452dc66",
"metadata": {},
"source": [
"<img src=\"https://scm.cms.hu-berlin.de/ibi/python/-/raw/master/img/by-nc-sa.png\" alt=\"CC BY-NC-SA\" style=\"width: 150px;\"/>\n",
"\n",
"Der Text dieses Notebooks ist als freies Werk unter der Lizenz [CC BY-NC-SA 4.0 ](https://creativecommons.org/licenses/by-nc-sa/4.0/) verfügbar.\n",
"Der Code dieses Notebooks ist als freies Werk unter der Lizenz [MIT License](https://mit-license.org/) verfügbar.\n",
"\n",
"Es handelt sich um übersetzte und leicht veränderte Notebooks von [Allen B. Downey](https://allendowney.com) aus [Think Python: 3rd Edition](https://allendowney.github.io/ThinkPython/index.html).\n"
]
}
],
"metadata": {
"celltoolbar": "Tags",
"colab": {
"provenance": [],
"toc_visible": true
},
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.2"
}
},
"nbformat": 4,
"nbformat_minor": 5
}