optimizing python code

mcwilliams python optimization talk.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pylab inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Look-up times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "462 ms ± 8.69 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "l = [i for i in range(5000)]\n",
    "x = [i for i in range(10000) if i in l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "924 µs ± 36 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "d = {i:i for i in range(5000)}\n",
    "x = [i for i in range(10000) if i in d]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Numpy vectorization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [i for i in range(1, 100)]\n",
    "b = [i for i in range(2, 101)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "18.6 µs ± 110 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "axb = []\n",
    "for i in range(len(a)):\n",
    "    axb.append(a[i]*b[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7.54 µs ± 282 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "axb = [ai*bi for ai, bi in zip(a, b)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "17.4 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit -r 1 -n 1000\n",
    "axb = np.array(a)*np.array(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "a_arr = np.array(a)\n",
    "b_arr = np.array(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "649 ns ± 0 ns per loop (mean ± std. dev. of 1 run, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit -r 1 -n 1000\n",
    "axb = a*b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.87 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit -r 1 -n 10000\n",
    "for i in range(len(a)):\n",
    "    a[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16.7 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit -r 1 -n 10000\n",
    "for i in range(len(a_arr)):\n",
    "    a_arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55.1 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit -r 1 -n 1\n",
    "matrix = [[i for i in range(1000)] for _ in range(1000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "matrix = [[i for i in range(1000)] for _ in range(1000)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "72.1 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit -r 1 -n 10\n",
    "np_matrix = np.array(matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "np_matrix = np.array(matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.72 s ± 0 ns per loop (mean ± std. dev. of 1 run, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit -r 1 -n 10\n",
    "mult = np_matrix @ np_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit -r 1 -n 1\n",
    "mult_nonp = [[sum(\n",
    "    [i*j for (i, j) in zip(row, col)]) \n",
    "         for col in list(zip(*matrix))]\n",
    "         for row in matrix]\n",
    "# takes ~3.5 mins"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9.54 µs ± 258 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit \n",
    "_ = list(a_arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all(np.array(mult_nonp) == mult)\n",
    "# returns True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## EAFP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "433 ms ± 5.57 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "a = 5\n",
    "for i in range(5000000):\n",
    "    if i!=0:\n",
    "        a /= i\n",
    "    else:\n",
    "        a = 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "356 ms ± 16.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "a = 5\n",
    "for i in range(5000000):\n",
    "    try:\n",
    "        a /= i\n",
    "    except ZeroDivisionError:\n",
    "        a = 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Caching"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    else:\n",
    "        return fib(n-1) + fib(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30.2 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit -r 1 -n 1\n",
    "fib(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.44 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit -r 1 -n 1\n",
    "fib(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "355 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit -r 1 -n 1\n",
    "fib(30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit -r 1 -n 1\n",
    "fib(40)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/usr/local/lib/python3.8/site-packages/IPython/core/magics/pylab.py:159: UserWarning: pylab import has clobbered these variables: ['matrix']\n",
      "`%matplotlib` prevents importing * from pylab and numpy\n",
      "  warn(\"pylab import has clobbered these variables: %s\"  % clobbered +\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x12c12b070>]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3deXwVhbn/8c9DSNgJ+xpC2BFCQAmgqJWqKCqIIrYutdraou217a+toKAVsS7I1bpcrS1XEe21ehUQQVDcxa0ComQDJLKFCASIhDVkOc/9I6G/lIIGssw5J9/368WLzJyTM99x8OHhmcmMuTsiIhJd6gUdQEREqp+Ku4hIFFJxFxGJQiruIiJRSMVdRCQK1Q86AECbNm08KSkp6BgiIhHls88+2+nubY/2WqDF3czGAGN69uzJihUrgowiIhJxzGzTsV4LdCzj7gvdfUJ8fHyQMUREok6gxd3MxpjZzIKCgiBjiIhEHXXuIiJRSJ27iEgUUucuIhKFdJ27iEgUUnEXEYlCmrmLiARg/6ES7lmUxfY9hTXy+Zq5i4jUsg/X7eS8h5by5IcbeP/LHTWyjbC4/YCISF2wp7CYexet5oXlOXRv04SXbjiN1KRWNbItFXcRkVrw7po8Js9LJ29vITec1Z3fntubhrExNba9sLm3jIhINNp9oIi7Xs1i3spcerdvyl+uOZ1BXVrU+HYDLe7uvhBYmJqa+vMgc4iI1IQlmdu4fX4G+fuL+NXZPbnp7J40qF9z3XpFGsuIiFSzXfsOMXVBJq+mbaVfx+Y8fd0QkjvX7oUjKu4iItXE3Xk1bStTF2Syt7CY34/szY0jehAbU/sXJqq4i4hUg7y9hfxhfgZLMrczMCGeGeNPpU+HZoHl0QlVEZEqcHfmrczlrlezOFhcyq0X9OVnZ3SjfgDdekU6oSoicoK2Fhxkyrx03l27g8FdWzJjfAo92jYNOhagsYyIyHFzd/53eQ73LFpNSciZOqYfPz4tiZh6FnS0f1JxFxE5Djn5B5g8L50Ps3dyavdW3H9ZCl1bNwk61r9RcRcRqYRQyPmfTzcx/bU1GHD3JclcNTSRemHUrVek4i4i8h027tzPpLlpLNuQz5m92jD9shQ6t2gUdKxvpeIuInIMpSHn6Y828MAba4mNqceM8SlcPjgBs/Ds1iuq9uJuZmcCV5d/dj93H17d2xARqWnZeXuZOCeNzzfv5py+7bjn0gF0iG8YdKxKq1RxN7NZwGggz92TK6wfBTwCxABPuvt0d/8A+MDMLgGW10BmEZEaU1Ia4q9L1/PIW+to3CCGh384iLGDOkVEt15RZTv32cBjwLOHV5hZDPA4MBLYAiw3swXunlX+lquA66svqohIzVq9dQ+T5qSRnlvABckduGtsMm2bNQg61gmpVHF396VmlnTE6qFAtruvBzCzF4CxQJaZJQIF7r73WJ9pZhOACQCJiYnHn1xEpJoUlYT483vZPP5uNs0bxvLnq0/hwgEdg45VJVWZuXcGciosbwGGlX99PfD0t32zu88EZgKkpqZ6FXKIiJyw9C0FTJyzijXb9jJ2UCemjulPqyZxQceqshq5Wsbdp1bmfbq3jIgEpbC4lEffXsdfl66ndZM4/vvHqYzs1z7oWNWmKsU9F+hSYTmhfJ2ISFhbufkbJs1JIztvH5cPTuD2i/oR3zg26FjVqiq3LVsO9DKzbmYWB1wBLDieD3D3he4+IT6+dm9iLyJ108GiUu5ZlMX4Jz7mwKESnvnpUP7z8oFRV9ih8pdCPg+MANqY2RZgqrs/ZWY3AUsouxRylrtnHs/GNZYRkdry6fpd3DI3jY27DnD1sERuvaAvzRpGX1E/zNyDP5eZmprqK1asCDqGiESh/YdKmPH6Gp75ZBNdWjXi/nEpDO/ZJuhY1cLMPnP31KO9pod1iEjU+nDdTm6dl0bu7oNcNzyJSaP60Diubtx1RQ/rEJGos6ewmPsWr+b5ZTl0b9OEF284jSFJrYKOVavqxl9hIlJnvLs2jynz0tm+p5Abvted347sTcPYmKBj1TqNZUQkKuw+UMRdr2Yxb2Uuvdo15Ylfns6gLi2CjhUYjWVEJOItydzG7fMzyN9fxK/O7slNZ/ekQf26161XpLGMiESsXfsOcefCLBau+pqTOjbn6euGkNxZPzcDGsuISARydxalb2XqK5nsKSzmdyN784sRPYiNqcrPZUYXjWVEJKLk7S3kD/MzWJK5nZSEeP4+/lT6dGgWdKywo7GMiEQEd+flz3OZtjCLg8Wl3HpBX352Rjfqq1s/KhV3EQl7WwsOctvLGbyzJo/BXVsyY3wKPdo2DTpWWNPMXUTClrvzv8tzuGfRaopDIe4Y3Y9rhycRUy+yHnkXBM3cRSQs5eQfYPK8dD7M3smp3Vtx/2UpdG3dJOhYEUNjGREJK6GQ8z+fbmL6a2sw4O5LkrlqaCL11K0fFxV3EQkbG3fuZ9LcNJZtyOfMXm24b9wAElo2DjpWRFJxF5HAlYacpz/awANvrCU2ph4zLkvh8tQEzNStnygVdxEJVHbePibNWcXKzbs5p2877rl0AB3iGwYdK+LpahkRCURJaYiZH6zn4bfW0Tguhod/OIixgzqpW68mulpGRGrdmm17mPhSGum5BYzq34G7LulPu2bq1quTxjIiUmuKSkI88d5XPPbuOpo3jOXxq07hopSOQceKSiruIlIrMnILuPmlVazZtpeLB3bizov706pJXNCxopaKu4jUqEMlpTz69jr+8v56WjeJY+Y1gzmvf4egY0U9FXcRqTGfb/6GiXPSyM7bx+WDE7j9on7EN44NOladUO3F3czqAX8EmgMr3P2Z6t6GiIS3g0Wl/OnNtTz14QY6NG/I7J8MYUSfdkHHqlMqVdzNbBYwGshz9+QK60cBjwAxwJPuPh0YCyQAu4At1Z5YRMLasg35TJqzio27DnDVsEQmX9CXZg3Vrde2ynbus4HHgGcPrzCzGOBxYCRlRXy5mS0A+gAfu/tfzWwO8Ha1JhaRsLT/UAkzXl/DM59sokurRvz9Z8MY3rNN0LHqrEoVd3dfamZJR6weCmS7+3oAM3uBsq49Bygqf09p9cQUkXD2UfZObpmbRu7ug1w3PImJ5/ehSQOd0gtSVf7rd6askB+2BRhG2Zjmv8zsTGDpsb7ZzCYAEwASExOrEENEgrKnsJj7Fq/h+WWb6damCS/ecBpDkloFHUuogROq7n4AuL4S75tpZluBMXFxcYOrO4eI1Kx31+YxZV462/cUMuF73fndyN40jI0JOpaUq8rDB3OBLhWWE8rXVZq7L3T3CfHx8VWIISK1qeBAMb9/cRU/eXo5TRvUZ+4vhjPlwpNU2MNMVTr35UAvM+tGWVG/ArjqeD5ANw4TiSxvZG7jtvkZ5O8v4qbv9+RX5/SkQX0V9XBUqc7dzJ4HPgH6mNkWM7ve3UuAm4AlwGrgRXfPPJ6Nq3MXiQz5+4v41fOfM+Fvn9GmaQNe+Y/Tufn8PirsYayyV8tceYz1i4HFJ7pxde4i4c3dWZS+lamvZLKnsJjfjezNjWf1IK5+VSa6Uht0y18ROaq8vYXcMT+T1zO3kZIQz3Pjh9G3Q/OgY0kl6WEdIvIv3J35X+QybWEWB4pKufWCvvzsjG7Uj1G3HknUuYvIP20tOMhtL2fwzpo8TklswYzxA+nZrmnQseQEqHMXEdydF1fkcPerqykOhfjD6H5cNzyJmHp65F2kUucuUsfl5B9g8rx0PszeybBurZgxPoWurZsEHUuqSDd/EKmjQiHnuU83Mf21NQD88ZJkrh6aSD1161FBxV2kDtq4cz+3zE3j0w35nNmrDfeNG0BCy8ZBx5JqpJm7SB1SGnKe/mgDD7yxltiYesy4LIXLUxMwU7cebTRzF6kjsvP2MWnOKlZu3s3Zfdtx76UD6BDfMOhYUkM0lhGJckUlIf77g/U88vY6GsXG8NAPB3LJoM7q1qOcirtIFPtsUz5T5mWwdvteLkjuwLSx/WnXTN16XaCZu0gUKjhYzIzX1/Dcp5vpFN+QJ3+cyrn92gcdS2qRZu4iUeTwjb6mLcxi175DXH9GN343srceeVcH6YiLRImc/APc8UoG767dQXLn5sy6dggDEnQ77bpKxV0kwpWUhpj10QYeenMdZvCH0f249rSuutFXHafiLhLBVuXsZvK8dLK27uHck9oxbWwynVs0CjqWhAGdUBWJQHsLi3nwjS955pONtG3agCeuPoVRyR10eaP8k06oikSYJZnbmPpKJtv3FnLNqV25+fw+NG8YG3QsCTMay4hEiK0FB5n6SiZvZG2nb4dm/PlHp3BKYsugY0mYUnEXCXOlIefZTzbywJK1lLpz6wV9uf6MbsTqhKl8CxV3kTCWkVvAlJfTSdtSwPd6t+XusckkttbdG+W7qbiLhKEDRSU89OaXzPpoIy0bx/LolSczJqWjTphKpam4i4SZd9fkcfv8DHJ3H+TKoV24ddRJxDfWCVM5PtVe3M1sBPBHIBN4wd3fq+5tiESjvD2FTFuYxaL0rfRq15SXbjyNIUmtgo4lEapSxd3MZgGjgTx3T66wfhTwCBADPOnu0wEH9gENgS3VnlgkyoRCzt+Xbeb+19dwqCTE70f25oazehBXXydM5cRVtnOfDTwGPHt4hZnFAI8DIykr4svNbAHwgbu/b2btgT8BV1drYpEosnbbXibPS2Pl5t0M79Gauy9JpnvbpkHHkihQqeLu7kvNLOmI1UOBbHdfD2BmLwBj3T2r/PVvgAbH+kwzmwBMAEhMTDy+1CIRrrC4lEffXsfMpetp1rA+D14+kHGn6AEaUn2qMnPvDORUWN4CDDOzccD5QAvKuv2jcveZwEyA1NRUr0IOkYjywbod3PZyBpvzDzB+cAJTLjyJVk3igo4lUabaT6i6+zxgXmXeq3vLSF2yc98h7n41i/lffE23Nk34+8+HMbxHm6BjSZSqSnHPBbpUWE4oXyciFbg7L67I4d7FazhQVMKvz+7JL7/fk4axMUFHkyhWleK+HOhlZt0oK+pXAFcdzwfoxmES7bLz9jHl5XSWbchnaFIr7h2XTM92zYKOJXVAZS+FfB4YAbQxsy3AVHd/ysxuApZQdinkLHfPPJ6Naywj0aqwuJQn3vuKJ977ioax9Zg+bgA/SO1CvXo6YSq1w9yDP5eZmprqK1asCDqGSLX45Ktd3PZyOut37mfsoE7cflE/2jY75oVjIifMzD5z99SjvaaHdYhUk2/2F3Hv4tW89NkWurRqxDM/HcpZvdsGHUvqKD2sQ6SK3J2XP8/l7kWr2XOwmF+M6MGvz+5FozidMJXg6MZhIlWwced+bpufzkfZuzg5sQX3jRtA3w7Ng44lorGMyIkoKgkxc+lXPPpONg1i6vHHS5K5emiiTphK2NBYRuQ4rdiYz5SX0/ly+z4uHNCBqWP60755w6BjifwLjWVEKqngQDHTX1/D88s207lFI566NpVzTmofdCyRo9JYRuQ7uDuvpm1l2sIs8vcf4mdndOO3I3vTpIF6IwlfGsuIfIuc/APcPj+D97/cwYDO8cz+yRCSO8cHHUvkO6n1EDmK4tIQsz7cwENvfUmMGXeM7se1w5OI0QlTiRAq7iJH+CJnN5PnpbN66x7OPak9d43tT6cWjYKOJXJcNHMXKbe3sJgHlqzl2X9sol2zBvzlR4M5v397PUBDIpJm7iLA6xnbmLogg7y9h/jxqV25+fw+NGsYG3QskROmsYzUaV/vPsjUBZm8mbWdkzo256/XpDKoS4ugY4lUmYq71EmlIeeZjzfy4BtrKXVn8gV9+ekZ3YiNqRd0NJFqoeIudU5GbgGT56WTnlvAWb3bcvclyXRp1TjoWCLVSsVd6oz9h0p46M0vmfXRBlo1acB/XXkyo1M66oSpRCVdLSN1wturt3PHK5nk7j7IVcMSueX8vsQ31glTiV66Wkai2vY9hUxbmMni9G30ateUOTeeRmpSq6BjidQ4jWUkKoVCznOfbmLG62s5VBri5vN6M+F7PYirrxOmUjeouEvUWbNtD5PnpfP55t2c3rM191wygKQ2TYKOJVKrVNwlahwsKuWRt9fx5Afrad4olj/9YCCXntxZJ0ylTlJxl6iw9Msd3D4/g835B7h8cAJTLjyJlk3igo4lEpgaKe5m1gR4H7jT3V+tiW2IAOzYe4i7F2Xxyhdf071NE57/+amc1qN10LFEAlep4m5ms4DRQJ67J1dYPwp4BIgBnnT36eUv3QK8WM1ZRf4pFHJeXJHDfa+t4WBRKb85pxe/GNGDhrExQUcTCQuV7dxnA48Bzx5eYWYxwOPASGALsNzMFgCdgSxAD5WUGpGdt5cp8zJYtjGfod1ace+lA+jZrmnQsUTCSqWKu7svNbOkI1YPBbLdfT2Amb0AjAWaAk2AfsBBM1vs7qFqSyx1VmFxKX9+N5sn3v+KxnH1mXFZCuMHJ1BPD9AQ+TdVmbl3BnIqLG8Bhrn7TQBmdh2w81iF3cwmABMAEhMTqxBD6oKPv9rJ7S9nsH7nfi4Z1InbR/ejTdMGQccSCVs1drWMu8/+jtdnmtlWYExcXNzgmsohkS1/fxH3LFrN3JVbSGzVmL9dP5Qze7UNOpZI2KtKcc8FulRYTihfV2m6/YAci7szb2Uudy/KYm9hCb8c0YNfn9NLJ0xFKqkqxX050MvMulFW1K8ArjqeD9CNw+RoNuzcz20vp/PxV7s4JbEF944bQN8OzYOOJRJRKnWjDTN7HvgE6GNmW8zsencvAW4ClgCrgRfdPfN4Nu7uC919Qnx8/PHmlihUVBLiv95ex/kPLyU9t4C7L0lmzo3DVdhFTkBlr5a58hjrFwOLT3Tj6tzlsOUb85k8L53svH1cNKAjU8f0o11zXU0rcqJ0y18JVMGBYqa/vprnl+XQuUUjZl2Xytl92wcdSyTi6WEdEgh3Z8Gqr/njq1l8c6CYn5/Zjd+O7E3jON3uSKQ6qHOXWpeTf4Db5mew9MsdpCTEM/snQ0nurPMuItVJnbvUmuLSEE99uIGH3/qSGDOmjunHj09LIkY/YSpS7dS5S634fPM3TJ6XzpptezmvX3umje1Px/hGQccSiVoacEqN2lNYzANL1vK3f2yifbOG/PWawZzfv0PQsUSinoq71Ah35/WMbdy5MJO8vYe49rQkfn9eb5o1jA06mkidoJm7VLvc3QeZ+koGb63Oo1/H5sy8JpWBXVoEHUukTjF3DzoDqampvmLFiqBjSBWFQs5zyzYzffFqQg6/HdmLn57ejfoxlfpBaBE5Tmb2mbunHu01jWWkWmzedYBJc1fxj/X5nNmrDfdeOoAurRoHHUukzlJxlyoJhZy//WMT019bQ0w9Y/q4AfxwSBfMdHmjSJA0c5cTtnHnfibNTWPZhnzO6t2W+8YNoFMLXd4oEg50nbsct1DImf3xRmYsWUNsTD1mjE/h8sEJ6tZFwojGMnJc1u/Yx6Q5aazY9A1n923HvZcOoEO87t4oEm5U3KVSSkPOrA838MAba2lQvx4PXj6Qcad0VrcuEqZU3OU7ZeftY+KcVXy+eTfnntSeey5Npr3utS4S1nRCVY6pNOQ8+cF6HnzzSxrHxfDIFYO4eGAndesiEUAnVOWo1m3fy81z0liVs5vz+rXn7kuTaddM3bpIpNBYRv5FSWmIvy5dzyNvraNJgxgevfJkxqR0VLcuEmFU3OWf1m7by8Q5q0jbUsCFAzow7eJk2jZrEHQsETkBKu5CcWmIv77/FY+8vY7mDWN5/KpTuCilY9CxRKQKVNzruNVb93DzS6vI/HoPo1M6Mu3i/rRuqm5dJNKpuNdRRSUh/vxeNo+9k02LxrH85UenMCpZ3bpItKj24m5mJwG/AdoAb7v7E9W9DamazK8LuPmlNFZv3cPYQZ24c0x/WjaJCzqWiFSjSt1o28xmmVmemWUcsX6Uma01s2wzuxXA3Ve7+43AD4DTqz+ynKiikhB/emMtYx/7iJ37DjHzmsE8csXJKuwiUaiynfts4DHg2cMrzCwGeBwYCWwBlpvZAnfPMrOLgV8Af6veuHKi0rcUMHHOKtZs28u4kztzx5h+tGisoi4SrSpV3N19qZklHbF6KJDt7usBzOwFYCyQ5e4LgAVmtgj4+9E+08wmABMAEhMTTyi8fLdDJaU8+vY6/vL+eto0jeOpa1M556T2QccSkRpWlZl7ZyCnwvIWYJiZjQDGAQ2Axcf6ZnefCcyEssfsVSGHHMOqnN1MnLOKL7fvY/zgBP5wUT/iG+sB1SJ1QbWfUHX394D3KvNe3VumZhQWl/LwW+uYufQr2jVryNM/GcL3+7QLOpaI1KKqFPdcoEuF5YTydRKglZu/YeJLq/hqx36uGNKFKRedRPOG6tZF6pqqPJZ+OdDLzLqZWRxwBbDgeD7A3Re6+4T4+PgqxBAo69bvXbya8U98zMGiUp756VCmX5aiwi5SR1Wqczez54ERQBsz2wJMdfenzOwmYAkQA8xy98zj2bjGMtXjs035THwpjfU793Pl0ESmXNiXZirqInWauQd/LjM1NdVXrFgRdIyIc7ColAfeWMusjzbQKb4R91+Wwhm92gQdS0RqiZl95u6pR3tND+uIUMs25DNpzio27jrANad25ZYL+tK0ge4mISJl9LCOCHOgqIQZr6/lmU82ktCyEX//+TCG91C3LiL/Sq1eBPnH+l1MmpPG5vwDXDc8iYnn96GJunUROQqNZSLA/kMl3P/6Gp79ZBNdWzfmhQmncmr31kHHEpEwprFMmPs4eyeT5qaRu/sgPz29Gzef35vGcerWReTbqUqEqX2HSrhv8Wqe+3Qz3do04aUbTiM1qVXQsUQkQmgsE4Y+XLeTW+am8XXBQX5+Zjd+N7IPjeJigo4lIhFEY5kwsqewmPsWr+b5ZTl0b9uEOTcOZ3DXlkHHEpEIpLFMmHhvbR6T56WzfU8hN5zVnd+e25uGserWReTEqLgHrOBgMfcsyuLFFVvo2a4pc38xnJMT1a2LSNVo5h6gd9ZsZ8q8DHbsO8QvR/Tg1+f0UrcuItVCM/cAFBwo5q5Xs5i7cgt92jdj5o8Hk5LQIuhYIhJFNJapZW9lbWfKy+ns2l/Er87uyU1n96RBfXXrIlK9VNxryTf7i5i2MJP5X3xN3w7NmHXdEJI76z72IlIzVNxrwZLMbdz2cga7DxTxm3N68R/f70lc/ao8J0VE5NupuNeg/P1F3LkgkwWrvqZfx+Y889Mh9O+kbl1Eap6ulqkhi9O3cscrGRQcLOZ3I3vzixE9iI1Rty4itUNXy1SznfsOMfWVTBalbyW5c3P+52fD6NuhedCxRKSO0Vimmrg7i9K3cscrmewrLGHi+X2Y8L3u6tZFJBAq7tVgx95D3PFKBq9lbGNgQjz/eflAerdvFnQsEanDVNyrwN1ZsOpr7lyQyf6iUm4Z1Zefn9mN+urWRSRgKu4nKG9PIbfNz+DNrO0M6tKCBy5PoWc7desiEh5qpLib2SXARUBz4Cl3f6MmthMEd2f+F7ncuSCLwuJSplzYl+vP6E5MPQs6mojIP1W6uJvZLGA0kOfuyRXWjwIeAWKAJ919urvPB+abWUvgASAqivv2PYVMmZfO22vyGNy1JTPGp9CjbdOgY4mI/Jvj6dxnA48Bzx5eYWYxwOPASGALsNzMFrh7Vvlbbi9/PaK5O3NX5nLXwkyKSkP8YXQ/rhuepG5dRMJWpYu7uy81s6QjVg8Fst19PYCZvQCMNbPVwHTgNXdfWU1ZA7G14CCT56Xz3todDElqyYzxA+nWpknQsUREvlVVZ+6dgZwKy1uAYcCvgHOBeDPr6e5/OfIbzWwCMAEgMTGxijGqn7vz4ooc7n51NSUhZ+qYflx7WhL11K2LSASokROq7v4o8Oh3vGemmW0FxsTFxQ2uiRwnKnf3QW6dm8YH63YyrFsrZoxPoWtrdesiEjmqWtxzgS4VlhPK11VKuN1+wN15YXkO9yxaTcidP47tz9XDuqpbF5GIU9XivhzoZWbdKCvqVwBXVfabw+nGYTn5B5g8L50Ps3cyvEdr7r8shS6tGgcdS0TkhFT6RynN7HngE6CPmW0xs+vdvQS4CVgCrAZedPfMyn6muy909wnx8cHdBjcUcv72j02Mengpn2/+hnsuTea5nw1TYReRiHY8V8tceYz1i4HFJ7LxoDv3nPwDTJqTxifrd3FGzzZMv2wACS1V1EUk8tXJW/4e7tbvf30N9cyYPm4APxzSBTPN1kUkOtS5h3Vs2rWfiXPSWLYhn7N6t+W+cQPo1KJRrW1fRKQ21JnOPRRyZn+8kRlL1hAbU48Z41O4fHCCunURiUp1onPfsHM/k+asYvnGbzi7bzvuvXQAHeIb1ug2RUSCFNWde2nIefqjDfznkrU0qF+PBy8fyLhTOqtbF5GoF7X3c/9qxz4mvrSKlZt3c+5J7bjn0gG0b65uXUTqhqgr7qUh58kP1vPgm1/SKDaGh384iLGDOqlbF5E6Japm7uu272XinDS+yNnNef3ac/elybRrpm5dROqeqJi5l5SGmPnBeh5+cx1NGsTw6JUnMyalo7p1EamzIn4ss3bbXibOWUXalgIuSO7AXWOTadusQdCxREQCFdHF/blPNzFtQRZNG9bn8atO4aKUjkFHEhEJCxE9c+/Wugnn9W/PtIv707qpunURkcPM3YPOQGpqqq9YsSLoGCIiEcXMPnP31KO9Vulb/oqISORQcRcRiUIq7iIiUSjQ4m5mY8xsZkFBQZAxRESiTqDFPRwesyciEo00lhERiUIq7iIiUUjFXUQkCoXFDzGZ2Q5g0wl+extgZzXGCZL2JfxEy36A9iVcVWVfurp726O9EBbFvSrMbMWxfkIr0mhfwk+07AdoX8JVTe2LxjIiIlFIxV1EJApFQ3GfGXSAaqR9CT/Rsh+gfQlXNbIvET9zFxGRfxcNnbuIiBxBxV1EJApFVHE3s1lmlmdmGRXWtTKzN81sXfnvLYPMWFnH2Jc7zSzXzL4o/3VhkBkrw8y6mNm7ZpZlZplm9pvy9RF3XL5lXyLxuDQ0s2Vmtqp8X6aVr+9mZp+aWbaZ/a+ZxQWd9dt8y37MNrMNFYciKusAAAMNSURBVI7JoKCzVpaZxZjZ52b2avlyjRyTiCruwGxg1BHrbgXedvdewNvly5FgNv++LwAPufug8l+LaznTiSgBfu/u/YBTgf8ws35E5nE51r5A5B2XQ8DZ7j4QGASMMrNTgfsp25eewDfA9QFmrIxj7QfAxArH5IvgIh633wCrKyzXyDGJqOLu7kuB/CNWjwWeKf/6GeCSWg11go6xLxHH3be6+8ryr/dS9oe2MxF4XL5lXyKOl9lXvhhb/suBs4E55evD/rh8y35EJDNLAC4CnixfNmromERUcT+G9u6+tfzrbUD7IMNUg5vMLK18bBP2o4yKzCwJOBn4lAg/LkfsC0TgcSn/5/8XQB7wJvAVsNvdS8rfsoUI+MvryP1w98PH5J7yY/KQmTUIMOLxeBiYBITKl1tTQ8ckGor7P3nZdZ0R+7c68ATQg7J/fm4FHgw2TuWZWVNgLvD/3H1Pxdci7bgcZV8i8ri4e6m7DwISgKFA34AjnZAj98PMkoHJlO3PEKAVcEuAESvFzEYDee7+WW1sLxqK+3Yz6whQ/ntewHlOmLtvL/+DHAL+m7L/IcOemcVSVgyfc/d55asj8rgcbV8i9bgc5u67gXeB04AWZla//KUEIDewYMepwn6MKh+hubsfAp4mMo7J6cDFZrYReIGyccwj1NAxiYbivgC4tvzra4FXAsxSJYeLYblLgYxjvTdclM8MnwJWu/ufKrwUccflWPsSocelrZm1KP+6ETCSsnMI7wLjy98W9sflGPuxpkLjYJTNqMP+mLj7ZHdPcPck4ArgHXe/mho6JhH1E6pm9jwwgrJbZG4HpgLzgReBRMpuG/wDdw/7E5XH2JcRlP3T34GNwA0V5tZhyczOAD4A0vn/c8QplM2qI+q4fMu+XEnkHZcUyk7OxVDWxL3o7neZWXfKusZWwOfAj8q737D0LfvxDtAWMOAL4MYKJ17DnpmNAG5299E1dUwiqriLiEjlRMNYRkREjqDiLiIShVTcRUSikIq7iEgUUnEXEYlCKu4iIlFIxV1EJAr9H0yW0lfsw0r3AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "%pylab inline\n",
    "plt.plot([10, 20, 30, 40], [29.5, 3.45e3, 314e3, 35.5e6])\n",
    "plt.yscale('log')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "\n",
    "@lru_cache\n",
    "def fib(n):\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    else:\n",
    "        return fib(n-1) + fib(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "66.7 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit -r 1 -n 1\n",
    "fib(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}