20160523-cohpy-speed-of-searching-sets-and-lists-simplified.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook explores the speed of searching for values in sets and lists.\n",
    "\n",
    "After reading this notebook, watch Brandon Rhodes' videos [All Your Ducks In A Row: Data Structures in the Standard Library and Beyond](http://pyvideo.org/video/2571/all-your-ducks-in-a-row-data-structures-in-the-s) and [The Mighty Dictionary](http://pyvideo.org/video/276/the-mighty-dictionary-55)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def make_list(n):\n",
    "    if True:\n",
    "        return list(range(n))\n",
    "    else:\n",
    "        return list(str(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "n = int(25e6)\n",
    "# n = 5\n",
    "m = (0, n // 2, n-1, n)\n",
    "a_list = make_list(n)\n",
    "a_set = set(a_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(25000000, (0, 12500000, 24999999, 25000000))"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n, m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 31.03 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 94.5 ns per loop\n",
      "The slowest run took 36.07 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 124 ns per loop\n",
      "The slowest run took 36.07 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 128 ns per loop\n",
      "The slowest run took 49.88 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 91 ns per loop\n"
     ]
    }
   ],
   "source": [
    "# Finding something that is in a set is fast.\n",
    "# The key one is looking for has little effect on the speed.\n",
    "beginning = 0\n",
    "middle = n//2\n",
    "end = n-1\n",
    "%timeit beginning in a_set\n",
    "%timeit middle in a_set\n",
    "%timeit end in a_set\n",
    "# Finding something that is _not_ in a set is also fast.\n",
    "%timeit n in a_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 55.34 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 82 ns per loop\n",
      "1 loop, best of 3: 318 ms per loop\n",
      "1 loop, best of 3: 717 ms per loop\n",
      "1 loop, best of 3: 641 ms per loop\n"
     ]
    }
   ],
   "source": [
    "# Searching for something in a list\n",
    "# starts at the beginning and compares each value.\n",
    "# The search time depends on where the value is in the list.\n",
    "# That can be slow.\n",
    "beginning = 0\n",
    "middle = n//2\n",
    "end = n-1\n",
    "%timeit beginning in a_list\n",
    "%timeit middle in a_list\n",
    "%timeit end in a_list\n",
    "# Finding something that is not is a list is the worst case.\n",
    "# It has to be compared to all values of the list.\n",
    "%timeit n in a_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "max_exponent = 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length is 10, looking for 0\n",
      "The slowest run took 43.58 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 107 ns per loop\n",
      "length is 10, looking for 5\n",
      "The slowest run took 44.00 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 105 ns per loop\n",
      "length is 10, looking for 9\n",
      "The slowest run took 19.51 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 104 ns per loop\n",
      "length is 10, looking for 10\n",
      "The slowest run took 20.81 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 104 ns per loop\n",
      "length is 100, looking for 0\n",
      "The slowest run took 44.31 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 104 ns per loop\n",
      "length is 100, looking for 50\n",
      "The slowest run took 18.72 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 104 ns per loop\n",
      "length is 100, looking for 99\n",
      "The slowest run took 43.18 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 105 ns per loop\n",
      "length is 100, looking for 100\n",
      "The slowest run took 45.36 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 102 ns per loop\n",
      "length is 1000, looking for 0\n",
      "The slowest run took 43.49 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 104 ns per loop\n",
      "length is 1000, looking for 500\n",
      "The slowest run took 33.52 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 133 ns per loop\n",
      "length is 1000, looking for 999\n",
      "The slowest run took 34.87 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 132 ns per loop\n",
      "length is 1000, looking for 1000\n",
      "The slowest run took 45.38 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 102 ns per loop\n",
      "length is 10000, looking for 0\n",
      "The slowest run took 307.19 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 109 ns per loop\n",
      "length is 10000, looking for 5000\n",
      "The slowest run took 34.24 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 133 ns per loop\n",
      "length is 10000, looking for 9999\n",
      "The slowest run took 34.74 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 133 ns per loop\n",
      "length is 10000, looking for 10000\n",
      "The slowest run took 45.18 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 102 ns per loop\n",
      "length is 100000, looking for 0\n",
      "The slowest run took 42.87 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 106 ns per loop\n",
      "length is 100000, looking for 50000\n",
      "The slowest run took 31.87 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 149 ns per loop\n",
      "length is 100000, looking for 99999\n",
      "The slowest run took 34.94 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 136 ns per loop\n",
      "length is 100000, looking for 100000\n",
      "The slowest run took 45.70 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 104 ns per loop\n",
      "length is 1000000, looking for 0\n",
      "The slowest run took 48.98 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 106 ns per loop\n",
      "length is 1000000, looking for 500000\n",
      "The slowest run took 35.03 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 136 ns per loop\n",
      "length is 1000000, looking for 999999\n",
      "The slowest run took 34.24 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 135 ns per loop\n",
      "length is 1000000, looking for 1000000\n",
      "The slowest run took 41.36 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 111 ns per loop\n"
     ]
    }
   ],
   "source": [
    "for n in (10 ** i for i in range(1, max_exponent+1)):\n",
    "    a_list = make_list(n)\n",
    "    a_set = set(a_list)\n",
    "\n",
    "    m = (0, n // 2, n-1, n)\n",
    "    for j in m:\n",
    "        print('length is %s, looking for %s' % (n, j))\n",
    "        %timeit j in a_set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the difference between searching small sets and large sets in not large. This is the magic of Python sets and dictionaries. Read the [hash table](https://en.wikipedia.org/wiki/Hash_table) Wikipedia article for an explanation of how this works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length is 10, looking for 0\n",
      "The slowest run took 50.46 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 92.7 ns per loop\n",
      "length is 10, looking for 5\n",
      "The slowest run took 20.69 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 3: 219 ns per loop\n",
      "length is 10, looking for 9\n",
      "The slowest run took 8.15 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 3: 317 ns per loop\n",
      "length is 10, looking for 10\n",
      "The slowest run took 13.85 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 3: 338 ns per loop\n",
      "length is 100, looking for 0\n",
      "The slowest run took 22.01 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 92 ns per loop\n",
      "length is 100, looking for 50\n",
      "1000000 loops, best of 3: 1.33 µs per loop\n",
      "length is 100, looking for 99\n",
      "100000 loops, best of 3: 2.56 µs per loop\n",
      "length is 100, looking for 100\n",
      "100000 loops, best of 3: 2.58 µs per loop\n",
      "length is 1000, looking for 0\n",
      "The slowest run took 50.02 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 90.8 ns per loop\n",
      "length is 1000, looking for 500\n",
      "100000 loops, best of 3: 12.5 µs per loop\n",
      "length is 1000, looking for 999\n",
      "10000 loops, best of 3: 25 µs per loop\n",
      "length is 1000, looking for 1000\n",
      "10000 loops, best of 3: 25 µs per loop\n",
      "length is 10000, looking for 0\n",
      "The slowest run took 22.14 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 91.5 ns per loop\n",
      "length is 10000, looking for 5000\n",
      "10000 loops, best of 3: 125 µs per loop\n",
      "length is 10000, looking for 9999\n",
      "1000 loops, best of 3: 249 µs per loop\n",
      "length is 10000, looking for 10000\n",
      "1000 loops, best of 3: 250 µs per loop\n",
      "length is 100000, looking for 0\n",
      "The slowest run took 22.30 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 90.8 ns per loop\n",
      "length is 100000, looking for 50000\n",
      "1000 loops, best of 3: 1.43 ms per loop\n",
      "length is 100000, looking for 99999\n",
      "100 loops, best of 3: 2.8 ms per loop\n",
      "length is 100000, looking for 100000\n",
      "100 loops, best of 3: 2.41 ms per loop\n",
      "length is 1000000, looking for 0\n",
      "The slowest run took 49.94 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 3: 90.9 ns per loop\n",
      "length is 1000000, looking for 500000\n",
      "100 loops, best of 3: 12.7 ms per loop\n",
      "length is 1000000, looking for 999999\n",
      "10 loops, best of 3: 25.5 ms per loop\n",
      "length is 1000000, looking for 1000000\n",
      "10 loops, best of 3: 25.6 ms per loop\n"
     ]
    }
   ],
   "source": [
    "for n in (10 ** i for i in range(1, max_exponent+1)):\n",
    "    a_list = make_list(n)\n",
    "    a_set = set(a_list)\n",
    "\n",
    "    m = (0, n // 2, n-1, n)\n",
    "    for j in m:\n",
    "        print('length is %s, looking for %s' % (n, j))\n",
    "        %timeit j in a_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the search time for finding something in a list is proportional to the length of the list and how far the item is from the beginning of the list."
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}