day 40 - counting ones.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import defaultdict\n",
    "from itertools import count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def stream_counter():\n",
    "    bucket = defaultdict(list)\n",
    "    timestamp = count(1)\n",
    "    estimate = None\n",
    "\n",
    "    while True:\n",
    "        code = yield estimate\n",
    "        estimate = None\n",
    "\n",
    "        # update buckets\n",
    "        if code is True:\n",
    "            bucket[1].append(next(timestamp))\n",
    "\n",
    "            i = 1\n",
    "            while len(bucket[i]) == 3:\n",
    "                bucket[2 * i].append(bucket[i][1])\n",
    "                del bucket[i][:2]\n",
    "                i *= 2\n",
    "\n",
    "        elif code is False:\n",
    "            next(timestamp)\n",
    "\n",
    "        # estimate count\n",
    "        elif isinstance(code, int):\n",
    "            counts = [i for i in bucket for t in bucket[i] if code < t] or [0]\n",
    "            estimate = sum(counts) - counts[-1] // 2\n",
    "        \n",
    "        # debug\n",
    "        elif code == 'debug':\n",
    "            for i in bucket:\n",
    "                print(i, bucket[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "last 10000 bits: 6932\n",
      "last 257501 bits: 140052\n",
      "last 505000 bits: 303892\n",
      "last 752500 bits: 434964\n",
      "last 1000000 bits: 434964\n"
     ]
    }
   ],
   "source": [
    "n = 10 ** 6\n",
    "ctr = stream_counter()\n",
    "next(ctr)\n",
    "for i in range(n):\n",
    "    ctr.send(np.random.rand() >= .5)\n",
    "\n",
    "for i in np.linspace(.99, 0, 5):\n",
    "    k = int(i * n)\n",
    "    print(f'last {n - k} bits: {ctr.send(k)}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 [999999, 1000000]\n",
      "2 [999998]\n",
      "4 [999989, 999995]\n",
      "8 [999984]\n",
      "16 [999944, 999970]\n",
      "32 [999910]\n",
      "64 [999850]\n",
      "128 [999732]\n",
      "256 [998922, 999481]\n",
      "512 [997478, 998417]\n",
      "1024 [996449]\n",
      "2048 [994456]\n",
      "4096 [990348]\n",
      "8192 [965868, 982223]\n",
      "16384 [949681]\n",
      "32768 [851510, 916898]\n",
      "65536 [655300, 785917]\n",
      "131072 [261942, 524040]\n"
     ]
    }
   ],
   "source": [
    "ctr.send('debug')"
   ]
  },
  {
   "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}