fundamental-adts.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fundamentale Datentypen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Implemetieren von Stack, Queues und Bags geht sehr einfach mithilfe von verketteten Listen. Verkettete Listen sind hier effizient, weil die grundlegenden Operationen ```add```, ```push```, ```pop```, ```enqueue```, ```dequeue``` jeweils nur am Anfang oder Ende der Liste Elemente hinzufügen oder löschen. Für diese Datenstrukturen haben die verketteten Listen also einen Vorteil gegenüber dynamischen Arrays. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir beginnen mit der Implementation des Stacks. Die wichtigsten Operationen sind ```push``` und ```pop```. Eine einfache und effiziente Implementationsstrategie für diese beiden Methoden ist jeweils beim ```push``` ein Element am Anfang der Liste einzufügen, und mit ```pop``` ein Element vom Anfang der Liste zu entfernen. Beides geht in konstanter Zeit und ist einfach zu implementieren. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "        \n",
    "    class Node:\n",
    "        \n",
    "        def __init__(self, value, next = None):\n",
    "            self.value = value\n",
    "            self.next = next\n",
    "            \n",
    "    def __init__(self):\n",
    "        self.first = None\n",
    "        self.numElements = 0\n",
    "    \n",
    "    def push(self, item):\n",
    "        if self.first == None:\n",
    "            self.first = Stack.Node(item)\n",
    "        else:\n",
    "            self.first = Stack.Node(item, self.first)\n",
    "        self.numElements += 1\n",
    "        \n",
    "    def pop(self):                \n",
    "        if self.first == None:\n",
    "            raise Exception(\"popping from empty stack\")\n",
    "        else:\n",
    "            self.numElements -= 1\n",
    "            value = self.first.value\n",
    "            self.first = self.first.next\n",
    "            return value\n",
    "        \n",
    "    def size(self):\n",
    "        return self.numElements\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.size() == 0\n",
    "   \n",
    "\n",
    "    # Diese Methode wird verwendet, um den Inhalt der Liste in den \n",
    "    # Jupyter-notebooks anzeigen zu können. Gehört nicht zum eigentlichen \n",
    "    # Interface. Die Implementation entspricht einer einfachen Traversierung \n",
    "    # der Liste.\n",
    "    def __repr__(self):\n",
    "        outstr = \"[\" \n",
    "        currentNode = self.first\n",
    "        while currentNode != None:\n",
    "            outstr += str(currentNode.value) + \" \"\n",
    "            currentNode = currentNode.next\n",
    "        return outstr + \"]\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Client"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stacks werden immer dann gebraucht, wenn man das letzte einkommende Element als erstes verarbeiten muss. Sie sind aber auch nützlich, um Elemente umzusortieren, wie in diesem Beispiel gezeigt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "testdata = [\"are\", \"you\", \"as\", \"happy\", \"as\", \"I\", \"am\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mittels der Push Methode werden die Elemente zum Stack hinzugefügt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "stack = Stack()\n",
    "for datum in testdata:\n",
    "    stack.push(datum)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diese können wir dann mittels der ```pop``` Methode wieder vom Stapel löschen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "am\n",
      "I\n",
      "as\n",
      "happy\n",
      "as\n",
      "you\n",
      "are\n"
     ]
    }
   ],
   "source": [
    "while not stack.isEmpty():\n",
    "    print(stack.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Um zu verstehen, wie die interne Repräsentation der Liste in jedem Schritt aussieht, können wir diese nach jedem push Ausgeben. Dies funktioniert, weil wir die spezielle Methode ```__repr__``` implementiert haben. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[are ]\n",
      "[you are ]\n",
      "[as you are ]\n",
      "[happy as you are ]\n",
      "[as happy as you are ]\n",
      "[I as happy as you are ]\n",
      "[am I as happy as you are ]\n"
     ]
    }
   ],
   "source": [
    "stack = Stack()\n",
    "for datum in testdata:\n",
    "    stack.push(datum)  \n",
    "    print(stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Implementation von einer Queue ist ganz ähnlich wie die des Stacks. Wir müssen aber aufpassen, dass wir bei der ```enqueue``` Methode die Elemente immer am Ende anfügen, damit wir vom Anfang entfernen können (warum?). Wir brauchen also auch einen Zeiger auf das letzte Element, damit wir effizient am Ende der Liste einfügen können."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    \n",
    "    class Node:        \n",
    "        def __init__(self, value, next = None):\n",
    "            self.value = value\n",
    "            self.next = next\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.first = None\n",
    "        self.last = None\n",
    "        self.numberOfElements = 0\n",
    "        \n",
    "    def enqueue(self, value):\n",
    "        if self.last == None:\n",
    "            self.first = Queue.Node(value)\n",
    "            self.last = self.first\n",
    "        else:\n",
    "            self.last.next = Queue.Node(value)\n",
    "            self.last = self.last.next\n",
    "        self.numberOfElements += 1\n",
    "\n",
    "    \n",
    "    def dequeue(self):  \n",
    "        value = None\n",
    "        if self.first == None:\n",
    "            value = None\n",
    "        else:\n",
    "            value = self.first.value\n",
    "            self.first = self.first.next        \n",
    "            \n",
    "            # Letztes Element wurde entfernt. Wir müssen den \n",
    "            # Last-Pointer noch entsprechend invalidieren\n",
    "            if self.first == None:\n",
    "                self.last = None\n",
    "        self.numberOfElements -= 1\n",
    "        return value\n",
    "    \n",
    "    def size(self):\n",
    "        return self.numberOfElements\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.size() == 0\n",
    "    \n",
    "    def __repr__(self):\n",
    "        outstr = \"[\" \n",
    "        currentNode = self.first\n",
    "        while currentNode != None:\n",
    "            outstr += str(currentNode.value) + \" \"\n",
    "            currentNode = currentNode.next\n",
    "        return outstr + \"]\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Client"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Warteschlangen sind immer dann sinnvoll, wenn wir Elemente speichern wollen, die relative Reihenfolge der Elemente aber beibehalten wollen. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "xs = [\"the\", \"order\", \"of\", \"the\", \"elements\", \"is\", \"important\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mittels der enqueue Methode werden Daten zur Warteschlange hinzugefügt. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "item: the\n",
      "item: order\n",
      "item: of\n",
      "item: the\n",
      "item: elements\n",
      "item: is\n",
      "item: important\n"
     ]
    }
   ],
   "source": [
    "queue = Queue()\n",
    "for x in xs:\n",
    "    print(\"item: \" +str(x))\n",
    "    queue.enqueue(x)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the\n",
      "order\n",
      "of\n",
      "the\n",
      "elements\n",
      "is\n",
      "important\n"
     ]
    }
   ],
   "source": [
    "while not queue.isEmpty():\n",
    "    print(queue.dequeue())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Bag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bei der Klasse Bag ist die Reihenfolge der Elemente nicht definiert. Wir sind also frei, ob wir lieber am Ende oder am Anfang einfügen. Wir haben uns in der folgenden Implementation für den Anfang entschieden, da dies etwas einfacher zu implementieren ist.  Beachten Sie, dass wir hier zusätzlich einen Iterator implementiert haben, um die Elemente im Bag zu traversieren. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Bag:\n",
    "        \n",
    "    class Node:\n",
    "        \n",
    "        def __init__(self, value, next = None):            \n",
    "            self.value = value\n",
    "            self.next = next\n",
    "    \n",
    "    class Iterator:\n",
    "        \n",
    "        def __init__(self, bag):\n",
    "            self.currentElement = bag.first\n",
    "        \n",
    "        def next(self):\n",
    "            if self.currentElement != None:\n",
    "                value = self.currentElement.value\n",
    "                self.currentElement = self.currentElement.next\n",
    "                return value\n",
    "            else:\n",
    "                return None\n",
    "                \n",
    "        def hasNext(self):\n",
    "            return self.currentElement != None\n",
    "        \n",
    "\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.first = None\n",
    "        self.numElements = 0\n",
    "    \n",
    "    def add(self, item):\n",
    "        self.numElements += 1\n",
    "        if self.first == None:\n",
    "            self.first = Bag.Node(item)\n",
    "        else:\n",
    "            self.first = Bag.Node(item, self.first)\n",
    "    \n",
    "        \n",
    "    def size(self):\n",
    "        return self.numElements\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.size() == 0    \n",
    "    \n",
    "\n",
    "    def iterator(self):\n",
    "        return Bag.Iterator(self)       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Client"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine typische Anwendung eines Bags ist zum Beispiel die Berechnung einer Statistik aus einer Sammlung von Daten. Für die meisten Statistiken ist die Reihenfolge der Daten irrelevant. \n",
    "\n",
    "In unserem Beispiel implementieren wir uns einen Client, der den Mittelwert einer Sammlung von Zahlen berechnet."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Testdaten generieren"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir simulieren uns Testdaten, indem wir 1000 zufällige normalverteilte Zahlen (mit mean 1 und Varianz 4) generieren. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "bag = Bag()\n",
    "for i in range(0, 10000):\n",
    "    bag.add(random.gauss(1.0, 4.0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Mittelwert approximieren"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun können wir uns das Stichprobenmittel mit der Formel $\\frac{1}{n} \\sum_{i=1}^n v_i$, wobei $v_i$ der $i-$te Wert ist, berechnen. Beachten Sie, dass wir hier einfach einmal über alle Werte iterieren müssen. Die Reihenfolge der Elemente ist nicht von Bedeutung. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum = 0.0\n",
    "it = bag.iterator()\n",
    "while (it.hasNext()):\n",
    "    sum = sum + it.next()\n",
    "mean = sum / bag.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0345076228730181\n"
     ]
    }
   ],
   "source": [
    "print(mean)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Übung:\n",
    "\n",
    "* Experimentieren Sie mit diesen Implementationen und versuchen Sie diese zu verstehen. \n",
    "* Fügen Sie falls nötig an den richtigen Stellen mit dem Befehl ```print``` Ausgaben hinzu, damit Sie nachverfolgen können, was in jedem Schritt passiert. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}