01-skiplist.ipynb

{
 "metadata": {
  "name": "01-skiplist"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "See http://ivory.idyll.org/blog/2013-pycon-awesome-big-data-algorithms-talk.html"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# SkipList\n",
      "\n",
      "An implementation and exploration of skiplists.\n",
      "\n",
      "Code taken/refactored from John Shipman's excellent SkipList implementation:\n",
      "http://infohost.nmt.edu/tcc/help/lang/python/examples/pyskip/pyskip.pdf"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import random\n",
      "def random_level(max_level):\n",
      "    num = random.randint(1, 2**max_level - 1)\n",
      "    lognum = math.log(num, 2)\n",
      "    level = int(floor(lognum))\n",
      "    return max_level - level\n",
      "\n",
      "print random_level(8)\n",
      "print random_level(8)\n",
      "print random_level(8)\n",
      "print random_level(8)\n",
      "print random_level(8)\n",
      "print random_level(8)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n",
        "1\n",
        "1\n",
        "4\n",
        "3\n",
        "3\n"
       ]
      }
     ],
     "prompt_number": 36
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Node(object):\n",
      "    def __init__(self, value, level=0):\n",
      "        self.value = value\n",
      "        self.next = [None] * level\n",
      "    \n",
      "    def __str__(self):\n",
      "        return \"Node(%s,%s)\" % (self.value, len(self.next))\n",
      "    __repr__ = __str__\n",
      "    \n",
      "class SkipList(object):\n",
      "    def __init__(self, max_level=8):\n",
      "        self.max_level = max_level\n",
      "        n = Node(None, max_level)\n",
      "        self.head = n\n",
      "        self.verbose = False\n",
      "    \n",
      "    def update_list(self, value):\n",
      "        update = [None] * (self.max_level)\n",
      "        n = self.head\n",
      "        \n",
      "        self._n_traverse = 0\n",
      "        \n",
      "        level = self.max_level - 1\n",
      "        while level >= 0:\n",
      "            if self.verbose and \\\n",
      "                n.next[level] != None and n.next[level].value >= value:\n",
      "                print 'DROP down from level', level + 1\n",
      "            while n.next[level] != None and n.next[level].value < value:\n",
      "                self._n_traverse += 1\n",
      "                if self.verbose:\n",
      "                    print 'AT level', level, 'value', n.next[level].value\n",
      "                n = n.next[level]\n",
      "            update[level] = n\n",
      "            level -= 1\n",
      "\n",
      "        return update\n",
      "    \n",
      "    def find(self, value, update=None):\n",
      "        if update is None:\n",
      "            update = self.update_list(value)\n",
      "                        \n",
      "        if len(update) > 0:\n",
      "            candidate = update[0].next[0]\n",
      "            if candidate != None and candidate.value == value:\n",
      "                return candidate\n",
      "        return None\n",
      "    \n",
      "    def insert_node(self, value, level=None):\n",
      "        if level is None:\n",
      "            level = random_level(self.max_level)\n",
      "            \n",
      "        node = Node(value, level)\n",
      "        \n",
      "        update = self.update_list(value)\n",
      "        if self.find(value, update) == None:\n",
      "            for i in range(level):\n",
      "                node.next[i] = update[i].next[i]\n",
      "                update[i].next[i] = node\n",
      "    \n",
      "def print_level(sl, level):\n",
      "    print 'level %d:' % level,\n",
      "    node = sl.head.next[level]\n",
      "    while node:\n",
      "        print node.value, '=>',\n",
      "        node = node.next[level]\n",
      "    print 'END'\n",
      "        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 37
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# create and load a skiplist with max level of 4\n",
      "x = SkipList(4)\n",
      "for i in range(0, 20, 2):\n",
      "    x.insert_node(i)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 46
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# print out the data structure\n",
      "print_level(x, 0)\n",
      "print_level(x, 1)\n",
      "print_level(x, 2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "level 0: 0 => 2 => 4 => 6 => 8 => 10 => 12 => 14 => 16 => 18 => END\n",
        "level 1: 2 => 6 => 10 => 12 => 18 => END\n",
        "level 2: 10 => 12 => END\n"
       ]
      }
     ],
     "prompt_number": 47
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# verbalize the insertion process for '11'\n",
      "x.verbose = True\n",
      "print 'INSERT', 11\n",
      "x.insert_node(11)\n",
      "print 'DONE;', x._n_traverse, 'traversals'"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "INSERT 11\n",
        "AT level 2 value 10\n",
        "DROP down from level 2\n",
        "DROP down from level 1\n",
        "DONE; 1 traversals\n"
       ]
      }
     ],
     "prompt_number": 48
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# print out the updated data structure\n",
      "print_level(x, 0)\n",
      "print_level(x, 1)\n",
      "print_level(x, 2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "level 0: 0 => 2 => 4 => 6 => 8 => 10 => 11 => 12 => 14 => 16 => 18 => END\n",
        "level 1: 2 => 6 => 10 => 12 => 18 => END\n",
        "level 2: 10 => 12 => END\n"
       ]
      }
     ],
     "prompt_number": 49
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# do a random simulation to evaluate how many traversals need to be done to reach\n",
      "# the last element in the list\n",
      "def skiplist_traverse_mc(max_level, max_count, n=100):\n",
      "    z = []\n",
      "    for _ in range(n):\n",
      "        x = SkipList(max_level)\n",
      "        for i in reversed(range(max_count)):\n",
      "            x.insert_node(i)\n",
      "        \n",
      "        x.find(254)\n",
      "        z.append(x._n_traverse)\n",
      "\n",
      "    return z\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 53
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "avgs = []\n",
      "for i in range(1, 10):\n",
      "    z = skiplist_traverse_mc(i, 200)\n",
      "    avgs.append((i, average(z)))\n",
      "\n",
      "avgs = numpy.array(avgs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 51
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# graph average to traverse to last of 200 elements\n",
      "plot(avgs[:,0], avgs[:,1])\n",
      "axis(ymin=0, xmin=0)\n",
      "xlabel('skiplist max level')\n",
      "ylabel('time to traverse to last of 200 elements')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 52,
       "text": [
        "<matplotlib.text.Text at 0x10b832150>"
       ]
      },
      {
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEMCAYAAADJQLEhAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xlc1PW+x/HXoIGmuOSCtiByVHB3MMAVkczUm0umD9Ms\nTW8lmktZN+taaZ1j2Y7e41Jpthy1POXJNvVQEq6gSdohlwxcc0FNBRUU+N0/5jBHFBiQYX4zzPv5\neMxD5zc/hjen43z47hbDMAxERMRr+ZgdQEREzKVCICLi5VQIRES8nAqBiIiXUyEQEfFyKgQiIl7O\n6YXg0KFD9OzZk9atWxMdHc3SpUsByMzMZODAgQQGBjJo0CCysrLsXzNnzhyaN29Oq1at2LBhg7Mj\niYhICSzOXkdw7Ngxjh07RocOHTh58iQRERHs2LGD+fPnc+jQIV5//XWmTp1KUFAQTz75JCdOnCAq\nKoq1a9eSnp7O448/zvbt250ZSURESuD0FkGjRo3o0KEDAPXr16d169Zs3bqV5ORkxo4di5+fH2PG\njCEpKQmApKQk+vTpQ2BgID169MAwDDIzM50dS0REilGhYwT79u0jNTWViIgItm7dSmhoKAChoaEk\nJycDtkLQsmVL+9eEhITYXxMRkYpXtaLeODMzk2HDhvHWW29Rs2ZNytIDZbFYSnVNREQcc/T5WyEt\ngsuXL3PvvffywAMPMHDgQADCw8PZtWsXALt27SI8PByAyMhIfvnlF/vX7t692/7a1QzDcJvHhQsG\nN9zwAufOmZ/lyscLL7xgegZPyOSuuZRJmZz9KA2nFwLDMBg7dixt2rRhypQp9uuRkZEsXryYixcv\nsnjxYjp16gRAREQEa9as4eDBgyQkJODj44O/v7+zYzld9epwyy2gSU4i4umcXgg2btzIxx9/zPff\nf4/VasVqtbJ69WpiY2M5ePAgISEhHDlyhHHjxgEQEBBAbGwsMTExjB8/nri4OGdHqjBBQfD992an\nEBEpH6ePEXTr1o38/PwiX/viiy+KvD558mQmT57s7CgVbvDgaD74wOwUhUVHR5sd4RrumAncM5cy\nlY4yOZfT1xFUFIvFUur+Lle5dAnq14cDB6BuXbPTiIhcqzSfndpiohx8faFzZ/jhB7OTiIhcPxWC\ncoqJgXXrzE4hInL9VAjKKSZGA8Yi4tk0RlBOubnQoAHs3g0BAWanEREpTGMELlC1KnTvDgkJZicR\nEbk+KgROoHECEfFkKgROoHECEfFkDgvBvn37yM7OBuCnn35i6dKl5ObmVngwT9KmDfzxBxw+bHYS\nEZGyc1gI7r33XqpWrcqJEycYOnQoiYmJjBkzxhXZPIaPD0RHq3tIRDyTw0JgsVioWrUq77//Po8+\n+igLFiyw7yIq/6HuIRHxVA4LQePGjVm0aBEff/wxI0eOBODixYsVHszTFBQCN5zhKiJSIoeF4J13\n3uHQoUO88sorNGrUiPT0dB544AFXZPMoLVrA5cuQlmZ2EhGRsnG4++jnn3/OjBkz7M+bNm2Kn59f\nRWbySBbLf6aR/ulPZqcRESk9hy2CJUuWXHPtA3fbe9lNaJxARDxRsS2CZcuWsXTpUtLT0+nfv7/9\nekZGBq1bt3ZJOE/Tsyc8+6xtnEBHLIuIpyi2EHTp0oXGjRuTkZHBk08+ad+rokmTJjRt2tRlAT1J\n06a2Iyx374aWLc1OIyJSOtp0zsnGjoWwMJgwwewkIiJO2nQuPj6emJgY6tSpg7+/P/7+/tSqVctp\nISsbjROIiKdx2CK4/fbbiYuLo3Pnzvj4mLc1kae0CH7/Hdq2hYwM24pjEREzOaVF4OvrS8eOHU0t\nAp7k5ptt5xPs3Gl2EhGR0nG4jqB79+4MGjSIoUOHUqdOHcBWYQYPHlzh4TxVQfdQhw5mJxERccxh\n19Do0aNtN141H/L999+vsFBF8ZSuIYAVK+CDD+Crr8xOIiLerjSfnZo1VAEyMqB5czh50naCmYiI\nWZwyRpCenk5sbCxWqxWAnTt38uc//9k5CSupBg2gSRP48Uezk4iIOOawEMyYMaPQyuK2bduybNmy\nCg1VGWgaqYh4CoeFYO/evfTr18/+PD8/H19f3woNVRn07KlCICKewWEh6NatGz/+u48jJyeHuXPn\nctddd1V4ME8XFQVbtkBOjtlJRERK5rAQTJkyhXnz5nHs2DGCg4NJTU1l0qRJrsjm0erUse03lJRk\ndhIRkZKVetZQbm6uqd1CnjRrqMDTT9s2obviOAcREZdyyvTRzMxM1q5dy+bNm8n5dz+HxWJhzpw5\nzktaCp5YCNasgVmz4IcfzE4iIt6qNJ+dDme5P/LII1SvXp3OnTvj6+uLYRjXLC6TonXrZptCeuEC\n3Hij2WlERIrmsBCkpqayUxvnXJcaNcBqhY0b4c47zU4jIlI0h4PFsbGx/OUvfyEtLY3Tp0/bH1I6\nPXvazjEWEXFXDlsEN954I1OnTmXevHn2gWKLxUJaWlqFh6sMYmJg2jSzU4iIFM/hYHFwcDDr1q2j\nSZMmrspUJE8cLAbIzrZtOXH4MNSubXYaEfE2TtlrqFmzZlSvXt1pobxNtWoQEQHr15udRESkaA67\nhurWrUv79u3p1atXofMIXD191JPFxNjGCe6+2+wkIiLXclgI+vbtS9++fYH/NDE0fbRsYmJg/Hiz\nU4iIFK3UK4vT0tIIDg6u6DzF8tQxAoDLl6FePUhPt/0pIuIqThkjSEhIIDIykpiYGABSUlIYMGCA\ncxJ6iRtusC0u0wpjEXFHDgvBa6+9xqpVq6hbty4AVqtVU0evg84nEBF35bAQZGVlERAQYH+emZlJ\nrVq1KjRUZaRCICLuymEhGDhwIHPmzCE3N5fExETGjRvHsGHDXJGtUmnfHo4dg6NHzU4iIlJYqbaY\nqFWrFkFBQcyePZt+/foxbtw4V2SrVKpUgR49ICHB7CQiIoWVetaQ2Tx51lCBuXNh5054912zk4iI\ntyjXeQRXHlhf1BuvWrWqfOnKqDIUgn/9CwYOhN9+MzuJiHiLcp1HMHXq1BLfuDhjxozh66+/pmHD\nhvz8888AzJgxg/fee48GDRoAMGvWLPsitTlz5jB37lxuuOEG3nnnHbp161ZiYE/WujVkZcGBA2Dy\n1k0iInZOX1C2fv16atasyYMPPmgvBDNnzsTf358nnnii0L0nTpwgKiqKtWvXkp6ezuOPP8727duL\nDloJWgQA990HffrA6NFmJxERb2DKgrLu3bvb1xxcqaggSUlJ9OnTh8DAQHr06IFhGGRmZjqK5NE0\njVRE3I3DvYYKFpT16dMHuP4FZXPnzmXFihXcc889jB8/Hn9/f5KTk2nZsqX9npCQEJKTk7njjjuK\nfI8ZV5wCHx0dTXR0dJlzmK1nT3jxRTAM0JZNIuJsCQkJJJRxeqLDQuCMBWWxsbE8//zznDt3jqee\neoqFCxfy5JNPFtlKKGn84cpC4KmaNbMVgH37oHlzs9OISGVz9S/JM2fOdPg1LllQ1rBhQywWC7Vr\n12bChAmsXLkSgMjISH755Rf7fbt37yY8PLxM7+1pLBZ1D4mIe3FYCMaPH1/uBWVH/72cNjc3l6VL\nl9KvXz8AIiIiWLNmDQcPHiQhIQEfHx/8/f2v48fwLD17qhCIiPtw+oKy4cOH88MPP3Dy5EkCAgKY\nOXMmCQkJ/PTTT/j6+hIVFcX06dO56aabAIiLi2Pu3Ln4+vqycOFCunfvXnTQSjJrCGzTR8PD4fhx\njROISMUq14Iyd1OZCgHYxgr+8Q9o08bsJCJSmTll+qhUDI0TiIi7UCEwicYJRMRdlNg1tG3bNpKS\nktiyZQsAnTp1IjIykttvv91lAQtUtq6hY8egVSvIyLDtTCoiUhHK1TX0v//7v0yZMoWcnBzuv/9+\nRowYQXZ2NlOmTOGZZ55xelhv06gRNG4MP/1kdhIR8XbFtgiCg4PZunUr9a46bf3kyZOEh4eTnp7u\nkoAFKluLAOCxx2ybzz31lNlJRKSyKleLoE6dOsTHx19zPT4+vsi9hKTsYmJg3TqzU4iItyu2RbBr\n1y6mTp3Knj17aNiwIQDHjx8nNDSU119/nVatWrk2aCVsEZw6BU2b2v684Qaz04hIZeS0dQT79u0D\noFmzZs5Jdh0qYyEACAuD//s/6NLF7CQiUhk5ZR1BVlYWBw4c4ODBg5V+i2gzaBqpiJit2BbBhg0b\nmDRpEoZhEBISAtg2hfPx8SEuLq7YrSAqLGglbRF8/TW8+SZ8953ZSUSkMipX11CrVq2YP38+PXr0\nKHQ9ISGB8ePHF9o11BUqayE4dw5uucW2nqBaNbPTiEhlU66uocuXL9O0adNrrgcHB3Pp0qXypxMA\natWynWW8ebPZSUTEWxV7MM3EiRPp3bs3ffr0sZ8i9ssvv7BmzRomTpzosoDeoGAaac+eZicREW9U\n4qyhEydOkJSURHJyMoZhEBkZSURERKETy1ylsnYNAcTHw4wZsGGD2UlEpLLRNtQe4sIFaNjQtv9Q\nzZpmpxGRyqRcYwQXL15k0aJFPPjgg6xYsaLQa+PHj3dOQgHgxhuhY0fYuNHsJCLijYotBM888wxb\ntmxhwIABvPfeewwZMoTs7GwANmtk0+l0PoGImKXYQpCYmMjChQsZMmQIa9asoV27dtxxxx2cOnXK\nlfm8hgqBiJil2FlDFy9eLPT8+eefJzAwkKioKLKysio8mLeJiIDdu+HMGahTx+w0IuJNim0R3H33\n3Xx31XLX0aNH88Ybb+Dr61vhwbyNnx907gyJiWYnERFvo1lDbuSVV2wzh95+2+wkIlJZ6PB6D6Nx\nAhExg1oEbiQ3F+rXh19/hQYNzE4jIpVBuVoEBWsH0tLSnJtKilW1KnTvDgkJZicREW9SbCF45ZVX\nALj33ntdFkbUPSQirlfs9NHQ0FCio6NJT0+nf//+hV6zWCysWrWqwsN5o549YcECs1OIiDcpcYxg\n586dDB48mEWLFhXqY7JYLNecU1DRvGGMACA/37bv0I4dtnMKRETKwymbzmVkZNCgQQNyc3MBqFq1\n2EZEhfKWQgAwZAgMGgQjR5qdREQ8nVOmj547d45hw4YRHBxMcHAw9913nwaQK5jOMRYRV3JYCGbN\nmsWAAQNIS0sjLS2NgQMH8pe//MUV2bxWwUE1IiKu4LBrqEOHDmzfvh0fH1vNyMvLo2PHjvz0008u\nCVjAm7qGDANuvhk2bYIiTgsVESk1p3QN9e/fnylTprB9+3Z+/PFHpk6des0sInEui0XTSEXEdRy2\nCM6dO8eSJUv4+uuvAdtmdKNGjaJWrVouCVjAm1oEAO+9Z+se+tvfzE4iIp5MR1V6sLQ06NYNjhyx\ntRBERK6HNp3zYE2bgq8v7NljdhIRqexUCNyUxaJppCLiGg4LwYYNG665tlGnrLuEppGKiCs4HCOw\nWq2kpKQ4vFbRvG2MAODwYejQAU6cAB+13UTkOpTms7PY/SI2b97Mpk2byMjI4M0337S/UUZGBvXq\n1XNuUinSrbdCvXrw88/Qvr3ZaUSksir298xLly6RmZlJXl4emZmZZGVlkZWVRWhoKB9++KErM3o1\njROISEVz2DV04MABmjRpYn+enZ1NtWrVKjzY1byxawjg00/h449Bu36LyPVwyvTRZ555hnPnzpGX\nl0dkZCQtWrRg8eLFTgspJYuOhsRE2zGWIiIVwWEhSE1NpVatWqxcuZKOHTuyd+9eFi1a5Ipsgu1s\ngttug+3bzU4iIpWVw0Jw4403cuHCBT766CNGjhxJtWrVyMzMdEU2+TdNIxWRiuSwEEycOJGwsDD8\n/f3p0qUL+/fvp3bt2q7IJv+mDehEpCKVea8hwzDIy8tz+Ull3jpYDHDmDAQGwsmTtm0nRERKy2l7\nDe3Zs4c5c+Ywc+ZMXnrpJWbNmlXsvWPGjCEgIIC2bdvar2VmZjJw4EACAwMZNGgQWVlZ9tfmzJlD\n8+bNadWqVZGrmAXq1IEWLSA52ewkIlIZleqEsqeeeopXX32VM2fOsGTJEk6cOFHs/Q899BCrV68u\ndG3+/PkEBgby66+/cuutt7JgwQIATpw4wbx58/juu++YP38+kyZNKuePU3mpe0hEKorDQrBy5UpW\nrlxJ7dq1eeutt1i/fn2Jp5N1796dunXrFrqWnJzM2LFj8fPzY8yYMSQlJQGQlJREnz59CAwMpEeP\nHhiGoYHoYqgQiEhFcVgILBYLVapUITQ0lH/961/Url2b06dPl+mbbN26ldDQUABCQ0NJ/ncfR1JS\nEi1btrTfFxISYn9NCuvWDbZtg4sXzU4iIpWNwxHfu+++mz/++INx48YxZMgQMjMzmTZtWpm+SVkG\neS0lnMIyY8YM+9+jo6OJjo4uUw5PVrOmbb+hTZvgjjvMTiMi7iohIYGEhIQyfY3DQvD8888DcOed\nd7Jr1y5ycnLKvMVEeHg4u3btwmq1smvXLsLDwwGIjIwkPj7eft/u3bvtrxXlykLgjQq6h1QIRKQ4\nV/+SPHPmTIdfU2wh+Oyzz+y/nRuGcc1v6oMHDy51sMjISBYvXsyrr77K4sWL6dSpEwARERE89dRT\nHDx4kLS0NHx8fPD39y/1+3qbmBh49lmzU4hIZVNsIfjyyy9L7KYprhAMHz6cH374gVOnTnHbbbfx\n4osvEhsby8iRIwkJCSEsLIzZs2cDEBAQQGxsLDExMfj6+rJw4cJy/jiVW+fO8K9/QWYmqF6KiLPo\n8HoPExMDTz4J/fqZnUREPIEOr6+ENI1URJxNhcDD6KAaEXE2dQ15mEuXoH592L8fbrrJ7DQi4u7K\ndWZxgdzcXP75z3+y6t9HZA0cOJBevXq5fNM5sfH1ha5d4Ycf4J57zE4jIpWBw66huLg4Fi5cSExM\nDD179uSdd94hLi7OFdmkGBonEBFnctg1FB4eTmJiItWrVwfg4sWLREVFsXXrVpcELKCuof/Ytg1G\nj7ZNJRURKYlTZg0FBQWxc+dO+/Off/6ZoKCgcoeT62e1wpEjcPy42UlEpDJw2NE/bdo0HnnkES5f\nvgyAn5+ffRtpMUeVKtCjh+34yvvuMzuNiHg6h11D2dnZVKtWjd9//x3DMLjlllvs11xJXUOFxcVB\naiq8847ZSUTEnTmla6hLly4A3Hzzzdxyyy2Frol5dKC9iDhLsV1DR48e5ffff+fChQts377dvvHc\niRMn8PPzc2VGKULr1nD2LBw8aDvPWETkehVbCNauXcuSJUs4cuQIU6dOtV9v0qQJL730kkvCSfF8\nfGyrjNetg1GjzE4jIp7M4RjB3//+d4YMGeKqPMXSGMG1FiyALVtgyRKzk4iIuyrNZ6e2mPBge/dC\nr15w4ACUsGO4iHgx7T5ayTVvDvn58NtvZicREU+mQuDBLBbtRioi5eewEOTk5PDJJ58wYcIEAH79\n9Ve++uqrCg8mpaNppCJSXg7HCKZNm4ZhGHz11VekpqZy/vx5unTpwo4dO1yVEdAYQXEOHICICDh2\nTOMEInItp4wRrFu3jtmzZ+Pr6wtAjRo19IHsRpo0gRo14JdfzE4iIp7KYSEICQnh7Nmz9udbtmzB\narVWaCgpG3UPiUh5ONx0buLEidxzzz0cPnyYnj17cvz4cT766CNXZJNSiomBv/8dHnvM7CQi4olK\nvY7gxx9/JD8/n/Dw8IrOVCSNERTv6FHblhMZGbadSUVECjhljGDDhg1kZWXRsWNHjh8/zqxZszh9\n+rTTQkr5NW4MAQHg4vF7EakkHBaC2NhYatSoQXp6Os888ww+Pj48/PDDrsgmZaBxAhG5Xg4LQdWq\nVbFYLLz//vuMHz+eadOmsX//fhdEk7LQOcYicr0cDhYHBQXx3HPPsWLFCpKSksjLy+PSpUuuyCZl\n0KMHjBkDly/DDTeYnUZEPInDFsHf/vY3goODWbZsGbVr1+bIkSM89dRTrsgmZVC/PjRtCj/+aHYS\nEfE0Jc4ays3N5a677uK7775zZaYiadaQY088YSsIzz5rdhIRcRflnjVUMD6gMQHPcNdd8NFHcO6c\n2UlExJM4HCOoW7cuYWFhxMTE0LhxY8BWYebMmVPh4aRseveG6GgYOhS++kpjBSJSOg4XlC254vir\ngiaGxWJhlIvPR1TXUOnk5sKgQdCoEbz7rjaiE/F2Tj2hLC0tjeDgYKcEux4qBKWXlWWbRXTPPTB9\nutlpRMRMTllZnJCQQGRkJDExMQCkpKQwYMAA5ySUClGzpq1r6L334OOPzU4jIu7OYSF47bXXWLVq\nFXXr1gXAarWSlpZW4cGkfBo3hq+/hqlTteJYRErmsBBkZWUREBBgf56ZmUmtWrUqNJQ4R+vWsHw5\n3HcfpKaanUZE3JXDQjBw4EDmzJlDbm4uiYmJjBs3jmHDhrkimzhBz57w+uvwX/9l26VURORqDgeL\ns7OzWb58OZ999hn5+fmMGDGCIUOG4Ofn56qMgAaLy+vPf4aVK+GHH2xjCCLiHZwya2j79u2EhYU5\nNdj1UCEoH8OAhx+2nW38j39AVYcrSESkMnBKIYiOjubYsWMMHTqUYcOG0aZNG6eGLC0VgvK7fBnu\nvhuCg2HePK0xEPEGTps+um7dOurXr8+jjz5K27Zteemll5wWUlznhhtgxQrYtAlee83sNCLiLkq9\noAzg559/Zvbs2XzyySdcvny5InNdQy0C5zl8GLp0sRUDjfuLVG5OaRH88ssvzJgxgzZt2vDYY4/R\npUsXjhw54rSQ4nq33mpbcDZxIqxfb3YaETGbwxZB586dGTZsGEOHDuWWW25xVa5rqEXgfGvXwgMP\nQGIihISYnUZEKoJT9xoymwpBxVi8GP7yF9i8GRo2NDuNiDibUwrB/v37WbhwIWvWrOGPP/6wv7Gr\nt5lQIag4zz8Pa9bYtqK48Uaz04iIMzlljOCFF17AarWSm5vLypUr6devH4888ojTQor5Zs60dQ2N\nGAF5eWanERFXc9gisFqtpKSk0L59e7Zt2wbA7bffzo4dO1wSsIBaBBXr0iXo0wfatoW4OLPTiIiz\nOKVFUL16dfLy8ujRowezZs1i2bJl1LzOPQqCgoJo164dVquViIgIwLaJ3cCBAwkMDGTQoEFkZWVd\n13tL+fj6wuefQ3w8vP222WlExJUcFoK4uDguXLjA9OnTMQyD9evXM3/+/Ov6ZhaLhYSEBFJSUkhO\nTgZg/vz5BAYG8uuvv3LrrbeyYMGC63pvKb86deCbb2yb1H3+udlpRMRVSiwEeXl5fPrpp/j7+9Ow\nYUNmzJjBu+++S7t27a77G17dRElOTmbs2LH4+fkxZswYkpKSrvu9pfyaNIFVq+DRR20ziUSk8iux\nEFSpUoXExEQyMzOd8s0sFgsxMTEMGjSIVatWAbB161ZCQ0MBCA0NtbcUxDxhYfDBBzB4MOzbZ3Ya\nEaloDveg7Nq1K/3792fIkCE0btwYsH2gDx48uMzfbOPGjTRu3Jhdu3bRv39/IiIiyjQAPGPGDPvf\no6OjiY6OLnMGKZ1+/eCFF2x/btoE9eubnUhESiMhIYGEhIQyfY3DWUOjR4+23XjVVpXvv/9+mb7R\n1Z544glatmzJ6tWrmT59OlarlR9//JGXX36Zv//979cG1awhU0ybZtuGIj4eqlc3O42IlJVTFpRt\n2LCBbt26ObzmyIULF8jLy8Pf35+MjAyio6NZvXo1y5Yt49ChQ7z66qs8+eSTNG3alCeffPK6fhhx\nvvx8uP9+2/qC5cvBx+H0AhFxJ04pBGFhYWzfvt3hNUfS09O55557AKhXrx73338/Y8aMITMzk5Ej\nR5KSkkJYWBgff/xxkdNTVQjMk50Nd94JnTpp+2oRT1Oaz85ixwg2b97Mpk2bOHHiBG+++ab9jTIy\nMrjpppvKHKZp06b89NNP11z39/fniy++KPP7ietUq2Y71axLFwgKggkTzE4kIs5UbCG4dOkSmZmZ\n5OXlFZo1FBoayqRJk1wSTtxHvXrw7bfQrRsEBkL//mYnEhFnKdWmc0FBQS6KUzx1DbmH5GT4r/+y\nFYXbbzc7jYg4om2opUJ88QXExtqmlbrB7wgiUoJyjRGIFGfgQDhwAPr2tRWDunXNTiQi5aEWgVy3\nJ56A7dttZxn4+ZmdRkSK4pTdR48fP87TTz9Nq1ataNWqFdOmTePEiRNOCyme6/XXbYPIY8bY1huI\niGdyWAheeeUV6tSpY1+2XKdOHV5++WVXZBM35+MDH38MaWnw3HNmpxGR6+Wwa6h9+/aFDqHJz8/H\narXqYBqxy8iAzp3h6afh4YfNTiMiV3JK11B0dDSvvfYap06d4uTJk7z11lva7E0KadDAdo7Bc8/Z\nppWKiGdxWAiefvppjh49Srdu3ejevTu///4706ZNc0U28SAtWtgOs3nwQShiAbmIuDGHXUMbN26k\na9euDq9VNHUNeYYVK+Dxx23TSgMDzU4jIk5ZUFZweL2jaxVNhcBzvP667WCbDRugdm2z04h4N6ds\nOpeRkXHNpnP16tVzblKpVKZOhf374d57bWMHvr5mJxKRkhQ7RnD1pnNZWVlkZWURGhrKhx9+6MqM\n4mEsFoiLgxtvhEceATXkRNybNp2TCnP+PERH284ymDkTbrjB7EQi3scp00fdoQiIZ6pRA778ErZs\nsW1O9+KLcPSo2alE5Go6eFAqVKNG8P33tv2Ijh6FVq1g+HDbQLIaeCLuQZvOiUudOWObUfTXv9rG\nEB57DEaMsP1dRJzPKV1D6enpxMbGYrVaAdi5cyd//vOfnZNQvE6dOjB5MuzeDa++CqtW2dYbTJ0K\nv/1mdjoR7+SwEMyYMYP+V5xL2LZtW5YtW1ahoaTy8/GB3r1thWDrVqhaFTp1sp1+9s032s1UxJUc\nFoK9e/fSr18/+/P8/Hx8NTFcnKhpU5g9Gw4ehKFDbXsWtWgBb74Jf/xhdjqRys9hIejWrRs//vgj\nADk5OcydO5e77rqrwoOJ96leHUaPhm3bbNtbb98OwcG2HU21f5FIxXFYCKZMmcK8efM4duwYwcHB\npKamMmnSJFdkEy9lsdi6iT7+2DaWEBQE/ftDt26wfDlcumR2QpHKpdSzhnJzc03tFtKsIe+Wmwtf\nfGGbbbTuiC/2AAAPUklEQVR7t23F8iOPwM03m51MxL05ZdO5zMxM1q5dy+bNm8nJybG/8Zw5c5yX\ntBRUCKRAairMmwfLltlWLU+YAN2721oSIlKYUwrB8OHDqV69Op07d8bX1xfDMLBYLIwaNcqpYR1R\nIZCrnT0LH35oayX4+trWJNx/v21Fs4jYOKUQtGvXjp07dzo12PVQIZDiGAZ89x383//ZViw/8ACM\nHw/Nm5udTMR8TikE8+fP5/Tp0wwfPpw6derYr990003OSVlKKgRSGgcOwIIFsGgRdOxo6zbq2xeq\nVDE7mYg5nFIIPvjgA2JjY6lbt659oNhisZCWlua8pKWgQiBlkZ0Nn3xiayWcOmVrIYwZAy7+/UXE\ndE4pBMHBwaxbt44mTZo4NVxZqRDI9UpOthWEL7+EwYNtrYSwMLNTibhGuU4oK9CsWTOqV6/utFAi\nrhYRYRtUPnHC1mU0aJBt2mm3bhAaanu0bAk6eE+8lcMWwbBhw0hMTKRXr172MQJNHxVPlpsL8fGw\nY4dtTcLu3bBrl+3gnILCcGWBaNJEYwziuZzSNbRkyZIi31jTR6UyMQw4fvw/heHKApGRAc2aXVsg\nWrTQVFVxf04pBO5ChUDMcv487N17bYH49Vdo2PDaAhEaCgEBWuAm7qFchWDo0KGsWLGCtm3bFvnG\nrl5boEIg7iYvzzZd9eoCsXs3XL5cdIEIDtbZzeJa5SoEv//+OzfffDMHDhy45k0sFovLZxGpEIgn\nOXkS9uy5tkAcPmzbdvvqIhESArVrm51aKiOndA09/fTTzJ492+G1iqZCIJVBdjbs23dtgdizB2rV\nsp3W1qhR4Ufjxv/5e0AAVKtm9k8hnsQphcBqtZKSklLoWlhYGNu3by9/wjJQIZDKLD8fjhyxtRiO\nHbv2cfSo7c/jx23nO19dLIp61K+v2U5SznUE8+fPZ968efz222+FxgnOnTvHsGHDnJdSRPDxgdtu\nsz1KYhi2U9uKKhapqYWf//GHrRgU17q48uHvr8Ftb1Zsi+Ds2bP88ccfTJs2jdmzZ9srSkBAgCkL\nzNQiECmby5dtU1+LKhpXP3Jzi29Z3HSTbZpsjRpQs+Z//l7w0Mm17k3TR0WkVM6fL75L6o8/bK9f\n+cjK+s/fLZZri0NRBaO46yVdq+pw74OKYRi2WWFleeTn21p2Vapc+2dprlVUi0yFQEQq3KVL1xaH\nogrG9VyrWrXoguHnV/YP6pI+wK++ZhiFP7BL8/Dxsb1Xwftd+b4lXSv4fhZL2YtHaa5t2aJCICIe\nyjAgJ6fogpGTU7YP6bJ8mFf0b+jF/axXFhFHxaMsRaZrVxUCERGvVprPTh8XZRERETelQiAi4uVU\nCEREvJxbFILExERatmxJ8+bNmTt3rtlxSi0hIcHsCNdQptJzx1zKVDrK5FxuUQgmT57MwoULiY+P\n569//SsnT540O1KpuON/eGUqPXfMpUylo0zOZXohOHv2LABRUVE0adKE3r17k5SUZHIqERHvYXoh\n2Lp1K6GhofbnrVq1YsuWLSYmEhHxLqavI4iPj2fRokUsW7YMgAULFnDkyBFeeumlQvdZtCOWiMh1\nue7dR10lPDycp556yv48NTWVPn36XHOfFpOJiFQM07uGav/7WKbExET279/PP//5TyIjI01OJSLi\nPUxvEQC8/fbbPProo1y+fJlJkyZRv359syOJiHgN01sEAD169GDXrl3s27ePSZMmFXrN3dYYjBkz\nhoCAgEKH9Zjt0KFD9OzZk9atWxMdHc3SpUvNjgRAdnY2kZGRdOjQgU6dOvHWW2+ZHQmAvLw8rFYr\n/fv3NzuKXVBQEO3atcNqtRIREWF2HADOnz/PqFGjaNGihVtM4tizZw9Wq9X+qF27NnPmzDE1E8C7\n775Lly5d6NixI1OmTDE7jt3SpUvp0aMHrVu35r333iv5ZsPNdejQwfjhhx+M/fv3GyEhIUZGRoap\neRITE43t27cbbdq0MTXHlY4ePWqkpKQYhmEYGRkZRtOmTY1z586ZnMrm/PnzhmEYRnZ2ttG6dWvj\n119/NTmRYbzxxhvGiBEjjP79+5sdxS4oKMg4deqU2TEKmTp1qjF9+nTj4sWLxuXLl40zZ86YHcku\nLy/PaNSokXHw4EFTc5w6dcoICgoysrKyjLy8PKNv377G6tWrTc1kGIZx5swZo0WLFsbp06eNzMxM\nIzw8vMT/fm7RIiiOO64x6N69O3Xr1jU1w9UaNWpEhw4dAKhfvz6tW7dm27ZtJqeyufHGGwHIysoi\nNzcXPz8/U/McPnyYb775hv/+7/92uwkI7pYnPj6eZ599lmrVqlG1alX7eJ47iI+P509/+hO3OTrb\ns4JVr14dwzA4e/YsFy9e5MKFC27x+bBp0ybCwsKoW7cuNWvWpGfPnmzevLnY+926EGiNQdnt27eP\n1NRUt+leyM/Pp3379gQEBPDYY4+Z/g/38ccf57XXXsPHx73+r2+xWIiJiWHQoEGsWrXK7DgcPnyY\n7OxsYmNjiYyMZPbs2WRnZ5sdy2758uWMGDHC7BhUr16d+fPnExQURKNGjejatatb/NuLiooiOTmZ\n9PR0jh49yjfffMOmTZuKvd+9/jVIuWRmZjJs2DDeeustatSoYXYcAHx8fNixYwf79u1j3rx5pKSk\nmJblq6++omHDhlitVrf77Xvjxo3s2LGDl19+mSeeeIJjx46Zmic7O5u9e/dy7733kpCQQGpqKp9+\n+qmpmQpcunSJL7/8kqFDh5odhYyMDGJjY/nll1/Yv38/mzdv5uuvvzY7FjVq1ODtt99mwoQJDBky\nhLZt21KtWrVi73frQhAeHs7u3bvtz1NTU+nUqZOJidzX5cuXuffee3nggQcYOHCg2XGuERQURL9+\n/Uzt2tu0aROrVq2iadOmDB8+nO+//54HH3zQtDxXaty4MQAtW7ZkwIABfPnll6bmadasGSEhIfTv\n35/q1aszfPhwvv32W1MzFfj222/p2LEjDRo0MDsKycnJdOrUiWbNmlGvXj2GDh1KYmKi2bEA6N+/\nP9988w0bN24kPz+/yPVZBdy6EGiNQekYhsHYsWNp06aNW81aOHnyJGfOnAHg1KlTrF271tQiNWvW\nLA4dOkR6ejrLly8nJiaGDz/80LQ8BS5cuEBmZiZg+w1zzZo1Jf6jdZXmzZuTlJREfn4+X3/9Nb16\n9TI7EgDLli1j+PDhZscAbGOG27Zt4/Tp0+Tk5PDtt9/Su3dvs2MBcOLECcA2nvLzzz8TFhZW/M2u\nGcO+fgkJCUZoaKjxpz/9yYiLizM7jnHfffcZjRs3Nnx9fY1bb73VWLx4sdmRjPXr1xsWi8Vo3769\n0aFDB6NDhw7Gt99+a3YsY+fOnYbVajXatWtn9O7d2/jggw/MjmSXkJDgNrOG0tLSjPbt2xvt27c3\nYmJijEWLFpkdyTAMw9izZ48RGRlptG/f3pg6daqRlZVldiQjKyvLqFevntvMijMMw3j//feNqKgo\n4/bbbzemT59u5OXlmR3JMAzD6N69uxESEmLcfvvtRlJSUon3mr7XkIiImMutu4ZERKTiqRCIiHg5\nFQIRES+nQiAi4uVUCMSjBAUFcfr06Wuud+3atUxf6+j+WbNmXV9AJ9i/f7/TNzWsiPeUykOFQDxK\ncSfVbdy4sUxf6+j+l19+uWzBRDyYCoG4JcMweOihhwgLC6Nt27asWLGi0OsXL16kb9++LFq0CICa\nNWsCkJCQYN+zp02bNsTFxRX5/gX3nz9/nnvuuQer1Urbtm3ZsGED06ZN4+LFi1itVh544IEiv/a5\n554jJCSEIUOGsHv3bnr27ElYWJh9Ven+/fuJiooiLCyMIUOGsGPHDgBWrlxpX5h19OhRQkJC7At/\nivvf4d133+XOO++kV69efP755wAMHz6cb775xn7f6NGj+fzzz4u9X6REFb+sQaTsvv/+e2PkyJH2\n52fPnjUMw7Zd8/79+41evXoZH330kf31mjVrGoZhGOvWrTN8fHyMbdu2GWfPnjU6d+5sbNu2zf61\nBVs9F9y/ePFiY/r06YZhGEZ+fr6RmZlZ6PWiWCwWY8mSJUZ+fr5xxx13GF27djXOnTtnJCQkGHff\nfbdhGIZx4cIFIzs72zAMw9iyZYsxfPhw+9ePHDnSmDt3rnH33Xcby5cvv+b909PT7ducr1u3znji\niSeM/Px8Iysry7BarUZOTo6xcuVKY9SoUYZhGEZOTo5x2223GdnZ2cXef+V7ilzNLU4oE7lay5Yt\nSU5OZurUqYwePdrev20YBgMHDuTpp58udpuB1q1b07FjRwAGDx7M6tWr7c+v1qFDB2bPno3FYuGh\nhx6iadOmDrNVrVqV++67D4vFQmRkJFWqVMHf35/OnTsX2ur3+eef57vvviMvL49Dhw7Zr8+dO5fW\nrVvTpUsXhg0bVuL3+uyzz1i7di3ff/89AOfOnWPLli307duXyZMnc+nSJb799lt69OiBn59fsfcH\nBgY6/LnEe6lrSNxSo0aN2LFjB+3bt+fhhx9m3rx5gK2fv1u3bmXaAK24cQUAq9VKUlISjRs3ZsCA\nAXz11VcO38/Pz89+roKvr699TyxfX19ycnIA+OSTTzh58iQbNmwgPj7evucS2E6Uq1KlCsePH3e4\nC2p+fj7PPvssKSkppKSk8NtvvxEVFYWfnx/R0dGsWbOGTz/91F5QirtfpCQqBOKWjh49CsCDDz7I\n5MmT+emnn+yvvfjii9StW5cJEyYU+bWpqamkpKRw7tw5/vGPf5S4gdvBgwepWbMmsbGx3H///ezc\nuROABg0acOHChevOf+TIEZo0aYKfnx/vvvsu+fn5AOTm5jJ27FiWL19OaGgob775ZonvM2LECD78\n8EMyMjIA2Lt3rz3XsGHDWLx4MevXr7f/jCXdL1IcFQJxSz///DORkZGEhYXxt7/9jf/5n/8p9Hpc\nXBwXL15k2rRpQOHf+qOjo5k5cyZdunRh6NChRe66WHD/unXr6NChAx07dmTr1q2MGzcOgIkTJ9K9\ne/ciB4uvbmFc+bzg76NGjWLDhg20bduWS5cu2QenZ82aRVRUFF26dOHNN9/kvffeY8+ePcV+j65d\nuzJixAiGDh1K27ZtiY2NJTc3F4DevXuTmJjInXfeSdWqVYu9Py8vr8jcIgW06ZxUKgkJCbzxxhum\n7+cv4knUIpBKxWKx6DdfkTJSi0BExMupRSAi4uVUCEREvJwKgYiIl1MhEBHxcioEIiJeToVARMTL\n/T/CZjq1Ab+myQAAAABJRU5ErkJggg==\n",
       "text": [
        "<matplotlib.figure.Figure at 0x10b827ad0>"
       ]
      }
     ],
     "prompt_number": 52
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}