seminar11.ipynb

{
 "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 den Operatoren aus diesem Kapitel können wir ganz leicht das Verfahren zur Umwandlung einer Dezimalzahl in ihre Binärdarstellung implementieren:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 11 Assoziative Datenfelder \n",
    "\n",
    "Dieses Kapitel behandelt einen weiteren eingebauten Datentyp, die sogenannten *assoziativen Datenfelder* (im Englischen *map, dictionary* oder *associative array* genannt). Assoziative Datenfelder sind eines der besten Feature von Python; sie sind die Bausteine vieler effizienter und eleganter Algorithmen. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 11.1 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 Zalen sein, in einem assoziativen Datenfeld können sie von (fast) jedem Typ sein.\n",
    "\n",
    "Ein assoziatives Datenfeld enthält eine Sammlung von Indexen, die **Schlüssel** (*keys*) genannt werden und eine Sammlung von **Werten** (*values*). Jeder Schlüssel ist mit genau einem Wert assoziiert. Diese Verknüpfung zwischen Schlüssel und Wert wird **Schlüssel-Wert-Paar** (*key-value pair*) oder manchmal auch **Eintrag** (*item*) genannt.\n",
    "\n",
    "Mathematisch ausgedrückt repräsentiert ein assoziatives Datenfeld eine **Abbildung** (*mapping*) der Schlüssel auf die Werte. Wir können also sagen, dass jeder Schlüssel auf genau einen Wert \"abgebildet\" wird. Als Beispiel bauen wir ein assoziatives Datenfeld, welches deutsche auf spanische Wörter abbildet; sowohl die Schlüssel als auch die Werte sind also Zeichenketten.\n",
    "\n",
    "Die Funktion `dict` erzeugt ein neues assoziatives Datenfeld ohne Einträge. Da `dict` der Name einer eingebauten Funktion ist, sollten wir vermeiden, sie als Variablenname zu verwenden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa = dict()\n",
    "deu2spa"
   ]
  },
  {
   "cell_type": "markdown",
   "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,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa['eins'] = 'uno'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diese Zeile erzeugt einen Eintrag, der den Schlüssel `'eins'` auf den Wert `'uno'` abbildet. Wenn wir das assoziative Datenfeld nochmal ausgeben, sehen wir ein Schlüssel-Wert-Paar mit einem Doppelpunkt zwischen Schlüssel und Wert: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dieses Ausgabe-Format ist auch ein Eingabe-Format! Wir können beispielsweise ein neues assoziatives Datenfeld mit drei Einträgen folgendermaßen erzeugen: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa = {'eins' : 'uno', 'zwei' : 'dos', 'drei' : 'tres'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn wir `deu2spa` ausgeben, sind wir aber eventuell etwas überascht:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Reihenfolge der Schlüssel-Wert-Paare ist nicht unbedingt die gleiche geblieben und auf unterschiedlichen Computern könnten wir unterschiedliche Reihenfolgen erhalten. Im allgemeinen ist die Reihenfolge der Einträge in einem assoziativen Datenfeld nicht vorhersagbar. (Die technischen Hintergründen werden später erklärt.)\n",
    "\n",
    "Das ist jedoch kein Problem, denn die Elemente eines assoziativen Datenfeldes werden nicht mit ganzen Zahlen indexiert. Stattdessen verwenden wir die Schlüssel, um die entsprechenden Werte abzurufen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa['zwei']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Schlüssel `'eins'` wird also stets auf den Wert `'dos'` abgebildet, so dass die Reihenfolge der Einträge keine Rolle spielt.\n",
    "\n",
    "Wenn ein Schlüssel nicht im assoziativen Datenfeld enthalten ist, erhalten wir eine Ausnahmemeldung (*exception*):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deu2spa['vier']"
   ]
  },
  {
   "cell_type": "markdown",
   "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,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(deu2spa)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Operator `in` funktioniert ebenfalls mit assoziativen Datenfeldern; er sagt uns, ob etwas als *Schlüssel* in einem assoziativen Datenfeld enthalten ist (es reicht nicht, als *Wert* enthalten zu sein!):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'eins' in deu2spa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'uno' in deu2spa"
   ]
  },
  {
   "cell_type": "markdown",
   "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,
   "metadata": {},
   "outputs": [],
   "source": [
    "vals = deu2spa.values()\n",
    "'uno' in vals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Operator `in` nutzt unterschiedliche Algorithmen für Listen und assoziative Datenfelder. In Listen durchsucht er die Elemente der Liste der Reihenfolge nach, wie in [Abschnitt 8.6](seminar08.ipynb#8.6-Suche) beschrieben. Wenn die Liste größer wird, dauert die Suche entsprechend länger. \n",
    "\n",
    "Für assoziative Datenfelder nutzt Python eine Datenstruktur, die **Hash-Tabelle** 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. In [Abschnitt B.4](seminarb.ipynb#B.4-Hash-Tabellen) wird erklärt, wie das möglich ist, aber die Erklärung ergibt für Sie vermutlich erst Sinn, nachdem Sie ein paar mehr Kapitel durchgearbeitet haben.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Speichern](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/floppy.png) Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). 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": [
    "![Smiley](https://upload.wikimedia.org/wikipedia/commons/3/3e/Cool-smiley.svg)\n",
    "\n",
    "Herzlichen Glückwunsch! Sie haben das 5. Kapitel geschafft. Weiter geht es in [6: Ergebnisreiche Funktionen](seminar06.ipynb)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}