demo_timeit.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table style=\"float:left;\">\n",
    "<tbody>\n",
    "<tr>\n",
    "<td ><img src=\"https://static1.squarespace.com/static/5992c2c7a803bb8283297efe/t/59c803110abd04d34ca9a1f0/1530629279239/\" alt=\"Kenzie Logo\" width=\"93\" height=\"93\" /></td>\n",
    "<td >\n",
    "<h1>&nbsp;A Brief Tour of Timeit&nbsp;</h1>\n",
    "</td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style=\"float:left\"><a href=\"https://colab.research.google.com/github/KenzieAcademy/python-notebooks/blob/master/demo_timeit.ipynb\"> <img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\" width=\"188\" height=\"32\" /> </a>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The timeit module provides a simple interface for determining the execution time of small bits of Python code. It uses a platform-specific time function to provide the most accurate time calculation possible and reduces the impact of start-up or shutdown costs on the time calculation by executing the code repeatedly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The module function `timeit.timeit(stmt, setup, timer, number)` accepts four arguments:\n",
    "\n",
    "- `stmt` which is the statement you want to measure; it defaults to 'pass'.\n",
    "- `setup` which is the code that you run before running the stmt; it defaults to 'pass'.\n",
    "- `timer` which is a timeit.Timer object; it usually has a sensible default value so you don't have to worry about it.\n",
    "- `number` which is the number of executions you'd like to run the stmt.\n",
    "\n",
    "Where the `timeit.timeit()` function returns the number of seconds it took to execute the code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# First, here is a naiive way to time a function\n",
    "import time\n",
    "start = time.time()\n",
    "# my function code goes here\n",
    "total = time.time() - start"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### It's okay, but ...\n",
    "This method is good for a quick look at a single time cost of a function.  But you may be mislead by the result:  There are background processes e.g. \"[Garbage Collection (GC)](https://rushter.com/blog/python-garbage-collector/)\" that may happen while you are timing.  This background process will throw off your result.\n",
    "\n",
    "It's better to use the built-in `timeit` module for more accurate measurements.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "\n",
    "def costly_func():\n",
    "    \"\"\"Joins numbers together\"\"\"\n",
    "    return \"-\".join(str(n) for n in range(10))\n",
    "\n",
    "# Measure it since costly_func is a callable without argument\n",
    "# costly_func will be called 1000000 times (the default)\n",
    "result = timeit.timeit(costly_func)\n",
    "print(\"Callable  cost: {:.4} seconds\".format(result))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Try it as a quoted statement -- also called 1000000 times\n",
    "result = timeit.timeit('\"-\".join(str(i) for i in range(10))')\n",
    "print(\"Statement cost: {:.4} seconds\".format(result))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remember that `timeit` measures the CUMULATIVE time over 1000000 calls.  One million = 1_000_000.  In order to get the time cost of a single call to the function, we divide by 1000000.  This is an easy conversion -- it's the same number just in microseconds.  One millionth of a second is a microsecond."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "result = timeit.timeit('\"-\".join(str(i) for i in range(10))')\n",
    "print(\"Cumulative time cost: {:.4} seconds\".format(result))\n",
    "print(\"Per call time cost  : {:.4} seconds\".format(result/1000000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why is the cost of running as a statement, LESS than the cost of the callable method (above) ?  That's a [good question](https://stackoverflow.com/questions/55187176/why-does-the-timeit-function-return-different-results-when-handed-a-function-v) ... The additional time cost is from setting up for a function call.\n",
    "\n",
    "Let's find out how much time is spent just setting up for a function call:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A function that does nothing (NO OPERATION)\n",
    "def no_op_func():\n",
    "    pass\n",
    "\n",
    "# The theory is that t_stmt + t_noop = t_costly\n",
    "t_noop = timeit.timeit(no_op_func)\n",
    "t_costly = timeit.timeit(costly_func)\n",
    "t_stmt = timeit.timeit('\"-\".join(str(i) for i in range(10))')\n",
    "print(\"Does {:.2} + {:.2} ≈ {:.2} ?\".format(t_stmt, t_noop, t_costly))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using the Jupyter %timeit\n",
    "Here are three different ways of creating a string of 100 integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%timeit '\"-\".join(str(n) for n in range(10))' # generator\n",
    "\n",
    "%timeit '\"-\".join([str(n) for n in range(10)])' # list comprehension\n",
    "\n",
    "%timeit '\"-\".join(map(str, range(10)))' # map function\n",
    "\n",
    "# Wait for it .... (below)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Importing the timeit module"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "n = 10000\n",
    "t1_sec = timeit.timeit('\"-\".join(str(n) for n in range(100))', number=n) # generator\n",
    "t2_sec = timeit.timeit('\"-\".join([str(n) for n in range(100)])', number=n) # list\n",
    "t3_sec = timeit.timeit('\"-\".join(map(str, range(100)))', number=n) # map\n",
    "\n",
    "t1_us = t1_sec / n * 1e+6\n",
    "t2_us = t2_sec / n * 1e+6\n",
    "t3_us = t3_sec / n * 1e+6\n",
    "print(f'Generator method: {t1_us:.4f} usec')\n",
    "print(f'list comprehension method: {t2_us:.4f} usec')\n",
    "print(f'map method: {t3_us:.2f} usec')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note** By default, timeit() temporarily turns off garbage collection during the timing. The advantage of this approach is that it makes independent timings more comparable. This disadvantage is that GC may be an important component of the performance of the function being measured. If so, GC can be re-enabled as the first statement in the setup string. For example:\n",
    "\n",
    "> `timeit.Timer('for i in xrange(10): oct(i)', 'gc.enable()').timeit()`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Creating a timeit.Timer class object\n",
    "We can use an instance of a `timeit.Timer` object to explore the `timer` and `repeat` methods"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "\n",
    "# Create the instance\n",
    "t = timeit.Timer(\"print('main statement')\", \"print('setup')\")\n",
    "\n",
    "print('TIMEIT number=2:')\n",
    "print(t.timeit(number=2))\n",
    "\n",
    "print('REPEAT repeat=3 number=2:')\n",
    "print(t.repeat(repeat=3, number=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Storing Values in a Dictionary\n",
    "These snippets use `timeit` to compare various methods of populating a dictionary\n",
    "\n",
    "This more complex example compares the amount of time it takes to populate a dictionary with a large number of values using a variety of methods. First, a few constants are needed to configure the Timer. The setup_statement variable initializes a list of tuples containing strings and integers that will be used by the main statements to build dictionaries using the strings as keys and storing the integers as the associated values.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# First, a few setups ...\n",
    "range_size = 1000\n",
    "count = 1000\n",
    "setup_statement = ';'.join([\n",
    "    \"l = [(str(x), x) for x in range(1000)]\",\n",
    "    \"d = {}\",\n",
    "])\n",
    "setup_statement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A helper function to print results\n",
    "def show_results(result):\n",
    "    \"\"\"Print microseconds per pass and per item.\"\"\"\n",
    "    global count, range_size\n",
    "    per_pass = 1000000 * (result / count)\n",
    "    print('{:6.2f} usec/pass'.format(per_pass), end=' ')\n",
    "    per_item = per_pass / range_size\n",
    "    print('{:6.2f} usec/item'.format(per_item))\n",
    "\n",
    "\n",
    "print(\"{} items\".format(range_size))\n",
    "print(\"{} iterations\".format(count))\n",
    "print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To establish a baseline, the first configuration tested uses __setitem__(). All of the other variations avoid overwriting values already in the dictionary, so this simple version should be the fastest.\n",
    "\n",
    "The first argument to Timer is a multi-line string, with white space preserved to ensure that it parses correctly when run. The second argument is a constant established to initialize the list of values and the dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import textwrap\n",
    "# Using __setitem__ (square brackets []) without checking for existing values first\n",
    "print('__setitem__:', end=' ')\n",
    "t = timeit.Timer(\n",
    "    textwrap.dedent(\n",
    "        \"\"\"\n",
    "        for s, i in l:\n",
    "            d[s] = i\n",
    "        \"\"\"),\n",
    "    setup_statement,\n",
    ")\n",
    "show_results(t.timeit(number=count))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using setdefault method\n",
    "print('setdefault :', end=' ')\n",
    "t = timeit.Timer(\n",
    "    textwrap.dedent(\n",
    "        \"\"\"\n",
    "        for s, i in l:\n",
    "            d.setdefault(s, i)\n",
    "        \"\"\"),\n",
    "    setup_statement,\n",
    ")\n",
    "show_results(t.timeit(number=count))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This method adds the value only if a KeyError exception is raised when looking for the existing value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using exceptions\n",
    "print('KeyError   :', end=' ')\n",
    "t = timeit.Timer(\n",
    "    textwrap.dedent(\n",
    "        \"\"\"\n",
    "        for s, i in l:\n",
    "            try:\n",
    "                existing = d[s]\n",
    "            except KeyError:\n",
    "                d[s] = i\n",
    "        \"\"\"),\n",
    "    setup_statement,\n",
    ")\n",
    "show_results(t.timeit(number=count))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And the last method uses “in” to determine if a dictionary has a particular key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using \"in\"\n",
    "print('\"not in\"   :', end=' ')\n",
    "t = timeit.Timer(\n",
    "    textwrap.dedent(\n",
    "        \"\"\"\n",
    "        for s, i in l:\n",
    "            if s not in d:\n",
    "                d[s] = i\n",
    "        \"\"\"),\n",
    "    setup_statement,\n",
    ")\n",
    "show_results(t.timeit(number=count))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusions\n",
    "- Use the `timeit` module for more accurate measurements of small code samples.  It collects results over many iterations of the code.\n",
    "- Use `timeit` to try out different approaches to solving an algorithm, transform, or other problem.  Compare the times and pick the approach that yields the fastest time."
   ]
  },
  {
   "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}