homeworks/hw7.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q1. Median Maintenance using a Heap\n",
    "\n",
    "\n",
    "### Part 1\n",
    "\n",
    "Implement a \"dominant heap\" class `BinaryHeap`, which can handle both the min heap and the max heap cases, by having the constructor explicitly pass the \"comparison\" operator in. Replace min and del_min by dominant and del_dominant methods. Change the classmethod to also take in the operator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#your code here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data = [1,8,5,9,23,2,45,6,7,99,-5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# from operator import gt, lt\n",
    "# bh = BinaryHeap.heapify_slow(data, lt)\n",
    "# print(bh.storage)\n",
    "# bh.dominant()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# bh = BinaryHeap.heapify_slow(data, gt)\n",
    "# print(bh.storage)\n",
    "# bh.dominant()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2\n",
    "\n",
    "Median maintenance is a very cool algorithm to find an online median.\n",
    "We create two arrays to test our implementation, using np.median to test our answer..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "150 499.5\n",
      "151 499.0\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "l = [random.randint(1,1000) for _ in range(150)]\n",
    "print(len(l), np.median(l))\n",
    "l2 = l + [random.randint(1,1000)]\n",
    "print(len(l2), np.median(l2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You will implement def online_median(iterator) which is a generator yielding successive values of your online median.\n",
    "\n",
    "The algorithm is as follows:\n",
    "\n",
    "We'll use 2 heaps, a max heap for the lower half of the data, and a min-heap for the upper half. We take the first 2values in our data and assign the smaller value to the max heap, while the larger value goes to the min-heap. Then, as we \"insert\" subsequent values in one of the two heaps, the following holds: if we keep the number of elements in both heaps equal (for the even case) or at-most differing by one, the median is respectively the average of the two dominants or the dominant in the heap with one extra item.\n",
    "\n",
    "What then is our strategy for this balanced insertion? Quite simple really: if a new value is not as dominant as the dominant value, add it to that heap. If it is more dominant, add it to the other. If two items in a row get added to the same heap, the heaps will be out of balance by more than one. In this case, take the dominant element from the larger heap and simply add it to the smaller one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Do your answers match?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "medians = list(online_median(iter(l)))\n",
    "print(medians[-1])\n",
    "plt.plot(medians)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "list(online_median(iter(l2)))[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lastly, lets repeat the analysis we did last time on the randomly generated data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from random import normalvariate, random\n",
    "from itertools import count\n",
    "def make_data(m, stop=None):\n",
    "    for _ in count():\n",
    "        if stop and _ > stop:\n",
    "            break\n",
    "        yield 1.0e09 + normalvariate(0, m*random() )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = online_median(make_data(5, 100))\n",
    "print(type(g))\n",
    "out = list(g)\n",
    "out[-10:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "plt.plot(out)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q2\n",
    "\n",
    "### Simulating a flight check-in counter\n",
    "\n",
    "It is your job to simulate a flight-checkin counter. There are m agents handling n passengers. The passengers arrive in line with in-between time given by an exponential distribution for INTER_ARRIVAL_TIME. Each passenger, once he or she gets to a counter, is processed in a time drawn from an exponential distribution with PROCESSING_TIME. \n",
    "\n",
    "Clearly, in the usual case of 3-4 agents and 200+ customers on a flight, the customer waits much longer. We have been hired by the airlines customer-relations group to see how many extra agents must we hire to reduce waiting times by how much.\n",
    "\n",
    "We start by representing each customer by a co-routine, which starts with the `inline` event. The state changes to the `atcounter` event, and then `ptime` seconds later, to the `leaves` event. Notice how this customer \"process\" is stopped at the yield, until the customer can be handled."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import collections, random\n",
    "Event = collections.namedtuple('Event', 'time cid action agent')\n",
    "def customer_process(idee, start, ptime):\n",
    "    t, agent = yield Event(start, idee, \"inline\", None)\n",
    "    t, agent = yield Event(t, idee, \"atcounter\", agent)\n",
    "    yield Event(t+ptime, idee, \"leaves\", agent)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following function simply implements the draw from the exponential distribution for a given customer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def duration(arr_time, service_time):\n",
    "    return random.expovariate(1./arr_time), random.expovariate(1./service_time)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is out main simulation class. you will be filling in parts of this class.\n",
    "\n",
    "The constructor sets up the simulation. Three queues are created, one for agents that become free, one priority queue for events so that they can be processed in the order recieved, and a backlog for queue for those customers waiting in line because no agent was available.\n",
    "\n",
    "We set up all the customers in the constructor, with two dictionaries, one to hold the co-routines, and one to hold time metadata which we shall use to figure the average waiting time.\n",
    "\n",
    "The `run` method is where all the action happens and is the one you will edit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import queue\n",
    "import logging\n",
    "class Simulator:\n",
    "    \n",
    "    def __init__(self, n_agents, n_customers, INTER_ARRIVAL_TIME =1., PROCESSING_TIME=3., DEBUG=False ): \n",
    "        #queues\n",
    "        self.free_agents = queue.Queue()\n",
    "        self.backlog = queue.Queue()\n",
    "        self.events=queue.PriorityQueue()\n",
    "        #save the arguments\n",
    "        self.n_customers = n_customers\n",
    "        self.n_agents = n_agents\n",
    "        self.intertime=INTER_ARRIVAL_TIME\n",
    "        self.proctime=PROCESSING_TIME\n",
    "        #dictionaries to hold customer process\n",
    "        self.customers={}\n",
    "        self.customer_meta={}\n",
    "        self.logger = logging.getLogger(\"sim\")\n",
    "        if DEBUG:\n",
    "            self.logger.setLevel(logging.DEBUG)\n",
    "        else:\n",
    "            self.logger.setLevel(logging.WARNING)\n",
    "        #on the free_agents queue, we put all the agents, and thee time\n",
    "        #they got free\n",
    "        for i in range(n_agents):\n",
    "            self.free_agents.put((i,0))\n",
    "        #this tracks when each customer came in.          \n",
    "        time_when_came=0.\n",
    "        for j in range(n_customers):\n",
    "            interarrtime, proctime = duration(self.intertime, self.proctime)\n",
    "            time_when_came += interarrtime\n",
    "            intuple = (j, time_when_came, proctime)\n",
    "            c = customer_process(*intuple)\n",
    "            self.logger.debug(\"Customer {}, arrived {}, will take {} at counter\".format(*intuple))\n",
    "            #add each customer to dictionaries\n",
    "            self.customers[j]=c\n",
    "            self.customer_meta[j]={'cid':j, 'start':time_when_came, 'finish':None}\n",
    "        self.logger.debug(\"========ending init==============\\n\\n\")\n",
    "        self.max_time_when_came=time_when_came  \n",
    "\n",
    "    def run(self, end_time):\n",
    "        #we prime each customer co-routine at the start\n",
    "        #and put that event in the events priority queue\n",
    "        #Since an event is a tuple, the ordering will be by start time\n",
    "        for cid, proc in sorted(self.customers.items()):\n",
    "            first_event = next(proc)#prime\n",
    "            self.events.put(first_event)#customer in line\n",
    "\n",
    "        #start at time 0\n",
    "        sim_time = 0\n",
    "        while sim_time < end_time:\n",
    "            #we are done if no events and no backlog\n",
    "            if self.events.empty() and self.backlog.empty(): \n",
    "                self.logger.debug('*** end of events and backlog***') \n",
    "                break\n",
    "            #if we have agents available and a backlog\n",
    "            #take customer from backlog queue. This is equivalent\n",
    "            #to taking customers from line\n",
    "            if not self.backlog.empty() and not self.free_agents.empty():\n",
    "                \"YOUR CODE HERE\"\n",
    "                #the sim time from this branch will be false\n",
    "                #as we get the old time the person in the line showed up\n",
    "            else: #get current event in all other cases\n",
    "                #his ensures that leave events are processed thus\n",
    "                #freeing up agents\n",
    "                \"YOUR CODE HERE\"\n",
    "            \n",
    "            sim_time, cid, action, agent = current_event\n",
    "            #get the current customer process\n",
    "            cproc = self.customers[cid]\n",
    "                \n",
    "            if action=='leaves':\n",
    "                self.logger.debug(\">>>Customer {} leaves, agent {} free at {}\".format(cid, agent, sim_time))\n",
    "                #an agent gets free. Put the time they got free on q\n",
    "                #also update the metadata\n",
    "                self.free_agents.put((agent, sim_time))\n",
    "                self.customer_meta[cid]['finish']=sim_time\n",
    "            elif action=='atcounter':\n",
    "                self.logger.debug(\"Customer {} atcounter Agent {} at {}\".format(cid, agent, sim_time))\n",
    "                next_time = sim_time#processing time already in coroutine\n",
    "            elif action=='inline':#the agent is None to start\n",
    "                self.logger.debug('----------------------------------------------')\n",
    "                self.logger.debug(\"Customer {}, arrived in line @ {}.\".format(cid, sim_time))\n",
    "\n",
    "                if self.free_agents.empty():\n",
    "                    self.logger.debug(\"NO agents available, putting {} inline on backlog at {}\".format(cid, sim_time))\n",
    "                    \"YOUR CODE HERE\"\n",
    "                else:\n",
    "                    self.logger.debug(\"{} agents available to serve.\".format(self.free_agents.qsize()))\n",
    "                    \"YOUR CODE HERE\"#handle both situations\n",
    "                    #of getting from backlog or regular. The time in\n",
    "                    #next_time which you will send in message to co-routine\n",
    "                    #below are different\n",
    "                    self.logger.debug(\"Customer {} inline to be served by Agent {} at {}\".format(cid, agent, next_time))\n",
    "            #drive the co-routine by sending in time and agent, and getting\n",
    "            #next event out. The event is put into the priority queue.\n",
    "            try:\n",
    "                next_event = cproc.send((next_time, agent)) \n",
    "            except StopIteration:\n",
    "                del self.customers[cid] \n",
    "            else:\n",
    "                self.events.put(next_event)\n",
    "                \n",
    "    def compute_ptimes(self):\n",
    "        ptimes=[]\n",
    "        for j in range(self.n_customers):\n",
    "            #print(j,self.customer_meta[j] )\n",
    "            if self.customer_meta[j]['finish']!=None:\n",
    "                ptimes.append(self.customer_meta[j]['finish'] - self.customer_meta[j]['start'])\n",
    "        return ptimes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sim_main(num_agents, num_customers, extratime=20., seed=None, debug=False):\n",
    "    if seed is not None:\n",
    "        random.seed(seed)\n",
    "    sim = Simulator(num_agents, num_customers, DEBUG=debug)\n",
    "    sim.run(sim.max_time_when_came+extratime)\n",
    "    return sim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Start small to test this out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sim=sim_main(2,6, debug=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now lets try it with some larger numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "sim=sim_main(3,100)\n",
    "plt.hist(sim.compute_ptimes(), bins=20);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sim2=sim_main(4,100)\n",
    "plt.hist(sim2.compute_ptimes(), bins=20);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "extra time needed below as with 400 passengers a long time is taken to process."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sim2=sim_main(2,400, extratime=100)\n",
    "plt.hist(sim2.compute_ptimes(), bins=20);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a proper statistical analysis, you would want to draw this multiple times and look at the distribution of the averages as well. But you should know what this distribution is :-)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}