Skip to content

Instantly share code, notes, and snippets.

@gazzar

gazzar/04-bloom-filters-GR.ipynb

Created March 17, 2013 08:33
Show Gist options
  • Save gazzar/5180685 to your computer and use it in GitHub Desktop.
Save gazzar/5180685 to your computer and use it in GitHub Desktop.
Download ZIP
Modified version of Titus Brown's ipynb from http://ivory.idyll.org/blog/2013-pycon-awesome-big-data-algorithms-talk.html with modified ipythonblocks
Display the source blob
Display the rendered blob
Raw
04-bloom-filters-GR.ipynb
{
"metadata": {
"name": "04-bloom-filters-GR"
},
"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\nBelow, I will use IPython Blocks (https://github.com/jiffyclub/ipythonblocks) to demonstrate Bloom filters.\n\nIPython 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, colors",
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 1
},
{
"cell_type": "code",
"collapsed": false,
"input": "grid = BlockGrid(10,10, fill=(0,0,128))\nx = grid.shape[0]\ny = grid.shape[1]\n\nfor 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 \ngrid",
"language": "python",
"metadata": {},
"outputs": [
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks2678bbe3-1aed-4f1a-a915-74e976ad8b6a td {border: 1px solid white;}</style><table id=\"blocks2678bbe3-1aed-4f1a-a915-74e976ad8b6a\" class=\"blockgrid\" style=\"margin-top: 14px; margin-bottom: 14px;\"><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 0x83217f0>"
}
],
"prompt_number": 2
},
{
"cell_type": "markdown",
"metadata": {},
"source": "## Bloom filters\n\nI'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\nFirst, 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\nclass Hash(object):\n def __init__(self, size):\n self.size = size\n self.bits = [0]*size\n self.grid = BlockGrid(height=1, width=size, padding=0)\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 bool(self.bits[num])\n\n def show(self):\n for j, bit in enumerate(self.bits):\n self.grid[0, j] = colors['Red'] if bit else colors['Black']\n return self.grid.show()",
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 3
},
{
"cell_type": "code",
"collapsed": false,
"input": "h = Hash(4)\nh.show()\nh.add(1)\nh.show()\nprint h.get(1)\nh.add(2)\nprint h.get(3)\n",
"language": "python",
"metadata": {},
"outputs": [
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks934befac-ccce-4eed-bdd8-ae815d2ddb60 td {border: 1px solid white;}</style><table id=\"blocks934befac-ccce-4eed-bdd8-ae815d2ddb60\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x8321470>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksedfc162d-dac1-4de9-921e-3a76f4d2ef51 td {border: 1px solid white;}</style><table id=\"blocksedfc162d-dac1-4de9-921e-3a76f4d2ef51\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x82ef080>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "True\nFalse\n"
}
],
"prompt_number": 4
},
{
"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\nI'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()\n '''\n\n def show(self):\n for h in self.hashes:\n h.show()\n",
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 5
},
{
"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)\nx.show()\nx.add(253)\nx.show()\nprint x.get(253)\n\n###\n\nx.add(8132)\nx.show()\nprint x.get(8132)",
"language": "python",
"metadata": {},
"outputs": [
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks29f5e7a5-f190-436e-a962-a7abb02afe96 td {border: 1px solid white;}</style><table id=\"blocks29f5e7a5-f190-436e-a962-a7abb02afe96\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x83228d0>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks51b84453-d71e-4f8c-bb22-f2281e10672d td {border: 1px solid white;}</style><table id=\"blocks51b84453-d71e-4f8c-bb22-f2281e10672d\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x82f7d30>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks79f450ed-4fc7-480a-85da-e840d86523b4 td {border: 1px solid white;}</style><table id=\"blocks79f450ed-4fc7-480a-85da-e840d86523b4\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x82f7ef0>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks16659ebd-c2b9-4580-bd63-143e3e85aae3 td {border: 1px solid white;}</style><table id=\"blocks16659ebd-c2b9-4580-bd63-143e3e85aae3\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x82f7ef0>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks1ce27846-15b7-488a-8832-31843ef0bd5a td {border: 1px solid white;}</style><table id=\"blocks1ce27846-15b7-488a-8832-31843ef0bd5a\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x82f7ef0>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks1dfa9ac3-5b3a-437d-a635-348893bd7421 td {border: 1px solid white;}</style><table id=\"blocks1dfa9ac3-5b3a-437d-a635-348893bd7421\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x82f7ef0>"
},
{
"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;} #blocks4b6df728-46f2-4e7a-8e74-e8be3e17358e td {border: 1px solid white;}</style><table id=\"blocks4b6df728-46f2-4e7a-8e74-e8be3e17358e\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x82f7fd0>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks500e25e6-3516-4ad8-8b7c-6078a9adb915 td {border: 1px solid white;}</style><table id=\"blocks500e25e6-3516-4ad8-8b7c-6078a9adb915\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x82f7fd0>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks288706cc-d448-4ff1-9915-a7045298c582 td {border: 1px solid white;}</style><table id=\"blocks288706cc-d448-4ff1-9915-a7045298c582\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x82f7fd0>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "1\n"
}
],
"prompt_number": 6
},
{
"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\nx = BloomFilter(5, 7, 11)\nactual = set()\nfor _ 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;} #blocks202d1136-19ed-463c-81ff-22375acc93bd td {border: 1px solid white;}</style><table id=\"blocks202d1136-19ed-463c-81ff-22375acc93bd\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x8322320>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks2478fb55-3f69-46cf-9f7d-2c11dd6619d8 td {border: 1px solid white;}</style><table id=\"blocks2478fb55-3f69-46cf-9f7d-2c11dd6619d8\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x83214a8>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks2067b4e6-3a50-4c61-abe4-a66ca2f808d3 td {border: 1px solid white;}</style><table id=\"blocks2067b4e6-3a50-4c61-abe4-a66ca2f808d3\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x83214a8>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "inserting 25\npredicted 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;} #blocks8c14a123-c4e0-4552-a6a3-d65263ba500d td {border: 1px solid white;}</style><table id=\"blocks8c14a123-c4e0-4552-a6a3-d65263ba500d\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x8322400>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksfaea60f4-1759-475d-918f-41e12e3cd269 td {border: 1px solid white;}</style><table id=\"blocksfaea60f4-1759-475d-918f-41e12e3cd269\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x83214a8>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksafb2e23b-b1c9-4239-95dd-5b60f1dca983 td {border: 1px solid white;}</style><table id=\"blocksafb2e23b-b1c9-4239-95dd-5b60f1dca983\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x83214a8>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "inserting 111\npredicted FP: 0.0207792207792 diff from actual: 0.0129360835243\n"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks321075de-d871-42e0-88c1-e430093d6474 td {border: 1px solid white;}</style><table id=\"blocks321075de-d871-42e0-88c1-e430093d6474\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x8322400>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks9b0bffb3-7a43-4b46-ad83-31086e82117b td {border: 1px solid white;}</style><table id=\"blocks9b0bffb3-7a43-4b46-ad83-31086e82117b\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x8322240>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks60699acc-d36c-4b30-81eb-cc270e08795b td {border: 1px solid white;}</style><table id=\"blocks60699acc-d36c-4b30-81eb-cc270e08795b\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x8322400>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "inserting 60\npredicted FP: 0.0311688311688 diff from actual: 0.0194041252865\n"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks9d17f0ff-4397-4fba-8dca-84ce00cc9c9d td {border: 1px solid white;}</style><table id=\"blocks9d17f0ff-4397-4fba-8dca-84ce00cc9c9d\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x8322240>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks0befaa4f-58cd-449a-b25a-70621e3bcbed td {border: 1px solid white;}</style><table id=\"blocks0befaa4f-58cd-449a-b25a-70621e3bcbed\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x8322400>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksa36a9406-00af-40e8-a9ff-c333cf16768e td {border: 1px solid white;}</style><table id=\"blocksa36a9406-00af-40e8-a9ff-c333cf16768e\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x8322240>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "inserting 138\npredicted FP: 0.0935064935065 diff from actual: 0.0268398268398\n"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksa7b1579d-768e-48fa-b0a2-5443a21269c8 td {border: 1px solid white;}</style><table id=\"blocksa7b1579d-768e-48fa-b0a2-5443a21269c8\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x8322400>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksd1883720-1dbd-41d8-9524-827db1e1d265 td {border: 1px solid white;}</style><table id=\"blocksd1883720-1dbd-41d8-9524-827db1e1d265\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x8322240>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksee3e746a-f2a7-43a2-afba-28dd0d94f8ee td {border: 1px solid white;}</style><table id=\"blocksee3e746a-f2a7-43a2-afba-28dd0d94f8ee\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x8322400>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "inserting 105\npredicted FP: 0.124675324675 diff from actual: 0.0227145403616\n"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks2fcf13a2-d249-4dfc-b6dc-4b988ee08588 td {border: 1px solid white;}</style><table id=\"blocks2fcf13a2-d249-4dfc-b6dc-4b988ee08588\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x8322240>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksa05f8246-fa63-4794-801a-add7ec0bf995 td {border: 1px solid white;}</style><table id=\"blocksa05f8246-fa63-4794-801a-add7ec0bf995\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x8322400>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksf7d5a5df-a8af-4c22-a224-935ca1900b48 td {border: 1px solid white;}</style><table id=\"blocksf7d5a5df-a8af-4c22-a224-935ca1900b48\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x8322240>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "inserting 183\npredicted FP: 0.194805194805 diff from actual: 0.0261777438248\n"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks2c924a9a-e059-4dbe-a4f8-c342599a602d td {border: 1px solid white;}</style><table id=\"blocks2c924a9a-e059-4dbe-a4f8-c342599a602d\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x8322400>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksed87df33-e62b-4796-9212-356cb4afaaa8 td {border: 1px solid white;}</style><table id=\"blocksed87df33-e62b-4796-9212-356cb4afaaa8\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x8322240>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks64e3daeb-38e8-4244-a8ab-dac341fb07b4 td {border: 1px solid white;}</style><table id=\"blocks64e3daeb-38e8-4244-a8ab-dac341fb07b4\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x8322400>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "inserting 36\npredicted FP: 0.194805194805 diff from actual: 0.0300993124523\n"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks909a74a2-0b81-4526-a945-5f320feb2dba td {border: 1px solid white;}</style><table id=\"blocks909a74a2-0b81-4526-a945-5f320feb2dba\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x8322240>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksa4b9f3f0-6816-4b67-a997-28020619c41c td {border: 1px solid white;}</style><table id=\"blocksa4b9f3f0-6816-4b67-a997-28020619c41c\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x8322400>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks1f5571d3-4c56-4ec1-8f4d-fe459044e47d td {border: 1px solid white;}</style><table id=\"blocks1f5571d3-4c56-4ec1-8f4d-fe459044e47d\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x8322240>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "inserting 113\npredicted FP: 0.194805194805 diff from actual: 0.0340208810797\n"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksc5ded8a3-2e0f-41d6-91e0-ce4d8a43f46a td {border: 1px solid white;}</style><table id=\"blocksc5ded8a3-2e0f-41d6-91e0-ce4d8a43f46a\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x8322400>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksc6b74b49-336b-49f7-9b0b-7ccb09a45499 td {border: 1px solid white;}</style><table id=\"blocksc6b74b49-336b-49f7-9b0b-7ccb09a45499\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x8322240>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks62396269-6737-4725-bfeb-601848e947bd td {border: 1px solid white;}</style><table id=\"blocks62396269-6737-4725-bfeb-601848e947bd\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x8322400>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "inserting 151\npredicted FP: 0.233766233766 diff from actual: 0.0298446651388\n"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksd7eb03d2-447e-4a4e-b8d1-ab4394a9f34b td {border: 1px solid white;}</style><table id=\"blocksd7eb03d2-447e-4a4e-b8d1-ab4394a9f34b\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x8322240>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks9dfcc71f-8233-40ec-bae3-56312e486d72 td {border: 1px solid white;}</style><table id=\"blocks9dfcc71f-8233-40ec-bae3-56312e486d72\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x8322400>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks0dce051b-2d3c-4a15-96c0-b6b415405a70 td {border: 1px solid white;}</style><table id=\"blocks0dce051b-2d3c-4a15-96c0-b6b415405a70\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (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, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x8322240>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "inserting 33\npredicted FP: 0.272727272727 diff from actual: 0.0335115864528\n"
}
],
"prompt_number": 7
},
{
"cell_type": "markdown",
"metadata": {},
"source": "## One-sided error\n\nBloom 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\nIf 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.\nx = BloomFilter(5, 7, 11)\nx.add(3)\nx.show()\n\nprint x.get(3), x.get(3 + (5*7*11))\nprint \"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;} #blocks27b0e13a-6353-4ec6-9f10-ef26ac1a23e3 td {border: 1px solid white;}</style><table id=\"blocks27b0e13a-6353-4ec6-9f10-ef26ac1a23e3\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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></tr></tbody></table>",
"output_type": "display_data",
"text": "<IPython.core.display.HTML at 0x82ef0b8>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocksb0a30835-094a-4281-8439-16ad27ca3e0a td {border: 1px solid white;}</style><table id=\"blocksb0a30835-094a-4281-8439-16ad27ca3e0a\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#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 0x82ef128>"
},
{
"html": "<style type=\"text/css\">table.blockgrid {border: none;} .blockgrid tr {border: none;} .blockgrid td {padding: 0px;} #blocks37f33b76-f97f-4151-9f89-3dcb1acc8a05 td {border: 1px solid white;}</style><table id=\"blocks37f33b76-f97f-4151-9f89-3dcb1acc8a05\" class=\"blockgrid\" style=\"margin-top: 0px; margin-bottom: 0px;\"><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: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 6]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 7]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 8]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 9]&#10;Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 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 0x82ef0b8>"
},
{
"output_type": "stream",
"stream": "stdout",
"text": "1 1\noh noes! 388 is falsely said to be present in the data set!\n"
}
],
"prompt_number": 8
},
{
"cell_type": "code",
"collapsed": false,
"input": "",
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 8
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment