{
"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] Color: (0, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 128);\"></td><td title=\"Index: [0, 1] Color: (0, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 26, 128);\"></td><td title=\"Index: [0, 2] Color: (0, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 51, 128);\"></td><td title=\"Index: [0, 3] Color: (0, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 77, 128);\"></td><td title=\"Index: [0, 4] Color: (0, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 102, 128);\"></td><td title=\"Index: [0, 5] Color: (0, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 128, 128);\"></td><td title=\"Index: [0, 6] Color: (0, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 153, 128);\"></td><td title=\"Index: [0, 7] Color: (0, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 179, 128);\"></td><td title=\"Index: [0, 8] Color: (0, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 204, 128);\"></td><td title=\"Index: [0, 9] Color: (0, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 230, 128);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (26, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 0, 128);\"></td><td title=\"Index: [1, 1] Color: (26, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 26, 128);\"></td><td title=\"Index: [1, 2] Color: (26, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 51, 128);\"></td><td title=\"Index: [1, 3] Color: (26, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 77, 128);\"></td><td title=\"Index: [1, 4] Color: (26, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 102, 128);\"></td><td title=\"Index: [1, 5] Color: (26, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 128, 128);\"></td><td title=\"Index: [1, 6] Color: (26, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 153, 128);\"></td><td title=\"Index: [1, 7] Color: (26, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 179, 128);\"></td><td title=\"Index: [1, 8] Color: (26, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 204, 128);\"></td><td title=\"Index: [1, 9] Color: (26, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(26, 230, 128);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (51, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 0, 128);\"></td><td title=\"Index: [2, 1] Color: (51, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 26, 128);\"></td><td title=\"Index: [2, 2] Color: (51, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 51, 128);\"></td><td title=\"Index: [2, 3] Color: (51, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 77, 128);\"></td><td title=\"Index: [2, 4] Color: (51, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 102, 128);\"></td><td title=\"Index: [2, 5] Color: (51, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 128, 128);\"></td><td title=\"Index: [2, 6] Color: (51, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 153, 128);\"></td><td title=\"Index: [2, 7] Color: (51, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 179, 128);\"></td><td title=\"Index: [2, 8] Color: (51, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 204, 128);\"></td><td title=\"Index: [2, 9] Color: (51, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(51, 230, 128);\"></td></tr><tr><td title=\"Index: [3, 0] Color: (77, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 0, 128);\"></td><td title=\"Index: [3, 1] Color: (77, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 26, 128);\"></td><td title=\"Index: [3, 2] Color: (77, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 51, 128);\"></td><td title=\"Index: [3, 3] Color: (77, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 77, 128);\"></td><td title=\"Index: [3, 4] Color: (77, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 102, 128);\"></td><td title=\"Index: [3, 5] Color: (77, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 128, 128);\"></td><td title=\"Index: [3, 6] Color: (77, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 153, 128);\"></td><td title=\"Index: [3, 7] Color: (77, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 179, 128);\"></td><td title=\"Index: [3, 8] Color: (77, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 204, 128);\"></td><td title=\"Index: [3, 9] Color: (77, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(77, 230, 128);\"></td></tr><tr><td title=\"Index: [4, 0] Color: (102, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 0, 128);\"></td><td title=\"Index: [4, 1] Color: (102, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 26, 128);\"></td><td title=\"Index: [4, 2] Color: (102, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 51, 128);\"></td><td title=\"Index: [4, 3] Color: (102, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 77, 128);\"></td><td title=\"Index: [4, 4] Color: (102, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 102, 128);\"></td><td title=\"Index: [4, 5] Color: (102, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 128, 128);\"></td><td title=\"Index: [4, 6] Color: (102, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 153, 128);\"></td><td title=\"Index: [4, 7] Color: (102, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 179, 128);\"></td><td title=\"Index: [4, 8] Color: (102, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 204, 128);\"></td><td title=\"Index: [4, 9] Color: (102, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(102, 230, 128);\"></td></tr><tr><td title=\"Index: [5, 0] Color: (128, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 0, 128);\"></td><td title=\"Index: [5, 1] Color: (128, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 26, 128);\"></td><td title=\"Index: [5, 2] Color: (128, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 51, 128);\"></td><td title=\"Index: [5, 3] Color: (128, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 77, 128);\"></td><td title=\"Index: [5, 4] Color: (128, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 102, 128);\"></td><td title=\"Index: [5, 5] Color: (128, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 128, 128);\"></td><td title=\"Index: [5, 6] Color: (128, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 153, 128);\"></td><td title=\"Index: [5, 7] Color: (128, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 179, 128);\"></td><td title=\"Index: [5, 8] Color: (128, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 204, 128);\"></td><td title=\"Index: [5, 9] Color: (128, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(128, 230, 128);\"></td></tr><tr><td title=\"Index: [6, 0] Color: (153, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 0, 128);\"></td><td title=\"Index: [6, 1] Color: (153, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 26, 128);\"></td><td title=\"Index: [6, 2] Color: (153, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 51, 128);\"></td><td title=\"Index: [6, 3] Color: (153, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 77, 128);\"></td><td title=\"Index: [6, 4] Color: (153, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 102, 128);\"></td><td title=\"Index: [6, 5] Color: (153, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 128, 128);\"></td><td title=\"Index: [6, 6] Color: (153, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 153, 128);\"></td><td title=\"Index: [6, 7] Color: (153, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 179, 128);\"></td><td title=\"Index: [6, 8] Color: (153, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 204, 128);\"></td><td title=\"Index: [6, 9] Color: (153, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(153, 230, 128);\"></td></tr><tr><td title=\"Index: [7, 0] Color: (179, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 0, 128);\"></td><td title=\"Index: [7, 1] Color: (179, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 26, 128);\"></td><td title=\"Index: [7, 2] Color: (179, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 51, 128);\"></td><td title=\"Index: [7, 3] Color: (179, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 77, 128);\"></td><td title=\"Index: [7, 4] Color: (179, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 102, 128);\"></td><td title=\"Index: [7, 5] Color: (179, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 128, 128);\"></td><td title=\"Index: [7, 6] Color: (179, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 153, 128);\"></td><td title=\"Index: [7, 7] Color: (179, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 179, 128);\"></td><td title=\"Index: [7, 8] Color: (179, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 204, 128);\"></td><td title=\"Index: [7, 9] Color: (179, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(179, 230, 128);\"></td></tr><tr><td title=\"Index: [8, 0] Color: (204, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 0, 128);\"></td><td title=\"Index: [8, 1] Color: (204, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 26, 128);\"></td><td title=\"Index: [8, 2] Color: (204, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 51, 128);\"></td><td title=\"Index: [8, 3] Color: (204, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 77, 128);\"></td><td title=\"Index: [8, 4] Color: (204, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 102, 128);\"></td><td title=\"Index: [8, 5] Color: (204, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 128, 128);\"></td><td title=\"Index: [8, 6] Color: (204, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 153, 128);\"></td><td title=\"Index: [8, 7] Color: (204, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 179, 128);\"></td><td title=\"Index: [8, 8] Color: (204, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 204, 128);\"></td><td title=\"Index: [8, 9] Color: (204, 230, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(204, 230, 128);\"></td></tr><tr><td title=\"Index: [9, 0] Color: (230, 0, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 0, 128);\"></td><td title=\"Index: [9, 1] Color: (230, 26, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 26, 128);\"></td><td title=\"Index: [9, 2] Color: (230, 51, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 51, 128);\"></td><td title=\"Index: [9, 3] Color: (230, 77, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 77, 128);\"></td><td title=\"Index: [9, 4] Color: (230, 102, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 102, 128);\"></td><td title=\"Index: [9, 5] Color: (230, 128, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 128, 128);\"></td><td title=\"Index: [9, 6] Color: (230, 153, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 153, 128);\"></td><td title=\"Index: [9, 7] Color: (230, 179, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 179, 128);\"></td><td title=\"Index: [9, 8] Color: (230, 204, 128)\" style=\"width: 20px; height: 20px;background-color: rgb(230, 204, 128);\"></td><td title=\"Index: [9, 9] 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] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 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] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 2] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 3] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [0, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [0, 5] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 6] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [0, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [1, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 2] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 3] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [1, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [1, 7] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 8] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 9] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td><td title=\"Index: [1, 10] Color: (255, 255, 255)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 255, 255);\"></td></tr><tr><td title=\"Index: [2, 0] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 1] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 2] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 3] Color: (255, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(255, 0, 0);\"></td><td title=\"Index: [2, 4] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 5] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 6] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 7] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 8] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 9] Color: (0, 0, 0)\" style=\"width: 20px; height: 20px;background-color: rgb(0, 0, 0);\"></td><td title=\"Index: [2, 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": {}
}
]
}