L4 - Multiway Merge.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction\n",
    "\n",
    "The key procedure in external memory inverted index construction is the external memory multiway merge algorithm. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from heapq import heappush, heappop, merge\n",
    "# documentation: https://docs.python.org/3.4/library/heapq.html\n",
    "from math import ceil\n",
    "\n",
    "## the heap is essentially a min-heap\n",
    "\n",
    "DEBUG = True\n",
    "\n",
    "def p(msg):\n",
    "    if DEBUG:\n",
    "        print('.. {}'.format(msg))\n",
    "\n",
    "## making use of the heapq.merge() function to simulate the in-memory heap based merging\n",
    "## (see source at https://fossies.org/dox/Python-3.5.2/heapq_8py_source.html)\n",
    "def merge_runs(list_of_runs):\n",
    "    return list(merge(*list_of_runs))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[15, 19, 46, 73, 93] [26, 33, 64, 73, 80] [7, 22, 27, 77, 83]\n",
      "[7, 15, 19, 22, 26, 27, 33, 46, 64, 73, 73, 77, 80, 83, 93]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "random.seed(1999)\n",
    "\n",
    "n1 = n2 = 5\n",
    "n3 = 2\n",
    "\n",
    "run1 = sorted([random.randint(1, 100) for _ in range(n1)])\n",
    "run2 = sorted([random.randint(1, 100) for _ in range(n2)])\n",
    "run3 = sorted([random.randint(1, 100) for _ in range(n3)])\n",
    "\n",
    "print(run1, run2, run3)\n",
    "\n",
    "runs = [run1, run2, run3]\n",
    "new_run = merge_runs(runs)\n",
    "print(new_run)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Implement the merge-way merge function `multiway_merge(data, k, pagesize)`, where `data` is an unordered list of integers, `k` is the maximum number of runs to merge simultaneously, and `pagesize` is the maximum number of integers in the initial runs. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def multiway_merge(data, k, pagesize):\n",
    "    p('{}-way merge, initial page size = {}'.format(k, pagesize))\n",
    "    ###\n",
    "    ### INSERT YOUR OWN CODE\n",
    "    ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you have implemented it correctly, if you run the code below, you should see the following output. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".. 3-way merge, initial page size = 2\n",
      ".. Initial runs = [[15, 46], [19, 93], [64, 73], [33, 80], [26, 73], [22, 77], [27, 83], [7, 52], [12, 51], [7, 80], [19, 95], [36]]\n",
      ".. New runs size = 4. Runs = [[15, 19, 46, 64, 73, 93], [22, 26, 33, 73, 77, 80], [7, 12, 27, 51, 52, 83], [7, 19, 36, 80, 95]]\n",
      ".. New runs size = 2. Runs = [[7, 12, 15, 19, 22, 26, 27, 33, 46, 51, 52, 64, 73, 73, 77, 80, 83, 93], [7, 19, 36, 80, 95]]\n",
      ".. New runs size = 1. Runs = [[7, 7, 12, 15, 19, 19, 22, 26, 27, 33, 36, 46, 51, 52, 64, 73, 73, 77, 80, 80, 83, 93, 95]]\n",
      "[7, 7, 12, 15, 19, 19, 22, 26, 27, 33, 36, 46, 51, 52, 64, 73, 73, 77, 80, 80, 83, 93, 95]\n",
      "\n",
      ".. 2-way merge, initial page size = 2\n",
      ".. Initial runs = [[15, 46], [19, 93], [64, 73], [33, 80], [26, 73], [22, 77], [27, 83], [7, 52], [12, 51], [7, 80], [19, 95], [36]]\n",
      ".. New runs size = 6. Runs = [[15, 19, 46, 93], [33, 64, 73, 80], [22, 26, 73, 77], [7, 27, 52, 83], [7, 12, 51, 80], [19, 36, 95]]\n",
      ".. New runs size = 3. Runs = [[15, 19, 33, 46, 64, 73, 80, 93], [7, 22, 26, 27, 52, 73, 77, 83], [7, 12, 19, 36, 51, 80, 95]]\n",
      ".. New runs size = 2. Runs = [[7, 15, 19, 22, 26, 27, 33, 46, 52, 64, 73, 73, 77, 80, 83, 93], [7, 12, 19, 36, 51, 80, 95]]\n",
      ".. New runs size = 1. Runs = [[7, 7, 12, 15, 19, 19, 22, 26, 27, 33, 36, 46, 51, 52, 64, 73, 73, 77, 80, 80, 83, 93, 95]]\n",
      "[7, 7, 12, 15, 19, 19, 22, 26, 27, 33, 36, 46, 51, 52, 64, 73, 73, 77, 80, 80, 83, 93, 95]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "random.seed(1999)\n",
    "n = 23\n",
    "data = [random.randint(1, 100) for _ in range(n)]\n",
    "\n",
    "sorted_data = multiway_merge(data, 3, 2)\n",
    "print(sorted_data)\n",
    "print()\n",
    "\n",
    "sorted_data = multiway_merge(data, 2, 2)\n",
    "print(sorted_data)"
   ]
  },
  {
   "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}