lessons/Code Optimization.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:383e612e95d39e999ff086db09dc847c56690a8c59d305c430f1ef89656ed61f"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Optimization in Python"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%matplotlib inline\n",
      "import matplotlib.pyplot as plt\n",
      "import numpy as np"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Basics"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Remember \"Premature optimization is the root of all evil in programming\" - Don Knuth\n",
      "\n",
      "Install profling tools:\n",
      "```bash\n",
      "pip install --pre line-profiler\n",
      "pip install psutil\n",
      "pip install memory_profiler\n",
      "```\n",
      "\n",
      "References:\n",
      "\n",
      "1. <http://scipy-lectures.github.com/advanced/optimizing/index.html>\n",
      "2. <http://pynash.org/2013/03/06/timing-and-profiling.html>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Timing code\n",
      "----"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import time\n",
      "import timeit\n",
      "\n",
      "def f(nsec=1.0):\n",
      "    \"\"\"Function sleeps for nsec seconds.\"\"\"\n",
      "    time.sleep(nsec) \n",
      "    \n",
      "start = timeit.default_timer()\n",
      "f()\n",
      "elapsed = timeit.default_timer() - start\n",
      "elapsed"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "1.0013420581817627"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# We can make a decorator for conveneience\n",
      "\n",
      "def process_time(f, *args, **kwargs):\n",
      "    def func(*args, **kwargs):\n",
      "        import timeit\n",
      "        start = timeit.default_timer()\n",
      "        f(*args, **kwargs)\n",
      "        print timeit.default_timer() - start\n",
      "    return func"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "@process_time\n",
      "def f1(nsec):\n",
      "    \"\"\"Function sleeps for nsec seconds.\"\"\"\n",
      "    time.sleep(nsec)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "f1(3.0)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3.00106906891\n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Within the ipython notebook, use the timeit magic function"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit f()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 1 s per loop\n"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Timing each function in a script."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def f2():\n",
      "    time.sleep(2)\n",
      "\n",
      "def f3():\n",
      "    time.sleep(3)\n",
      "\n",
      "def f5():\n",
      "    f2()\n",
      "    f3()\n",
      "    \n",
      "%prun f5()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " "
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Checking memory usage"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%load_ext memory_profiler"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%%file foo.py\n",
      "\n",
      "def foo(n):\n",
      "    phrase = 'repeat me'\n",
      "    pmul = phrase * n\n",
      "    pjoi = ''.join([phrase for x in xrange(n)])\n",
      "    pinc = ''\n",
      "    for x in xrange(n):\n",
      "        pinc += phrase\n",
      "    del pmul, pjoi, pinc"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Writing foo.py\n"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# mprun requires the code be in a file \n",
      "# funcions declared interactively in python will not work\n",
      "\n",
      "from foo import foo\n",
      "\n",
      "%mprun -f foo foo(100000)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "('',)\n"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# However, memit does work with interactive functions\n",
      "# Unlike mprun which gives a line by line analysis\n",
      "# memit gives the total amount of memory used\n",
      "\n",
      "def gobble(n):\n",
      "    x = [i*i for i in range(n)]\n",
      "    \n",
      "%memit -r 3 gobble(1000000)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "peak memory: 116.90 MiB, increment: 56.50 MiB\n"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Sequence of possible optimizations to try"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "- Appropriate data structures\n",
      "- Appropriate algorithms\n",
      "- Caching, memoization and dynamic programming\n",
      "- Python-specific idioms\n",
      "- Vectorizaation\n",
      "- Using native code (JIT, Cython, wrappers)\n",
      "- Simple parallelization (IPython parallel, multiprocessing)\n",
      "- Using MPI\n",
      "- Massively parallel programming\n",
      "- Map-reduce\n",
      "- Using cloud computing resoruces"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Data structures"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Find unique elements in common between xs and ys. Illustrates use of the set data structure.\"\"\"\n",
      "\n",
      "def common1(xs, ys):\n",
      "    \"\"\"Using lists.\"\"\"\n",
      "    zs = set([])\n",
      "    for x in xs:\n",
      "        for y in ys:\n",
      "            if x==y:\n",
      "                zs.add(x)\n",
      "    return zs\n",
      "\n",
      "def common2(xs, ys):\n",
      "    \"\"\"Using sets.\"\"\"\n",
      "    return set(xs) & set(ys)\n",
      "\n",
      "def main():\n",
      "    n = 5000\n",
      "    xs = npr.randint(1, 100, n)\n",
      "    ys = npr.randint(50, 150, n)\n",
      "    \n",
      "    z1 = common1(xs, ys)\n",
      "    z2 = common2(xs, ys)\n",
      "    \n",
      "    assert(z1 == z2)\n",
      "\n",
      "xs = np.random.randint(0, 1000, 100)\n",
      "ys = np.random.randint(0, 1000, 100)\n",
      "%timeit common1(xs, ys)\n",
      "%timeit common2(xs, ys)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100 loops, best of 3: 2.67 ms per loop\n",
        "10000 loops, best of 3: 69.1 \u00b5s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Find values corresponding to set of keys from a dictionary. \n",
      "Illustrates subtle mistake in searching dictionary.\"\"\"\n",
      "\n",
      "adict = dict(zip(np.arange(100000), np.random.randint(0,10,10000)))\n",
      "\n",
      "def search1(adict, targets):\n",
      "    \"\"\"Using a list.\"\"\"\n",
      "    return [adict[t] for t in targets if t in adict.keys()]\n",
      "\n",
      "def search2(adict, targets):\n",
      "    \"\"\"Using a dict.\"\"\"\n",
      "    return [adict[t] for t in targets if t in adict]\n",
      "\n",
      "targets = np.random.randint(0, 1000000, 10000)\n",
      "%timeit search1(adict, targets)\n",
      "%timeit search2(adict, targets)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 4.34 s per loop\n",
        "100 loops, best of 3: 2.17 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Find minimum item in a list each time a new item is inserted. \n",
      "Illustrates use of priority queue data structure.\"\"\"\n",
      "\n",
      "from heapq import heappushpop, heapify\n",
      "\n",
      "def f1(alist, entries):\n",
      "    \"\"\"Using repeated sorts.\"\"\"\n",
      "    zs = []\n",
      "    for entry in entries:\n",
      "        alist.append(entry)\n",
      "        alist.sort(reverse=True)\n",
      "        zs.append(alist.pop())\n",
      "    return zs\n",
      "\n",
      "def f2(alist, entries):\n",
      "    \"\"\"Using a priority queue.\"\"\"\n",
      "    heapify(alist)\n",
      "    zs = []\n",
      "    for entry in entries:\n",
      "        zs.append(heappushpop(alist, entry))\n",
      "    return zs\n",
      "\n",
      "alist = list(np.random.randint(1000, 100000, 1000))\n",
      "blist = alist[:]\n",
      "entries = np.random.randint(1, 10000, 10000)\n",
      "    \n",
      "%timeit f1(alist, entries)\n",
      "%timeit f2(blist, entries)    "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 369 ms per loop\n",
        "100 loops, best of 3: 6.5 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Algorithms"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Subset sum problem solved by brute force and with dynamic programming.\"\"\"\n",
      "\n",
      "import itertools\n",
      "\n",
      "def knapsack1(size, values):\n",
      "    \"\"\"Using brute force search.\"\"\"\n",
      "    n = len(values)\n",
      "    if size > np.sum(values):\n",
      "        return False\n",
      "    for i in range(1, n):\n",
      "        for group in itertools.combinations(values, i):\n",
      "            if size == np.sum(group):\n",
      "                return True\n",
      "    return False\n",
      "            \n",
      "def knapsack2(size, values):\n",
      "    \"\"\"Using dynamic programming. Note trade-off in complexity.\"\"\"\n",
      "    n = len(values)\n",
      "    s = np.sum(values)\n",
      "    if size > np.sum(values):\n",
      "        return False\n",
      "    solns = {}\n",
      "    table = np.zeros((n, s+1), dtype='bool')\n",
      "    table[0][values[0]] = True\n",
      "    for i in xrange(1, n):\n",
      "        for j in xrange(0, s):\n",
      "            table[i][j] = values[i] == j or table[i-1][j] or table[i-1][j-values[i]]\n",
      "    return table[-1][size]\n",
      "    \n",
      "s = 149\n",
      "values = np.array([12, 15, 8, 13, 11, 19, 12, 13, 14, 15, 7, 1, 12, 8, 9])\n",
      "%timeit knapsack1(s, values)\n",
      "%timeit knapsack2(s, values)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 724 ms per loop\n",
        "100 loops, best of 3: 11.1 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Python idioms for speed"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"String concatenation\"\"\"\n",
      "\n",
      "def concat1(alist):\n",
      "    \"\"\"Using string concatenation.\"\"\"\n",
      "    s = alist[0]\n",
      "    for item in alist[1:]:\n",
      "        s += \" \" + item\n",
      "    return s\n",
      "    \n",
      "def concat2(alist):\n",
      "    \"\"\"Using join.\"\"\"\n",
      "    return \" \".join(alist)\n",
      "\n",
      "alist = ['abcde'] * 1000000\n",
      "%timeit concat1(alist)\n",
      "%timeit concat2(alist)    "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 308 ms per loop\n",
        "100 loops, best of 3: 17.5 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Avoiding loops.\"\"\"\n",
      "\n",
      "import math\n",
      "\n",
      "def loop1(n):\n",
      "    \"\"\"Using for loop with function call.\"\"\"\n",
      "    z = []\n",
      "    for i in xrange(n):\n",
      "        z.append(math.sin(i))\n",
      "    return z\n",
      "\n",
      "def loop2(n):\n",
      "    \"\"\"Using local version of function.\"\"\"\n",
      "    z = []\n",
      "    sin = math.sin\n",
      "    for i in xrange(n):\n",
      "        z.append(sin(i))\n",
      "    return z\n",
      "\n",
      "def loop3(n):\n",
      "    \"\"\"Using list comprehension.\"\"\"\n",
      "    sin = math.sin\n",
      "    return [sin(i) for i in xrange(n)]\n",
      "\n",
      "def loop4(n):\n",
      "    \"\"\"Using map.\"\"\"\n",
      "    sin = math.sin\n",
      "    return map(sin, xrange(n))\n",
      "\n",
      "def loop5(n):\n",
      "    \"\"\"Using numpy.\"\"\"\n",
      "    return np.sin(np.arange(n)).tolist()\n",
      "\n",
      "n = 1000000\n",
      "%timeit loop1(n)\n",
      "%timeit loop2(n)\n",
      "%timeit loop3(n)\n",
      "%timeit loop4(n)\n",
      "%timeit loop5(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 396 ms per loop\n",
        "1 loops, best of 3: 292 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10 loops, best of 3: 192 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10 loops, best of 3: 153 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10 loops, best of 3: 80.5 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"I/O bounded.\"\"\"\n",
      "\n",
      "def io1(xs):\n",
      "    \"\"\"Using loops to write.\"\"\"\n",
      "    with open('foo1.txt', 'w') as f:\n",
      "        for x in xs:\n",
      "            f.write('%d\\t' % x)\n",
      "    \n",
      "def io2(xs):\n",
      "    \"\"\"Join before writing.\"\"\"\n",
      "    with open('foo2.txt', 'w') as f:\n",
      "        f.write('\\t'.join(map(str, xs)))\n",
      "        \n",
      "def io3(xs):\n",
      "    \"\"\"Numpy savetxt is surprisingly slow.\"\"\"\n",
      "    np.savetxt('foo3.txt', xs, delimiter='\\t')\n",
      "        \n",
      "def io4(xs):\n",
      "    \"\"\"NUmpy save is better if binary format is OK.\"\"\"\n",
      "    np.save('foo4.npy', xs)\n",
      "   \n",
      "def io5(xs):\n",
      "    \"\"\"Using HDF5.\"\"\"\n",
      "    import h5py\n",
      "    with h5py.File(\"mytestfile.h5\", \"w\") as f:\n",
      "        ds = f.create_dataset(\"xs\", (len(xs),), dtype='i')\n",
      "        ds[:] = xs\n",
      "    \n",
      "n = 1000*1000\n",
      "xs = range(n)\n",
      "%timeit io1(xs)\n",
      "%timeit io2(xs)\n",
      "%timeit io3(xs)\n",
      "%timeit io4(xs)\n",
      "%timeit io5(xs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 1.68 s per loop\n",
        "1 loops, best of 3: 334 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1 loops, best of 3: 6.12 s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10 loops, best of 3: 212 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1 loops, best of 3: 160 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Use of caching to trade space for time.\"\"\"\n",
      "\n",
      "def fib(n):\n",
      "    if n <= 2:\n",
      "        return 1\n",
      "    else:\n",
      "        return fib(n-1) + fib(n-2)\n",
      "\n",
      "def memoize1(f):\n",
      "    store = {}\n",
      "    def func(n):\n",
      "        if n not in store:\n",
      "            store[n] = f(n)\n",
      "        return store[n]\n",
      "    return func\n",
      "\n",
      "   \n",
      "# From http://code.activestate.com/recipes/578231-probably-the-fastest-memoization-decorator-in-the-/\n",
      "\n",
      "def memoize2(f):\n",
      "  class memodict(dict):\n",
      "      __slots__ = ()\n",
      "      def __missing__(self, key):\n",
      "          self[key] = ret = f(key)\n",
      "          return ret\n",
      "  return memodict().__getitem__\n",
      "    \n",
      "# Version with LRU cache to prevent excessive memory use\n",
      "from pylru import lrudecorator\n",
      "\n",
      "lrufib = lrudecorator(100)(fib)\n",
      "\n",
      "@memoize1\n",
      "def cfib(n):\n",
      "    return fib(n)\n",
      "\n",
      "@memoize2\n",
      "def mfib(n):\n",
      "    return fib(n)\n",
      "\n",
      "print fib(10)\n",
      "print cfib(10)\n",
      "print mfib(10)\n",
      "print lrufib(10)\n",
      "\n",
      "%timeit -n 3 fib(30)\n",
      "%timeit -n 10 cfib(30)\n",
      "%timeit -n 10 mfib(30)\n",
      "%timeit -n 10 lrufib(30)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "55\n",
        "55\n",
        "55\n",
        "55\n",
        "3 loops, best of 3: 372 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10 loops, best of 3: 286 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10 loops, best of 3: 191 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10 loops, best of 3: 2.69 \u00b5s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# We can also remove recursion entirely\n",
      "# and this is the most efficient approach\n",
      "# for large n\n",
      "\n",
      "def ifib(n):\n",
      "    t = [0, 1]\n",
      "    for i in xrange(n):\n",
      "        t.append(t[-1] + t[-2])\n",
      "    return t[-2]\n",
      "\n",
      "%timeit -n 10 ifib(1000)\n",
      "ifib(10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10 loops, best of 3: 310 \u00b5s per loop\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 21,
       "text": [
        "55"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Of course, the fastest calculation is with the closed-form solution\n",
      "\n",
      "def binetfib(n):\n",
      "    sqrt5 = 5**0.5\n",
      "    Phi = 0.5*(1+sqrt5)\n",
      "    _phi = 0.5*(1-sqrt5)\n",
      "    return int((Phi**n  - _phi**n)/sqrt5 + 0.5) # round to correct floating point errors\n",
      "\n",
      "%timeit -n 10 ifib(1000)\n",
      "%timeit -n 10 binetfib(1000)\n",
      "binetfib(10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10 loops, best of 3: 308 \u00b5s per loop\n",
        "10 loops, best of 3: 1.6 \u00b5s per loop\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 22,
       "text": [
        "55"
       ]
      }
     ],
     "prompt_number": 22
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Numpy and Scipy"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"In place operations are faster than copying.\"\"\"\n",
      "\n",
      "a = np.arange(1e6)\n",
      "    \n",
      "%timeit global a; a = a * 0\n",
      "%timeit global a; a *= 0"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100 loops, best of 3: 4.9 ms per loop\n",
        "100 loops, best of 3: 2.6 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Use small strides to maximize cache hits. Variable results.\"\"\"\n",
      "\n",
      "def f1(xs):\n",
      "    return xs.sum(axis=1)\n",
      "\n",
      "def f2(xs):\n",
      "    return xs.sum(axis=0)\n",
      "\n",
      "xs = np.zeros((1e4, 1e4), order='C')\n",
      "%timeit global xs; f1(xs)\n",
      "%timeit global xs; f2(xs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 232 ms per loop\n",
        "1 loops, best of 3: 243 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Numpy indexing tricks to avoid looping.\"\"\"\n",
      "\n",
      "def idx1(xs):\n",
      "    \"\"\"Using loops.\"\"\"\n",
      "    s = 0\n",
      "    for x in xs:\n",
      "        if (x > 10) and (x < 20):\n",
      "            s += x\n",
      "    return s\n",
      "\n",
      "def idx2(xs):\n",
      "    \"\"\"Using logical indexing.\"\"\"\n",
      "    return np.sum(xs[(xs > 10) & (xs < 20)])\n",
      "\n",
      "n = 1000000\n",
      "xs = np.random.randint(0, 100, n)\n",
      "%timeit idx1(xs)\n",
      "%timeit idx2(xs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 2.11 s per loop\n",
        "100 loops, best of 3: 12 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"More indexing tricks - stencil operations to average over 9 neighbors with zero boundary conditions\"\"\"\n",
      "\n",
      "def average1(xs):\n",
      "    \"\"\"Using loops.\"\"\"\n",
      "    ys = xs.copy()\n",
      "    rows, cols = xs.shape\n",
      "    for i in range(rows):\n",
      "        for j in range(cols):\n",
      "            s = 0\n",
      "            for u in range(i-1, i+2):\n",
      "                if u < 0 or u >= rows:\n",
      "                    continue\n",
      "                for v in range(j-1, j+2):\n",
      "                    if v < 0 or v >= cols:\n",
      "                        continue\n",
      "                    s += xs[u, v]\n",
      "            ys[i, j] = s/9.0\n",
      "    return ys\n",
      "\n",
      "def average2(xs):\n",
      "    \"\"\"Using shifted array views and border to avoid out of bounds checks.\"\"\"\n",
      "    rows, cols = xs.shape\n",
      "    xs1 = np.zeros((rows+2, cols+2))\n",
      "    xs1[1:-1, 1:-1] = xs[:]\n",
      "    ys = (xs1[:-2, :-2]  + xs1[1:-1, :-2]  + xs1[2:, :-2] +\n",
      "          xs1[:-2, 1:-1] + xs1[1:-1, 1:-1] + xs1[2:, 1:-1] +\n",
      "          xs1[:-2, 2:]   + xs1[1:-1, 2:]   + xs1[2:, 2:])/9.0\n",
      "    return ys\n",
      "\n",
      "n = 25\n",
      "xs = np.random.uniform(0,10,(n, n))\n",
      "%timeit average1(xs)\n",
      "%timeit average2(xs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100 loops, best of 3: 9.32 ms per loop\n",
        "10000 loops, best of 3: 118 \u00b5s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 26
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Repeat and tile.\"\"\"\n",
      "\n",
      "def main():\n",
      "    x = np.arange(1,5)\n",
      "    print x\n",
      "    print '='*30\n",
      "    print x.repeat(2)\n",
      "    print '='*30\n",
      "    print x.repeat([1,2,3,4])\n",
      "    print\n",
      "    print\n",
      "\n",
      "    y = np.arange(1,9).reshape(2,4)\n",
      "    print y\n",
      "    print '='*30\n",
      "    print y.repeat(2)\n",
      "    print '='*30\n",
      "    print y.repeat(2, axis=1)\n",
      "    print '='*30\n",
      "    print y.repeat(2, axis=0)\n",
      "    print '='*30\n",
      "    print y.repeat([1,2,3,4], axis=1)\n",
      "    print '='*30\n",
      "    print y.repeat([1,2], axis=0)\n",
      "    print \n",
      "    print\n",
      "\n",
      "    z = np.arange(1, 5).reshape(2,2)\n",
      "    print z\n",
      "    print '='*30\n",
      "    # make 1 row and 2 cols of the block z\n",
      "    # broadcasting rules prepend1 to missing dimensions\n",
      "    # so tile(z, 2) is equivalnet to tile(z, (1,2))\n",
      "    print np.tile(z, 2)\n",
      "    print '='*30\n",
      "    # make 2 rows and 3 cols of the block z\n",
      "    print np.tile(z, (2,3))\n",
      "    \n",
      "main()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[1 2 3 4]\n",
        "==============================\n",
        "[1 1 2 2 3 3 4 4]\n",
        "==============================\n",
        "[1 2 2 3 3 3 4 4 4 4]\n",
        "\n",
        "\n",
        "[[1 2 3 4]\n",
        " [5 6 7 8]]\n",
        "==============================\n",
        "[1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8]\n",
        "==============================\n",
        "[[1 1 2 2 3 3 4 4]\n",
        " [5 5 6 6 7 7 8 8]]\n",
        "==============================\n",
        "[[1 2 3 4]\n",
        " [1 2 3 4]\n",
        " [5 6 7 8]\n",
        " [5 6 7 8]]\n",
        "==============================\n",
        "[[1 2 2 3 3 3 4 4 4 4]\n",
        " [5 6 6 7 7 7 8 8 8 8]]\n",
        "==============================\n",
        "[[1 2 3 4]\n",
        " [5 6 7 8]\n",
        " [5 6 7 8]]\n",
        "\n",
        "\n",
        "[[1 2]\n",
        " [3 4]]\n",
        "==============================\n",
        "[[1 2 1 2]\n",
        " [3 4 3 4]]\n",
        "==============================\n",
        "[[1 2 1 2 1 2]\n",
        " [3 4 3 4 3 4]\n",
        " [1 2 1 2 1 2]\n",
        " [3 4 3 4 3 4]]\n"
       ]
      }
     ],
     "prompt_number": 27
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Random choice.\"\"\"\n",
      "\n",
      "def main():\n",
      "    x = np.arange(1, 30)\n",
      "    k = 10\n",
      "\n",
      "    # select with repetition \n",
      "    print np.random.choice(x, 10)\n",
      "\n",
      "    # select without repetition\n",
      "    print np.random.choice(x, 10, replace=False)\n",
      "\n",
      "    # weighted selection to favor bigger numbers\n",
      "    wts = np.arange(1, len(x)+1, dtype='float')\n",
      "    wts /= np.sum(wts)\n",
      "    print np.random.choice(x, 10, p=wts)\n",
      "    \n",
      "main()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[ 8  3  6 23  8 14 15 18 26 23]\n",
        "[25 13  8 17 18  3 24  9 21 15]\n",
        "[21 10 22 10 28 28 21  4 14 23]\n"
       ]
      }
     ],
     "prompt_number": 28
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Distance cacluations.\"\"\"\n",
      "\n",
      "from scipy.spatial.distance import pdist, cdist, squareform\n",
      "\n",
      "def main():\n",
      "    # find all pairwise distance between a set of points\n",
      "    xs = np.arange(1, 13).reshape(4, 3)\n",
      "    print squareform(pdist(xs), 'sqeuclidean')\n",
      "    print '=' * 30\n",
      "\n",
      "    # find all pairwise distances between 2 sets of points\n",
      "    print cdist(xs, xs[::-1], 'sqeuclidean')\n",
      "    \n",
      "main()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[[  0.           5.19615242  10.39230485  15.58845727]\n",
        " [  5.19615242   0.           5.19615242  10.39230485]\n",
        " [ 10.39230485   5.19615242   0.           5.19615242]\n",
        " [ 15.58845727  10.39230485   5.19615242   0.        ]]\n",
        "==============================\n",
        "[[ 243.  108.   27.    0.]\n",
        " [ 108.   27.    0.   27.]\n",
        " [  27.    0.   27.  108.]\n",
        " [   0.   27.  108.  243.]]\n"
       ]
      }
     ],
     "prompt_number": 29
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Dot products for matching lists of vectors or matrices.\"\"\"\n",
      "\n",
      "# find dot product of matching vectors in 2 sets of points\n",
      "from numpy.core.umath_tests import inner1d\n",
      "\n",
      "def main():\n",
      "    xs = np.arange(1,13).reshape(3,4)\n",
      "    print inner1d(xs, xs[::-1])\n",
      "\n",
      "    print '='*30\n",
      "\n",
      "    # same thing but for matrices\n",
      "    from numpy.core.umath_tests import matrix_multiply\n",
      "\n",
      "    xs = np.random.randint(0, 10, (5, 2, 2))\n",
      "    ys = np.random.randint(0, 10, (5, 2, 2))\n",
      "    print matrix_multiply(xs, ys)\n",
      "    \n",
      "main()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[110 174 110]\n",
        "==============================\n",
        "[[[65 72]\n",
        "  [81 81]]\n",
        "\n",
        " [[26 67]\n",
        "  [20 71]]\n",
        "\n",
        " [[57 36]\n",
        "  [48 63]]\n",
        "\n",
        " [[48 64]\n",
        "  [38 36]]\n",
        "\n",
        " [[63 45]\n",
        "  [28 88]]]\n"
       ]
      }
     ],
     "prompt_number": 30
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Using a memory map to read chunks from file.\"\"\"\n",
      "\n",
      "from tempfile import mktemp\n",
      "\n",
      "def main():\n",
      "    s = 6\n",
      "    x = np.arange(s*s, dtype='float').reshape(s, s)\n",
      "    f = mktemp()\n",
      "    x.tofile(f)\n",
      "\n",
      "    y1 = np.memmap(f, dtype='float', offset=0, shape=(s/2, s))\n",
      "    y2 = np.memmap(f, dtype='float', offset=s/2*x[0].nbytes, shape=(s/2, s))\n",
      "\n",
      "    print x\n",
      "    print '='*30\n",
      "    print y1\n",
      "    print '='*30\n",
      "    print y2\n",
      "    \n",
      "main()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[[  0.   1.   2.   3.   4.   5.]\n",
        " [  6.   7.   8.   9.  10.  11.]\n",
        " [ 12.  13.  14.  15.  16.  17.]\n",
        " [ 18.  19.  20.  21.  22.  23.]\n",
        " [ 24.  25.  26.  27.  28.  29.]\n",
        " [ 30.  31.  32.  33.  34.  35.]]\n",
        "==============================\n",
        "[[  0.   1.   2.   3.   4.   5.]\n",
        " [  6.   7.   8.   9.  10.  11.]\n",
        " [ 12.  13.  14.  15.  16.  17.]]\n",
        "==============================\n",
        "[[ 18.  19.  20.  21.  22.  23.]\n",
        " [ 24.  25.  26.  27.  28.  29.]\n",
        " [ 30.  31.  32.  33.  34.  35.]]\n"
       ]
      }
     ],
     "prompt_number": 31
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Vectorizing a function.\"\"\"\n",
      "\n",
      "def tlog(x):\n",
      "    if x < 1:\n",
      "        return 0\n",
      "    else:\n",
      "        return np.log(x)\n",
      "    \n",
      "vtlog = np.vectorize(tlog, otypes='d')\n",
      "\n",
      "def func1(xs):\n",
      "    return np.array(map(tlog, xs))\n",
      "\n",
      "def func2(xs):\n",
      "    return vtlog(xs)\n",
      "\n",
      "n = 100000\n",
      "xs = np.random.uniform(-10, 10, n)\n",
      "%timeit func1(xs)\n",
      "%timeit func2(xs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 433 ms per loop\n",
        "1 loops, best of 3: 216 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 32
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Using numexpr. Provides automatic parallelism and smarter JIT compilation to C code.\"\"\"\n",
      "\n",
      "import numexpr as ne\n",
      "\n",
      "a = np.random.rand(1e6)\n",
      "\n",
      "%timeit global a; np.sin(a)**2 + np.cos(a)**2\n",
      "%timeit global a; ne.evaluate(\"sin(a)**2 + cos(a)**2\")\n",
      "\n",
      "import numba\n",
      "@numba.autojit\n",
      "def f(a):\n",
      "    return np.sin(a)**2 + np.cos(a)**2\n",
      "\n",
      "%timeit f(a)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10 loops, best of 3: 63.8 ms per loop\n",
        "100 loops, best of 3: 7.8 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1 loops, best of 3: 65.7 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 33
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Parallelization"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Example showing basic use of multiprocessing.Pool.\"\"\"\n",
      "\n",
      "def slow_calc(*args):\n",
      "    import time\n",
      "    time.sleep(1)\n",
      "    return args\n",
      "\n",
      "def serial(njobs):\n",
      "    results = []\n",
      "    for i in range(njobs):\n",
      "        results.append(slow_calc([i]))\n",
      "    return results\n",
      "       \n",
      "def parallel(njobs):\n",
      "    from multiprocessing import Pool\n",
      "    p = Pool()\n",
      "    \n",
      "    argss = [[i] for i in range(njobs)]\n",
      "    p.map(slow_calc, argss)\n",
      "    \n",
      "njobs = 2\n",
      "%timeit serial(njobs)\n",
      "%timeit parallel(njobs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 2 s per loop\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 loops, best of 3: 1.03 s per loop\n"
       ]
      }
     ],
     "prompt_number": 34
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Comparing sync and async versions of apply and map. \n",
      "There is also a threading module in Python, but for numerical calculations, \n",
      "mutliprocessing is more straightforward to use.\"\"\"\n",
      "\n",
      "def calc(args):\n",
      "    i, j = args\n",
      "    return i, j\n",
      "\n",
      "def calc2(i, j):\n",
      "    return i, j\n",
      "\n",
      "def main():\n",
      "    n = 5\n",
      "    \n",
      "    from multiprocessing import Pool\n",
      "    argss = [(i, i) for i in range(n)]\n",
      "    p = Pool()\n",
      "\n",
      "    \"\"\"Use synchronous map.\"\"\"\n",
      "    results1 = p.map(calc, argss)\n",
      "    # blocks until all workers complete their tasks\n",
      "    print results1\n",
      "    \n",
      "    \"\"\"Use asynchronous map.\"\"\"\n",
      "    results2 = p.map_async(calc, argss)\n",
      "    # Do other stuff here\n",
      "    print results2.get()\n",
      "    \n",
      "    \"\"\" Use synchronous apply.\"\"\"\n",
      "    results3 = []\n",
      "    for i in range(n):\n",
      "        args = (i, i)\n",
      "        results3.append(p.apply(calc2, args))\n",
      "    # blocks until all workers complete their tasks\n",
      "    print results3\n",
      "    \n",
      "    \"\"\" Use asynchronous apply.\"\"\"\n",
      "    results4 = []\n",
      "    for i in range(n):\n",
      "        args = (i, i)\n",
      "        results4.append(p.apply_async(calc2, args))\n",
      "    # Do other stuff here\n",
      "    print [worker.get() for worker in results4]\n",
      "    \n",
      "main()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]\n",
        "[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]\n",
        "[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]\n",
        "[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]\n"
       ]
      }
     ],
     "prompt_number": 35
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Out of memory problems with multiprocessing.Pool.\n",
      "By default, each worker in a pool does not release its memory \n",
      "until all tasks are complete. This can be changed with the\n",
      "maxtasksperchild argument.\n",
      "\"\"\"\n",
      "\n",
      "from multiprocessing import Pool\n",
      "\n",
      "# each thread is destroyed and recreated after every task\n",
      "# use only 4 threadss.\n",
      "p = Pool(4, maxtasksperchild=1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 36
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"Interactive parallelism with IPython. \n",
      "\n",
      "Python has support for interactive parallel processing. See\n",
      "\n",
      "http://ipython.org/ipython-doc/dev/parallel/parallel_intro.html#parallel-overview and \n",
      "http://minrk.github.com/scipy-tutorial-2011/\n",
      "\n",
      "for details.\"\"\"\n",
      "\n",
      "pass"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 37
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Cython"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"The following series of examples shows how to code fast Cython versions.\"\"\"\n",
      "import operator\n",
      "\n",
      "def adder1(xs):\n",
      "    \"\"\"Illustrative pure Python code written in a functional style just for fun.\"\"\"\n",
      "    sqrt = np.sqrt\n",
      "    add = operator.add\n",
      "    s = reduce(add, map(sqrt, xs), 0)\n",
      "    return s"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 38
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%load_ext cythonmagic"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 39
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%%cython\n",
      "cimport numpy as np\n",
      "cimport cython\n",
      "\n",
      "# loadign a function from a C library\n",
      "cdef extern from \"math.h\":\n",
      "    double sqrt(double)\n",
      "\n",
      "# this is a slow version - next example shows stuff we can do to make it faster\n",
      "cdef double cadder1(xs):\n",
      "    cdef double s = 0\n",
      "    cdef int i\n",
      "    cdef int n = len(xs)\n",
      "    for i in range(n):\n",
      "        s += sqrt(xs[i])\n",
      "    return s\n",
      "\n",
      "def adder2(xs not None):\n",
      "    return cadder1(xs)\n",
      "\n",
      "# [1] typing the numpy array makes it much faster\n",
      "cdef double cadder2(np.ndarray[np.double_t, ndim=1] xs):\n",
      "    cdef double s = 0\n",
      "    cdef unsigned int i # [2] turn off check for negative indices\n",
      "    cdef int n = len(xs)\n",
      "    for i in range(n):\n",
      "        s += sqrt(xs[i])\n",
      "    return s\n",
      "\n",
      "# [3] turn off bounds checking with decorator\n",
      "@cython.boundscheck(False)\n",
      "def adder3(xs not None):\n",
      "    return cadder2(xs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 40
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def main():\n",
      "    import time\n",
      "    \n",
      "    n = 1e6\n",
      "    xs = np.random.rand(n)\n",
      "    \n",
      "    start = time.time()\n",
      "    z1 = adder1(xs)\n",
      "    print \"'adder1' %.03f sec\" % (time.time() - start)\n",
      "    \n",
      "    start = time.time()\n",
      "    z2 = adder2(xs)\n",
      "    print \"'adder2' %.03f sec\" % (time.time() - start)\n",
      "        \n",
      "    start = time.time()\n",
      "    z3 = adder3(xs)\n",
      "    print \"'adder3' %.03f sec\" % (time.time() - start)\n",
      "            \n",
      "    # numpy version for comparison\n",
      "    start = time.time()\n",
      "    z4 = np.sqrt(xs).sum()\n",
      "    print \"'adder4' %.03f sec\" % (time.time() - start)\n",
      "    \n",
      "    assert(z1 == z2 == z3 == z4)\n",
      "\n",
      "main()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "'adder1' 3.200 sec\n",
        "'adder2' 0.143 sec"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "'adder3' 0.007 sec\n",
        "'adder4' 0.010 sec\n"
       ]
      }
     ],
     "prompt_number": 41
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "References"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%load_ext version_information\n",
      "\n",
      "%version_information numpy, numexpr, numba"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<table><tr><th>Software</th><th>Version</th></tr><tr><td>Python</td><td>2.7.7 |Anaconda 2.0.0 (x86_64)| (default, Jun  2 2014, 12:48:16) [GCC 4.0.1 (Apple Inc. build 5493)]</td></tr><tr><td>IPython</td><td>2.1.0</td></tr><tr><td>OS</td><td>posix [darwin]</td></tr><tr><td>numpy</td><td>1.8.1</td></tr><tr><td>numexpr</td><td>2.3.1</td></tr><tr><td>numba</td><td>0.13.1</td></tr><tr><td colspan='2'>Mon Jun 09 10:32:33 2014 EDT</td></tr></table>"
       ],
       "json": [
        "{\"Software versions\": [{\"version\": \"2.7.7 |Anaconda 2.0.0 (x86_64)| (default, Jun  2 2014, 12:48:16) [GCC 4.0.1 (Apple Inc. build 5493)]\", \"module\": \"Python\"}, {\"version\": \"2.1.0\", \"module\": \"IPython\"}, {\"version\": \"posix [darwin]\", \"module\": \"OS\"}, {\"version\": \"1.8.1\", \"module\": \"numpy\"}, {\"version\": \"2.3.1\", \"module\": \"numexpr\"}, {\"version\": \"0.13.1\", \"module\": \"numba\"}]}"
       ],
       "latex": [
        "\\begin{tabular}{|l|l|}\\hline\n",
        "{\\bf Software} & {\\bf Version} \\\\ \\hline\\hline\n",
        "Python & 2.7.7 |Anaconda 2.0.0 (x86\\letterunderscore{}64)| (default, Jun  2 2014, 12:48:16) [GCC 4.0.1 (Apple Inc. build 5493)] \\\\ \\hline\n",
        "IPython & 2.1.0 \\\\ \\hline\n",
        "OS & posix [darwin] \\\\ \\hline\n",
        "numpy & 1.8.1 \\\\ \\hline\n",
        "numexpr & 2.3.1 \\\\ \\hline\n",
        "numba & 0.13.1 \\\\ \\hline\n",
        "\\hline \\multicolumn{2}{|l|}{Mon Jun 09 10:32:33 2014 EDT} \\\\ \\hline\n",
        "\\end{tabular}\n"
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 42,
       "text": [
        "Software versions\n",
        "Python 2.7.7 |Anaconda 2.0.0 (x86_64)| (default, Jun  2 2014, 12:48:16) [GCC 4.0.1 (Apple Inc. build 5493)]\n",
        "IPython 2.1.0\n",
        "OS posix [darwin]\n",
        "numpy 1.8.1\n",
        "numexpr 2.3.1\n",
        "numba 0.13.1\n",
        "<tr><td colspan='2'>Mon Jun 09 10:32:33 2014 EDT</td></tr>"
       ]
      }
     ],
     "prompt_number": 42
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 42
    }
   ],
   "metadata": {}
  }
 ]
}