08-fallstudie-listen-etc-filled.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "360e0bba",
   "metadata": {},
   "source": [
    "# Repetition: Zusammengesetzte Datentypen"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "baec4206",
   "metadata": {},
   "source": [
    "### Übersicht\n",
    "\n",
    "#### Listen, Tupel und Dictionaries\n",
    "\n",
    "| Typ | Verwaltet | Veränderbarkeit | Indizierung | \n",
    "| ----|-----------|-----------------|-------------|\n",
    "| Tupel| Fixe Anzahl Werte | Unveränderlich | Indiziert durch Zahl|\n",
    "| Liste | Variable Anzahl Werte | Veränderlich |Indiziert durch Zahl |\n",
    "| Dictionary | Variable Anzahl Werte | Veränderlich | Indiziert durch beliebigen Wert |\n",
    "\n",
    "\n",
    "#### Klassen \n",
    "\n",
    "Flexibler, eigener Datentyp mit eigenen Operationen. Jede der obigen Typen kann mittels Klassen implementiert werden. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "521425b1",
   "metadata": {},
   "source": [
    "### Objekte erstellen"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e31723e8",
   "metadata": {},
   "source": [
    "Tupel:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "145f0046",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = (\"first\", \"second\", \"third\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5bf5ef9",
   "metadata": {},
   "source": [
    "Liste:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53955940",
   "metadata": {},
   "outputs": [],
   "source": [
    "l = [\"first\", \"second\", \"third\"]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c233755b",
   "metadata": {},
   "source": [
    "Dictionary:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd89ebe8",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {\"key1\" : \"first\", \"key2\" : \"second\", \"key3\" : \"third\"}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "132a4fbc",
   "metadata": {},
   "source": [
    "### Elemente ansprechen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "61b6790c",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(t[0], t[1], t[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e02b16a5",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(l[0], l[1], l[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7bc10a5d",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(d[\"key1\"], d[\"key2\"], d[\"key3\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72f54517",
   "metadata": {},
   "source": [
    "### Elemente verändern"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f19d9dfe",
   "metadata": {},
   "source": [
    "Tupel (nicht möglich):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bff99bf1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Elemente von Tupeln sind unveränderlich\n",
    "t[0] = \"1st\"\n",
    "print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1907fa5",
   "metadata": {},
   "source": [
    "Listen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "91e17686",
   "metadata": {},
   "outputs": [],
   "source": [
    "l[0] = \"1st\"\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c00318c",
   "metadata": {},
   "source": [
    "Dictionaries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "54b61a04",
   "metadata": {},
   "outputs": [],
   "source": [
    "d[\"key1\"] = \"1st\"\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edbc3536",
   "metadata": {},
   "source": [
    "#### Mehrere Werte an Variablen zuweisen (unpacking)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05cea051",
   "metadata": {},
   "source": [
    "Tupel:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c7ed8c53",
   "metadata": {},
   "outputs": [],
   "source": [
    "#(Variable1, Variable2, Variable3) = (Wert1, Wert2, Wert3)\n",
    "(a, b, c) = t\n",
    "print(a, b, c)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "607ab667",
   "metadata": {},
   "source": [
    "Listen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "00520cff",
   "metadata": {},
   "outputs": [],
   "source": [
    "(a, b, c) = l\n",
    "print(a, b, c)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f31cd01",
   "metadata": {},
   "source": [
    "Dictionaries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ff52f475",
   "metadata": {},
   "outputs": [],
   "source": [
    "((key1, value1), (key2, value2), (key3, value3)) = d.items()\n",
    "print(key1, value1, key2, value2, key3, value3)\n",
    "(a, b, c) = d.values()\n",
    "print(a, b, c)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "691b9730",
   "metadata": {},
   "source": [
    "### Elemente hinzufügen"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bdcb1517",
   "metadata": {},
   "source": [
    "Tupel (nicht möglich)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9eaa375f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# append Methode ist nicht definiert\n",
    "t.append(\"fourth\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8377df45",
   "metadata": {},
   "source": [
    "Liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a38aba7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "l.append(\"fourth\")\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01530c58",
   "metadata": {},
   "source": [
    "Dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e6a684b0",
   "metadata": {},
   "outputs": [],
   "source": [
    "d[\"key4\"] = \"fourth\"\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50dc68d6",
   "metadata": {},
   "source": [
    "### Iterieren"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00b36a34",
   "metadata": {},
   "source": [
    "Tupel"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8d4353fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "for element in t:\n",
    "    print(element)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b329eb0",
   "metadata": {},
   "source": [
    "Liste"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f8084038",
   "metadata": {},
   "outputs": [],
   "source": [
    "for element in l:\n",
    "    print(element)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0d3a290",
   "metadata": {},
   "source": [
    "Dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "421a8e73",
   "metadata": {},
   "outputs": [],
   "source": [
    "for element in d:\n",
    "    print(element)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a2f4ee2a-1f0c-45bf-b0ea-486c516115f2",
   "metadata": {},
   "outputs": [],
   "source": [
    "for key in d.keys():\n",
    "    print(d[key])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "667aecbc-923a-402c-8fb0-562bc7858e85",
   "metadata": {},
   "outputs": [],
   "source": [
    "for element in d.values():\n",
    "    print(element)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a48e8185",
   "metadata": {},
   "outputs": [],
   "source": [
    "for keyAndValue in d.items():\n",
    "    print(keyAndValue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "912532e5",
   "metadata": {},
   "outputs": [],
   "source": [
    "for (key, Value) in d.items():\n",
    "    print(Value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "793b30c9-8f6e-4ed6-81ea-69bf3f6716c3",
   "metadata": {},
   "source": [
    "## Exkurs: suchen in sortierten Listen\n",
    "\n",
    "Um zu prüfen, ob eine Zahl in einer aufsteigend sortierten Liste von Zahlen vorkommt, gibt es mehrere Möglichkeiten. Einige davon sind jedoch schneller, wie wir sehen werden. Für unsere Experimente generieren wir zuerst eine (grosse) Liste mit zufälligen Zahlen, und sortieren diese."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "96404e3f-65de-4db5-866f-57f9e91b4011",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "length = 1000000\n",
    "l = []\n",
    "\n",
    "for i in range(length):\n",
    "    num = random.randint(0,10*length)\n",
    "    l.append(num)\n",
    "\n",
    "l = sorted(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46d82bfe-7ce8-454b-8e96-9057c23c9184",
   "metadata": {},
   "source": [
    "Wir möchten nun eine Funktion schreiben, die testet, ob die Zahl ```a``` in der Liste ```l```vorkommt.\n",
    "\n",
    "#### Miniübung\n",
    "* Wie würden Sie das machen?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f290f5e7-2418-477c-a35c-a2407b4b7e80",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Lösung 1:\n",
    "def sequential_in(a, l):\n",
    "    for i in range(len(l)):\n",
    "        if l[i] == a:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "# Lösung 2:\n",
    "def binary_in(a, l):\n",
    "    start = 0\n",
    "    end = len(l)-1\n",
    "    while start < end:\n",
    "        index = (start + end) // 2\n",
    "        if l[index] == a:\n",
    "            return True\n",
    "        if l[index] > a:\n",
    "            end = index - 1\n",
    "        if l[index] < a:\n",
    "            start = index + 1\n",
    "    return False\n",
    "\n",
    "# Lösung 3:\n",
    "# das Schlüsselwort 'in' macht genau das\n",
    "\n",
    "testlist = [1, 2, 4, 5, 7, 8, 9, 12, 15]\n",
    "print(sequential_in(12, testlist))\n",
    "print(sequential_in(3, testlist))\n",
    "print(binary_in(12, testlist))\n",
    "print(binary_in(3, testlist))\n",
    "print(12 in testlist)\n",
    "print(3 in testlist)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0003f0e8-9566-44f2-9acd-663e5fd5526b",
   "metadata": {},
   "source": [
    "Wir möchten nun testen, wie schnell unsere Lösungen sind. Dazu können wir mit dem Befehl ```%%time``` die Zeit messen, die eine Zelle benötigt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "73407c63-54c8-4834-97d2-2be5aed4c99a",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "print(sequential_in(999,l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fd63c413-11d6-4d66-9125-d30149cefdde",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "print(binary_in(999,l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "089013c1-14ed-4437-990c-cbe3aacf894e",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "print(999 in l)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35b1987f-9f64-4c23-b4d1-38e5868c62fb",
   "metadata": {},
   "source": [
    "Wir sehen, dass die Binärsuche deutlich schneller ist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f2251694-790f-45c0-af91-5771afc3d543",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.8.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}