priority-queues.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Priority Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In diesem Notebook werden wir zwei einfache Implementationen des ADTs *Priority Queue* anschauen. Diese Implementationen dienen nur zur Illustration des Prinzips, und zur Veranschaulichung, dass auch hier verschiedene Implementationen verschiedene Kompromisse machen. Für eine praktische Implementation werden wir später einen Heap verwenden.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zwei einfache Implementationen mittels Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### Implementation mit unsortiertem Array\n",
    "\n",
    "Die erste Implementation verwendet ein einfaches, unsortiertes (dynamisches) Array. Bei dieser Implementation ist die ```insert``` Methode sehr effizient. Die Hauptarbeit passiert, wenn die Methode ```max``` oder ```delmax``` aufgerufen wird. In diesem Fall wird das grösste Element gesucht und mit dem letzten Element vertauscht. Damit kann es einfach zurückgegeben werden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MaxPQUnorderedArray:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "    \n",
    "    def insert(self, k):\n",
    "        self._data.append(k)\n",
    "    \n",
    "    def max(self):\n",
    "        self._largestToEnd()\n",
    "        return self._data[-1] #[-1] greift auf letztes Element zu\n",
    "            \n",
    "    def delMax(self):\n",
    "        self._largestToEnd()\n",
    "        return self._data.pop()\n",
    "    \n",
    "    def _largestToEnd(self):\n",
    "        if len(self._data) == 0:\n",
    "            return\n",
    "        \n",
    "        maxElem = self._data[0]            \n",
    "        maxIndex = 0\n",
    "        for i, d in enumerate(self._data):\n",
    "            if (maxElem < d):\n",
    "                maxElem = self._data[i]\n",
    "                maxIndex = i\n",
    "        self._data[maxIndex], self._data[-1] = self._data[-1], self._data[maxIndex]\n",
    "        \n",
    "    \n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return len(self._data) == 0\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self._data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implementation mit sortiertem Array\n",
    "\n",
    "In dieser zweiten Implementation, passiert die Hauptarbeit in der Methode ```insert```. Unsere Implementation stellt sicher, dass das neue Element jeweils an die richtige Position im Array eingefügt wird. Im Vergleich zur vorherigen Methode, sind dafür die Methoden ```max``` und ```delMax``` sehr effizient."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MaxPQOrderedArray:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._data = []\n",
    "    \n",
    "    def insert(self, k):\n",
    "        \n",
    "        # Suche im sortierten Array data die Position vom neuen Element\n",
    "        idx = 0\n",
    "        while (idx < len(self._data) and self._data[idx] < k):            \n",
    "            idx += 1\n",
    "        self._data.insert(idx, k)        \n",
    "        \n",
    "    def max(self):\n",
    "        if self.isEmpty():\n",
    "            return None\n",
    "        else:\n",
    "            return self._data[-1]\n",
    "            \n",
    "    def delMax(self):\n",
    "        return self._data.pop()\n",
    "        \n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return len(self._data) == 0\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self._data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Komplexität"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun schauen wir uns die Laufzeit der beiden Implementationen an. Wir nutzen dafür wieder das Python Modul ```timeit``` welches wir schon früher kennengelernt haben. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die folgenden beiden Hilfsfunktionen fügen jeweils $N$-Elemente hinzu oder entfernen diese aus der Queue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertNElements(pq, N):\n",
    "    for i in range(0, N):\n",
    "        pq.insert(random.randint(0, N))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeLargestNElements(pq, N):\n",
    "    for i in range(0, N):\n",
    "        pq.delMax()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir können die Tests nun ausführen. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "insert ordered  17.053412966999986\n",
      "insert unordered 0.03697726100000409\n",
      "removeLargest ordered 0.007038775000012265\n",
      "removeLargest unordered 10.458904170999972\n"
     ]
    }
   ],
   "source": [
    "orderedPQ = MaxPQOrderedArray()\n",
    "unorderedPQ = MaxPQUnorderedArray()\n",
    "\n",
    "print(\"insert ordered \", timeit.timeit(lambda: insertNElements(orderedPQ, 10000), number = 1))\n",
    "print(\"insert unordered\", timeit.timeit(lambda: insertNElements(unorderedPQ, 10000), number = 1))\n",
    "\n",
    "# ACHTUNG: Wir nutzen hier aus, dass orderedPQ und unorderedPQ bereits wegen dem vorigen Experiment gefüllt sind\n",
    "print(\"removeLargest ordered\", timeit.timeit(lambda: removeLargestNElements(orderedPQ, 10000), number = 1))\n",
    "print(\"removeLargest unordered\", timeit.timeit(lambda: removeLargestNElements(unorderedPQ, 10000), number = 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wie erwartet ist das Einfügen sehr viel teurer, wenn wir für die Implementation ein geordnetes Array nutzen. Dafür wird das Entfernen des grössten Elements entsprechend effizienter. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Beispielanwendung von Priority-Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine typische Beispielanwendung ist, dass man aus einem sehr grossen Datenstrom die extremsten Elemente extrahieren möchte. \n",
    "\n",
    "In unserem Beispiel besteht der Datenstrom aus normalverteilten Zufallswerten. Wir schreiben einen Client, der die $M$ kleinsten Werte, die generiert wurden, ausgibt. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die folgende Funktion generiert einen Stream von $N$ normalverteilen Zufallszahlen. Das Python Keyword yield stellt hier sicher, dass die Zahlen jeweils einzeln generiert werden, so dass wir nicht eine grosse Liste von Zahlen speichern müssen. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def numberGen(N):\n",
    "    num = 0\n",
    "    while num < N:\n",
    "        yield random.gauss(0, 1)\n",
    "        num += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0318195835626296\n"
     ]
    }
   ],
   "source": [
    "n = numberGen(100)\n",
    "for i in range(0, 1):\n",
    "    print(next(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Da wir hier nur eine MaxPQ zur Verfügung haben, ist es etwas einfacher die kleinsten Elemente zu suchen. Wir speichern jedes Element in der PriorityQueue, lassen aber nur jeweils die $M$ grössten Elemente in der Queue. Die anderen werden sofort wieder entfernt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def printSmallestNumbers(M, N):\n",
    "    pq = MaxPQUnorderedArray()\n",
    "    for number in numberGen(N):\n",
    "\n",
    "        pq.insert(number) \n",
    "        if pq.size() > M:\n",
    "            pq.delMax() \n",
    "        \n",
    "    while not pq.isEmpty():\n",
    "        print(pq.delMax())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In unserer Anwendung können wir nun mit diesem Algorithmus ermitteln, wie extrem die Werte, die zufällig von einer Standard-Normalverteilung gezogen werden, eigentlich werden können. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-4.3108543565987985\n",
      "-4.398257551380942\n",
      "-4.46868371509699\n",
      "-4.840967723274965\n",
      "-5.049624820080376\n"
     ]
    }
   ],
   "source": [
    "printSmallestNumbers(5, 1000000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir sehen, dass auch wenn wir 1 Million zufällige Elemente ziehen, kaum eines extremer als -5 ist. \n",
    "\n",
    "*Anmerkung für Statistik-Interessierte:  Unter der Normalverteilung sind, wie wir sehen, extreme Werte sehr unwahrscheinlich. Deshalb ist die Normalverteilung kein gutes Modell für Prozesse, bei denen auch ab und zu mal ein grösserer Wert vorkommt.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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": 1
}