{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Seminar Problemorientierte Programmierung\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,
"metadata": {},
"outputs": [],
"source": [
"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",
"# from 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",
"metadata": {},
"source": [
"## 10 Listen\n",
"\n",
"In diesem Kapitel lernen wir einen der nützlichsten eingebauten Datentypen von Python kennen: Listen. Wir lernen auch mehr über Objekte und was passieren kann, wenn es mehr als einen Namen für das gleiche Objekt gibt.\n",
"\n",
"### 10.1 Eine Liste ist eine Folge\n",
"\n",
"Wie eine Zeichenkette, ist eine **Liste** eine Folge (*sequence*) von Werten. In einer Zeichenkette sind die Werte Zeichen; in einer Listen können sie von jedem Typ sein. Die Werte in einer Liste heißen **Elemente**, im Englischen manchmal auch *items*.\n",
"\n",
"Es gibt mehrere Möglichkeiten, eine neue Liste zu erzeugen. Die einfachste ist es, Elemente in eckigen Klammern einzuschließen (`[` und `]`):"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[10, 20, 30, 40]\n",
"l = ['crunchy frog', 'ram bladder', 'lark vomit']"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das erste Beispiel ist eine Liste mit vier ganzen Zahlen. Das zweite Beispiel ist eine Liste mit drei Zeichenketten. Die Elemente einer Liste müssen nicht vom gleichen typ sein. Die folgende Liste enthält eine Zeichenkette, eine Gleitkommazhal, eine ganze Zahl und (ja!) eine andere Liste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"['spam', 2.0, 5, [10, 20]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Eine Liste innerhalb einer anderen Liste ist **verschachtelt** (*nested*).\n",
"\n",
"Eine Liste, die keine Elemente enthält wird **leere Liste** genannt. Wir können Sie mit Hilfe von leeren Klammern erzeugen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wir Sie vielleicht schon vermutet haben, können wir Listen Variablen zuweisen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cheeses = ['Cheddar', 'Edam', 'Gouda']\n",
"numbers = [42, 123]\n",
"empty = []\n",
"print(cheeses, numbers, empty)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.2 Listen sind veränderbar\n",
"\n",
"Die Syntax, um auf Elemente einer Liste zuzugreifen, ist die gleiche wie die zum Zugriff auf die Zeichen einer Zeichenkette: der Klammer-Operator. Der Ausdruck innerhalb der Klammern gibt den Index an. Denken Sie daran, dass die Zählung der Indizes mit 0 beginnt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cheeses[0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Anders als Zeichenketten sind Listen veränderbar. Wenn der Klammer-Operator auf der linken Seite einer Zuweisung auftaucht, identifiziert er das Element der Liste, dessen Wert geändert wird."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"numbers = [42, 123]\n",
"numbers[1] = 5\n",
"numbers"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das zweite Element von `numbers`, welches 123 war, ist jetzt 5.\n",
"\n",
"Die folgende Abbildung zeigt das Zustandsdiagramm für `cheeses`, `numbers` and `empty`:\n",
"\n",
"\n",
"\n",
"In diesen Diagrammen sind Listen als Boxen mit dem Wort \"Liste\" oberhalb und den Elementen der Liste innerhalb repräsentiert. Dabei zeigt `cheeses` auf eine Liste mit drei Elementen, die mit 0, 1 und 2 indiziert sind. `numbers` enthält zwei Elemente; das Diagramm zeigt, dass der Wert des zweiten Elements von 123 zu 5 geändert wurde. `empty` verweist auf eine Liste ohne Elemente.\n",
"\n",
"Listenindizes funktionieren genauso wie Indizes bei Zeichenketten:\n",
"- Jeder Ausdruck, der eine ganze Zahl ergibt, kann als Index verwendet werden.\n",
"- Wenn wir versuchen, ein Element zu lesen oder zu schreiben, welches nicht existiert, erhalten wir einen `IndexError`.\n",
"- Wenn ein Index einen negativen Wert hat, zählt er rückwärts vom Ende der Liste.\n",
"\n",
"Der `in`-Operator funktioniert auch für Listen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cheeses = ['Cheddar', 'Edam', 'Gouda']\n",
"'Edam' in cheeses"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"'Brie' in cheeses"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.3 eine Liste durchlaufen\n",
"\n",
"Üblicherweise durchläuft man die Elemente einer Liste mit einer `for`-Schleife. Die Syntax ist die gleiche wie für Zeichenketten:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for cheese in cheeses:\n",
" print(cheese)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das funktioniert gut wenn wir die Elemente einer Liste lediglich *lesen* wollen. Wenn wir die Elemente aber schreiben oder verändern wollen, benötigen wir die Indizes. Eine übliche Variante das zu tun ist, die eingebauten Funktionen `range` und `len` zu kombinieren: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for i in range(len(numbers)):\n",
" numbers[i] = numbers[i] * 2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Diese Schleife durchläuft die Liste und aktualisiert jedes Element. Dabei gibt `len` die Anzahl der Elemente in der Liste zurück und `range` gibt eine Liste von Indizes zurück, die mit 0 bis $n-1$ numeriert sind - wobei $n$ die Länge der Liste ist. Bei jedem Schleifendurchlauf erhält `i` den Index des nächsten Elements. Die Zuweisung im Rumpf verwendet `i`, um den alten Wert des Elementes zu lesen den neuen Wert zuzuweisen. \n",
"\n",
"Eine `for`-Schleife über eine leere Liste durchläuft niemals den Schleifenrumpf:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for x in []:\n",
" print(\"This never happens.\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Obwohl eine Liste eine andere Liste enthalten kann, zählt die verschachtelte Liste als ein einzelnes Element. Die Länge der folgenden Liste ist vier: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"allerhand = ['spam', 1, ['Brie', 'Roquefort', 'Pol le Veq'], [1, 2, 3]]\n",
"len(allerhand)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.4 Listenoperatoren\n",
"\n",
"Der `+`-Operator verknüpft Listen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = [1,2,3]\n",
"b = [4,5,6]\n",
"c = a + b\n",
"c"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Der `*`-Operator wiederholt eine Liste so oft wie angegeben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[0] * 4"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[1,2,3] * 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das erste Beispiel wiederholt `[0]` viermal. Das zweite Beispiel wiederholt die Liste `[1,2,3]` dreimal.\n",
"\n",
"### 10.5 Listensegmente\n",
"\n",
"Der Segmentoperator (*slice operator*) funktioniert auch auf Listen: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c', 'd', 'e', 'f']\n",
"t[1:3]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t[:4]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t[3:]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wenn wir den ersten Index weglassen, dann beginnt das Segment mit dem Anfang. Wenn wir den zweiten Index weglassen, dann geht das Segment bis zum Ende. Wenn wir also beide weglassen, dann ist das Segment eine Kopie der gesamten Liste. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t[:]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Da Listen veränderbar sind, ist es oft nützlich, eine Kopie der Liste zu erstellen, bevor man Operationen anwendet, die die Liste verändern.\n",
"\n",
"Wenn wir den Segmentoperator auf der linken Seite einer Zuweisung verwenden, können wir mehrere Listenelemente verändern: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c', 'd', 'e', 'f']\n",
"t[1:3] = ['x', 'y']\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.6 Listenmethoden\n",
"\n",
"Python stellt Methoden bereit, die auf Listen operieren. Zum Beispiel fügt `append` neue Elemente am Ende einer Liste hinzu:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"t.append('d')\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`extend` erwartet eine Liste als Argument und fügt alle Elemente der Liste am Ende hinzu:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t1 = ['a', 'b', 'c']\n",
"t2 = ['d', 'e']\n",
"t1.extend(t2)\n",
"t1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In diesem Beispiel wird `t2` nicht verändert.\n",
"\n",
"Mit `sort` können wir die Elemente einer Liste sortieren - vom kleinsten zum größten:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['d', 'c', 'e', 'b', 'a']\n",
"t.sort()\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Die meisten Listenmethoden sind leer - sie verändern die Liste und geben `None` zurück. Wenn wir fälschlicherweise `t = t.sort()` schreiben, werden wir vom Ergebnis enttäuscht sein.\n",
"\n",
"### 10.7 Map, filter und reduce\n",
"\n",
"Um die Elemente einer Liste aufzuaddieren, können wir eine Schleife wie die folgende nutzen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def add_all(t):\n",
" total = 0\n",
" for x in t:\n",
" total += x\n",
" return total"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`total` wird mit 0 initialisiert. Bei jedem Durchlauf der Schleife enthält `x` ein Element der Liste. Der `+=`-Operator ist eine Kurzschreibweise zum Verändern einer Variable. Diese **erweiterte Zuweisung** (*augmented assignment statement*),\n",
"\n",
"```python\n",
"total += x\n",
"```\n",
"\n",
"ist äquivalent zu \n",
"\n",
"```python\n",
"total = total + x\n",
"```\n",
"\n",
"Während die Schleife läuft, akkumuliert `total` die Summe der Elemente. Eine Variable die so verwendet wird, wird manchmal **Akkumulator** genannt.\n",
"\n",
"Die Elemente einer Liste aufzuaddieren ist eine so übliche Operation, dass Python dafür die eingebaute Funktion `sum` bereitstellt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = [1, 2, 3]\n",
"sum(t)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Eine Operation wie diese, die eine Folge von Elementen in einen einzelnen Wert kombinbiert, wird manchmal **Reducer** genannt. \n",
"\n",
"Manchmal wollen wir eine Liste durchlaufen während wir eine andere aufbauen. Beispielsweise erwartet die folgende Funktion eine Liste von Zeichenketten und gibt eine neue Liste zurück, die großgeschriebene Zeichenketten enthält:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def capitalize_all(t):\n",
" res = []\n",
" for s in t:\n",
" res.append(s.capitalize())\n",
" return res"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`res` wird mit der leeren Liste initialisiert. Bei jedem Schleifendurchlauf fügen wir das nächste Element hinzu. Also ist `res` eine andere Art von Akkumulator.\n",
"\n",
"Eine Operation wie `capitalize_all` wird manchmal **Mapper** genannt, da sie eine Funktion auf alle Elemente einer Folge anwendet (*maps*). \n",
"\n",
"Eine andere übliche Operation ist es, einige Elemente einer Liste auszuwählen und dann eine Teilliste zurückzugeben. Beispielsweise erwartet die folgende Funktion eine Liste von Zeichenketten und gibt eine Liste zurück, die nur die Zeichenketten enthält, die nur aus Großbuchstaben bestehen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def only_upper(t):\n",
" res = []\n",
" for s in t:\n",
" if s.isupper():\n",
" res.append(s)\n",
" return res"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`isupper` ist eine Zeichenketten-Methode, die `True` zurückgibt, wenn die Zeichenkette nur aus Großbuchstaben besteht.\n",
"\n",
"Eine operation wie `only_upper` wird **Filter** genannt, denn sie wählt einige der Elemente aus und filtert andere heraus.\n",
"\n",
"Die meisten üblichen Listenoperatoren können als eine Kombination aus Mapper, Filter und Reducer ausgedrückt werden."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.8 Elemente löschen\n",
"\n",
"Es gibt mehrere Möglichkeiten, um Elemente aus einer Liste zu entfernen. Wenn wir den Index des Elementes kennen, dann können wir es mittels `pop` entfernen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"x = t.pop(1)\n",
"t"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`pop` verändert die Liste und gibt das Element zurück, welches entfernt wurde. Wenn wir keinen Index angeben, dann wird das letzte Element entfernt und zurückgegeben.\n",
"\n",
"Wenn wir den gelöschten Wert nicht benötigen, können wir den `del`-Operator verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"del t[1]\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wenn wir das Element kennen, welches wir entfernen wollen (aber nicht seinen Index), können wir `remove` verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"t.remove('b')\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Der Rückgabewert von `remove` ist `None`.\n",
"\n",
"Um mehr als ein Element zu löschen, können wir `del` mit einem einem Segment-Index nutzen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c', 'd', 'e', 'f']\n",
"del t[1:5]\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wie sonst auch, beinhalted das Segment alle Elemente bis zum zweiten Index."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.9 Listen und Zeichenketten\n",
"\n",
"Eine Zeichenkette ist eine Folge von Zeichen und eine Liste ist eine Folge von Werten, aber eine Liste von Zeichen ist nicht das gleiche wie eine Zeichenkette. Um eine Zeichenkette in eine Liste von Zeichen zu konvertieren, können wir die Funktion `list` verwenden:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s = 'spam'\n",
"t = list(s)\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Da `list` der Name einer eingebauten Funktion ist, sollten wir diesen nicht als Variablennamen verwenden. Da `l` der `1` sehr ähnlich sieht, sollten wir `l` als Name für Listen vielleicht auch verwenden. Daher verwenden wir hier `t`.\n",
"\n",
"Die `list`-Funktion teilt eine Zeichenkette in die individuellen Zeichen auf. Wenn wir eine Zeichenkette in die enthaltenen Wörter aufteilen wollen, können wir die `split`-Methode verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s = 'pining for the fjords'\n",
"t = s.split()\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ein optionales Argument, genannt **Trennzeichen** (*delimiter*) gibt an, welche Zeichen als Wortgrenzen verwendet werden sollen. Im folgenden Beispiel wird ein Bindestrich als Trennzeichen verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s = 'spam-spam-spam'\n",
"delimiter = '-'\n",
"t = s.split(delimiter)\n",
"t"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das Gegenstück zu `split` ist `join`. Die Methode erwartet eine Liste von Zeichenketten und verkettet die einzelnen Elemente. `join` ist eine Zeichenketten-Methode, daher müssen wir sie auf ein Trennzeichen anwenden und die Liste als Parameter übergeben:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['pining', 'for', 'the', 'fjords']\n",
"delimiter = ' '\n",
"s = delimiter.join(t)\n",
"s"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In diesem Fall ist das Trennzeichen das Leerzeichen, so dass `join` ein Leerzeichen zwischen die Wörter setzt. Um die Zeichenketten ohne Trennzeichen miteinander zu verketten, können wir die leere Zeichenkette `''` als Trennzeichen verwenden."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.10. Objekte und Werte\n",
"\n",
"Wenn wir diese beiden Zuweisungen ausführen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = 'banana'\n",
"b = 'banana'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"wissen wir, dass sowohl `a` als auch `b` auf eine Zeichenkette verweisen, aber wir wissen nicht, ob sie auf *die selbe* Zeichenkette verweisen. Es gibt zwei mögliche Zustände:\n",
"\n",
"\n",
"\n",
"Im ersten Fall verweisen `a` und `b` auf zwei unterschiedliche Objekte, die den gleichen Wert haben. Im zweiten Fall verweisen sie auf das selbe Objekt.\n",
"\n",
"Um zu prüfen, ob zwei Variablen auf das selbe Objekt verweisen, können wir den `is`-Operator verwenden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = 'banana'\n",
"b = 'banana'\n",
"a is b"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In diesem Beispiel erzeugt Python nur ein Zeichenketten-Objekt und sowohl `a` als auch `b` verwiesen darauf. Wenn wir jedoch zwei Listen erzeugen, erhalten wir zwei Objekte:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = [1, 2, 3]\n",
"b = [1, 2, 3]\n",
"a is b"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das Zustandsdiagramm sieht in diesem Fall so aus:\n",
"\n",
"\n",
"\n",
"In diesem Fall würden wir sagen, dass die beiden Listen **äquivalent** sind, denn sie enthalten die gleichen Elemente, aber sie sind nicht **identisch**, denn sie sind nicht das selbe Objekt. Wenn zwei Objekte identisch sind, sind sie auch äquivalent; aber wenn sie äquivalent sind, sind sie nicht notwendig auch identisch.\n",
"\n",
"Bis jetzt haben wir die Begriffe \"Objekt\" und \"Wert\" synonym verwendet, aber es ist eigentlich präziser, zu sagen, dass ein Objekt einen Wert hat. Wenn wir `[1,2,3]` evaluieren, dann erhalten wir ein Listenobjekt, dessen Werte eine Folge von ganzen Zahlen darstellen. Wenn ein anderes Listenobjekt die gleichen Elemente enthält sagen wir, dass es den gleichen Wert hat, aber es ist nicht das selbe Objekt."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.11 Aliasing\n",
"\n",
"Wenn `a` auf ein Objekt verweist und wir die Zuweisung `b = a` ausführen, dann verweisen beide Variablen auf das selbe Objekt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = [1, 2, 3]\n",
"b = a\n",
"b is a"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das Zustandsdiagramm schaut dann folgendermaßen aus:\n",
"\n",
"\n",
"\n",
"Die Verbindung (*association*) einer Variable mit einem Objekt wird **Referenz** (*reference*) genannt. In diesem Beispiel gibt es zwei Referenzen auf das selbe Objekt.\n",
"\n",
"Ein Objekt mit mehr als einer Referenz hat mehr als einen Namen, daher sagen wir, dass dieses Objekt einen **Alias** besitzt. \n",
"\n",
"Falls das Objekt mit Alias veränderbar ist, dann betreffen Veränderungen, die an einem Alias vorgenommen werden auch den anderen:\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"b[0] = 42\n",
"a"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Obwohl dieses Verhalten nützlich sein kann, ist es auch fehleranfällig. Im allgemeinen ist es sicherer, Aliasing zu vermeiden wenn wir mit veränderbaren Objekten arbeiten.\n",
"\n",
"Bei unveränderbaren Objekte wie z.B. Zeichenketten ist Aliasing kein großes Problem. Im Beispiel\n",
"```python\n",
"a = 'banana'\n",
"b = 'banana'\n",
"```\n",
"macht es so gut wie nie einen Unterschied, ob `a` und `b` auf die gleiche Zeichenkette verweisen oder nicht."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.12 Listen als Argumente\n",
"\n",
"Wenn wir eine Liste an eine Funktion als Argument übergeben, erhält die Funktion eine Referenz auf die Liste. Wenn die Funktion die Liste verändert, verändert sich auch die Liste an der aufrufenden Stelle (denn es ist die selbe Liste). Beispielsweise entfernt die Funktion `delete_head` das erste Element einer Liste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def delete_head(t):\n",
" del t[0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Hier sehen wir, wie die Funktion verwendet werden kann und wie sie wirkt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"letters = ['a', 'b', 'c']\n",
"delete_head(letters)\n",
"letters"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Der Parameter `t` und die Variable `letters` sind Aliase für das selbe Objekt. Das Stapeldiagramm beim Aufruf von `delete_head` sieht folgendermaßen aus:\n",
"\n",
"\n",
"\n",
"Die zwei Blöcke `__main__` und `delete_head` teilen sich die Liste, daher zeigen zwei Pfeile auf sie.\n",
"\n",
"Es ist wichtig, dass wir zwischen Operationen unterscheiden, die Listen *verändern* und jenen, die neue Listen *erzeugen*. Beispielsweise verändert die Methode `append` eine Liste, aber der Operator `+` erzeugt eine neue Liste.\n",
"\n",
"Nachfolgend ein Beispiel zu `append`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t1 = [1, 2]\n",
"t2 = t1.append(3)\n",
"print(t1)\n",
"print(t2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Der Rückgabewert von `append` ist `None`.\n",
"\n",
"Nachfolgend ein Beispiel für den Operator `+`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t3 = t1 + [4]\n",
"print(t1)\n",
"print(t3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Das Ergebnis des Operators ist eine neue Liste; die Ursprungsliste ist unverändert.\n",
"\n",
"Dieser Unterschied ist wichtig, wenn wir Funktionen schreiben die Listen verändern. Beispielsweise entfernt die folgende Funktion *nicht* das erste Element einer Liste: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def bad_delete_head(t):\n",
" t = t[1:] # FALSCH!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Der Segmentoperator erzeugt eine neue Liste und die Zuweisung sorgt dafür, dass `t` auf die neue Liste verweist, aber das verändert nicht die Ursprungsliste:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t4 = [1, 2, 3]\n",
"bad_delete_head(t4)\n",
"t4"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Am Anfang von `bad_delete_head` verweisen `t` und `t4` auf die gleiche Liste. Am Ende verweist `t` auf eine neue Liste, aber `t4` verweist immer noch auf die ursprüngliche, unveränderte Liste.\n",
"\n",
"Eine Alternative ist, eine Funktion zu schreiben, die eine neue Liste erzeugt und zurückgibt. Beispielsweise gibt `tail` alle bis auf das erste Element einer Liste zurück:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def tail(t):\n",
" return t[1:]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Diese Funktion verändert die Ursprungsliste nicht! Folgendermaßen kann die Funktion verwendet werden:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"letters = ['a', 'b', 'c']\n",
"rest = tail(letters)\n",
"rest"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.13 Debugging\n",
"\n",
"Unvorsichtige Verwendung von Listen (und anderen veränderbaren Objekten) kann langwieriges Debuggen verursachen. Einige übliche Fehler und Wege, sie zu vermeiden:\n",
"\n",
"#### 1. Die meisten Listenmethoden verändern das Argument und geben `None` zurück.\n",
"\n",
"Das ist das Gegenteil zum Verhalten der Methoden für Zeichenketten, die eine neue Zeichenkette zurückgeben und die ursprüngliche Zeichenkette unverändert lassen.\n",
"\n",
"Wenn Sie gewohnt sind, Code für Zeichenketten so zu schreiben:\n",
" \n",
"```python\n",
"word = word.strip()\n",
"```\n",
" \n",
"Dann ist es verlpckend, folgenden Code für Listen zu schreiben:\n",
" \n",
"```python\n",
"t = t.sort() # FALSCH!\n",
"```\n",
" \n",
"Weil `sort` keinen Wert (also `None`) zurückliefert, wird die nächste Operation, die wir mit `t` durchführen würden wahrscheinlich fehlschlagen. \n",
" \n",
"Bevor wir Methoden und Operatoren für Listen verwenden, sollten wir aufmerksam die Dokumentation lesen und mit etwas Beispielcode testen.\n",
" \n",
"#### 2. Sich für ein Idiom entscheiden und dann dabei bleiben.\n",
"\n",
"Ein Teil des Problems mit Listen ist, dass es zu viele Möglichkeiten gibt, mit Ihnen umzugehen. Beispielsweise können wir zum Entfernen eines Elements `pop`, `remove`, `del` oder sogar den Segmentoperator verwenden. \n",
" \n",
"Um ein Element hinzuzufügen, können wir die Methode `append` oder den Operator `+` verwenden. Angenommen, `t` ist eine Liste und `x` ist ein Listenelement, dann sind die folgenden Varianten korrekt:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = ['a', 'b', 'c']\n",
"x = 'n'\n",
"\n",
"t.append(x)\n",
"print(t)\n",
"\n",
"t = t + [x]\n",
"print(t)\n",
"\n",
"t += [x]\n",
"print(t)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"und die folgenden sind falsch:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t.append([x]) # FALSCH!\n",
"print(t)\n",
"\n",
"t = t.append(x) # FALSCH!\n",
"print(t)\n",
"\n",
"t + [x] # FALSHC!\n",
"print(t)\n",
"\n",
"t = t + x # FLASCH!\n",
"print(t)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Probieren Sie diese Beispiele (einzeln!) aus und stellen Sie sicher, dass Sie wirklich verstanden haben, was sie tun. Beachten Sie, dass nur das letzte Beispiel einen Laufzeitfehler (*runtime error*) verursacht. Die anderen drei Varianten sind erlaubt, aber sie tun das Falsche.\n",
" \n",
"#### 3. Kopien erzeugen, um Aliasing zu vermeiden.\n",
"\n",
"Wenn Sie eine Methode wie z.B. `sort` verwenden wollen, die das Argument verändert, aber Sie benötigen auch die Ursprungsliste, dann können Sie eine Kopie erzeugen:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t = [3, 1, 2]\n",
"t2 = t[:]\n",
"t2.sort()\n",
"print(t)\n",
"print(t2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In diesem Beispiel könnten Sie auch die eingebaute Funktion `sorted` verwenden, die eine neue, sortierte Liste zurückgibt, ohne die Ursprungsliste zu verändern: "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"t2 = sorted(t)\n",
"print(t)\n",
"print(t2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.14 Glossar\n",
"\n",
"Legen wir uns eine Liste mit den wichtigsten Begriffen an, die wir im Kapitel 10 gelernt haben:\n",
"\n",
"- Liste: eine Folge von Werten\n",
"- Element:\n",
"- verschachtelte Liste: \n",
"- Akkumulator:\n",
"- erweiterte Zuweisung\n",
"- Reducer:\n",
"- Mapper:\n",
"- Filter:\n",
"- Objekt:\n",
"- äquivalent:\n",
"- identisch:\n",
"- Referenz:\n",
"- Aliasing:\n",
"- Trennzeichen:\n",
"\n",
"Ergänzen Sie die Liste in eigenen Worten. Das ist eine gute Erinnerungs- und Übungsmöglichkeit."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 10.15 Übung\n",
"\n",
"Sie finden die Lösungen für die Aufgaben hier: http://thinkpython2.com/code/list_exercises.py\n",
"\n",
"#### Aufgabe 1\n",
"Schreiben Sie eine Funktion `nested_sum`, die eine Liste von Listen von ganzen Zahlen erwartet und die Werte der einzelnen Elemente aufaddiert und das Ergebnis zurückgibt. Beispielsweise sollte die Funktion für die Liste `t = [[1, 2], [3], [4, 5, 6]]` den Wert `21` zurückgeben."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"\n",
"def nested_sum(t):\n",
" # Implementieren Sie hier die Funktion\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 2\n",
"Schreiben Sie eine Funktion `cumsum`, die eine Liste von Zahlen erwartet und die kumulative Summe zurückgibt, d.h. eine neue Liste, in der das *i*te Element die Summe der ersten *i + 1* Elemente der Original-Liste enthält. Beispielsweise sollte die Funktion für die Liste `t = [1, 2, 3]` die Liste `[1, 3, 6]` zurückgeben."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def cumsum(t):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Testen Sie die Funktion mit verschiedenen Listen als Eingabe.\n",
"\n",
"Welche Liste müssten Sie der Funktion `cumsum` übergeben, um als Ergebnis die Liste `[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]` der ersten zehn Fibonacci-Zahlen zu erhalten?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 3\n",
"Schreiben Sie eine Funktion `middle`, die eine Liste als Argument erwartet und eine neue Liste zurückgibt, die alle Elemente bis auf das erste und letzte der Ausgangsliste enthält. Beispielsweise sollte die Funktion für die Liste `t = [1,2,3,4]` die Liste `[2,3]` zurückgeben:\n",
"\n",
"```python\n",
"t = [1,2,3,4]\n",
"middle(t)\n",
"```\n",
"sollte `[2,3]` ergeben."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def middle(t):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 4\n",
"Schreiben Sie eine Funktion `chop`, die eine Liste als Argument erwartet, das erste und letzte Element entfernt und `None` zurückgibt. Beispielsweise sollte\n",
"\n",
"```python\n",
"t = [1,2,3,4]\n",
"chop(t)\n",
"t\n",
"```\n",
"`[2,3]` ergeben."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def chop(t):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 5\n",
"Schreiben Sie eine Funktion `is_sorted`, die eine Liste als Argument erwartet und `True` zurückgibt, falls die Liste in aufsteigender Reihenfolge sortiert ist und ansonsten `False`. Also zum Beispiel:\n",
"\n",
"```python\n",
">>> is_sorted([1, 2, 2])\n",
"True\n",
">>> is_sorted(['b', 'a'])\n",
"False\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def is_sorted(t):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 6\n",
"Zwei Wörter bilden ein *Anagramm*, wenn wir die Buchstaben des einen Wortes so umordnen können, dass sich das andere Wort ergibt. (Beispielsweise bilden *LAGER* und *REGAL* ein Anagramm.) Schreiben Sie eine Funktion `is_anagram`, die zwei Zeichenketten erwartet und `True` zurückgibt, falls sie ein Anagramm bilden (sonst `False`). "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def is_anagram(v, w):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Zusatzaufgabe: Suchen Sie in der Wortliste aus dem [8. Kapitel](seminar08.ipynb) nach Anagrammen."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 7\n",
"Schreiben Sie eine Funktion `has_duplicates`, die eine Liste als Argument erwartet und `True` zurückgibt, falls ein Element der Liste mehr als einmal in der Liste enthalten ist. Die Funktion soll die Ursprungsliste nicht verändern."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def has_duplicates(t):\n",
" # Implementieren Sie hier die Funktion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 8\n",
"In dieser Aufgabe geht es um das sogenannte \"Geburtstags-Paradoxon\" über das Sie mehr in [Wikipedia](http://en.wikipedia.org/wiki/Birthday_paradox) lesen können.\n",
"\n",
"Wenn 23 Studierende in Ihrem Kurs sind, wie hoch ist dann die Wahrscheinlichkeit, dass zwei davon am gleichen Tag Geburtstag haben? Sie können diese Wahrscheinlichkeit schätzen, indem Sie zufällig 23 Geburtstage auswürfeln und prüfen, ob mindestens zwei davon identisch sind. (*Hinweis: Sie können zufällige Geburtstage mit Hilfe der Funktion `randint` aus dem [Modul `random`](https://docs.python.org/3.5/library/random) erzeugen.)\n",
"\n",
"Eine Lösung für diese Aufgabe finden Sie hier: http://thinkpython2.com/code/birthday.py"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from random import randint\n",
"\n",
"# Implementieren Sie hier Ihr Programm"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 9\n",
"Schreiben Sie eine Funktion, die die Datei \"top10000de.txt\" einliest (siehe [Abschnitt 9.1](seminar09.ipynb#9.1-Wortlisten-einlesen)) und daraus eine Liste erzeugt mit den Wörtern als Elementen erzeugt. Implementieren Sie zwei Versionen dieser Funktion: eine, die die Methode `append` verwendet und eine, die den Operator `+` mittels `t = t + [t]` verwendet. Welche der beiden Versionen hat eine größere Laufzeit? Warum?\n",
"\n",
"Eine Lösung für diese Aufgabe finden Sie hier: http://thinkpython2.com/code/wordlist.py"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier die beiden Varianten Ihrer Funktion"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 10\n",
"\n",
"Um zu überprüfen, ob ein Wort in einer Wortliste ist, können wir den Operator `in` verwenden, aber das wäre recht langsam, denn der Operator muss dazu die Liste linear durchlaufen.\n",
"\n",
"Wenn wir mit einer sortierten Liste arbeiten, können wir den Vorgang beschleunigen, indem wir *binäre Suche* (auch bekannt als *bisection search*) verwenden. Das entspricht dem Verfahren, welches wir verwenden, wenn wir ein Wort in einem Wörterbuch nachschlagen: wir beginnen in der Mitte und schauen, ob das gesuchte Wort vor dem Wort in der Mitte der Liste stehen müsste. Falls dem so ist, durchsuchen wir die erste Hälfte der Liste auf die gleiche Art, ansonsten durchsuchen wir die zweite Hälfte.\n",
"\n",
"In jedem Fall halbieren wir damit den Suchraum. Im Fall unserer Wortliste mit 10000 Wörtern benötigen wir höchstens 13 Schritte, um das gesuchte Wort zu finden oder festzustellen, dass die Liste das Wort nicht enthält. \n",
"\n",
"Schreiben Sie eine Funktion `binary_search` die eine sortierte Liste sowie ein Wort als Argumente erwartet und `True` zurückgibt, falls das Wort in der Liste enthalten ist, ansonsten `False`.\n",
"\n",
"Alternativ können Sie auch die [Dokumentation für das Modul `bisect`](https://docs.python.org/3.5/library/bisect) lesen und dieses verwenden. Eine Lösung finden Sie hier: http://thinkpython2.com/code/inlist.py"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def binary_search(t, w):\n",
" # Implementieren Sie hier die Funktion\n",
"\n",
"# Hinweis: Sie müssen die Liste sortieren, damit \n",
"# binary_search funktioniert. Dies geht mittels\n",
"# der Funktion sort - siehe help(list.sort)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 11\n",
"Zwei Wörter sind ein \"umgekehrtes Paar\" (*reverse pair*), wenn jedes Wort rückwärts gelesen das jeweils andere ergibt (wie bei \"LAGER\" und \"REGAL\"). Schreiben Sie ein Programm, welches alle umgekehrten Paare in unserer Wortliste findet. (Ignorieren Sie dabei wieder Groß- und Kleinschreibung.) Eine Lösung finden Sie hier: http://thinkpython2.com/code/reverse_pair.py\n",
"\n",
"(*Hinweis: Sie werden einige doppelte Paare finden, was daran liegt, dass in top10000.txt Groß- und Kleinschreibung unterschieden wird.*)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier Ihr Programm\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 12\n",
"Zwei Wörter \"greifen ineinander\" (*interlock*), wenn sich durch abwechselndes Hinzufügen eines Buchstabens aus beiden Wörtern ein neues Wort ergibt. Beispielsweise greifen \"Mai\" und \"im\" ineinander und bilden das Wort \"Miami\". \n",
"\n",
"\n",
"\n",
"1. Schreiben Sie ein Program, welches alle Wortpaare findet, die ineinandergreifen. Hinweis: durchlaufen Sie nicht alle möglichen Wortpaare!\n",
"2. Gibt es Wörter, die dreifach ineinandergreifen; das heißt, jeder dritte Buchstabe ergibt ein Wort, beginnend mit dem ersten, zweiten oder dritten Buchstaben? (*Leider ist unsere Wortliste mit 10000 Wörtern recht kurz ... als einziges einigermaßen sinnvolles Beispiel ergibt sich \"bekommt\", welches die \"Wörter\" \"Bot\", \"EM\", und \"km\" enthält.*)\n",
"\n",
"(Diese Aufgabe wurde durch ein Beispiel auf http://puzzlers.org/ inspiriert, eine Lösung finden Sie hier: http://thinkpython2.com/code/interlock.py)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Implementieren Sie hier das Programm"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). \n",
"Klicken Sie dazu oben links auf das Disketten-Icon und nutzen Sie beispielsweise einen USB-Stick, E-Mail, Google Drive, Dropbox oder Ihre [HU-Box](https://box.hu-berlin.de/). "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"Herzlichen Glückwunsch! Sie haben das 10. Kapitel geschafft. Weiter geht es in [11: assoziative Felder](seminar11.ipynb)."
]
}
],
"metadata": {
"language_info": {
"name": "python",
"pygments_lexer": "ipython3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}