Memoize Speed Test

memoize.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:1a7ba7b1452f518a5e9ac5a32b309371d9c44324a8cc7da0281596f81193dd10"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from pytools.decorator import decorator\n",
      "\n",
      "try:\n",
      "    decorator_module = __import__(\"decorator\", level=0)\n",
      "except TypeError:\n",
      "    # this must be Python 2.4\n",
      "    my_decorator = decorator\n",
      "else:\n",
      "    my_decorator = decorator_module.decorator\n",
      "    \n",
      "@my_decorator\n",
      "def memoize(func, *args):\n",
      "    # by Michele Simionato\n",
      "    # http://www.phyast.pitt.edu/~micheles/python/\n",
      "\n",
      "    try:\n",
      "        return func._memoize_dic[args]\n",
      "    except AttributeError:\n",
      "        # _memoize_dic doesn't exist yet.\n",
      "\n",
      "        result = func(*args)\n",
      "        func._memoize_dic = {args: result}\n",
      "        return result\n",
      "    except KeyError:\n",
      "        result = func(*args)\n",
      "        func._memoize_dic[args] = result\n",
      "        return result\n",
      "\n",
      "@my_decorator\n",
      "def _memoize(func, *args):\n",
      "    # by Michele Simionato\n",
      "    # http://www.phyast.pitt.edu/~micheles/python/\n",
      "    try:\n",
      "        return func._memoize_dic[args]\n",
      "    except AttributeError:\n",
      "        # _memoize_dic doesn't exist yet.\n",
      "        result = func(*args)\n",
      "        func._memoize_dic = {args: result}\n",
      "        return result\n",
      "    except KeyError:\n",
      "        result = func(*args)\n",
      "        func._memoize_dic[args] = result\n",
      "        return result\n",
      "\n",
      "def memoize2(*args, **kwargs):\n",
      "    use_kw = bool(kwargs.pop('use_kwargs', False))\n",
      "    key_func = kwargs.pop('key',\n",
      "                          (lambda *a, **kw: (a, frozenset(kw.iteritems())))\n",
      "                          if use_kw else None)\n",
      "    if kwargs:\n",
      "        raise TypeError(\n",
      "            \"memorize recived unexpected keyword arguments: %s\"\n",
      "            % \", \".join(kwargs.keys()))\n",
      "    if key_func is not None:\n",
      "        @my_decorator\n",
      "        def _deco(func, *args, **kwargs):\n",
      "            # by Michele Simionato\n",
      "            # http://www.phyast.pitt.edu/~micheles/python/\n",
      "            key = key_func(*args, **kwargs)\n",
      "            try:\n",
      "                return func._memoize_dic[key]\n",
      "            except AttributeError:\n",
      "                # _memoize_dic doesn't exist yet.\n",
      "                result = func(*args, **kwargs)\n",
      "                func._memoize_dic = {key: result}\n",
      "                return result\n",
      "            except KeyError:\n",
      "                result = func(*args, **kwargs)\n",
      "                func._memoize_dic[key] = result\n",
      "                return result\n",
      "    else:\n",
      "        @my_decorator\n",
      "        def _deco(func, *_args):\n",
      "            # by Michele Simionato\n",
      "            # http://www.phyast.pitt.edu/~micheles/python/\n",
      "            try:\n",
      "                return func._memoize_dic[_args]\n",
      "            except AttributeError:\n",
      "                # _memoize_dic doesn't exist yet.\n",
      "                result = func(*_args)\n",
      "                func._memoize_dic = {_args: result}\n",
      "                return result\n",
      "            except KeyError:\n",
      "                result = func(*_args)\n",
      "                func._memoize_dic[_args] = result\n",
      "                return result\n",
      "    if not args:\n",
      "        return _deco\n",
      "    if callable(args[0]) and len(args) == 1:\n",
      "        return _deco(args[0])\n",
      "    raise TypeError(\n",
      "        \"memorize recived unexpected position arguments: %s\" % args)\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# pypy\n",
      "def count():\n",
      "    i = 0\n",
      "    while True:\n",
      "        i = i + 1\n",
      "        yield i\n",
      "\n",
      "mem0 = lambda a, b=0: a + b\n",
      "mem1 = memoize(lambda a, b=0: a + b)\n",
      "mem2 = memoize2(lambda a, b=0: a + b)\n",
      "mem3 = memoize2(use_kwargs=True)(lambda a, b=0: a + b)\n",
      "mem4 = memoize2(key=lambda a, b=0: (a, b))(lambda a, b=0: a + b)\n",
      "\n",
      "counter = count()\n",
      "%timeit mem0(next(counter))\n",
      "counter = count()\n",
      "%timeit mem1(next(counter))\n",
      "counter = count()\n",
      "%timeit mem2(next(counter))\n",
      "counter = count()\n",
      "%timeit mem3(next(counter))\n",
      "counter = count()\n",
      "%timeit mem4(next(counter))\n",
      "\n",
      "%timeit mem0(1)\n",
      "%timeit mem1(1)\n",
      "%timeit mem2(1)\n",
      "%timeit mem3(1)\n",
      "%timeit mem4(1)\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10000000 loops, best of 3: 84.3 ns per loop\n",
        "1000000 loops, best of 3: 632 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1000000 loops, best of 3: 670 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1000000 loops, best of 3: 1.68 \u00b5s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1000000 loops, best of 3: 532 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10000000 loops, best of 3: 24.1 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10000000 loops, best of 3: 110 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10000000 loops, best of 3: 103 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1000000 loops, best of 3: 264 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10000000 loops, best of 3: 105 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# cpython\n",
      "def count():\n",
      "    i = 0\n",
      "    while True:\n",
      "        i = i + 1\n",
      "        yield i\n",
      "\n",
      "mem0 = lambda a, b=0: a + b\n",
      "mem1 = memoize(lambda a, b=0: a + b)\n",
      "mem2 = memoize2(lambda a, b=0: a + b)\n",
      "mem3 = memoize2(use_kwargs=True)(lambda a, b=0: a + b)\n",
      "mem4 = memoize2(key=lambda a, b=0: (a, b))(lambda a, b=0: a + b)\n",
      "\n",
      "counter = count()\n",
      "%timeit mem0(next(counter))\n",
      "counter = count()\n",
      "%timeit mem1(next(counter))\n",
      "counter = count()\n",
      "%timeit mem2(next(counter))\n",
      "counter = count()\n",
      "%timeit mem3(next(counter))\n",
      "counter = count()\n",
      "%timeit mem4(next(counter))\n",
      "\n",
      "%timeit mem0(1)\n",
      "%timeit mem1(1)\n",
      "%timeit mem2(1)\n",
      "%timeit mem3(1)\n",
      "%timeit mem4(1)\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1000000 loops, best of 3: 237 ns per loop\n",
        "100000 loops, best of 3: 1.8 \u00b5s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1000000 loops, best of 3: 1.78 \u00b5s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "100000 loops, best of 3: 2.35 \u00b5s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "100000 loops, best of 3: 1.95 \u00b5s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "10000000 loops, best of 3: 101 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1000000 loops, best of 3: 326 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1000000 loops, best of 3: 325 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1000000 loops, best of 3: 792 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "1000000 loops, best of 3: 509 ns per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 2
    }
   ],
   "metadata": {}
  }
 ]
}