hw6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Q1.\n",
    "\n",
    "Add a __setitem__ to the python linked list implementation from the lecture (this past wednesday)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#your code here\n",
    "#added some tests for the new setitem function\n",
    "from doctest import run_docstring_examples as dtest\n",
    "import numbers\n",
    "import reprlib\n",
    "class LL:\n",
    "    \"\"\"\n",
    "    >>> A = LL()  \n",
    "    >>> A[0]\n",
    "    Traceback (most recent call last):\n",
    "        ...\n",
    "    IndexError: trying to index an empty LL\n",
    "    >>> A.insert_front(1)\n",
    "    >>> A[0]\n",
    "    1\n",
    "    >>> A.insert_back(2)\n",
    "    >>> A[1]\n",
    "    2\n",
    "    >>> A\n",
    "    LL([1,...])\n",
    "    >>> myll = LL.from_components([1,2])\n",
    "    >>> myll[1]\n",
    "    1\n",
    "    >>> len(myll)\n",
    "    2\n",
    "    >>> myll[2]\n",
    "    Traceback (most recent call last):\n",
    "        ...\n",
    "    IndexError: LL index out of range\n",
    "    >>> myll[0:1]\n",
    "    Traceback (most recent call last):\n",
    "        ...\n",
    "    TypeError: LL indices must be integers\n",
    "    >>> myll[0]=5\n",
    "    >>> myll[0]\n",
    "    5\n",
    "    >>> myll[0]=5\n",
    "    Traceback (most recent call last):\n",
    "        ...\n",
    "    IndexError: LL index out of range\n",
    "    >>> myll[0:1]=2\n",
    "    Traceback (most recent call last):\n",
    "        ...\n",
    "    TypeError: LL indices must be integers\n",
    "    \"\"\"\n",
    "    @classmethod\n",
    "    def from_components(cls, components):\n",
    "        inst = cls(components[0])\n",
    "        for c in components[1:]:\n",
    "            inst.insert_front(c)\n",
    "        return inst\n",
    "        \n",
    "    def __init__(self, head=None):\n",
    "        if head is None:\n",
    "            self._headNode = None\n",
    "        else:\n",
    "            self._headNode = [head, None]\n",
    "            \n",
    "    def insert_front(self, element):\n",
    "        new_node = [element, None]\n",
    "        new_node[1] = self._headNode\n",
    "        self._headNode = new_node\n",
    "        \n",
    "    def insert_back(self, element):\n",
    "        new_node = [element, None]\n",
    "        curr_ptr = self._headNode\n",
    "        while curr_ptr[1] is not None:\n",
    "            curr_ptr = curr_ptr[1]\n",
    "        curr_ptr[1]= new_node\n",
    "        \n",
    "    def __repr__(self):\n",
    "        class_name = type(self).__name__\n",
    "        if len(self)==0:\n",
    "            components=\"\"\n",
    "        else:\n",
    "            components = reprlib.repr(self[0])\n",
    "        return '{}([{},...])'.format(class_name,components)\n",
    "\n",
    "\n",
    "    def __len__(self):\n",
    "        curr_ptr = self._headNode\n",
    "        count = 0\n",
    "        if curr_ptr==None:\n",
    "            return 0\n",
    "        while 1:\n",
    "            count = count + 1\n",
    "            if curr_ptr[1] is None:\n",
    "                break\n",
    "            curr_ptr = curr_ptr[1]\n",
    "        return count    \n",
    "    \n",
    "    def __getitem__(self, index):\n",
    "        class_name = type(self).__name__\n",
    "        if isinstance(index, numbers.Integral): \n",
    "            curr_ptr = self._headNode\n",
    "            if curr_ptr==None:\n",
    "                msg = 'trying to index an empty {class_name}' \n",
    "                raise IndexError(msg.format(class_name=class_name))\n",
    "            next_ptr = self._headNode[1]\n",
    "            count = 0\n",
    "            while 1:\n",
    "                if index == count:\n",
    "                    return curr_ptr[0]\n",
    "                if curr_ptr[1] is None:\n",
    "                    msg = '{class_name} index out of range' \n",
    "                    raise IndexError(msg.format(class_name=class_name))       \n",
    "                count += 1\n",
    "                curr_ptr = curr_ptr[1]\n",
    "        else:\n",
    "            msg = '{class_name} indices must be integers' \n",
    "            raise TypeError(msg.format(class_name=class_name))\n",
    "    \n",
    "    #add my setter function here\n",
    "    def __setitem__(self, index, value):\n",
    "        class_name = type(self).__name__\n",
    "        if isinstance(index, numbers.Integral): \n",
    "            curr_ptr = self._headNode\n",
    "            if curr_ptr==None:\n",
    "                msg = 'trying to index an empty {class_name}' \n",
    "                raise IndexError(msg.format(class_name=class_name))\n",
    "            next_ptr = self._headNode[1]\n",
    "            count = 0\n",
    "            while 1:\n",
    "                if index == count:\n",
    "                    curr_ptr[0] = value\n",
    "                    return\n",
    "                if curr_ptr[1] is None:\n",
    "                    msg = '{class_name} index out of range' \n",
    "                    raise IndexError(msg.format(class_name=class_name))       \n",
    "                count += 1\n",
    "                curr_ptr = curr_ptr[1]\n",
    "        else:\n",
    "            msg = '{class_name} indices must be integers' \n",
    "            raise TypeError(msg.format(class_name=class_name))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the orginal new_ll[1] =  4\n",
      "the new new_ll[1] =  10\n"
     ]
    }
   ],
   "source": [
    "#test by hand\n",
    "new_ll = LL.from_components([1,2,3,4,5])\n",
    "new_ll\n",
    "print (\"the orginal new_ll[1] = \",new_ll[1])\n",
    "new_ll[1] = 10\n",
    "print (\"the new new_ll[1] = \",new_ll[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finding tests in NoName\n",
      "Trying:\n",
      "    A = LL()  \n",
      "Expecting nothing\n",
      "ok\n",
      "Trying:\n",
      "    A[0]\n",
      "Expecting:\n",
      "    Traceback (most recent call last):\n",
      "        ...\n",
      "    IndexError: trying to index an empty LL\n",
      "ok\n",
      "Trying:\n",
      "    A.insert_front(1)\n",
      "Expecting nothing\n",
      "ok\n",
      "Trying:\n",
      "    A[0]\n",
      "Expecting:\n",
      "    1\n",
      "ok\n",
      "Trying:\n",
      "    A.insert_back(2)\n",
      "Expecting nothing\n",
      "ok\n",
      "Trying:\n",
      "    A[1]\n",
      "Expecting:\n",
      "    2\n",
      "ok\n",
      "Trying:\n",
      "    A\n",
      "Expecting:\n",
      "    LL([1,...])\n",
      "ok\n",
      "Trying:\n",
      "    myll = LL.from_components([1,2])\n",
      "Expecting nothing\n",
      "ok\n",
      "Trying:\n",
      "    myll[1]\n",
      "Expecting:\n",
      "    1\n",
      "ok\n",
      "Trying:\n",
      "    len(myll)\n",
      "Expecting:\n",
      "    2\n",
      "ok\n",
      "Trying:\n",
      "    myll[2]\n",
      "Expecting:\n",
      "    Traceback (most recent call last):\n",
      "        ...\n",
      "    IndexError: LL index out of range\n",
      "ok\n",
      "Trying:\n",
      "    myll[0:1]\n",
      "Expecting:\n",
      "    Traceback (most recent call last):\n",
      "        ...\n",
      "    TypeError: LL indices must be integers\n",
      "ok\n",
      "Trying:\n",
      "    myll[0]=5\n",
      "Expecting nothing\n",
      "ok\n",
      "Trying:\n",
      "    myll[0]\n",
      "Expecting:\n",
      "    5\n",
      "ok\n",
      "Trying:\n",
      "    myll[0]=5\n",
      "Expecting:\n",
      "    Traceback (most recent call last):\n",
      "        ...\n",
      "    IndexError: LL index out of range\n",
      "**********************************************************************\n",
      "File \"__main__\", line ?, in NoName\n",
      "Failed example:\n",
      "    myll[0]=5\n",
      "Expected:\n",
      "    Traceback (most recent call last):\n",
      "        ...\n",
      "    IndexError: LL index out of range\n",
      "Got nothing\n",
      "Trying:\n",
      "    myll[0:1]=2\n",
      "Expecting:\n",
      "    Traceback (most recent call last):\n",
      "        ...\n",
      "    TypeError: LL indices must be integers\n",
      "ok\n"
     ]
    }
   ],
   "source": [
    "#test function\n",
    "from doctest import run_docstring_examples as dtest\n",
    "dtest(LL, globals(), verbose = True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q2.\n",
    "\n",
    "An online mean and standard deviation algorithm.\n",
    "\n",
    "Below is a function to generate a potentially infinite stream of 1-D data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "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() )\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an implementation of an online mean algorithm..see http://www.johndcook.com/blog/standard_deviation/ and the link to http://www.johndcook.com/blog/2008/09/26/comparing-three-methods-of-computing-standard-deviation/ in-between. (Convince yourselves of the formulas...)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def online_mean(iterator):\n",
    "    n = 0\n",
    "    mu = 0\n",
    "    for value in iterator:\n",
    "        n += 1\n",
    "        delta = value - mu\n",
    "        mu = mu + delta/n\n",
    "        yield mu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use out generator functions to implement iterators:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1000000004.5834945,\n",
       " 1000000000.2397718,\n",
       " 1000000005.9309393,\n",
       " 1000000000.1992723,\n",
       " 999999999.9159048,\n",
       " 1000000005.5472574,\n",
       " 999999999.985557,\n",
       " 1000000003.802062,\n",
       " 999999997.451966,\n",
       " 1000000000.2294283,\n",
       " 1000000000.3789095]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = make_data(5, 10)\n",
    "list(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'generator'>\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1000000000.6552489,\n",
       " 1000000000.7975172,\n",
       " 999999999.9984211,\n",
       " 999999998.4701021,\n",
       " 999999997.4741294,\n",
       " 999999997.9535875,\n",
       " 999999998.2976263,\n",
       " 999999998.550967,\n",
       " 999999998.6738406,\n",
       " 999999998.1696899,\n",
       " 999999998.5598752,\n",
       " 999999998.6825113,\n",
       " 999999999.213579,\n",
       " 999999999.2315682,\n",
       " 999999999.2725004,\n",
       " 999999999.3656243,\n",
       " 999999999.4017954,\n",
       " 999999999.2455289,\n",
       " 999999999.2749722,\n",
       " 999999999.350103,\n",
       " 999999999.3634704,\n",
       " 999999999.5954804,\n",
       " 999999999.6121589,\n",
       " 999999999.4601843,\n",
       " 999999999.5052751,\n",
       " 999999999.5378042,\n",
       " 999999999.575523,\n",
       " 999999999.5939517,\n",
       " 999999999.679495,\n",
       " 999999999.6657784,\n",
       " 999999999.6850799,\n",
       " 999999999.7621598,\n",
       " 999999999.882578,\n",
       " 999999999.9320632,\n",
       " 999999999.9652117,\n",
       " 999999999.80753,\n",
       " 999999999.8142406,\n",
       " 999999999.8237469,\n",
       " 999999999.8432302,\n",
       " 999999999.8190268,\n",
       " 999999999.8502184,\n",
       " 999999999.9239597,\n",
       " 999999999.9055282,\n",
       " 999999999.907876,\n",
       " 999999999.8196111,\n",
       " 999999999.8733263,\n",
       " 999999999.9901202,\n",
       " 1000000000.0434613,\n",
       " 1000000000.0278983,\n",
       " 1000000000.0217879,\n",
       " 999999999.9935004,\n",
       " 999999999.9881417,\n",
       " 999999999.9741586,\n",
       " 1000000000.0266232,\n",
       " 1000000000.1690372,\n",
       " 1000000000.1525851,\n",
       " 1000000000.1461779,\n",
       " 1000000000.1859072,\n",
       " 1000000000.185916,\n",
       " 1000000000.3437755,\n",
       " 1000000000.3588399,\n",
       " 1000000000.3116151,\n",
       " 1000000000.2847981,\n",
       " 1000000000.2680365,\n",
       " 1000000000.285676,\n",
       " 1000000000.2548922,\n",
       " 1000000000.3015717,\n",
       " 1000000000.2009127,\n",
       " 1000000000.2083628,\n",
       " 1000000000.127464,\n",
       " 1000000000.134292,\n",
       " 1000000000.0841277,\n",
       " 1000000000.1211677,\n",
       " 1000000000.0721252,\n",
       " 1000000000.0629153,\n",
       " 1000000000.0641024,\n",
       " 1000000000.0932268,\n",
       " 1000000000.0660304,\n",
       " 1000000000.0671209,\n",
       " 1000000000.0637378,\n",
       " 1000000000.0671996,\n",
       " 1000000000.0888588,\n",
       " 1000000000.1131799,\n",
       " 1000000000.1135052,\n",
       " 1000000000.1087035,\n",
       " 1000000000.0952035,\n",
       " 1000000000.083589,\n",
       " 1000000000.1661909,\n",
       " 1000000000.1721071,\n",
       " 1000000000.1838138,\n",
       " 1000000000.1781454,\n",
       " 1000000000.1432043,\n",
       " 1000000000.1460278,\n",
       " 1000000000.1698269,\n",
       " 1000000000.1885762,\n",
       " 1000000000.1654413,\n",
       " 1000000000.1254014,\n",
       " 1000000000.1282986,\n",
       " 1000000000.1286924,\n",
       " 1000000000.1288321,\n",
       " 1000000000.1321918]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = online_mean(make_data(5, 100))\n",
    "print(type(g))\n",
    "list(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1\n",
    "\n",
    "Implement the standard deviation algorithm as a generator function as\n",
    "\n",
    "```python\n",
    "def online_mean_dev(iterator):\n",
    "    BLA BLA\n",
    "    if n > 1:\n",
    "        stddev = math.sqrt(dev_accum/(n-1))\n",
    "        yield (n, value, mu, stddev)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# your code here\n",
    "import math\n",
    "def online_mean_dev(iterator):\n",
    "    n = 0\n",
    "    mu = 0\n",
    "    stddev = 0 \n",
    "    dev_accum = 0\n",
    "    for value in iterator:\n",
    "        n += 1\n",
    "        delta = value - mu\n",
    "        mu = mu + delta/n\n",
    "        dev_accum = dev_accum + delta * (value - mu)     \n",
    "        #stddev = 0 when n = 1\n",
    "        if n == 1:\n",
    "            yield (n, value, mu, stddev) \n",
    "        #calculate stddev when n > 1\n",
    "        if n > 1:\n",
    "            stddev = math.sqrt(dev_accum/(n-1))\n",
    "            yield (n, value, mu, stddev)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we make 100000 element data, and run this iterator on it (imagine running this on a time-series being slowly read from disk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data_with_stats = online_mean_dev(make_data(5, 100000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q3.\n",
    "\n",
    "Let's do Anomaly detection. Write a routine `is_ok`:\n",
    "\n",
    "```python\n",
    "def is_ok(level, t)\n",
    "```\n",
    "\n",
    "which takes a tuple like the one yielded by your code above and returns True if the value is inbetween `level`-$\\sigma$ of the mean."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#your code here\n",
    "def is_ok(level, t):\n",
    "    #t[1] is value, t[2] is mu and t[3] is stddev \n",
    "    if t[1] <= t[2] + level * t[3] and t[1] >= t[2] - level * t[3]:\n",
    "        return True;\n",
    "    else:\n",
    "        return False;\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use this function to create a predicate passed through to `itertools.filterfalse` which is then used to obtain an iterator on the anomalies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools import filterfalse\n",
    "pred = lambda t: is_ok(5, t)\n",
    "anomalies = filterfalse(pred, data_with_stats)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We materialize the anomalies..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2134, 1000000015.5823402, 1000000000.033787, 2.8650804747793),\n",
       " (6497, 1000000014.7996919, 1000000000.0125442, 2.85873441118026),\n",
       " (8839, 1000000014.420672, 1000000000.0147656, 2.8554296225210023),\n",
       " (11266, 999999985.0794199, 1000000000.016058, 2.8734404855595255),\n",
       " (16232, 999999985.0126258, 1000000000.0160203, 2.8666733650933462),\n",
       " (18568, 1000000014.9727159, 1000000000.0123947, 2.8661785747567894),\n",
       " (19882, 999999985.3206801, 1000000000.0049789, 2.8641038757899486),\n",
       " (22229, 999999984.8285364, 1000000000.0068933, 2.8629432801419417),\n",
       " (22924, 1000000015.917237, 1000000000.013269, 2.868009564452385),\n",
       " (29638, 999999985.2836536, 1000000000.01163, 2.86313507170784),\n",
       " (35870, 1000000015.0126604, 1000000000.0033212, 2.8584727816776168),\n",
       " (43793, 1000000014.4205505, 1000000000.008517, 2.859976925545974),\n",
       " (45498, 999999984.2911081, 1000000000.009721, 2.862815475192187),\n",
       " (55838, 1000000014.6404401, 1000000000.0183852, 2.8618612557346257),\n",
       " (59272, 999999983.5433967, 1000000000.017508, 2.8680593603423787),\n",
       " (60624, 1000000016.6849812, 1000000000.0194883, 2.868793789690009),\n",
       " (62674, 999999984.6802146, 1000000000.0169858, 2.8698823735113956),\n",
       " (64938, 999999984.7452075, 1000000000.013506, 2.872024738014853),\n",
       " (65040, 1000000016.8847642, 1000000000.0140678, 2.873000266388038),\n",
       " (65945, 1000000014.6018486, 1000000000.0131685, 2.8736282736567826),\n",
       " (68942, 1000000017.2936774, 1000000000.0109804, 2.872218480831874),\n",
       " (74447, 999999982.9247656, 1000000000.0068197, 2.8686058230129037),\n",
       " (77554, 1000000014.8986005, 1000000000.0043845, 2.8686160944800485),\n",
       " (79864, 999999984.4308913, 1000000000.0036198, 2.8711803363638846),\n",
       " (85106, 999999983.2079996, 1000000000.0026027, 2.865675713789703),\n",
       " (91654, 1000000014.8045871, 1000000000.0015339, 2.8617550904741673),\n",
       " (91881, 1000000014.518154, 1000000000.0029179, 2.862000512446749),\n",
       " (94487, 999999984.336944, 1000000000.0046356, 2.860744649258068),\n",
       " (99807, 999999982.610074, 1000000000.005632, 2.8659556803438506)]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(anomalies)#materialize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## To think of, but not hand in\n",
    "\n",
    "What kinds of anomalies will this algorithm pick up? What kinds would a shorter \"window\" of anomaly detection, like 100 points around the time in question pick? How might you create an algorithm which does window based averaging? (hint: the window size is small compared to the time series size). \n",
    "\n",
    "Finally think a bit of how you might implement all of this in a production environment..remember that data streaming in might get backed up when you handle an anomaly.\n",
    "\n",
    "(Some inspiration might accrue if you look at the docs for `collections.deque`)."
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "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
}