Generator.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Obsah dnesnej prednasky\n",
    "## 1. Iterator a generator\n",
    "## 2. Lenive vyhodnocovanie (Lazy evaluation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Iterator a Generator\n",
    "\n",
    "inspirovane http://www.python-course.eu/python3_generators.php"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Iterator\n",
    "* je objekt, ktory ma funkciu `__next__` a funkciu `__iter__`, ktora vracia `self`\n",
    "* je to vseobecnejsi pojem ako generator\n",
    "* da sa pouzivat na iterovanie cez kolekciu bez toho, aby sme vedeli aka je jej vnutorna struktura. Staci definovat funkciu `__next__`. Podobny koncept sa da najst vo vela jazykoch. Napriklad aj v Jave."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Iterator sa napriklad implicitne pouziva pri prechadzani kolekcii for cyklom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "location: Paris\n",
      "location: Berlin\n",
      "location: Hamburg\n",
      "location: Frankfurt\n",
      "location: London\n",
      "location: Vienna\n",
      "location: Amsterdam\n",
      "location: Den Haag\n"
     ]
    }
   ],
   "source": [
    "cities = [\"Paris\", \"Berlin\", \"Hamburg\", \"Frankfurt\", \"London\", \"Vienna\", \"Amsterdam\", \"Den Haag\"]\n",
    "for location in cities:\n",
    "    print(\"location: \" + location)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['__class__',\n",
       " '__delattr__',\n",
       " '__dir__',\n",
       " '__doc__',\n",
       " '__eq__',\n",
       " '__format__',\n",
       " '__ge__',\n",
       " '__getattribute__',\n",
       " '__gt__',\n",
       " '__hash__',\n",
       " '__init__',\n",
       " '__iter__',\n",
       " '__le__',\n",
       " '__length_hint__',\n",
       " '__lt__',\n",
       " '__ne__',\n",
       " '__new__',\n",
       " '__next__',\n",
       " '__reduce__',\n",
       " '__reduce_ex__',\n",
       " '__repr__',\n",
       " '__setattr__',\n",
       " '__setstate__',\n",
       " '__sizeof__',\n",
       " '__str__',\n",
       " '__subclasshook__']"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dir(cities.__iter__())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'list_iterator'>\n",
      "<class 'list_iterator'>\n",
      "Paris\n"
     ]
    }
   ],
   "source": [
    "print(type(cities.__iter__()))\n",
    "print(type(cities.__iter__().__iter__()))\n",
    "print(cities.__iter__().__next__())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Rovnako sa pouzivaju iteratory aj pri prechadzani inych kolekcii"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The capital city of France is Paris\n",
      "The capital city of Austria is Vienna\n",
      "The capital city of Switzerland is Bern\n",
      "The capital city of Germany is Berlin\n",
      "The capital city of Netherlands is Amsterdam\n"
     ]
    }
   ],
   "source": [
    "capitals = { \"France\":\"Paris\", \"Netherlands\":\"Amsterdam\", \"Germany\":\"Berlin\", \"Switzerland\":\"Bern\", \"Austria\":\"Vienna\"}\n",
    "for country in capitals:\n",
    "    print(\"The capital city of \" + country + \" is \" + capitals[country])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Generator\n",
    "* kazdy generator objekt je iterator, ale nie naopak\n",
    "* tento pojem sa pouziva na pomenovanie funkcie (generator funkcia) ako aj jej navratovej hodnoty (generator objekt)\n",
    "* generator objekt sa vytvara volanim funkcie (generator funkcie), ktora pouziva `yield`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Generator pouziva vyraz `yield` na zastavenie vykonavania a na vratenie hodnoty\n",
    "\n",
    "* Vykonavanie sa spusta folanim funkcie `next()` (alebo metody `__next__()`)\n",
    "* Dalsie volanie zacina od posledneho `yield`\n",
    "* Medzi volaniami sa hodnoty lokalnych premennych uchovavaju.\n",
    "\n",
    "## Pozor, toto nieje ten isty `yield` ako je v Ruby\n",
    "* V Ruby je `yield` volanie bloku asociovaneho s metodou\n",
    "* V Ruby je nieco podobne generatorom napriklad trieda `Enumerator`\n",
    "\n",
    "[http://stackoverflow.com/questions/2504494/are-there-something-like-python-generators-in-ruby](http://stackoverflow.com/questions/2504494/are-there-something-like-python-generators-in-ruby)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def city_generator():\n",
    "    yield \"Konstanz\"\n",
    "    yield \"Zurich\"\n",
    "    yield \"Schaffhausen\"\n",
    "    yield \"Stuttgart\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "gen = city_generator()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "next(gen)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Vo vnutri generator funkcie mozem pouzivat cyklus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "cities = [\"Konstanz\", \"Zurich\", \"Schaffhausen\", \"Stuttgart\"]\n",
    "def city_generator():\n",
    "    for city in cities:\n",
    "        yield city\n",
    "gen = city_generator()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "StopIteration",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m                             Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-36-8a6233884a6c>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mnext\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mgen\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(gen)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Generator funkcia moze prijmat parametre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def city_generator(local_cities):\n",
    "    for city in local_cities:\n",
    "        yield city\n",
    "gen = city_generator([\"Konstanz\", \"Zurich\", \"Schaffhausen\", \"Stuttgart\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "StopIteration",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m                             Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-42-8a6233884a6c>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mnext\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mgen\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(gen)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Trik ako napisat generator, ktory velmi casto funguje\n",
    "\n",
    "Uloha: Mame sekvenciu cisel a chceme vytvorit pohyblivy priemer dvoch po sebe nasledujucich cisel pre celu sekvenciu.\n",
    "\n",
    "napr:\n",
    "\n",
    "sekvencie = [1,2,3,4,5]\n",
    "\n",
    "phyblivy priemer = [(0+1)/2, (1+2)/2, (2+3)/2, (3+4)/2, (4+5)/2] = [0.5, 1.5, 2.5, 3.5, 4.5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Ako by ste to napisali imperativne ak to chcete len zapisat do konzoly?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "sequence = [1,2,3,4,5]\n",
    "previous = 0\n",
    "for actual in sequence:\n",
    "    print((actual + previous) * 0.5)\n",
    "    previous = actual"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Zabalim to do funkcie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "sequence = [1,2,3,4,5]\n",
    "def moving_average(sequence):\n",
    "    previous = 0\n",
    "    for actual in sequence:\n",
    "        print((actual + previous) * 0.5)\n",
    "        previous = actual\n",
    "moving_average(sequence)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Vymenim print za `yield`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.5, 1.5, 2.5, 3.5, 4.5]\n"
     ]
    }
   ],
   "source": [
    "sequence = [1,2,3,4,5]\n",
    "def moving_average(sequence):\n",
    "    previous = 0\n",
    "    for actual in sequence:\n",
    "        yield (actual + previous) * 0.5\n",
    "        previous = actual\n",
    "print(list(moving_average(sequence)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Pomocou generatoru by sa dala napriklad spravit funkcia `map`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def map(f, seq):\n",
    "    for x in seq:\n",
    "        print(f(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def map(f, seq):\n",
    "    for x in seq:\n",
    "        yield f(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Porovnajte si ako by vyzerala implementacia `map` v python2 a python3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def map(f, seq): # V pythone 2 map vracia list, implementacia by mohla byt napriklad takato\n",
    "    result = []\n",
    "    for x in seq:\n",
    "        result.append(f(x))\n",
    "    return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def map(f, seq): # V pythone 3 map je generator a zabera konstantne mnozstvo pamati\n",
    "    for x in seq:\n",
    "        yield f(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Niektore generatory sa daju nahradit funkciou `map`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<generator object squares at 0x7f37353cafc0>\n",
      "1\n",
      "[4, 9, 16, 25, 36, 49, 64, 81]\n"
     ]
    }
   ],
   "source": [
    "a, b = 1, 10\n",
    "def squares(start, stop):\n",
    "    for i in range(start, stop):\n",
    "        yield i * i\n",
    "\n",
    "generator = squares(a, b)\n",
    "print(generator)\n",
    "print(next(generator))\n",
    "print(list(generator))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<map object at 0x7f373537ca20>\n",
      "1\n",
      "[4, 9, 16, 25, 36, 49, 64, 81]\n"
     ]
    }
   ],
   "source": [
    "generator = map(lambda i: i*i, range(a, b))\n",
    "print(generator)\n",
    "print(next(generator))\n",
    "print(list(generator))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# List comprehension tiez moze vytvarat generator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "generator = (i*i for i in range(a, b))\n",
    "print(generator)\n",
    "print(next(generator))\n",
    "print(list(generator))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Explicitny generator ma ale vacsiu vyjadrovaciu silu\n",
    "\n",
    "Nieje obmedzeny len na formu:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def generator(funkcia, iterator):\n",
    "    for i in iterator:\n",
    "        yield funkcia(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Na co je to cele dobre?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Lenive vyhodnocovanie - Lazy evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Strategie vyhodnocovania\n",
    "\n",
    "## Skratene vyhodocovanie (Short-circuit)\n",
    "## Lenive vyhodnocovanie (Lazy)\n",
    "## Netrpezlive vyhodocovanie (Eager)\n",
    "## Ciastocne vyhodocovanie (Partial)\n",
    "## Vzdialene vyhodocovanie (Remote)\n",
    "\n",
    "https://en.wikipedia.org/wiki/Evaluation_strategy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Skratene vyhodnocovanie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['1', '2']\n"
     ]
    }
   ],
   "source": [
    "pole = []\n",
    "def fun1(pole):\n",
    "    pole.append('1')\n",
    "    return False\n",
    "\n",
    "def fun2(pole):\n",
    "    pole.append('2')\n",
    "    return True\n",
    "\n",
    "if fun1(pole) or fun2(pole):\n",
    "    pass\n",
    "print(pole)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Lenive vyhodocovanie\n",
    "\n",
    "Oddaluje vyhodnocovanie az do doby, ked je to treba"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "pom = (x*x for x in range(5))\n",
    "next(pom) #prvok z generatora sa vyberie az ked ho je treba a nie pri vytvoreni generatora"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Nedockave vyhodocovanie\n",
    "Opak leniveho vyhodnotenia. Vyraz sa vyhodnoti hned ako je priradeny do premennej"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "pom = [x*x for x in range(5)]\n",
    "pom[4] # vyraz sa hned vyhodnocuje cely"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vyhody\n",
    "* programator moze kontrolovat poradie vykonavania\n",
    "* nemusi sledovat a planovat poradie vyhodnocovania\n",
    "\n",
    "## Nevyhody\n",
    "* neumoznuje vynechat vykonavanie kodu, ktory vobec nieje treba\n",
    "* neda sa vykonavat kod, ktory je v danej chvili dolezitejsi\n",
    "* programator musi organizovat kod tak, aby optimalizoval poradie vykonavanie \n",
    "\n",
    "Moderne kompilatory ale uz niektore veci vedia optimalizovat za programatora"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Vzdialene vyhodnocovanie\n",
    "\n",
    "* Vyhodnocovanie na vzdialenom pocitaci. \n",
    "* Hociaky vypoctovy model, ktory spusta kod na inom stroji.\n",
    "* Client/Server, Message passing, MapReduce, Remote procedure call (RCP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Partial evaluation\n",
    "\n",
    "* Viacero optimalizacnych strategii na to aby sme vytvorili program, ktory bezi rychlejsie ako povodny program.\n",
    "  * Napriklad predpocitavanie kodu na zaklade dat, ktore su zname uz v case kompilacie.\n",
    "  * Mamoization (Memoizacia?) - nevykonavanie (cistych) funkcii s rovnakymi vstupmi opakovane\n",
    "  * Partial application - fixovanie niektorych parametrov funkcie a vytvorenie novej s mensim poctom parametrov."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Lenive vyhodnocovanie moze zrychlit vyhodocovanie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "CPU times: user 33 µs, sys: 8 µs, total: 41 µs\n",
      "Wall time: 54.6 µs\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "print(2+2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<map object at 0x7f37353c04a8>\n",
      "CPU times: user 58 µs, sys: 0 ns, total: 58 µs\n",
      "Wall time: 66.3 µs\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "import time\n",
    "def slow_square(x):\n",
    "    time.sleep(0.2)\n",
    "    return x**2\n",
    "\n",
    "generator = map(slow_square, range(10))\n",
    "print(generator)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]\n",
      "CPU times: user 1.37 ms, sys: 348 µs, total: 1.71 ms\n",
      "Wall time: 2 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "print(list(generator))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 4, 9, 16]\n",
      "CPU times: user 2.16 ms, sys: 0 ns, total: 2.16 ms\n",
      "Wall time: 2 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "generator = map(slow_square, range(10))\n",
    "pole = list(generator)\n",
    "print(pole[:5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def head(iterator, n):\n",
    "    result = []\n",
    "    for _ in range(n):\n",
    "        result.append(next(iterator))\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 4, 9, 16]\n",
      "CPU times: user 1.71 ms, sys: 0 ns, total: 1.71 ms\n",
      "Wall time: 1 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "print(head(map(slow_square, range(10)), 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 4, 9, 16]\n",
      "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
      "Wall time: 1 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "from itertools import islice\n",
    "generator = map(slow_square, range(10000))\n",
    "print(list(islice(generator, 5)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Lenive vyhodnocovanie setri pamat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from operator import add\n",
    "from functools import reduce\n",
    "\n",
    "reduce(add, [x*x for x in range(10000000)])\n",
    "reduce(add, (x*x for x in range(10000000)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from functools import reduce\n",
    "import gc\n",
    "import os\n",
    "import psutil\n",
    "process = psutil.Process(os.getpid())\n",
    "\n",
    "def print_memory_usage():\n",
    "    print(process.memory_info().rss)\n",
    "\n",
    "counter = [0] # Toto je hnusny hack a slubujem, ze nabuduce si povieme ako to spravit lepsie. Spytajte sa ma na to! \n",
    "def measure_add(a, result, counter=counter):\n",
    "    if counter[0] % 2000000 == 0:\n",
    "        print_memory_usage()\n",
    "    counter[0] = counter[0] + 1\n",
    "    return a + result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "35061760\n",
      "441720832\n",
      "441720832\n",
      "441720832\n",
      "441720832\n",
      "441720832\n",
      "333333283333335000000\n"
     ]
    }
   ],
   "source": [
    "gc.collect()\n",
    "counter[0] = 0\n",
    "print_memory_usage()\n",
    "print(reduce(measure_add, [x*x for x in range(10000000)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "35811328\n",
      "35811328\n",
      "35811328\n",
      "35811328\n",
      "35811328\n",
      "35811328\n",
      "333333283333335000000\n"
     ]
    }
   ],
   "source": [
    "gc.collect()\n",
    "counter[0] = 0\n",
    "print_memory_usage()\n",
    "print(reduce(measure_add, (x*x for x in range(10000000))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Ani ked su funkcie povnarane do seba a kolekcia sa predava ako parameter, nikdy nieje cela v pamati\n",
    "map, filter, reduce aj list comprehension vnutorne pracuju skolekciami ako s iteratormi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "gc.collect()\n",
    "counter[0] = 0\n",
    "print_memory_usage()\n",
    "print(reduce(measure_add, map(lambda x: x*x, range(10000000))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Ked vieme, ze generator sa vyhodnocuje lenivo, tak nam nic nebrani vlozit do neho nekonecny cyklus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fibonacci():\n",
    "    \"\"\"Fibonacci numbers generator\"\"\"\n",
    "    a, b = 1, 1\n",
    "    while True:\n",
    "        yield a\n",
    "        a, b = b, a + b\n",
    "        \n",
    "f = fibonacci()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]\n"
     ]
    }
   ],
   "source": [
    "print(list(islice(f, 10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Voila, nekonecna datova struktura, ktora nezabera skoro ziadnu pamat dokedy ju nechcem materializovat celu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "list(fibonacci()) # toto netreba pustat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Vedeli by ste to pouzit na:\n",
    "* generator prvocisel?\n",
    "* citanie z velmi velkeho suboru, ktory vam nevojde do pamati?\n",
    "* citanie dat z nejakeho senzoru, ktory produkuje kludne nekonecne mnozstvo dat?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Dalo by sa to pouzit napriklad na cakanie na data\n",
    "Predstavte si, ze mate subor, do ktoreho nejaky proces zapisuje logy po riadkoch a vy ich spracovavate.\n",
    "\n",
    "Ako by ste spravili iterovanie cez riadky suboru tak, aby ste cakali na dalsie riadky a dojdete na koniec suboru?\n",
    "\n",
    "inspirovane - http://stackoverflow.com/questions/6162002/whats-the-benefit-of-using-generator-in-this-case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "%%bash\n",
    "echo -n 'log line' > log.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "log line\n"
     ]
    }
   ],
   "source": [
    "# s generatorom napriklad takto\n",
    "def read(file_name):\n",
    "    with open(file_name) as f:\n",
    "        while True:\n",
    "            line = f.readline()\n",
    "            if not line:\n",
    "                time.sleep(0.1)\n",
    "                continue\n",
    "            yield line\n",
    "\n",
    "lines = read(\"log.txt\")\n",
    "print(next(lines))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "next line\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(next(lines))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "next line\n",
      "\n",
      "next line\n",
      "\n",
      "next line\n",
      "\n",
      "next line\n",
      "\n",
      "next line\n",
      "\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-64-b5dd17cf8202>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;32mfor\u001b[0m \u001b[0mline\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mlines\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      2\u001b[0m     \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mline\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-62-bf9f113a8cae>\u001b[0m in \u001b[0;36mread\u001b[1;34m(file_name)\u001b[0m\n\u001b[0;32m      5\u001b[0m             \u001b[0mline\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mreadline\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mline\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m                 \u001b[0mtime\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0.1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      8\u001b[0m                 \u001b[1;32mcontinue\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      9\u001b[0m             \u001b[1;32myield\u001b[0m \u001b[0mline\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "for line in lines:\n",
    "    print(line)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Toto by som vedel spravit aj bez generatora ale ...\n",
    "* nemal by som oddelenu logiku cakania a spracovavania riadku\n",
    "* nevedel by som priamociaro znovupouzivat generator vzdy by som to musel kodit odznova \n",
    "  * jedine, ze by som pouzil funkciu ako parameter\n",
    "  * stale tam ale zostava problem ako vratit viacero hodnot z jednej funkcie\n",
    "* nevedel by som pekne transparentne, lenivo iterovat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "while True:\n",
    "        line = logfile.readline()\n",
    "        if not line:\n",
    "            time.sleep(0.1)\n",
    "            continue\n",
    "        print line"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Generator moze byt aj trochu zlozitejsi, napriklad rekurzivny"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "\n",
    "    def __init__(self, title, children=None):\n",
    "        self.title = title\n",
    "        self.children = children or []\n",
    "        \n",
    "tree = Node(\n",
    "    'A', [\n",
    "        Node('B', [\n",
    "            Node('C', [\n",
    "                Node('D')\n",
    "                ]),\n",
    "            Node('E'),\n",
    "            ]),\n",
    "        Node('F'),\n",
    "        Node('G'),\n",
    "        ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'B', 'C', 'D', 'E', 'F', 'G']"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def node_recurse_generator(node):\n",
    "    yield node\n",
    "    for n in node.children:\n",
    "        for rn in node_recurse_generator(n):\n",
    "            yield rn\n",
    "        \n",
    "[node.title for node in node_recurse_generator(tree)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "http://stackoverflow.com/posts/7634323/edit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Ale castokrat sa to da aj bez pouzitia rekurzie\n",
    "\n",
    "http://stackoverflow.com/questions/26145678/implementing-a-depth-first-tree-iterator-in-python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'B', 'C', 'D', 'E', 'F', 'G']"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "def node_stack_generator(node):\n",
    "    stack = deque([node])\n",
    "    while stack:\n",
    "        # Pop out the first element in the stack\n",
    "        node = stack.popleft()\n",
    "        yield node\n",
    "        # push children onto the front of the stack.\n",
    "        # Note that with a deque.extendleft, the first on in is the last\n",
    "        # one out, so we need to push them in reverse order.\n",
    "        stack.extendleft(reversed(node.children))\n",
    "        \n",
    "[node.title for node in node_stack_generator(tree)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Vedeli by ste tieto dva generatory upravit pre binarny strom?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Rekurzivny generator sa da napriklad pouzit na vyrabanie permutacii"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def permutations(items):\n",
    "    n = len(items)\n",
    "    if n==0: \n",
    "        yield []\n",
    "    else:\n",
    "        for i in range(len(items)):\n",
    "            for cc in permutations(items[:i]+items[i+1:]):\n",
    "                yield [items[i]]+cc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "red\n",
      "rde\n",
      "erd\n",
      "edr\n",
      "dre\n",
      "der\n"
     ]
    }
   ],
   "source": [
    "for p in permutations('red'): \n",
    "    print(''.join(p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "game, gaem, gmae, gmea, geam, gema, agme, agem, amge, ameg, aegm, aemg, mgae, mgea, mage, maeg, mega, meag, egam, egma, eagm, eamg, emga, emag, "
     ]
    }
   ],
   "source": [
    "for p in permutations(\"game\"): \n",
    "    print(''.join(p) + \", \", end=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Spominate si na `from itertools import islice` ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 3, 5]\n"
     ]
    }
   ],
   "source": [
    "def fibonacci():\n",
    "    \"\"\"Fibonacci numbers generator\"\"\"\n",
    "    a, b = 1, 1\n",
    "    while True:\n",
    "        yield a\n",
    "        a, b = b, a + b\n",
    "        \n",
    "print(list(islice(fibonacci(), 5)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Generator generatorov"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def firstn(g, n): # generator objekt je paraetrom generator funkcie\n",
    "    for i in range(n):\n",
    "        yield next(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(firstn(fibonacci(), 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.4.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}