Advanced Python - 3. Iterators and higher-order functions

Advanced Python - 3. Iterators and higher-order functions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Advanced Python - 3. Iterators and higher-order functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "#### the power of iterators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "does range(4) == [0, 1, 2, 3]?: False\n"
     ]
    }
   ],
   "source": [
    "# so was range just a list?\n",
    "print('does range(4) == [0, 1, 2, 3]?: '\n",
    "      '{}'.format(range(4) == [0, 1, 2, 3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "summation over [1,..., 10 ** 8] = 5000000050000000\n"
     ]
    }
   ],
   "source": [
    "# Nope, range is a iterator - it generates the next value \n",
    "# dynamically as it is requested. This way we don't need \n",
    "# all the things we want to iterate over in memory\n",
    "\n",
    "# no memory cost\n",
    "summation = 0\n",
    "for i in range(1, 10 ** 8 + 1):\n",
    "    summation += i\n",
    "print('summation over [1,..., 10 ** 8] = {}'.format(summation))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "summation over [1, ..., 10 ** 8] = 5000000050000000\n"
     ]
    }
   ],
   "source": [
    "# a list with 10 ** 8 elements in RAM!\n",
    "# boy this is expensive (check your RAM usage)\n",
    "range_as_list = list(range(1, 10 ** 8 + 1))\n",
    "\n",
    "summation = 0\n",
    "for i in range_as_list:\n",
    "    summation += i\n",
    "print('summation over [1, ..., 10 ** 8] = {}'.format(summation))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "### Functional programming"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "# let's write a bubble sort!\n",
    "\n",
    "def bubble_sort(a):\n",
    "    n = len(a)\n",
    "    for i in range(n):\n",
    "        for j in range(n - 1, i - 1, -1):\n",
    "            if a[j] < a[j - 1]:\n",
    "                a[j], a[j - 1] = a[j - 1], a[j]\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1, 1, 2, 4, 8]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# let's try our implementation\n",
    "l = [-1, 4, 1, 2, 8]\n",
    "bubble_sort(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', 'b', 'd', 'w']"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# interestingly we can sort letters too..\n",
    "l = ['b', 'w', 'a', 'd']\n",
    "\n",
    "bubble_sort(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false,
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['d', 'e', 'h', 'l', 'l', 'l', 'o', 'o', 'r', 'w']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# to convert a string to a list is trivial\n",
    "bubble_sort(list('helloworld'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['h', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'd']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list('helloworld')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "### Measuring performance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Generating some data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false,
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "# make us a random list length (between 1 - 2000)\n",
    "def rand_len():\n",
    "    return random.randint(1, 2e3)\n",
    "\n",
    "# choose a random value for a list element (between 0 1e6)\n",
    "def rand_int():\n",
    "    return random.randint(0, 1e6)\n",
    "\n",
    "# generate a random list of random length -\n",
    "# here we use a list comprehension, a very tidy\n",
    "# way of transforming lists of data\n",
    "\n",
    "def rand_list():\n",
    "    return [rand_int() for i in range(rand_len())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[257270, 144602, 358684, 525680, 988993]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# test our rand_list() function\n",
    "# peek at the first 5 elements\n",
    "rand_list()[:5]  # hit ctrl + enter to run this cell many times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1917"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# check lists are randomly sized\n",
    "len(rand_list())  # hit ctrl + enter to run this cell many times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# build 100 lists to test\n",
    "random_lists = [rand_list() for i in range(100)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100000 loops, best of 3: 4.56 µs per loop\n"
     ]
    }
   ],
   "source": [
    "# IPython has a very convienient timer module!\n",
    "# chooses how many times to repeat based on how\n",
    "# long the execution time is and averages for us\n",
    "%timeit bubble_sort([0, 1, 2, 3])\n",
    "\n",
    "# but we want to programatically record the\n",
    "# timings..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loops, best of 3: 103 ms per loop\n"
     ]
    }
   ],
   "source": [
    "# on a longer input the %timeit does many less\n",
    "# loops to keep running time sensible\n",
    "%timeit bubble_sort(random_lists[10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Making a  timer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to write a re-usable piece of code that times the length of another function's execution.\n",
    "\n",
    "With our Java hats on..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def big_loop():\n",
    "    summation = 0\n",
    "    for i in range(1, 10 ** 8 + 1):\n",
    "        summation += i\n",
    "    return summation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "\n",
    "class TimableInterface:\n",
    "    \n",
    "    def call(self):\n",
    "        # do your work here!\n",
    "        pass\n",
    "    \n",
    "\n",
    "class ThingIWantToTime(TimableInterface):\n",
    "    \n",
    "    def call(self):\n",
    "        big_loop()  # hope we can statically see this function..\n",
    "\n",
    "def java_timer(timable):\n",
    "    before = time.clock()\n",
    "    timable.call()  # use our interface\n",
    "    after = time.clock()\n",
    "    return after - before"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.104903"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "timable = ThingIWantToTime()\n",
    "java_timer(timable)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a lot of work! Wouldn't it be easier if I could just pass **the function I want to time** into my timer?\n",
    "\n",
    "In Python, functions are first-class citizens, so you can."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false,
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def time_f(f):\n",
    "    before = time.clock()\n",
    "    f()\n",
    "    after = time.clock()\n",
    "    return after - before"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.605234000000003"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time_f(big_loop)  # much nicer :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false,
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "t = []\n",
    "n = []\n",
    "\n",
    "# test our bubble sort - record the time (t) it took to\n",
    "# run and the length of the input (n)\n",
    "for r_list in random_lists:\n",
    "    # lambdas are very convienient here (we want\n",
    "    # to delay the invocation of the function).\n",
    "    # notice we are passing a *function*, not it's\n",
    "    # result (fuctions are first class citizens in\n",
    "    # Python)\n",
    "    t.append(time_f(lambda: bubble_sort(r_list)))\n",
    "    n.append(len(r_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false,
    "internals": {},
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 0.50000000000000011)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": [
       "iVBORw0KGgoAAAANSUhEUgAAAYoAAAEPCAYAAABcA4N7AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n",
       "AAALEgAACxIB0t1+/AAAHU5JREFUeJzt3X2QXNV55/HvbwQoEiDjGe9CwAo4BuzgldfgCniDvJnY\n",
       "CIlsLbLW2QUKJxi7WByMJ2RErWKFlLUFxsaxZKIiXrCsteXEG1UlKWylCiKRiieVomzzIjCykYxU\n",
       "CyxIBuMRYgDhQTDP/nHuqHt6unt6pvv26+9T1UXfl759+tLqZ855zosiAjMzs0r6Wl0AMzNrbw4U\n",
       "ZmZWlQOFmZlV5UBhZmZVOVCYmVlVDhRmZlZVroFC0gpJeyTtlbSmzPFBSS9JeiR73JRneczMbPaO\n",
       "yevCkuYBdwAXAfuBByVti4jdJaf+S0Rcmlc5zMysPnnWKM4H9kXEUxFxBNgKrCxznnIsg5mZ1SnP\n",
       "QHEa8EzR9rPZvmIB/JakH0m6R9I5OZbHzMzmILemJ1IQmMlOYHFEHJZ0CfAd4Owcy2RmZrOUZ6DY\n",
       "Dywu2l5MqlUcFREvFz2/V9JXJfVHxMHi8yR5QiozszmIiLqb9/MMFA8BZ0k6AzgAXAZcUXyCpJOB\n",
       "n0dESDofUGmQmNSID9sNJK2LiHWtLkc78L0o8L0o8L0oaNQf2bkFioh4Q9L1wHZgHrA5InZLujY7\n",
       "fhfwe8AfSnoDOAxcnld5zMxsbvKsURAR9wL3luy7q+j5XwJ/mWcZzMysPh6Z3XlGWl2ANjLS6gK0\n",
       "kZFWF6CNjLS6AN1GnbBwkaRwjsLMbHYa9dvpGoWZmVXlQGFmZlU5UJiZWVUOFGZmVpUDhZmZVeVA\n",
       "YWZmVTlQmJlZVQ4UZmZWlQOFmZlV5UBhZmZVOVCYWVuTtFwa2JEeWt7q8vQiz/VkZm0rBYZFd8PG\n",
       "BWnP0GswtioitheO969Oxw6un9xvSaN+O3OdZtzMrD79q2HDArhqcscCGF4NbC8EkQ2TQWSppFUO\n",
       "Fo3nQGFmHapyEGlhobqSA4WZtbGD62FoKVDc9LS+pUXqQc5RmFlbq5SHmCl/YY377XSgMLOO5WR2\n",
       "dQ4UZmZWlVe4MzOzpnCgMDOzqhwozMysKgcKMzOryoHCzMyqcqAwM7OqHCjMzKwqBwozM6vKgcLM\n",
       "zKpyoDCzjuAFjFrHU3iYWdvzBIBz44WLzKyHeO2JVnLTk5mZVeWmJzNre9Obnq4bh+N+An2jnl68\n",
       "Mk8zbmYdoxHrRhSuMT4A894DG+enI85XVOJAYWYdYTaJ6FoCijSwAzYsK+QrtgDD90WMXpzXZ+hU\n",
       "HbEehaQVkvZI2itpTZXzflPSG5L+S57lMbNW6F+dgsRVpMfGBYVgUFAIKBuWpceiu90Ntj3k1utJ\n",
       "0jzgDuAiYD/woKRtEbG7zHm3Af8IuNZg1rNq7dl0cD0MLU3HIauhrG9eOXtPnt1jzwf2RcRTAJK2\n",
       "AiuB3SXnfQb4O+A3cyyLmbVM+R/20mYm6K/pahGxXdKqLIgAY05m5yzPQHEa8EzR9rPABcUnSDqN\n",
       "FDw+RAoU7Z8wMbNZKffDnv676O5Ug4AUSA7eUmtNIQsMDg5NkmegqOVH/3bgTyIiJIkqTU+S1hVt\n",
       "jkTESH3FM7NmKf1hzxLSpc1Mg3DQNYU6SBoEBht93TwDxX5gcdH2YlKtotj7ga0pRvA24BJJRyJi\n",
       "W+nFImJdTuU0szbhmkJ9sj+gRya3JX2uEdfNM1A8BJwl6QzgAHAZcEXxCRHx65PPJX0D+IdyQcLM\n",
       "uo0T0p0kt0AREW9Iup7018E8YHNE7JZ0bXb8rrze28zamxPSncUD7szMulRHDLgzM7PO52nGzazp\n",
       "SsZQjED/YPbcTVBtyE1PZtZUZeZ+Aq4BluAJ/hrLCxeZWYeaNlUHsA34MnhBorbkHIWZmVXlpicz\n",
       "ayo3PTWP16Mws47lZHZzOFCYmVlVHkdhZmZN4UBhZmZVOVCYmVlVDhRm1nCSlksDO9LD6153Oiez\n",
       "zayhsu6v34WN89OeoXEYW+neTM3nXk9m1paktz4Mt59XGHm9BbhuH/zKk2nbXWCbxVN4mFmb6jt9\n",
       "6vYu4JgzYcOZaXtoqSQPqusgDhRm1mDjT8ONA4XtbwAbKVkf2/M5dRAHCjNrsFfXQnwX7sxyFG9O\n",
       "4I4zHc05CjNruOlTdCy6qWhuJ8/n1CROZptZxygJHE5mN4kDhZm1BQeB9uVAYWYtV2bKcDcrtRF3\n",
       "jzWzNjBttTr3aOpC7olgZkd56g0rx01PZgbMrRnJTU/tzTkKM2soaWAHbFiWmpG2A+uAJ0bh4JUz\n",
       "Bwsns9uRcxRmlpPtpGBxG8AADN1dbcqNbL+DQxdzjcKsR8z0l3+hGemcBfAppk7qN3xfxOjFTS2w\n",
       "1c1LoZpZzQpBYMOy9Fh0d2myOgWOsVWpuanydZzs7j2uUZj1gKn5B6hWS6iUoE7PnbjuJM5RmFku\n",
       "ImK7pFXZeAhgbH3aN7DDYyZ6kwOFWU84uB6GlgLFtYH1lc52gtqKuenJrEfU243VYyY6j8dRmFnT\n",
       "ecxEZ3GgMDOzqtw91szMmiLXQCFphaQ9kvZKWlPm+EpJP5L0iKSHJX0oz/KY2XQeG2Ezya3pSdI8\n",
       "4KfARcB+4EHgiojYXXTO8RHxavZ8CXB3RJxZ5lpuejJrgNIcQ/qvE9TdqhPGUZwP7IuIpwAkbQVW\n",
       "AkcDxWSQyJwA/CLH8pj1tKLR2ZNBYSn07YbbPTbCqsozUJwGPFO0/SxwQelJkj4CfAH4VcBzyZjl\n",
       "puwiQ6e3skTWGfIMFDW1aUXEd4DvSPog8FfAu3Isk5lNMf40DC2kxoF41pvyDBT7gcVF24tJtYqy\n",
       "IuJfJR0jaSAipk1KJmld0eZIRIw0qqBmvaF0dPZ143AcwG74NDB/dHK6jtaV0eohaRAYbPh1c0xm\n",
       "H0NKZn8YOAA8wPRk9juB/xsRIek84G8j4p1lruVktlkDFJLZ4wMw7z2wcX464iR2N2pqMlvS8aQa\n",
       "QQDPliShy4qINyRdT0qKzQM2R8RuSddmx+8CPgr8gaQjwCvA5XP7GGZWi2zCP6D/27BhvpPYVouK\n",
       "gULSicA1pB/vtwHPAwJOljQKfBvYFBGvVLpGRNwL3Fuy766i518CvlTPBzCz2hV6Pp29oNVlsc5R\n",
       "rUbxHWAr8J8j4vniA5JOAS4FvktqWjKzjjDZ8+kUimoTOIlt1XiuJ7MeMnUBo+3AOtKKdgevdH6i\n",
       "+zRtridJSyWdkD3/fUlfkeS+12Yd6eD6VHvYAjwHPP6ag4TNZMYahaRdwHuzxzeBrwP/LSJ+O/fS\n",
       "FcrgGoVZg3iq8N7RtGnGJT0SEedK+hywPyK+LmlnRJxX75vXyoHCzGz2mtk99mVJa4GPAR/MJvs7\n",
       "tt43NjOzzlDLNOOXAePAJyLiOdIcTn+ea6nMzKxtVGx6krQd+Efg3ojY09RSTS+Lm57MzGapGb2e\n",
       "Pg4cAtZlCwvdmS00dHy9b2pm+fFCRNZoNY2jyPISFwCXAB8Cfglsz0ZW5841CrPaFEZeT1mI6Bbo\n",
       "H0zb7uXUS5rW66nCm/8b4OKI+Ha9Bajx/RwozGowdUAdwI3ApgnYmLUeePK/XpJ705OkdZJOLncs\n",
       "Il4A/lnS/6y3AGZWv8nmJuA82FV05H5SkLiK9Ni4oDCGwqw21brHPgRslXQcsBP4GWlSwFOA80g9\n",
       "ob6cewnNrKrUfX3RzbBhstaQHVkC7Jmgtt6NZhXVMuBuMXAh8GvZrqeB+yOi4iJEjeamJ7PyUk7i\n",
       "pHvg9r5Cc9MWYHgU2AkHR2DRTSU5Czc99YimDbiLiGdIs8iaWdvpXw1nl6sx7IwYvRhA0sPZWhN4\n",
       "BTubizyXQjWzprgQWFO0PTRRPGV4FhgcHGzOPM24WQcrdIe9ZkFKXO+ZgEN/FhG3trps1not7R7b\n",
       "bA4UZpV5NlirpJmzx74L+CpwSkS8R9J7gUsj4pZ637xWDhRmZrPXtIWLgE3AWuD1bHsXcEW9b2xm\n",
       "Zp2hlkCxMCJ+OLkRqQpyJL8imZlZO6klULwg6czJDUm/Rxp8Z2ZmPaCWHMU7ga8BvwW8CDwJXBkR\n",
       "T+VeukIZnKMwM5ulpvd6yqYX74uIl+t909lyoDAzm72mjcyW9FbgD4AzgGMkQUpVDFV7nZmZdYda\n",
       "RmbfA3wfeAyYIE0M2P6DL8w6gMdAWCeoJUexMyLOa1J5KpXBTU/WdSosMnR0wj4HEatXMwfc3QiM\n",
       "Af9AmlocgIg4WO+b18qBwrpJUQA4D64eKMzWvwUYvi9i9OKZgohZLZqWoyAte/rnwJ+Smp4gNT39\n",
       "er1vbtZrCgFgQxYAbgSWAaVLW/evTudMTh3OgmwGWAcKa7paAsVq4J0R8Yu8C2PW/aYFAGAd8BxZ\n",
       "rWF9+deZtU4tgWIv8FreBTHrXU+MwvDOqWtFHFwPQ0uB4qYnBxFriVoCxWHgUUnfo5CjcPdYszmZ\n",
       "FgDG4c2nYf6UsyJiu6RVXnDI2kEtyeyPl9kdEbEllxKVL4OT2dY1CsnsiQF4/T3w1SxKOGFtjeX1\n",
       "KMw6nDSwAzYsK1nr+r7JJUzN6pV7rydJfxsR/1XSrjKHIyLeW++bm5lZ+6tYo5B0akQckHQ6aTR2\n",
       "sYiIp3MvXaEsrlFY1/FYCctb7gsXRcSB7Ol1EfFU8QO4rtY3kLRC0h5JeyWtKXP8Skk/kvSYpPuz\n",
       "FfTMul4KCGOrYPi+9HCQsPZUSzL7kYg4t2TfrohYMuPFpXnAT4GLgP3Ag8AVEbG76Jz/ADweES9J\n",
       "WgGsi4gPlFzHNQozs1nKvUYh6Q+z/MS7JO0qejxFmiCwFucD+7KayBFgK7Cy+ISI+H5EvJRt/hB4\n",
       "+6w/hVkHkLRcGtiRHiodim3WtqqNo/g/wL3AF4E1FPIUL0fEaI3XPw14pmj7WeCCKud/kjRbrVlX\n",
       "mT51x9BSSW5qso5QMVBkf+W/BFxex/Vr7nsr6XeATwAX1vF+Zm3KczdZ56plZHY99gOLi7YXk2oV\n",
       "U2QJ7E3Aioh4sdyFJK0r2hyJiJHGFdPMrPNJGgQGG37dPAfcSTqGlMz+MHAAeIDpyexfA/4Z+FhE\n",
       "/KDCdZzMto7mrrDWCh0zMlvSJcDtwDxgc0R8QdK1ABFxl6SvA6uA/5e95EhEnF9yDQcKa1u1LjDk\n",
       "hYis2TomUDSCA4W1q6k1hV3A5gngVTiyF15d62BgreRAYdYGCvM1nUJKVN+WHbkRODwOh1c6WFir\n",
       "NHOFOzOb0ddIQaJ4QaI758MT7tlkHa/igDszq2xy8ByMD6Q1JQ7M/CKzDuUahdksTR88d904PLYP\n",
       "ht7J0YGpR5uevCqddTwHCrNZmzZ4bj4MPwkHr4cbboW+02H8aTjsZLZ1BQcKswbJgoIDg3UdBwqz\n",
       "GpSMgRgpWff6NRhzE5N1LXePNZtBhVHVt0D/YNr24DlrT+4ea9Y0ZSf0G/Ta1tYr3D3WzMyqco3C\n",
       "bEYH16ecxK4FcD+wZwIOjbS6VGbN4hqF9bRaVp3L1ra+BTZNwKeA2/tg0U1epc56hWsU1rNmt+pc\n",
       "/yBs6PPCQ9aLHCisp0zt5nr8QOrJ5B9/s2ocKKxnlKlBTKSpwWsxmafw2AnrPQ4U1kOmdXPtgxsm\n",
       "YEmWq6v84x8R2yWtymocwJjHTljPcKCwXvcoDI+mp9V//D1Fh/UqBwrrIWWbj/6+MMLazMrxFB7W\n",
       "tcqtUT19zqZFN5VMzVGh15NZ5/EUHmZVzND1dXs6Z2BHmak53OvJrIQDhXWpsvMzOQiYzYEDhfUw\n",
       "d3k1q4VzFNaVKkwNPi3/UC6P0eyymuWlUb+dDhTWtQpBYGIAjgDzRx0MrJc4UJjVoNaahVk3cq8n\n",
       "szJKm5Kc1DarnwOFdY1yXWJhfHdrS2XW+RworIuUqz3cQGpucs8ms7lyoLCOV2huig+UP2PMk/mZ\n",
       "1cGBwjra1OamXcBQ0dEbgSOezM+sTg4U1hEqj3eY1twE3Az8e9K+b4w2t6Rm3ceBwtpehXmbboHj\n",
       "PwrHLYEvA6cAy4ElwP3ApTgfYdYYHkdhbS+bvG9ZodawBfijCTi2LwUJgGHgamDTOLz5Ew+uM/M4\n",
       "Cut5J/bBLUxtchoehbErHRzMGsuBwjrAwREY+jAwuWTpBJzaV+bEna0IEp4vyrqdm56srRXyE9cs\n",
       "SLmHPRNw6Fuw8ApYOL/Q9DQ0DmMrm/0j7SlCrJ016rez3F9lDSNphaQ9kvZKWlPm+LslfV/SLyWt\n",
       "zrMs1qn6V6cf4S8D3wdu74P+0+DwSnhtZ2puumFnK4LE1PJdRXpsXFCoXZh1h9yaniTNA+4ALgL2\n",
       "Aw9K2hYRxVMqjAKfAT6SVzmsO3lshFnz5JmjOB/YFxFPAUjaCqwEjgaKiHgBeEHSf8qxHNamamvb\n",
       "b/fFhdq9fGb1yzNQnAY8U7T9LHBBju9nHWSGNa2Piojtktp2Co52L59ZI+QZKBqaJZe0rmhzJCJG\n",
       "Gnl9a7bap/9u92amdi+f9Q5Jg8Bgo6+bZ6DYDywu2l5MqlXMSUSsq7dAZmbdLPsDemRyW9LnGnHd\n",
       "PAPFQ8BZks4ADgCXAVdUONddX3vOtLb9CRgbaWWJzKy8XMdRSLoEuB2YB2yOiC9IuhYgIu6SdArw\n",
       "ILAImABeBs6JiFdKruNxFF1I0lo46WZ4dx9cCGzyGASzBvKa2dbxys/hNHxfxOjFrSyXWbfoiAF3\n",
       "ZmbW+TzXkzXU7OY98hgEs07gpidrmArzHt0C/YNpe3rg8IR6ZvlxjsLaTvmcww0TaX4m8IR5Zs3l\n",
       "9SisLUytEUwMTD/j3X21DKozs/blQGFzNn0ajmuPwFBwdFzM0ARc4w4TZh3OgcLq0L8arl4A20gT\n",
       "Ac8/Fq4B7iStGzH2Ldh0GSxxstqsg/mvPavD+EDKQ1xKWq/6OGAZU9eNGFsFw/elh/MTZp3INQqr\n",
       "w7GkBYWK163+GrD86JYnzDPrfK5R2KxJWp56OPWdPv3oAVItY+i1NE7CzDqdaxQ2K1MT2LuAoaKj\n",
       "Q+Pw5k/S8qRel8GsWzhQ2DQlg+BGigfMlVlHghQY2OngYNadHChsijIrzy1LieolpOk2JnZPfcUS\n",
       "gJ2eyM+sezlQ2FFZTeLb02sM20hJaxbAp0n5B8/PZNYrHCgMKK5JnL2g+pnzR+Gg14g26yGe66lH\n",
       "VJp8r2j/eXD1QBoHcRVwW/bKIdIguiV4riazzuJJAa1mFWZ1XQVcDm/9OBwPXAD8C/DX2avWAU+M\n",
       "wsEN1WZ/NbP25UBhNSnkHc4eSD/+y0njHK7dB/PPhI3ZmUOk2sR+4FO49mDW+Tx7rM1oeg+mq0hB\n",
       "AmDh6fAVpiatbwIOj8Kwu7qa2VEOFF3tLXfAX5T0YFoHPP4azHuDNAdHkVeBF690gDCzYg4UXUrS\n",
       "N+CkM6cfeWIUxq4E3g9Dny/sHwLGvukgYWalHCi6hKS10D8Mrx8LE6/ASafCJ4E1RWcNAWOTNYbt\n",
       "koDh4XRsbENE3Nr0gptZ23Myu8OlAPHWP4VYmKb5fh14d3b0U8AppBldDwA/Hot4+S0tKqqZNVmj\n",
       "fjs9e2yHSjO4Hr8XFn0evrIQbicFiU8CpwIXkmoTz5HWi3gceOW2ihc0M6vATU8dKNUiFt0M5/Sl\n",
       "WkNxsvpOUsL6KuBj2fYesvyDm5bMbNZco+gwqcvrSTfDxr5Ucyi1l1SL+BiweQL27IRDKyLi6uaW\n",
       "1My6hWsUbaz8tBv9q+HsLMD/d6bWJm4EBoEbAngEDq11LyYzq5cDRZsqM933UkmroJ9C/uE2Us3h\n",
       "BiAOw5ED8L0n4ZAHy5lZw7jXU5tKS41uWFaoMWwBhu9LiwctuhuuWQD3A3sm4NCfOf9gZqU8hUeP\n",
       "iojtqWbxjaxJyrUHM8uXaxQ5qrak6Ew/7pVmfHVQMLNaefbYNlUIDhMD8Pp74Kvz05HZr+tQaQ0J\n",
       "M7NauOmpDU1PQN9IGhm9PDujeEnR4dVA1R/+yak28iqvmVktHChmYWpt4bVFcMypcNz81OPo0BdT\n",
       "01LpetNfoxAozMw6jwNFFdngtluh73R49UVYtBg2FDUlQVrTgRPTTKxv7pt+lQOkHkuTTU9byJqe\n",
       "1uf/CczM6pdrjkLSCtIkRPOAr0fEtLmGJG0ELgEOAx+PiEfKnJNbjqL6WtKLvgsbs8AwDGxganfV\n",
       "O4HvF21fPwZ9xxYloMfhzZ/A/NHZJrPNzOrVsN/OiMjlQQoO+4AzSAvkPAr8Rsk5vwvckz2/APhB\n",
       "hWvFDO+1HPp3wFv2wgkvQf8vgLVTj/XvANbCSQ+n48c/nLYXHYZvRnosOgwsT6/r35H2Rfb4QEzd\n",
       "/ma2r3i7/xcl77c8h/s6mNf/s057+F74XvhezHgvohHXybPp6XxgX0Q8BSBpK7AS2F10zqVka3NG\n",
       "xA8lnSTp5Ih4vvRi6S98gONvhfmnw5svwpGF0PdvYdEx6a99SAnkq4BNn5d0Fiy6LOUNdgGblqUK\n",
       "DsCNA8D70pxJR3MKVZLMF5JGQE+abHraUrQ9tiHyT0APAiM5Xr+TDOJ7MWkQ34tJg/heNFSegeI0\n",
       "4Jmi7WdJtYaZznk7MC1QwMLvAn2w4Nis59BACgpvA/6EqQnkbcBG4I+vhK8cm459NNs3ZY3oKpMi\n",
       "HlwPQ/8RyJqetgCvHYEbdqXt8SyZ/cdZMnvsi+HR0WbWhfIMFLUmP0rbzyq87r3ZD3bptNo3z65U\n",
       "U5wEDE1wdBbdQpI50gjolXBDlswefxrG10b80rkFM+spuSWzJX0AWBcRK7LtzwITUZTQlnQnMBIR\n",
       "W7PtPcBvlzY9SWr/UYFmZm0o2nzA3UPAWZLOIPURvQy4ouScbcD1wNYssBwql59oxAc1M7O5yS1Q\n",
       "RMQbkq4nJXbnAZsjYreka7Pjd0XEPZJ+V9I+4FXAi+uYmbWZjpjryczMWqetl0KVtELSHkl7Ja1p\n",
       "dXmaQdJTkh6T9IikB7J9/ZLuk/SEpB2STio6/7PZ/dkj6eLWlbx+kv63pOcl7SraN+vPLun9knZl\n",
       "x/6i2Z+jESrci3WSns2+G49IuqToWDffi8WSvifpJ5J+LGko299z340q9yLf70arB4RUGSgy44C9\n",
       "bnwATwL9Jfu+BPyP7Pka4IvZ83Oy+3Jsdp/2AX2t/gx1fPYPAucCu+b42SdryA8A52fP7wFWtPqz\n",
       "NehefA4YLnNut9+LU4D3Zc9PAH4K/EYvfjeq3ItcvxvtXKM4OmAvIo4AkwP2ekFp8v7owMTsvx/J\n",
       "nq8E/iYijkQa2LiPdN86UkT8K/Biye7ZfPYLJP0qcGJEPJCd962i13SMCvcCpn83oPvvxXMR8Wj2\n",
       "/BXSoN3T6MHvRpV7ATl+N9o5UJQbjHdahXO7SQD/JOkhSddk+4pHqz8PnJw9P5V0XyZ14z2a7Wcv\n",
       "3b+f7ronn5H0I0mbi5paeuZeZL0ozwV+SI9/N4ruxQ+yXbl9N9o5UPRqlv3CiDiXNFHipyV9sPhg\n",
       "pHpitXvTtfeths/e7f4X8A7gfcDPgJ6agVjSCcDfA38UES8XH+u170Z2L/6OdC9eIefvRjsHiv3A\n",
       "4qLtxUyNgF0pIn6W/fcF4G5SU9Lzkk4ByKqMP89OL71Hb8/2dZPZfPZns/1vL9nfFfckIn4eGeDr\n",
       "FJoZu/5eSDqWFCT+KiK+k+3uye9G0b3468l7kfd3o50DxdEBe5KOIw3Y29biMuVK0kJJJ2bPjwcu\n",
       "Js1muI3CvCVXAZP/ULYBl0s6TtI7gLNICapuMqvPHhHPAWOSLpAk4PeLXtPRsh/DSatI3w3o8nuR\n",
       "lX0z8HhE3F50qOe+G5XuRe7fjVZn8WfI8F9CyurvAz7b6vI04fO+g9RD4VHgx5OfGegH/gl4AtgB\n",
       "nFT0mrXZ/dlDDtOaN/nz/w1pFP/rpPzU1XP57MD7s38o+4CNrf5cDboXnyAlHB8DfpT9oz65R+7F\n",
       "UmAi+3fxSPZY0YvfjQr34pK8vxsecGdmZlW1c9OTmZm1AQcKMzOryoHCzMyqcqAwM7OqHCjMzKwq\n",
       "BwozM6vKgcLMzKpyoDAzs6ocKMzmIJtaZrekr2ULyGyX9CutLpdZHhwozObuTOCOiPh3wCHgoy0u\n",
       "j1kuHCjM5u7JiHgse/4waQUxs67jQGE2d+NFz98EjmlVQczy5EBhZmZVOVCYzV3p1Mueitm6kqcZ\n",
       "NzOzqlyjMDOzqhwozMysKgcKMzOryoHCzMyqcqAwM7OqHCjMzKwqBwozM6vKgcLMzKr6/9fGwBBZ\n",
       "PVPjAAAAAElFTkSuQmCC\n"
      ],
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1fe7cf6a0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "from matplotlib import pyplot as plt\n",
    "plt.scatter(n, t)\n",
    "plt.xlabel('n')\n",
    "plt.ylabel('time (/s)')\n",
    "plt.xlim(0)\n",
    "plt.ylim(0)"
   ]
  }
 ],
 "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.4.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}