L1 - List Intersection.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# List intersection algorithms\n",
    "\n",
    "In this notebook, you can experiment with two algorithms (the naive one and the one using galloping search) to perform list intersection, which is an essential operator in supporting conjunction keyword queries.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "## define the function p() that outputs debugging messages if DEBUG flag is True. \n",
    "\n",
    "#DEBUG = True\n",
    "DEBUG = False\n",
    "\n",
    "def p(msg):\n",
    "    if DEBUG:\n",
    "        print(\".. {}\".format(msg)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The InvertedList class\n",
    "\n",
    "We implement this class which encapsulates all the important *operations* one can perform on an inverted list. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pprint import pprint\n",
    "from bisect import *\n",
    "\n",
    "## You may find many similarity between this class and the file operation (in C/Java). \n",
    "class InvertedList:\n",
    "    def __init__(self, l):\n",
    "        self.data = l[:] # make a copy\n",
    "        self.cur = 0     # the cursor \n",
    "\n",
    "    def get_list(self):\n",
    "        return self.data\n",
    " \n",
    "    def eol(self):\n",
    "        # we use cur == len(list) to indicate EOL\n",
    "        return False if self.cur < len(self.data) else True\n",
    "    \n",
    "    def next(self, val = 1):\n",
    "        # does not allow cur to be out-of-range, but use len(list) to indicate EOL\n",
    "        self.cur = min(self.cur + val, len(self.data)) \n",
    "            \n",
    "    def elem(self):\n",
    "        if self.eol():\n",
    "            return None\n",
    "        else: \n",
    "            return self.data[self.cur]\n",
    "\n",
    "    def peek(self, pos):\n",
    "        # look at the element under the current cursor, but does not advance the cursor. \n",
    "        if pos < len(self.data):\n",
    "            return self.data[pos]\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "    def reset(self):\n",
    "        self.cur = 0\n",
    "    \n",
    "    def dump(self):\n",
    "        print(\"* {} : {} (cur = {})\".format(self.data[:self.cur], self.data[self.cur:], self.cur))\n",
    "        \n",
    "    def skip_to(self, val):\n",
    "        ##!! This is a naive and inefficient implementation. \n",
    "        ##!! Once you have implemented gallop_to(), you can just call it here instead.\n",
    "        # move the cursor to the first element no smaller than `val`\n",
    "\n",
    "        while not self.eol() and self.elem() < val:\n",
    "            self.next()               \n",
    "            \n",
    "    def gallop_to(self, val):\n",
    "        ##!! Not implemented yet. \n",
    "        pass\n",
    "\n",
    "                        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test the class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "4\n",
      "6\n",
      "8\n",
      "10\n",
      "12\n",
      "14\n",
      "16\n",
      "18\n",
      "* [2, 4, 6, 8, 10, 12, 14, 16, 18] : [] (cur = 9)\n"
     ]
    }
   ],
   "source": [
    "a = InvertedList([2, 4, 6, 8, 10, 12, 14, 16, 18])\n",
    "b = InvertedList([1, 2, 4, 8, 16, 32])\n",
    "\n",
    "while not a.eol():\n",
    "    e = a.elem()\n",
    "    a.next()\n",
    "    print(e)\n",
    "\n",
    "a.dump()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you have implemented the `gallop_to()` correctly, you should pass the following test. You may change the call to `skip_to()` for now to see how it should work. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def test_gallop(l, val):\n",
    "    print(\"=> gallop_to({})\".format(val))\n",
    "    l.reset()\n",
    "    l.gallop_to(val)\n",
    "    l.dump()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "* [2, 4, 6, 8, 10, 12, 14, 16, 18] : [] (cur = 9)\n",
      "=> gallop_to(1)\n",
      "* [] : [2, 4, 6, 8, 10, 12, 14, 16, 18] (cur = 0)\n",
      "=> gallop_to(3)\n",
      "* [2] : [4, 6, 8, 10, 12, 14, 16, 18] (cur = 1)\n",
      "=> gallop_to(5)\n",
      "* [2, 4] : [6, 8, 10, 12, 14, 16, 18] (cur = 2)\n",
      "=> gallop_to(7)\n",
      "* [2, 4, 6] : [8, 10, 12, 14, 16, 18] (cur = 3)\n",
      "=> gallop_to(9)\n",
      "* [2, 4, 6, 8] : [10, 12, 14, 16, 18] (cur = 4)\n",
      "=> gallop_to(11)\n",
      "* [2, 4, 6, 8, 10] : [12, 14, 16, 18] (cur = 5)\n",
      "=> gallop_to(13)\n",
      "* [2, 4, 6, 8, 10, 12] : [14, 16, 18] (cur = 6)\n",
      "=> gallop_to(15)\n",
      "* [2, 4, 6, 8, 10, 12, 14] : [16, 18] (cur = 7)\n",
      "=> gallop_to(17)\n",
      "* [2, 4, 6, 8, 10, 12, 14, 16] : [18] (cur = 8)\n",
      "=> gallop_to(118)\n",
      "* [2, 4, 6, 8, 10, 12, 14, 16, 18] : [] (cur = 9)\n"
     ]
    }
   ],
   "source": [
    "test_a = [val - 1 for val in a.get_list()]\n",
    "test_a.append(a.get_list()[-1] + 100)\n",
    "\n",
    "DEBUG = False # to show the overview\n",
    "a.dump()\n",
    "for t_a in test_a:\n",
    "    test_gallop(a, t_a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=> gallop_to(17)\n",
      ".. moved to pos = 2, elem = 6\n",
      ".. moved to pos = 6, elem = 14\n",
      ".. moved to pos = 14, elem = None\n",
      ".. Stage 1 complete: interval = [6, 8], elems = [14, 18]\n",
      ".. Stage 2 complete: cur = 8, sub_pos = 1, sub_list = [16, 18]\n",
      "* [2, 4, 6, 8, 10, 12, 14, 16] : [18] (cur = 8)\n"
     ]
    }
   ],
   "source": [
    "DEBUG = True # to show the details. Your detailed debugging info may vary. \n",
    "test_gallop(a, test_a[-2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see above, the galloping search algorithm quickly skip over the list to reposition the cursor. In the additional note, it is proved that its complexity is $O(\\log x)$, where $x$ is the difference between the correct cursor position and the initial cursor position. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Naive Intersection Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def intersection_naive(a, b):\n",
    "    # just in case these lists have been traversed.\n",
    "    a.reset()\n",
    "    b.reset()\n",
    "    \n",
    "    ret = []\n",
    "    while not a.eol() and not b.eol():\n",
    "        if a.elem() < b.elem():\n",
    "            p(\"move a\")\n",
    "            a.next()\n",
    "        elif a.elem() > b.elem():\n",
    "            p(\"move b\")\n",
    "            b.next()\n",
    "        else:\n",
    "            p(\"found one\")\n",
    "            ret.append(a.elem())\n",
    "            a.next()\n",
    "            b.next()\n",
    "    return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".. move b\n",
      ".. found one\n",
      ".. found one\n",
      ".. move a\n",
      ".. found one\n",
      ".. move a\n",
      ".. move a\n",
      ".. move a\n",
      ".. found one\n",
      ".. move a\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[2, 4, 8, 16]"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "intersection_naive(a, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Intersection Algorithm using `gallop_to()`\n",
    "\n",
    "Here, we call `gallop_to` explicitly to show some detailed info if you have it implemented correctly. You can change the calls to `skip_to` in a more general setting. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def intersection_galloping(a, b):\n",
    "    # just in case these lists have been traversed.\n",
    "    a.reset()\n",
    "    b.reset()\n",
    "    \n",
    "    ret = []\n",
    "    while not a.eol() and not b.eol():\n",
    "        if a.elem() == b.elem():\n",
    "            p(\"found one\")\n",
    "            ret.append(a.elem())\n",
    "            a.next()\n",
    "        else:\n",
    "            if a.elem() < b.elem():\n",
    "                a.gallop_to(b.elem())\n",
    "            else:\n",
    "                b.gallop_to(a.elem())\n",
    "    # end_while\n",
    "    return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".. moved to pos = 2, elem = 4\n",
      ".. Stage 1 complete: interval = [0, 2], elems = [1, 4]\n",
      ".. Stage 2 complete: cur = 1, sub_pos = 0, sub_list = [2, 4]\n",
      ".. found one\n",
      ".. moved to pos = 3, elem = 8\n",
      ".. Stage 1 complete: interval = [1, 3], elems = [2, 8]\n",
      ".. Stage 2 complete: cur = 2, sub_pos = 0, sub_list = [4, 8]\n",
      ".. found one\n",
      ".. moved to pos = 4, elem = 16\n",
      ".. Stage 1 complete: interval = [2, 4], elems = [4, 16]\n",
      ".. Stage 2 complete: cur = 3, sub_pos = 0, sub_list = [8, 16]\n",
      ".. moved to pos = 4, elem = 10\n",
      ".. Stage 1 complete: interval = [2, 4], elems = [6, 10]\n",
      ".. Stage 2 complete: cur = 3, sub_pos = 0, sub_list = [8, 10]\n",
      ".. found one\n",
      ".. moved to pos = 5, elem = 32\n",
      ".. Stage 1 complete: interval = [3, 5], elems = [8, 32]\n",
      ".. Stage 2 complete: cur = 4, sub_pos = 0, sub_list = [16, 32]\n",
      ".. moved to pos = 6, elem = 14\n",
      ".. moved to pos = 10, elem = None\n",
      ".. Stage 1 complete: interval = [6, 8], elems = [14, 18]\n",
      ".. Stage 2 complete: cur = 7, sub_pos = 0, sub_list = [16, 18]\n",
      ".. found one\n",
      ".. moved to pos = 6, elem = None\n",
      ".. Stage 1 complete: interval = [4, 6], elems = [16, None]\n",
      ".. Stage 2 complete: cur = 5, sub_pos = 0, sub_list = [32]\n",
      ".. moved to pos = 10, elem = None\n",
      ".. Stage 1 complete: interval = [8, 10], elems = [18, None]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[2, 4, 8, 16]"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "intersection_galloping(a, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Exercise\n",
    "\n",
    "You need to correctly implement `gallop_to` using the galloping search algorithm, and then play with the intersection algorithm to appreciate how efficient it works in action. Note that the implementation is not hard, but you do need to take care of a few corner cases. That's why the `test_gallop()` evaluates almost all possible situation. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}