04-bloom-filters.ipynb

{
 "metadata": {
  "name": "04-bloom-filters"
 },
 "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": [
      "## IPython Blocks\n",
      "\n",
      "Below, I will use IPython Blocks (https://github.com/jiffyclub/ipythonblocks) to demonstrate Bloom filters.\n",
      "\n",
      "IPython Blocks is a nifty little visualization tool built by Matt Davis @jiffyclub for use in teaching Python and programming basics.  Here's a quick little demo --"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from ipythonblocks import BlockGrid"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "grid = BlockGrid(10,10, fill=(0,0,128))\n",
      "\n",
      "x = grid.shape[0]\n",
      "y = grid.shape[1]\n",
      "\n",
      "for block in grid:\n",
      "    r = block.row * 255 / float(x)\n",
      "    g = block.col * 255 / float(y)\n",
      "    block.red = r\n",
      "    block.green = g\n",
      "    \n",
      "grid"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks400f3d84-2282-4b68-a5ac-0b2229ca8255 td {border: 1px solid white;}</style><table id=\"blocks400f3d84-2282-4b68-a5ac-0b2229ca8255\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (0, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 128);\"></td><td title=\"Index: [0, 1]&#10;Color: (0, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 26, 128);\"></td><td title=\"Index: [0, 2]&#10;Color: (0, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 51, 128);\"></td><td title=\"Index: [0, 3]&#10;Color: (0, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 77, 128);\"></td><td title=\"Index: [0, 4]&#10;Color: (0, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 102, 128);\"></td><td title=\"Index: [0, 5]&#10;Color: (0, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 128, 128);\"></td><td title=\"Index: [0, 6]&#10;Color: (0, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 153, 128);\"></td><td title=\"Index: [0, 7]&#10;Color: (0, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 179, 128);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 204, 128);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 230, 128);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (26, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 0, 128);\"></td><td title=\"Index: [1, 1]&#10;Color: (26, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 26, 128);\"></td><td title=\"Index: [1, 2]&#10;Color: (26, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 51, 128);\"></td><td title=\"Index: [1, 3]&#10;Color: (26, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 77, 128);\"></td><td title=\"Index: [1, 4]&#10;Color: (26, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 102, 128);\"></td><td title=\"Index: [1, 5]&#10;Color: (26, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 128, 128);\"></td><td title=\"Index: [1, 6]&#10;Color: (26, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 153, 128);\"></td><td title=\"Index: [1, 7]&#10;Color: (26, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 179, 128);\"></td><td title=\"Index: [1, 8]&#10;Color: (26, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 204, 128);\"></td><td title=\"Index: [1, 9]&#10;Color: (26, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 230, 128);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (51, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 0, 128);\"></td><td title=\"Index: [2, 1]&#10;Color: (51, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 26, 128);\"></td><td title=\"Index: [2, 2]&#10;Color: (51, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 51, 128);\"></td><td title=\"Index: [2, 3]&#10;Color: (51, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 77, 128);\"></td><td title=\"Index: [2, 4]&#10;Color: (51, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 102, 128);\"></td><td title=\"Index: [2, 5]&#10;Color: (51, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 128, 128);\"></td><td title=\"Index: [2, 6]&#10;Color: (51, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 153, 128);\"></td><td title=\"Index: [2, 7]&#10;Color: (51, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 179, 128);\"></td><td title=\"Index: [2, 8]&#10;Color: (51, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 204, 128);\"></td><td title=\"Index: [2, 9]&#10;Color: (51, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 230, 128);\"></td></tr><tr><td title=\"Index: [3, 0]&#10;Color: (77, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 0, 128);\"></td><td title=\"Index: [3, 1]&#10;Color: (77, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 26, 128);\"></td><td title=\"Index: [3, 2]&#10;Color: (77, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 51, 128);\"></td><td title=\"Index: [3, 3]&#10;Color: (77, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 77, 128);\"></td><td title=\"Index: [3, 4]&#10;Color: (77, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 102, 128);\"></td><td title=\"Index: [3, 5]&#10;Color: (77, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 128, 128);\"></td><td title=\"Index: [3, 6]&#10;Color: (77, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 153, 128);\"></td><td title=\"Index: [3, 7]&#10;Color: (77, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 179, 128);\"></td><td title=\"Index: [3, 8]&#10;Color: (77, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 204, 128);\"></td><td title=\"Index: [3, 9]&#10;Color: (77, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 230, 128);\"></td></tr><tr><td title=\"Index: [4, 0]&#10;Color: (102, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 0, 128);\"></td><td title=\"Index: [4, 1]&#10;Color: (102, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 26, 128);\"></td><td title=\"Index: [4, 2]&#10;Color: (102, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 51, 128);\"></td><td title=\"Index: [4, 3]&#10;Color: (102, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 77, 128);\"></td><td title=\"Index: [4, 4]&#10;Color: (102, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 102, 128);\"></td><td title=\"Index: [4, 5]&#10;Color: (102, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 128, 128);\"></td><td title=\"Index: [4, 6]&#10;Color: (102, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 153, 128);\"></td><td title=\"Index: [4, 7]&#10;Color: (102, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 179, 128);\"></td><td title=\"Index: [4, 8]&#10;Color: (102, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 204, 128);\"></td><td title=\"Index: [4, 9]&#10;Color: (102, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 230, 128);\"></td></tr><tr><td title=\"Index: [5, 0]&#10;Color: (128, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 0, 128);\"></td><td title=\"Index: [5, 1]&#10;Color: (128, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 26, 128);\"></td><td title=\"Index: [5, 2]&#10;Color: (128, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 51, 128);\"></td><td title=\"Index: [5, 3]&#10;Color: (128, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 77, 128);\"></td><td title=\"Index: [5, 4]&#10;Color: (128, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 102, 128);\"></td><td title=\"Index: [5, 5]&#10;Color: (128, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 128, 128);\"></td><td title=\"Index: [5, 6]&#10;Color: (128, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 153, 128);\"></td><td title=\"Index: [5, 7]&#10;Color: (128, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 179, 128);\"></td><td title=\"Index: [5, 8]&#10;Color: (128, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 204, 128);\"></td><td title=\"Index: [5, 9]&#10;Color: (128, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 230, 128);\"></td></tr><tr><td title=\"Index: [6, 0]&#10;Color: (153, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 0, 128);\"></td><td title=\"Index: [6, 1]&#10;Color: (153, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 26, 128);\"></td><td title=\"Index: [6, 2]&#10;Color: (153, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 51, 128);\"></td><td title=\"Index: [6, 3]&#10;Color: (153, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 77, 128);\"></td><td title=\"Index: [6, 4]&#10;Color: (153, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 102, 128);\"></td><td title=\"Index: [6, 5]&#10;Color: (153, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 128, 128);\"></td><td title=\"Index: [6, 6]&#10;Color: (153, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 153, 128);\"></td><td title=\"Index: [6, 7]&#10;Color: (153, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 179, 128);\"></td><td title=\"Index: [6, 8]&#10;Color: (153, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 204, 128);\"></td><td title=\"Index: [6, 9]&#10;Color: (153, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 230, 128);\"></td></tr><tr><td title=\"Index: [7, 0]&#10;Color: (179, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 0, 128);\"></td><td title=\"Index: [7, 1]&#10;Color: (179, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 26, 128);\"></td><td title=\"Index: [7, 2]&#10;Color: (179, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 51, 128);\"></td><td title=\"Index: [7, 3]&#10;Color: (179, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 77, 128);\"></td><td title=\"Index: [7, 4]&#10;Color: (179, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 102, 128);\"></td><td title=\"Index: [7, 5]&#10;Color: (179, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 128, 128);\"></td><td title=\"Index: [7, 6]&#10;Color: (179, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 153, 128);\"></td><td title=\"Index: [7, 7]&#10;Color: (179, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 179, 128);\"></td><td title=\"Index: [7, 8]&#10;Color: (179, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 204, 128);\"></td><td title=\"Index: [7, 9]&#10;Color: (179, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 230, 128);\"></td></tr><tr><td title=\"Index: [8, 0]&#10;Color: (204, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 0, 128);\"></td><td title=\"Index: [8, 1]&#10;Color: (204, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 26, 128);\"></td><td title=\"Index: [8, 2]&#10;Color: (204, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 51, 128);\"></td><td title=\"Index: [8, 3]&#10;Color: (204, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 77, 128);\"></td><td title=\"Index: [8, 4]&#10;Color: (204, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 102, 128);\"></td><td title=\"Index: [8, 5]&#10;Color: (204, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 128, 128);\"></td><td title=\"Index: [8, 6]&#10;Color: (204, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 153, 128);\"></td><td title=\"Index: [8, 7]&#10;Color: (204, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 179, 128);\"></td><td title=\"Index: [8, 8]&#10;Color: (204, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 204, 128);\"></td><td title=\"Index: [8, 9]&#10;Color: (204, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 230, 128);\"></td></tr><tr><td title=\"Index: [9, 0]&#10;Color: (230, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 0, 128);\"></td><td title=\"Index: [9, 1]&#10;Color: (230, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 26, 128);\"></td><td title=\"Index: [9, 2]&#10;Color: (230, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 51, 128);\"></td><td title=\"Index: [9, 3]&#10;Color: (230, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 77, 128);\"></td><td title=\"Index: [9, 4]&#10;Color: (230, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 102, 128);\"></td><td title=\"Index: [9, 5]&#10;Color: (230, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 128, 128);\"></td><td title=\"Index: [9, 6]&#10;Color: (230, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 153, 128);\"></td><td title=\"Index: [9, 7]&#10;Color: (230, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 179, 128);\"></td><td title=\"Index: [9, 8]&#10;Color: (230, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 204, 128);\"></td><td title=\"Index: [9, 9]&#10;Color: (230, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 230, 128);\"></td></tr></tbody></table>"
       ],
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "<ipythonblocks.ipythonblocks.BlockGrid at 0x1084522d0>"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Bloom filters\n",
      "\n",
      "I'll implement Bloom filters using multiple individual hash tables. (The canonical way to implement them is to use multiple hash functions with one big hash table, but I find that a bit harder to understand.)\n",
      "\n",
      "First, let's build a simple hash table object that doesn't track collisions.  Note, to get 'num' from a string you'd just use a hash function."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import math\n",
      "\n",
      "class Hash(object):\n",
      "    def __init__(self, size):\n",
      "        self.size = size\n",
      "        self.bits = [0]*size\n",
      "        \n",
      "    def add(self, num):\n",
      "        num = num % self.size\n",
      "        self.bits[num] = 1\n",
      "        \n",
      "    def get(self, num):\n",
      "        num = num % self.size\n",
      "        return self.bits[num]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Next, build a full Bloom filter that creates multiple hash tables; here, 'add' inserts the element into each hash table, and 'get' checks to see if the element is in all the hash tables.\n",
      "\n",
      "I've also included three utility methods: fp(), empirical_fp(), and show().  The first calculates the predicted false positive rate based on hash table occupancy; the second calculates the actual false positive rate for a range of numbers; and the third shows the hash table occupancy using IPython Blocks. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class BloomFilter(object):\n",
      "    def __init__(self, *sizes):\n",
      "        self.hashes = [ Hash(size) for size in sizes ]\n",
      "        \n",
      "    def add(self, num):\n",
      "        for h in self.hashes:\n",
      "            h.add(num)\n",
      "            \n",
      "    def get(self, num):\n",
      "        for h in self.hashes:\n",
      "            if not h.get(num):\n",
      "                return 0\n",
      "        return 1\n",
      "    \n",
      "    def fp(self):\n",
      "        total = 0.\n",
      "        for h in self.hashes:\n",
      "            occupancy = sum(h.bits)\n",
      "            f = occupancy / float(h.size)\n",
      "            total += math.log(f, 2)\n",
      "            \n",
      "        return 2**total\n",
      "    \n",
      "    def empirical_fp(self, actual, max):\n",
      "        found_true = 0\n",
      "        found_false = 0\n",
      "        for i in range(max):\n",
      "            if self.get(i):\n",
      "                if i in actual:\n",
      "                    found_true += 1\n",
      "                else:\n",
      "                    found_false += 1\n",
      "                    \n",
      "        return found_false / float(max)\n",
      "            \n",
      "    \n",
      "    def show(self):\n",
      "        rows = len(self.hashes)\n",
      "        cols = max([ h.size for h in self.hashes ])\n",
      "        grid = BlockGrid(cols, rows, fill=(0,0,0))\n",
      "        for i, h in enumerate(self.hashes):\n",
      "            for pos in range(h.size, cols):\n",
      "                grid[i, pos] = (255, 255, 255)\n",
      "            for j, bit in enumerate(h.bits):\n",
      "                if bit:\n",
      "                    grid[i, j] = (255, 0, 0)\n",
      "        return grid.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Let's create a Bloom filter with three hash tables, size 5, 7, and 11, and then show the occupied cells in the three hash tables after adding '253' and '8132' (no special significance to the numbers)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x = BloomFilter(5, 7, 11)\n",
      "x.show()\n",
      "x.add(253)\n",
      "x.show()\n",
      "print x.get(253)\n",
      "\n",
      "###\n",
      "\n",
      "x.add(8132)\n",
      "x.show()\n",
      "print x.get(8132)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks7cce2ee4-5647-4542-baea-47637333a287 td {border: 1px solid white;}</style><table id=\"blocks7cce2ee4-5647-4542-baea-47637333a287\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463650>"
       ]
      },
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks45c91bd0-d2b9-4d93-a650-fa9a6e39b861 td {border: 1px solid white;}</style><table id=\"blocks45c91bd0-d2b9-4d93-a650-fa9a6e39b861\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x109756610>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksb009ff76-8d02-49a5-9e4f-28847af04d04 td {border: 1px solid white;}</style><table id=\"blocksb009ff76-8d02-49a5-9e4f-28847af04d04\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463510>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Next, let's check out what happens when you start filling up the hash tables with lots and lots of entries."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import random, time\n",
      "\n",
      "x = BloomFilter(5, 7, 11)\n",
      "actual = set()\n",
      "for _ in range(10):\n",
      "    num = random.randint(0, 255)\n",
      "    actual.add(num)\n",
      "    x.add(num)\n",
      "    x.show()\n",
      "    theory, empirical = x.fp(), x.empirical_fp(actual, 255)\n",
      "    print 'inserting', num\n",
      "    print 'predicted FP:', theory, 'diff from actual:', abs(theory-empirical)\n",
      "    time.sleep(1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksca8a9981-a7bf-4214-b82c-2809804886a6 td {border: 1px solid white;}</style><table id=\"blocksca8a9981-a7bf-4214-b82c-2809804886a6\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463f50>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "inserting 2\n",
        "predicted FP: 0.0025974025974 diff from actual: 0.0025974025974\n"
       ]
      },
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks1b02432c-a5c4-4d2f-959f-f61f9540f0d3 td {border: 1px solid white;}</style><table id=\"blocks1b02432c-a5c4-4d2f-959f-f61f9540f0d3\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463f50>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "inserting 49\n",
        "predicted FP: 0.0207792207792 diff from actual: 0.00509294626942\n"
       ]
      },
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksc777dde8-baec-42b8-8114-e8fe9b601837 td {border: 1px solid white;}</style><table id=\"blocksc777dde8-baec-42b8-8114-e8fe9b601837\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463f50>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "inserting 141\n",
        "predicted FP: 0.0701298701299 diff from actual: 0.0034632034632\n"
       ]
      },
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksec1d13ef-7af0-41cc-ae86-d7e27a97395b td {border: 1px solid white;}</style><table id=\"blocksec1d13ef-7af0-41cc-ae86-d7e27a97395b\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463f50>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "inserting 151\n",
        "predicted FP: 0.124675324675 diff from actual: 0.0187929717341\n"
       ]
      },
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks17ccc631-eba9-488e-b2bc-1a54adf63c2e td {border: 1px solid white;}</style><table id=\"blocks17ccc631-eba9-488e-b2bc-1a54adf63c2e\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463f50>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "inserting 26\n",
        "predicted FP: 0.194805194805 diff from actual: 0.0183346065699\n"
       ]
      },
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks667c43bd-8b4b-4064-95bf-47f4b967a90a td {border: 1px solid white;}</style><table id=\"blocks667c43bd-8b4b-4064-95bf-47f4b967a90a\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463f50>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "inserting 54\n",
        "predicted FP: 0.233766233766 diff from actual: 0.0220015278839\n"
       ]
      },
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksf78fd866-4250-4bc5-9053-7046b1695a2a td {border: 1px solid white;}</style><table id=\"blocksf78fd866-4250-4bc5-9053-7046b1695a2a\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463f50>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "inserting 0\n",
        "predicted FP: 0.363636363636 diff from actual: 0.0185383244207\n"
       ]
      },
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksf7c47423-6e6a-4d98-a8b5-8f80258898b6 td {border: 1px solid white;}</style><table id=\"blocksf7c47423-6e6a-4d98-a8b5-8f80258898b6\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463f50>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "inserting 96\n",
        "predicted FP: 0.363636363636 diff from actual: 0.0224598930481\n"
       ]
      },
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksfbbac611-3190-4f84-8bb5-1a2a6143987f td {border: 1px solid white;}</style><table id=\"blocksfbbac611-3190-4f84-8bb5-1a2a6143987f\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463f50>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "inserting 248\n",
        "predicted FP: 0.623376623377 diff from actual: 0.0390628978864\n"
       ]
      },
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks098dd1bb-7e69-4390-9cd6-68e2143a83d3 td {border: 1px solid white;}</style><table id=\"blocks098dd1bb-7e69-4390-9cd6-68e2143a83d3\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463f50>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "inserting 54\n",
        "predicted FP: 0.623376623377 diff from actual: 0.0390628978864\n"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## One-sided error\n",
      "\n",
      "Bloom filters have what's called one-sided error: they may report elements that were never inserted as being members of the set -- false positives -- but they will never miss reporting elements that WERE inserted as being members -- false negatives.  This is a straightforward consequence of the \"no collision tracking\" aspect of the hash tables: collisions lead to false reporting, but you never miss something you've already inserted.\n",
      "\n",
      "If you know the hash table sizes, it's easy to predict the collisions.  One simple way is to test something that's 5*7*11 times added to something you've already inserted, i.e. to force a collision based on the modulus of the hash table sizes."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# here, we add '3' and test for '3 + 5*7*11', or 388.\n",
      "x = BloomFilter(5, 7, 11)\n",
      "x.add(3)\n",
      "x.show()\n",
      "\n",
      "print x.get(3), x.get(3 + (5*7*11))\n",
      "print \"oh noes! 388 is falsely said to be present in the data set!\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksb13a484d-8fc7-4108-9f2f-f99555c6ae75 td {border: 1px solid white;}</style><table id=\"blocksb13a484d-8fc7-4108-9f2f-f99555c6ae75\" class=\"blockgrid\"><tbody><tr><td title=\"Index: [0, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 3]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 2]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 3]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10]&#10;Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 3]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 4]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 10]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td></tr></tbody></table>"
       ],
       "output_type": "display_data",
       "text": [
        "<IPython.core.display.HTML at 0x108463110>"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 1\n",
        "oh noes! 388 is falsely said to be present in the data set!\n"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    }
   ],
   "metadata": {}
  }
 ]
}