Span Secondary Sort Simulation.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ss/mockendpoint.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile ss/mockendpoint.py\n",
    "\n",
    "import math\n",
    "import re\n",
    "import pprint\n",
    "\n",
    "import numpy\n",
    "\n",
    "class MockEndpoint(object):\n",
    "    def __init__(self, r, desired_span_count, weight=0):\n",
    "        super(MockEndpoint, self).__init__()\n",
    "        \n",
    "        self.r = r\n",
    "        self.weight = weight\n",
    "        self.displayed_graph = None\n",
    "        self.dbratio = 0.7\n",
    "\n",
    "        self.desired_span_count = desired_span_count\n",
    "        self.desired_depth = self.sub_sample(self.desired_span_count)\n",
    "        self.desired_external_count = max(1,\n",
    "            self.sub_sample(self.desired_span_count) - 1)\n",
    "\n",
    "        self.base_graph = self.make_base_graph(\n",
    "            self.desired_span_count,\n",
    "            self.desired_depth)\n",
    "        \n",
    "        self.assign_externals(self.desired_external_count)\n",
    "        self.total_spans = (self.actual_external_count\n",
    "                            + self.sum_base_graph_nodes(\n",
    "                               self.base_graph, include_links=True))\n",
    "        \n",
    "        self.pp = None\n",
    "        \n",
    "    def __repr__(self):\n",
    "        self.pp = self.pp or pprint.PrettyPrinter(indent=4)\n",
    "\n",
    "        infostring = \"%s // %s %s // %s\" % (\n",
    "            self.weight,\n",
    "            self.desired_span_count, self.total_base_nodes,\n",
    "            self.desired_depth,\n",
    "        )\n",
    "\n",
    "        external_string = \"%s // %s (%s/%s)\" % (\n",
    "            self.desired_external_count, self.actual_external_count,\n",
    "            self.iinfo['ce'], self.iinfo['cd']\n",
    "        )\n",
    "\n",
    "        pps = self.pp.pformat(self.expanded_graph)\n",
    "        return \"%s\\n%s\\n%s\" % (infostring, external_string, pps)\n",
    "\n",
    "    def sub_sample(self, mean):\n",
    "        if mean < 3:\n",
    "            return 2\n",
    "        return int(max(2, self.r.normal(math.log(mean) + 1, 0.5)))\n",
    "\n",
    "    def allocate_spans(self, total_spans_remaining):\n",
    "        if total_spans_remaining < 2:\n",
    "            return [max(1, total_spans_remaining)]\n",
    "\n",
    "        num_chunks = self.sub_sample(total_spans_remaining)\n",
    "        allocation = numpy.abs(self.r.normal(0, 1, num_chunks))\n",
    "\n",
    "        return [int(x)\n",
    "            for x in numpy.rint(\n",
    "                total_spans_remaining * allocation / sum(allocation)\n",
    "            )]\n",
    "\n",
    "    def make_base_graph(self, total_spans, total_layers):\n",
    "        return self._make_base_graph(\n",
    "            total_spans - 1, total_layers, total_layers)\n",
    "\n",
    "    def _make_base_graph(self, total_spans_remaining, total_layers,\n",
    "                         layers_remaining):\n",
    "        if layers_remaining == 1:\n",
    "            return [total_spans_remaining]\n",
    "\n",
    "        allocation = self.allocate_spans(total_spans_remaining)\n",
    "        ma = float(max(allocation))\n",
    "\n",
    "        bonus = max(0, (\n",
    "            layers_remaining - (total_layers-1)/2) / float(total_layers))\n",
    "        deepening_probability = [bonus + x/ma for x in allocation]\n",
    "\n",
    "        graph = []\n",
    "        for i in range(0, len(allocation)):\n",
    "            is_deepened = self.r.uniform(0, 1) < deepening_probability[i]\n",
    "            \n",
    "            if (allocation[i] > 2) and is_deepened:\n",
    "                graph.append(\n",
    "                    self._make_base_graph(\n",
    "                        allocation[i] - 1,\n",
    "                        total_layers,\n",
    "                        layers_remaining - 1\n",
    "                    ))\n",
    "            else:\n",
    "                graph.append(allocation[i])\n",
    "\n",
    "        return graph\n",
    "\n",
    "    def sum_base_graph_nodes(self, graph, include_links=False):\n",
    "        total = 0\n",
    "\n",
    "        for node in graph:\n",
    "            if type(node) == list:\n",
    "                total += self.sum_base_graph_nodes(\n",
    "                    node, include_links=include_links)\n",
    "                if include_links:\n",
    "                    total += 1\n",
    "            else:\n",
    "                total += node\n",
    "\n",
    "        return total\n",
    "\n",
    "    def expand_graph_nodes(self, graph):\n",
    "        expanded_graph = []\n",
    "\n",
    "        for node in graph:\n",
    "            if type(node) == list:\n",
    "                expanded_graph.append(self.expand_graph_nodes(node))\n",
    "            else:\n",
    "                expanded_graph += ['node'] * node\n",
    "\n",
    "        return expanded_graph\n",
    "\n",
    "    def assign_externals(self, num_externals):\n",
    "        self.total_base_nodes = self.sum_base_graph_nodes(self.base_graph)\n",
    "        self.expanded_graph = self.expand_graph_nodes(self.base_graph)\n",
    "\n",
    "        self.actual_external_count = min(\n",
    "            int(self.total_base_nodes/2), 2*num_externals)\n",
    "        external_locs = self.r.uniform(0, 1, self.total_base_nodes)\n",
    "\n",
    "        aec = self.actual_external_count\n",
    "        external_locs = numpy.argpartition(external_locs, -aec)[-aec:]\n",
    "\n",
    "        self.iinfo = {x:0 for x in ['ci', 'cd', 'ce', 'cn']}\n",
    "        self._assign_externals(external_locs, self.expanded_graph)\n",
    "\n",
    "    def _assign_externals(self, external_locs, expanded_graph):\n",
    "        for i in range(0, len(expanded_graph)):\n",
    "            if expanded_graph[i] == 'node':\n",
    "                if self.iinfo['ci'] in external_locs:\n",
    "                    if self.r.uniform(0, 1) < self.dbratio:\n",
    "                        expanded_graph[i] = 'dbcall' + str(self.iinfo['cd'])\n",
    "                        self.iinfo['cd'] += 1\n",
    "\n",
    "                    else:\n",
    "                        expanded_graph[i] = 'external' + str(self.iinfo['ce'])\n",
    "                        self.iinfo['ce'] += 1\n",
    "\n",
    "                else:\n",
    "                    expanded_graph[i] = 'node' + str(self.iinfo['cn'])\n",
    "                    self.iinfo['cn'] += 1\n",
    "\n",
    "                self.iinfo['ci'] += 1\n",
    "\n",
    "            else:\n",
    "                self._assign_externals(external_locs, expanded_graph[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ss/mockexecution.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile ss/mockexecution.py\n",
    "\n",
    "class MockExecution(object):\n",
    "    def __init__(self, r, endpoint_index, completed, path_spans, priority):\n",
    "        self.r = r\n",
    "\n",
    "        self.endpoint_index = endpoint_index\n",
    "        self.priority = priority\n",
    "        self.completed = completed\n",
    "        self.path_spans = path_spans\n",
    "        self.partial = False\n",
    "\n",
    "        if self.completed is False:\n",
    "            self.path_spans = self.r.poisson(path_spans)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return \"%s %s %s %s %s\" % (\n",
    "            self.endpoint_index, self.priority,\n",
    "            self.path_spans, self.partial, self.completed)\n",
    "\n",
    "    def mark_partial(self, spans_not_fitting_in_reservoir):\n",
    "        self.partial = True\n",
    "        self.completed = False\n",
    "        self.path_spans -= spans_not_fitting_in_reservoir"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ss/mockreservoir.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile ss/mockreservoir.py\n",
    "\n",
    "class MockReservoir(object):\n",
    "    def __init__(self, reservoir_size, sampledTrue_count, raw_results):\n",
    "        self.reservoir_size = reservoir_size\n",
    "        self.sampledTrue_count = sampledTrue_count\n",
    "        self.raw_results = raw_results\n",
    "\n",
    "        sorted_executions = sorted(\n",
    "            raw_results,\n",
    "            key=lambda x: x.priority,\n",
    "            reverse=True)\n",
    "\n",
    "        self.reservoir = []\n",
    "        reservoir_space_remaining = self.reservoir_size\n",
    "        for execution_path in sorted_executions:\n",
    "            reservoir_space_remaining -= execution_path.path_spans\n",
    "            self.reservoir.append(execution_path)\n",
    "\n",
    "            if reservoir_space_remaining == 0:\n",
    "                break\n",
    "\n",
    "            elif reservoir_space_remaining < 0:\n",
    "                execution_path.mark_partial(-reservoir_space_remaining)\n",
    "                break\n",
    "\n",
    "    def __repr__(self):\n",
    "        total_spans_sent = sum([x.path_spans for x in self.reservoir])\n",
    "        header = \"**%s %s\\n  \" % (self.sampledTrue_count, total_spans_sent)\n",
    "        return header + \"\\n  \".join([str(x) for x in self.reservoir])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ss/mockagent.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile ss/mockagent.py\n",
    "\n",
    "import math\n",
    "import numpy\n",
    "import sys\n",
    "\n",
    "from ss.mockendpoint import MockEndpoint\n",
    "from ss.mockexecution import MockExecution\n",
    "from ss.mockreservoir import MockReservoir\n",
    "\n",
    "class MockAgent(object):\n",
    "    def __init__(self, r, sampler,\n",
    "                 reservoir_size=1000, bundle_span_counts=False): # seed=1234567\n",
    "        self.r = r\n",
    "\n",
    "        self.reservoir_size = reservoir_size\n",
    "        self.sampler = sampler\n",
    "        \n",
    "        self.completion_threshold = 1.00\n",
    "\n",
    "        self.num_endpoints = int(self.r.uniform(5, 11))\n",
    "        self.weights = self.r.uniform(0, 1, self.num_endpoints)\n",
    "        self.weights /= sum(self.weights)\n",
    "\n",
    "        # for scipy: lognorm(s=1.22, loc=0, scale=14)\n",
    "        if bundle_span_counts is False:\n",
    "            expected_span_count = int(max(8, self.r.lognormal(math.log(14), 1.22)))\n",
    "            span_sigma = math.sqrt(expected_span_count) * math.log(expected_span_count) / 2 \n",
    "            path_span_counts = self.r.normal(expected_span_count, span_sigma, self.num_endpoints)\n",
    "\n",
    "        else:\n",
    "            path_span_counts = self.r.lognormal(math.log(14), 1.22, self.num_endpoints)\n",
    "\n",
    "        self.path_span_counts = [max(8, int(x)) for x in numpy.rint(path_span_counts)]\n",
    "        self.span_count_estimate = numpy.mean(self.path_span_counts)\n",
    "        self.span_count_variation = numpy.std(self.path_span_counts, ddof=1)\n",
    "\n",
    "        self.endpoint_paths = [\n",
    "            MockEndpoint(self.r, self.path_span_counts[i], self.weights[i])\n",
    "                for i in range(self.num_endpoints)]\n",
    "\n",
    "        self.cum_weights = numpy.cumsum(self.weights)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return \"\\n\\n\".join([\n",
    "            str(x) for x in sorted(\n",
    "                self.endpoint_paths,\n",
    "                key=lambda x: x.weight,\n",
    "                reverse=True)])\n",
    "    \n",
    "    def montecarlo_simulate(self, fan_in, num_harvests):\n",
    "        percent_traced = []\n",
    "        choice_hist = numpy.zeros(self.num_endpoints)\n",
    "        target_trace_count = self.sampler.sampling_target * (fan_in + 1) * num_harvests\n",
    "        \n",
    "        total_trace_count = 0\n",
    "        total_sampled_count = 0\n",
    "        \n",
    "        datasets = []\n",
    "        while target_trace_count > 0:\n",
    "            result = self.simulate_harvest(fan_in)\n",
    "            target_trace_count -= result.sampledTrue_count\n",
    "            \n",
    "            complete_trace_count = 0\n",
    "\n",
    "            for execution in result.reservoir:\n",
    "                if execution.completed:\n",
    "                    choice_hist[execution.endpoint_index] += 1\n",
    "                    complete_trace_count += 1\n",
    "\n",
    "            datasets.append((complete_trace_count, result.sampledTrue_count))\n",
    "            total_trace_count += complete_trace_count\n",
    "            total_sampled_count += result.sampledTrue_count\n",
    "            \n",
    "        #print(\"  estimated length:%d, traced:%d, sampled: %d\" % (\n",
    "        #    self.span_count_estimate, total_trace_count, total_sampled_count), file=sys.stderr)\n",
    "        #for ds in datasets:\n",
    "        #    print(\"    traced:%d, sampled: %d\" % ds, file=sys.stderr)\n",
    "        \n",
    "        percent_traced = total_trace_count / total_sampled_count\n",
    "\n",
    "        s = sum(choice_hist)\n",
    "        if s > 0:\n",
    "            choice_hist /= s\n",
    "        error_hist = (choice_hist - self.weights) ** 2\n",
    "\n",
    "        header = \"  %d, %.3f/%.3f, %.3E\" % (\n",
    "            fan_in+1, percent_traced, 0.0, sum(error_hist))\n",
    "        \n",
    "        return header\n",
    "\n",
    "    def simulate_harvest(self, fan_in):\n",
    "        sampledTrue_count = self.sampler.generate_samples(fan_in)\n",
    "        \n",
    "        if sampledTrue_count == 0:\n",
    "            return MockReservoir(self.reservoir_size, 0, [])\n",
    "\n",
    "        endpoint_path_choices = self.r.uniform(0, 1, sampledTrue_count)\n",
    "        priorities = self.r.uniform(0, 1, sampledTrue_count)\n",
    "\n",
    "        executions = []\n",
    "        for i in range(0, sampledTrue_count):\n",
    "            choice = endpoint_path_choices[i]\n",
    "            priority = priorities[i]\n",
    "\n",
    "            chosen_index = sum(choice > self.cum_weights)\n",
    "            path = self.endpoint_paths[chosen_index]\n",
    "\n",
    "            e = MockExecution(\n",
    "                self.r, chosen_index, True,\n",
    "                path.total_spans, priority)\n",
    "\n",
    "            executions.append(e)\n",
    "\n",
    "        return MockReservoir(self.reservoir_size, sampledTrue_count, executions)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ss/simulate_degradation.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile ss/simulate_degradation.py\n",
    "\n",
    "import sys\n",
    "import numpy\n",
    "\n",
    "from ss.mockagent import MockAgent\n",
    "from ss.mocksampler import MockSampler\n",
    "\n",
    "num_runs = 1000\n",
    "num_agents = 1000\n",
    "\n",
    "#param_sets = [(100, 1), (100, 10), (1000, 10)]\n",
    "param_sets = [(1000, 10)]\n",
    "\n",
    "class UniformSampler(MockSampler):\n",
    "    def _generate_samples(self, fan_in):\n",
    "        return self.r.uniform(0, 2 * self.sampling_target, fan_in + 1)\n",
    "        \n",
    "class NormalSampler(MockSampler):\n",
    "    def _generate_samples(self, fan_in):\n",
    "        sigma = numpy.log(max(2, self.sampling_target))\n",
    "        return self.r.normal(self.sampling_target, sigma, fan_in + 1)\n",
    "        \n",
    "def simulate_for_reservoir(num_runs, num_agents, reservoir_size,\n",
    "                           sampling_target, sampler_class):\n",
    "    \n",
    "    r = numpy.random.RandomState(1234567)\n",
    "    seeds = [int(x) for x in r.uniform(1, 999999999, num_agents)]\n",
    "    sampler = sampler_class(r, sampling_target)\n",
    "    \n",
    "    out_filename = 'ss/degradation_results_%s_%d_%d.txt' % (\n",
    "        sampler.name, reservoir_size, sampler.sampling_target)\n",
    "    \n",
    "    with open(out_filename, 'w') as outfile:\n",
    "        #print(sampler.name, file=sys.stderr)\n",
    "        \n",
    "        for agent_id in range(num_agents):\n",
    "            ir = numpy.random.RandomState(seeds[agent_id])\n",
    "            \n",
    "            ms = MockAgent(\n",
    "                ir, sampler=sampler,\n",
    "                reservoir_size=reservoir_size)\n",
    "\n",
    "            outfile.write(\"for agent with %d endpoints with mean/std length %.3f/%.3f:\" % (\n",
    "                ms.num_endpoints, ms.span_count_estimate, ms.span_count_variation))\n",
    "            outfile.write(\"\\n\")\n",
    "\n",
    "            for fan_in in range(10):\n",
    "                result = ms.montecarlo_simulate(fan_in, num_runs)\n",
    "                outfile.write(result)\n",
    "                outfile.write(\"\\n\")\n",
    "\n",
    "            outfile.write(\"\\n\")\n",
    "            if (agent_id % 10) == 9:\n",
    "                print(\"For sampler %s, reservoir size %d, and target %d, done with run %d\" % (\n",
    "                    sampler.name, reservoir_size,\n",
    "                    sampler.sampling_target, agent_id), file=sys.stderr)\n",
    "                \n",
    "        print(\"\", file=sys.stderr)\n",
    "\n",
    "for sampler_class in [UniformSampler, NormalSampler]:\n",
    "    for params in param_sets:\n",
    "        simulate_for_reservoir(num_runs, num_agents, params[0], params[1], sampler_class)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "For sampler uniform, reservoir size 1000, and target 10, done with run 9\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 19\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 29\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 39\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 49\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 59\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 69\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 79\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 89\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 99\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 109\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 119\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 129\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 139\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 149\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 159\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 169\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 179\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 189\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 199\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 209\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 219\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 229\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 239\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 249\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 259\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 269\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 279\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 289\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 299\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 309\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 319\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 329\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 339\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 349\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 359\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 369\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 379\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 389\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 399\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 409\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 419\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 429\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 439\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 449\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 459\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 469\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 479\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 489\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 499\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 509\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 519\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 529\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 539\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 549\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 559\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 569\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 579\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 589\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 599\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 609\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 619\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 629\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 639\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 649\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 659\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 669\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 679\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 689\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 699\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 709\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 719\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 729\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 739\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 749\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 759\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 769\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 779\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 789\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 799\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 809\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 819\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 829\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 839\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 849\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 859\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 869\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 879\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 889\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 899\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 909\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 919\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 929\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 939\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 949\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 959\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 969\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 979\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 989\n",
      "For sampler uniform, reservoir size 1000, and target 10, done with run 999\n",
      "\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 9\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 19\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 29\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 39\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 49\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 59\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 69\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 79\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 89\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 99\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "For sampler normal, reservoir size 1000, and target 10, done with run 109\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 119\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 129\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 139\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 149\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 159\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 169\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 179\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 189\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 199\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 209\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 219\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 229\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 239\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 249\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 259\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 269\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 279\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 289\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 299\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 309\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 319\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 329\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 339\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 349\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 359\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 369\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 379\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 389\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 399\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 409\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 419\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 429\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 439\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 449\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 459\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 469\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 479\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 489\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 499\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 509\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 519\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 529\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 539\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 549\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 559\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 569\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 579\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 589\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 599\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 609\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 619\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 629\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 639\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 649\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 659\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 669\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 679\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 689\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 699\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 709\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 719\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 729\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 739\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 749\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 759\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 769\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 779\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 789\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 799\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 809\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 819\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 829\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 839\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 849\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 859\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 869\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 879\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 889\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 899\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 909\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 919\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 929\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 939\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 949\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 959\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 969\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 979\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 989\n",
      "For sampler normal, reservoir size 1000, and target 10, done with run 999\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%run ss/simulate_degradation.py\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ss/mocktrace.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile ss/mocktrace.py\n",
    "\n",
    "import pprint\n",
    "import functools\n",
    "import numpy\n",
    "\n",
    "from ss.mockspan import MockSpan\n",
    "\n",
    "import os\n",
    "os.environ[\"PATH\"] += os.pathsep + '/usr/local/Cellar/graphviz/2.40.1/bin/'\n",
    "\n",
    "from graphviz import Digraph\n",
    "from IPython.display import SVG\n",
    "\n",
    "class MockTrace(object):\n",
    "    important_types = ['root', 'external', 'dbcall', 'long_generics']\n",
    "    \n",
    "    def __init__(self, r, endpoint):\n",
    "        self.r = r\n",
    "        self.expanded_graph = endpoint.expanded_graph\n",
    "\n",
    "        self.spans_by_name = {\n",
    "            'root': MockSpan(0, 'root', None)\n",
    "        }\n",
    "\n",
    "        self.spans_by_type = {\n",
    "            'root': set(['root']),\n",
    "            'node': set(),\n",
    "            'call': set(),\n",
    "            'external': set(),\n",
    "            'dbcall': set(),\n",
    "            'long_generics': set(),\n",
    "            'relevant': set()\n",
    "        }\n",
    "\n",
    "        self.gvid = 1\n",
    "        self.fcount = 0\n",
    "        self._convert_expanded_graph(self.spans_by_name['root'], self.expanded_graph)\n",
    "        \n",
    "        self.spans_by_category = {\n",
    "            'unimportant': set(),\n",
    "            'relevant': set(),\n",
    "            'important': functools.reduce(\n",
    "                lambda x, y: x | y, [\n",
    "                self.spans_by_type[z] for z in MockTrace.important_types\n",
    "            ])\n",
    "        }\n",
    "\n",
    "        self.pp = None\n",
    "        self.displayed_graph = None\n",
    "        \n",
    "    def _convert_expanded_graph(self, current_parent, expanded_graph):\n",
    "        for i in range(0, len(expanded_graph)):\n",
    "            span = expanded_graph[i]\n",
    "            name = span\n",
    "            if type(span) != str:\n",
    "                name = 'call' + str(self.fcount)\n",
    "                self.fcount += 1\n",
    "\n",
    "            s = MockSpan(self.gvid, name, current_parent)\n",
    "            self.spans_by_name[name] = s\n",
    "            self.spans_by_type[s.node_type].add(name)\n",
    "            if s.long_generic:\n",
    "                self.spans_by_type['long_generics'].add(name)\n",
    "\n",
    "            self.gvid += 1\n",
    "\n",
    "            if type(span) != str:\n",
    "                self._convert_expanded_graph(self.spans_by_name[name], span)\n",
    "        \n",
    "    def count_spans(self):\n",
    "        return self.spans_by_name['root'].count_spans()\n",
    "    \n",
    "    def count_nonprunable_spans(self):\n",
    "        return self.spans_by_name['root'].count_nonprunable_spans()\n",
    "\n",
    "    def mark_prunable_spans(self):\n",
    "        self.spans_by_name['root'].mark_prunable_spans()\n",
    "        self.spans_by_name['root'].mark_color = 'Green'\n",
    "        \n",
    "    #############################################################\n",
    "    #   \n",
    "    # first, assign 1s:\n",
    "    #   dbs and externals get a 1\n",
    "    #   \"long segments\" get a 1\n",
    "    #   root gets a 1\n",
    "    # \n",
    "    # next, assign 0s:\n",
    "    #   non-long, non-db/ext leaves get 0\n",
    "    #\n",
    "    # next, count total spans, and then subtract off all the 1s so far\n",
    "    # then count spans without a number so far\n",
    "    # remaining spans will get an avg score of (remainders)/(total - 1s)\n",
    "    # split that avg into 3 parts:\n",
    "    #    a. 1/3 gifted directly\n",
    "    #    b. 2/3 distributed based on which spans have the most '1s' children\n",
    "    #\n",
    "\n",
    "    def calculate_importance(self):\n",
    "        self.mark_prunable_spans()\n",
    "\n",
    "        total = self.spans_by_name['root'].count_spans()\n",
    "        total_1s = len(self.spans_by_category['important'])\n",
    "\n",
    "        total_0s = 0\n",
    "        for span in self.spans_by_name.values():\n",
    "            if span.is_unimportant:\n",
    "                self.spans_by_category['unimportant'].add(span.name)\n",
    "                total_0s += 1\n",
    "\n",
    "        total_unassigned = total - total_1s - total_0s\n",
    "        total_to_assign = float(total_unassigned / 2)\n",
    "        total_to_distribute = (2.0/3.0) * total_to_assign\n",
    "        \n",
    "        if total_unassigned == 0:\n",
    "            return\n",
    "        \n",
    "        baseline = (1.0/3.0) * total_to_assign / total_unassigned\n",
    "\n",
    "        cic = 0 # cumulative_important_children\n",
    "        weight_index = {}\n",
    "        for name in self.spans_by_name:\n",
    "            span = self.spans_by_name[name]\n",
    "            if span.is_unimportant or span.is_important:\n",
    "                continue\n",
    "\n",
    "            ic = span.count_important_children()\n",
    "            cic += ic\n",
    "            weight_index[name] = ic\n",
    "\n",
    "        sorted_order = sorted(\n",
    "            weight_index.keys(),\n",
    "            key=lambda x: weight_index[x],\n",
    "            reverse=True)\n",
    "\n",
    "        for name in sorted_order:\n",
    "            self.spans_by_category['relevant'].add(name)\n",
    "            span = self.spans_by_name[name]\n",
    "\n",
    "            if cic > 0:\n",
    "                fraction_share = weight_index[name] / cic\n",
    "                weight_share = min(1 - baseline, fraction_share * total_to_distribute)\n",
    "\n",
    "                cic -= weight_index[name]\n",
    "                total_to_distribute -= weight_share\n",
    "                span.importance_score = weight_share + baseline\n",
    "\n",
    "    def display_graph(self, display_raw=False, show_importance=False):\n",
    "        if display_raw:\n",
    "            print(\"RAW FORM:\\n\")\n",
    "            self.pp = self.pp or pprint.PrettyPrinter(indent=4)\n",
    "            self.pp.pprint(self.expanded_graph)\n",
    "        \n",
    "        self.displayed_graph = Digraph()\n",
    "        self.displayed_graph.attr(rankdir='LR', scale='0.5')\n",
    "\n",
    "        self.spans_by_name['root'].display_span(self.displayed_graph, show_importance)\n",
    "        display(SVG(self.displayed_graph.pipe(format='svg')))\n",
    "        \n",
    "    #############################################################\n",
    "    \n",
    "    def reset_seen_counts(self):\n",
    "        for name in self.spans_by_name:\n",
    "            self.spans_by_name[name].reset_seen_count()\n",
    "    \n",
    "    def simulate_secondary_sort(self, harvests, fraction_captured, random_factor):\n",
    "        self.reset_seen_counts()\n",
    "        \n",
    "        finish_times = {}\n",
    "        traces = {\n",
    "            'full': set(self.spans_by_name.keys()),\n",
    "            'basic': set(self.spans_by_category['important'])\n",
    "        }\n",
    "        traces['relevant'] = traces['basic'] | set(self.spans_by_category['relevant'])\n",
    "        \n",
    "        for i in range(0, harvests):\n",
    "            if len(finish_times) == 3:\n",
    "                return finish_times\n",
    "\n",
    "            seen = self.simulate_harvest_clipping(fraction_captured, random_factor)\n",
    "\n",
    "            for trace in traces:\n",
    "                if trace in finish_times:\n",
    "                    continue\n",
    "\n",
    "                traces[trace] -= seen\n",
    "                if len(traces[trace]) == 0:\n",
    "                    finish_times[trace] = i\n",
    "\n",
    "        for trace in traces:\n",
    "            if trace not in finish_times:\n",
    "                finish_times[trace] = harvests + 1\n",
    "\n",
    "        return finish_times\n",
    "\n",
    "    def simulate_harvest_clipping(self, fraction_captured, random_factor):\n",
    "        sorted_spans = self.sort_spans_for_clipping(random_factor)\n",
    "        num_captured = int(numpy.rint(fraction_captured * self.count_spans()))\n",
    "\n",
    "        spans_captured = sorted_spans[0:num_captured]\n",
    "        for name in spans_captured:\n",
    "            self.spans_by_name[name].mark_seen()\n",
    "\n",
    "        return set(spans_captured)\n",
    "\n",
    "    def sort_spans_for_clipping(self, random_factor):\n",
    "        ordered_spans = [\n",
    "            (name, 1 + random_factor * self.r.uniform(0, 1))\n",
    "                for name in self.spans_by_category['important']]\n",
    "\n",
    "        for category in ['relevant', 'unimportant']:\n",
    "            for name in self.spans_by_category[category]:\n",
    "                span = self.spans_by_name[name]\n",
    "                score = span.importance_score + random_factor * self.r.uniform(0, 1)\n",
    "                ordered_spans.append((name, score))\n",
    "\n",
    "        sorted_spans = sorted(ordered_spans, key=lambda x: x[1], reverse=True)\n",
    "        return [y[0] for y in sorted_spans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ss/mockspan.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile ss/mockspan.py\n",
    "\n",
    "import re\n",
    "\n",
    "class MockSpan(object):\n",
    "    def __init__(self, gvid, name, parent):\n",
    "        self.gvid = str(gvid)\n",
    "        self.name = name\n",
    "        self.node_type = re.sub(r'\\d', '' , name)\n",
    "        self.parent = parent\n",
    "\n",
    "        self.children = []\n",
    "        self.mark_color = None\n",
    "        self.times_seen = 0\n",
    "        self.long_generic = False\n",
    "\n",
    "        self.importance_score = 0\n",
    "        if (self.node_type in ['root', 'dbcall', 'external']) or (self.long_generic):\n",
    "            self.importance_score = 1\n",
    "        \n",
    "        if parent is not None:\n",
    "            self.parent.add_child(self)\n",
    "\n",
    "    @property\n",
    "    def is_important(self):\n",
    "        return self.importance_score == 1\n",
    "\n",
    "    @property\n",
    "    def is_unimportant(self):\n",
    "        if ((self.mark_color == 'Red')\n",
    "            or ((self.node_type == 'node')\n",
    "                and (len(self.children) == 0)\n",
    "                and (self.long_generic is False))):\n",
    "\n",
    "            self.importance_score = 0\n",
    "            return True\n",
    "\n",
    "        return False\n",
    "\n",
    "    def reset_seen_count(self):\n",
    "        self.times_seen = 0\n",
    "        \n",
    "    def add_child(self, child):\n",
    "        self.children.append(child)\n",
    "        \n",
    "    def count_spans(self):\n",
    "        return 1 + sum([c.count_spans() for c in self.children])\n",
    "        \n",
    "    def count_important_children(self):\n",
    "        initial = int(self.importance_score == 1)\n",
    "        return initial + sum([c.count_important_children() for c in self.children])\n",
    "\n",
    "    def count_nonprunable_spans(self):\n",
    "        initial = int(self.mark_color == 'Green')\n",
    "        return initial + sum([c.count_nonprunable_spans() for c in self.children])\n",
    "        \n",
    "    def mark_prunable_spans(self):\n",
    "        if self.mark_color is not None:\n",
    "            return self.mark_color\n",
    "\n",
    "        if len(self.children) == 0:\n",
    "            self.mark_color = 'Green'\n",
    "            return\n",
    "    \n",
    "        all_green = True\n",
    "        for child in self.children:\n",
    "            child.mark_prunable_spans()\n",
    "            if child.mark_color != 'Green':\n",
    "                all_green = False\n",
    "\n",
    "        self.mark_color = 'Red' if all_green is True else 'Green'\n",
    "\n",
    "    def mark_seen(self):\n",
    "        self.times_seen += 1\n",
    "        \n",
    "    #############################################################\n",
    "\n",
    "    span_colors = {\n",
    "        'root': '#FF00FF',\n",
    "        'external': '#FF0000',\n",
    "        'dbcall': '#00FF00',\n",
    "        'call': '#666666',\n",
    "        'node': '#000000',\n",
    "        'Green': '#ceffe7',\n",
    "        'Red': '#ffd6ce'\n",
    "    }\n",
    "\n",
    "    @property\n",
    "    def fontcolor(self):\n",
    "        return MockSpan.span_colors[self.node_type]\n",
    "\n",
    "    @property\n",
    "    def fillcolor(self):\n",
    "        if self.mark_color is None:\n",
    "            return '#ffffff'\n",
    "        return MockSpan.span_colors[self.mark_color]\n",
    "\n",
    "    def display_span(self, displayed_graph, show_importance):\n",
    "        ic = ''\n",
    "        if show_importance:\n",
    "            ic = ' / %.3f' % self.importance_score\n",
    "        \n",
    "        displayed_graph.node(self.gvid,\n",
    "                             self.name + ic,\n",
    "                             style='filled',\n",
    "                             fillcolor=self.fillcolor,\n",
    "                             fontcolor=self.fontcolor)\n",
    "\n",
    "        if self.parent is not None:\n",
    "            displayed_graph.edge(self.parent.gvid, self.gvid)\n",
    "\n",
    "        for child in self.children:\n",
    "            child.display_span(displayed_graph, show_importance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}