Mission530Solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Importing and Initializing\n",
    "\n",
    "We need to import the `BTree` class that is located in file `btree.py`. Note that when we import we don't put the `.py` extension.\n",
    "\n",
    "To call the constructor of the `BTree` method we need to use the `super()` function.\n",
    "\n",
    "To simplify testing, we will always build the `BTree` using a `split_threshold` equal to `2`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from btree import BTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KVStore(BTree):\n",
    "    \n",
    "    def __init__(self):\n",
    "        super().__init__(split_threshold=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Overriding the Add Method\n",
    "\n",
    "To override a method from the superclass we need to declare a method with the same name as the one we are overriding. \n",
    "\n",
    "We override the `add()` method because we want a different behavior in the `KVStore` than the one inherited from the `BTree`. Namely, we want to have no duplicates.\n",
    "\n",
    "To implement the new `add()` method we will need to use the `BTree._find_node()` and `BTree.add()` methods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KVStore(BTree):\n",
    "    \n",
    "    def __init__(self):\n",
    "        super().__init__(split_threshold=2)\n",
    "        \n",
    "    def add(self, key, value):\n",
    "        node = self._find_node(self.root, key)\n",
    "        if node is None:\n",
    "            super().add(key, value)\n",
    "        else:\n",
    "            # Replace the old value by the new\n",
    "            for i, node_key in enumerate(node.keys):\n",
    "                if node_key == key:\n",
    "                    node.values[i] = value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Testing\n",
    "\n",
    "Let's test the current implementation. We want to make sure that:\n",
    "\n",
    "1. The split threshold is correct.\n",
    "2. We can add entries.\n",
    "3. We can retrieve a value given a key.\n",
    "4. If we add two entries with the same key, the value is updated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "kv = KVStore()\n",
    "\n",
    "# Check the split threshold\n",
    "assert kv.split_threshold == 2, \"Split threshold is 2\"\n",
    "\n",
    "# Add the entries (i, i) for i from 0 to 9\n",
    "for i in range(10):\n",
    "    kv.add(i, i)\n",
    "\n",
    "# Check the values\n",
    "for i in range(10):\n",
    "    assert kv.get_value(i) == i, \"Value of i is i\"\n",
    "\n",
    "# Add again with different values\n",
    "for i in range(10):\n",
    "    kv.add(i, i + 1)\n",
    "\n",
    "# Check the new values\n",
    "for i in range(10):\n",
    "    assert kv.get_value(i) == i + 1, \"Value of i is i + 1\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementing the Item Getter and Setter\n",
    "\n",
    "To allow users to use the bracket notation, we need to implement the `__getitem__()` and `__setitem__()` methods.\n",
    "\n",
    "These methods are already implement but are named `get_value()` and `add()`, respectively. We can thus implement them by calling the corresponding method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KVStore(BTree):\n",
    "    \n",
    "    def __init__(self):\n",
    "        super().__init__(split_threshold=2)\n",
    "        \n",
    "    def add(self, key, value):\n",
    "        node = self._find_node(self.root, key)\n",
    "        if node is None:\n",
    "            super().add(key, value)\n",
    "        else:\n",
    "            # Replace the old value by the new\n",
    "            for i, node_key in enumerate(node.keys):\n",
    "                if node_key == key:\n",
    "                    node.values[i] = value\n",
    "                    \n",
    "    def __setitem__(self, key, value):\n",
    "        self.add(key, value)\n",
    "        \n",
    "    def __getitem__(self, key):\n",
    "        return self.get_value(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Testing Getter and Setter\n",
    "\n",
    "Let's redo the same tests but using bracket syntax."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "kv = KVStore()\n",
    "\n",
    "# Check the split threshold\n",
    "assert kv.split_threshold == 2, \"Split threshold is 2\"\n",
    "\n",
    "# Add the entries (i, i) for i from 0 to 9\n",
    "for i in range(10):\n",
    "    kv[i] = i\n",
    "\n",
    "# Check the values\n",
    "for i in range(10):\n",
    "    assert kv[i] == i, \"Value of i is i\"\n",
    "\n",
    "# Add again with different values\n",
    "for i in range(10):\n",
    "    kv[i] = i + 1\n",
    "\n",
    "# Check the new values\n",
    "for i in range(10):\n",
    "    assert kv[i] == i + 1, \"Value of i is i + 1\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Enhancing the Contains Method\n",
    "\n",
    "To enable the `in` operator, we need wrap the `BTree.contains()` method inside a new method named `__contains__()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KVStore(BTree):\n",
    "    \n",
    "    def __init__(self):\n",
    "        super().__init__(split_threshold=2)\n",
    "\n",
    "    def add(self, key, value):\n",
    "        node = self._find_node(self.root, key)\n",
    "        if node is None:\n",
    "            super().add(key, value)\n",
    "        else:\n",
    "            # Replace the old value by the new\n",
    "            for i, node_key in enumerate(node.keys):\n",
    "                if node_key == key:\n",
    "                    node.values[i] = value\n",
    "                    \n",
    "    def __setitem__(self, key, value):\n",
    "        self.add(key, value)\n",
    "        \n",
    "    def __getitem__(self, key):\n",
    "        return self.get_value(key)\n",
    "    \n",
    "    def __contains__(self, key):\n",
    "        return self.contains(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Testing the In Operator\n",
    "\n",
    "Let's do a test to see if we can use the `in` operator. We'll use alphabet letters as keys to see if other kind of keys are supported."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "kv = KVStore()\n",
    "for c in 'abcdefghijklmnopqrstuvwxyz':\n",
    "    kv[c] = c\n",
    "\n",
    "for c in 'abcdefghijklmnopqrstuvwxyz':\n",
    "    assert c in kv, \"Character is in the key-value store\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Range Queries\n",
    "\n",
    "Our solution consisted in replacing both `float('-inf')` and `float('inf')` by `None`. Then we created a method named `_range_intersects` that checks whether the query range intersects with the node range.\n",
    "\n",
    "We make the condition work in a way such that if `min_key` is `None` then it is always considered smaller than any other key and if `max_key` is `None` then it is always considered larger than any other key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KVStore(BTree):\n",
    "    \n",
    "    def __init__(self):\n",
    "        super().__init__(split_threshold=2)\n",
    "        \n",
    "    def add(self, key, value):\n",
    "        node = self._find_node(self.root, key)\n",
    "        if node is None:\n",
    "            super().add(key, value)\n",
    "        else:\n",
    "            # Replace the old value by the new\n",
    "            for i, node_key in enumerate(node.keys):\n",
    "                if node_key == key:\n",
    "                    node.values[i] = value\n",
    "                    \n",
    "    def __setitem__(self, key, value):\n",
    "        self.add(key, value)\n",
    "        \n",
    "    def __getitem__(self, key):\n",
    "        return self.get_value(key)\n",
    "\n",
    "    def __contains__(self, key):\n",
    "        return self.contains(key)\n",
    "    \n",
    "    def _range_query(self, range_start, range_end, current_node, min_key, max_key):\n",
    "        if not self._range_intersects(range_start, range_end, min_key, max_key):\n",
    "            return []\n",
    "        results = []\n",
    "        for i, key in enumerate(current_node.keys):\n",
    "            if range_start <= key and key <= range_end:\n",
    "                results.append(current_node.values[i])\n",
    "        if not current_node.is_leaf():\n",
    "            for i, child in enumerate(current_node.children):\n",
    "                new_min_key = current_node.keys[i - 1] if i > 0 else min_key\n",
    "                new_max_key = current_node.keys[i] if i < len(current_node) else max_key\n",
    "                results += self._range_query(range_start, range_end, child, new_min_key, new_max_key)\n",
    "        return results \n",
    "\n",
    "    def range_query(self, range_start, range_end):\n",
    "        return self._range_query(range_start, range_end, self.root, float('-inf'), float('inf'))\n",
    "    \n",
    "    def _range_intersects(self, range_start, range_end, node_min, node_max):\n",
    "        if not node_min is None and node_min > range_end:\n",
    "            return False\n",
    "        if not node_max is None and node_max < range_start:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DictKVStore(dict):\n",
    "    \n",
    "    def range_query(self, range_start, range_end):\n",
    "        result = []\n",
    "        for key in self.keys():\n",
    "            if range_start <= key and key <= range_end:\n",
    "                result.append(self[key])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test range query\n",
    "\n",
    "Test the range against the dictionary range query."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "dict_kv = DictKVStore()\n",
    "our_kv = KVStore()\n",
    "for i in range(10):\n",
    "    dict_kv[i] = i\n",
    "    our_kv[i] = i\n",
    "\n",
    "for range_start, range_end in [(1, 3), (4, 6), (1, 10), (5, 5)]:\n",
    "    dict_res = sorted(dict_kv.range_query(range_start, range_end))\n",
    "    our_res = sorted(our_kv.range_query(range_start, range_end))\n",
    "    assert dict_res == our_res, \"Both data structures return the same range query result.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Random Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing Insertion\n",
      "Testing Length\n",
      "Testing Values\n",
      "Testing in Operator\n",
      "Testing Range Queries\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "random.seed(0)\n",
    "\n",
    "NUM_INSERTS = 10\n",
    "NUM_CONTAINS = 10\n",
    "NUM_RANGE_QUERIES = 10\n",
    "\n",
    "dict_kv = DictKVStore()\n",
    "\n",
    "kv = KVStore()\n",
    "\n",
    "print(\"Testing Insertion\")\n",
    "for _ in range(NUM_INSERTS):\n",
    "    key = random.randint(0, 100)\n",
    "    value = random.randint(0, 1000000)\n",
    "    dict_kv[key] = value\n",
    "    kv[key] = value\n",
    "    \n",
    "print(\"Testing Length\")\n",
    "assert len(dict_kv) == len(kv), \"Wrong length. Length should be {} but is {}.\".format(len(dict_kv), len(kv))\n",
    "    \n",
    "\n",
    "print(\"Testing Values\")\n",
    "for key in dict_kv:\n",
    "    assert dict_kv[key] == kv[key], \"Wrong value for key {}. Expected value {} but found value {}.\".format(key, dict_kv[key], kv[key])\n",
    "\n",
    "    \n",
    "print(\"Testing in Operator\")\n",
    "for i in range(NUM_CONTAINS):\n",
    "    key = random.randint(0, 1000)\n",
    "    assert (key in dict_kv) == (key in kv), \"Contains method did not return the correct value for key {}.\".format(key)\n",
    "\n",
    "\n",
    "print(\"Testing Range Queries\")\n",
    "for _ in range(NUM_RANGE_QUERIES):\n",
    "    range_start = random.randint(0, 100)\n",
    "    range_end = random.randint(range_start, 100)\n",
    "    dict_results = dict_kv.range_query(range_start, range_end)\n",
    "    kv_results = kv.range_query(range_start, range_end)\n",
    "    assert len(dict_results) == len(kv_results), \"Wrong number of reuslt in range query [{}, {}]. Should be {} but was {}.\".format(range_start, range_end, len(dict_result), len(kv_result))\n",
    "    dict_results.sort()\n",
    "    kv_results.sort()\n",
    "    assert dict_results == kv_results, \"Wrong number of reuslt in range query [{}, {}]. Should be {} but was {}.\".format(range_start, range_end, len(dict_result), len(kv_result))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Speed Tests\n",
    "\n",
    "To perform the speed tests we start by creating an empty data structure of each type.\n",
    "\n",
    "Then we load all entries from the `entries.csv` file.\n",
    "\n",
    "After that, loop over each query in the `queries.csv` file. For each query, we measure its execution time on both data structure. Then we compute the execution time ratio between the dictionary solution and our solution.\n",
    "\n",
    "In the end we plot the result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEGCAYAAABiq/5QAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deXxU5dn/8c+VnX0N+y6biCIYFHdFa1Gr1qVaH7Vq9Uc3a1trW7RabX2qtrbaWn20PFrlUduqdcEdEdwVJYCyCAiyyb5DWLJfvz/OyZiESTIJmQyZ+b5fr7xmzjbnOjNwzT33Oee6zd0REZHUkZboAEREpGkp8YuIpBglfhGRFKPELyKSYpT4RURSTEaiA4hF586dvV+/fokOQ0SkWZk1a9Zmd8+tPr9ZJP5+/fqRn5+f6DBERJoVM1sZbb66ekREUowSv4hIiolrV4+ZrQAKgDKg1N3zzKwj8CTQD1gBXOju2+IZh4iIfKUpWvwnu/vh7p4XTk8Aprn7IGBaOC0iIk0kEV095wCTwueTgG8mIAYRkZQV78TvwOtmNsvMxofzurr7OoDwsUu0Dc1svJnlm1n+pk2b4hymiEjqiPflnMe6+1oz6wJMNbNFsW7o7hOBiQB5eXkqISoi0kji2uJ397Xh40bgOeBIYIOZdQcIHzfGOQaezv+SotKyeO5GRKTZiFviN7NWZtam4jlwGjAfeAG4PFztcmByvGIAmPrZBn7xn7ncPfXzeO5GRKTZiGdXT1fgOTOr2M8/3f01M5sJPGVmVwGrgG/FMQZ27C0BYHNBcTx3IyLSbMQt8bv7MmBElPlbgFPitd999tdUOxIRaSZS5s7d4IeHiIgkf+IPm/zK+yIigaRP/B5mfrX4RUQCyZ/4Iy1+ZX4REUiBxC8iIlUlfeKvuKpHXT0iIoHkT/y6nlNEpIrkT/w6uSsiUkXSJ/5JH6wInynzi4hAkif+5+as5vMNuwC1+EVEKiR14v/fd5ZHnivvi4gEkjrxi4jIvlIm8aurR0QkkDqJX509IiJACiX+cnfKynVRv4hIyiT+Jz5axUE3vpLoMEREEi5lEr+IiASSOvGrY0dEZF9JnfhFRGRfSvwiIilGiV9EJMUo8YuIpBglfhGRFKPELyKSYpT4RURSjBK/iEiKUeIXEUkxSvwiIilGiV9EJMUo8YuIpBglfhGRFBP3xG9m6WY2x8xeCqf7m9lHZrbEzJ40s6x4xyAiIl9pihb/T4CFlab/ANzj7oOAbcBVTRBDhLuKNYtIaotr4jezXsCZwEPhtAFjgf+Eq0wCvhnPGKrT8Isikuri3eL/C/BLoDyc7gRsd/fScHo10DPOMVShvC8iqS5uid/MvgFsdPdZlWdHWTVqKjaz8WaWb2b5mzZtarS4ytXVIyIpLp4t/mOBs81sBfBvgi6evwDtzSwjXKcXsDbaxu4+0d3z3D0vNze3QQFE689X4heRVBe3xO/uN7h7L3fvB3wbmO7ulwBvAheEq10OTI5XDNGoj19EUl0iruP/FXCdmS0l6PN/OF47ita4V94XkVSXUfcq+8/d3wLeCp8vA45siv1G69YpV+YXkRSX1HfuRk386uMXkRSX1Ik/Wo4vU+IXkRSX1Ik/WuteeV9EUl2SJ/5o85T5RSS1JXXij3bppi7nFJFUl9SJP9oNXIvXFyQgEhGRA0dSJ/5ojfvfTF7Q9IGIiBxAkjrxe5QyQEcN6JiASEREDhxJnfirt/gz042ubXMSE4yIyAEiqRP/4K6tq0xnZ6RTXFpew9oiIqkhqRP/g5ceUWU6OyONotKyBEUjInJgSOrE3yYnkxV3nhmZzspIo6hELX4RSW1Jnfiry85Io7hMiV9EUluKJf50tfhFJOWlVOLPUh+/iEhqJf7g5K5a/CKS2lIq8Wemp1GiPn4RSXEpkfhbZaUDkJFuKtImIikvJRL/Gz8/kae/fzRp9lXiLy0rV+tfRFJSSiT+7u1aMLpfR9LTLDIC12n3vMOgX7+a4MhERJpeSiT+CulpRkUjf9nm3YkNRkQkQVIr8ZtRVq7uHRFJbamV+NN0cldERIlfRCTFZNS1gpllAj8ATghnvQ086O4l8QwsHiqf3BURSVV1Jn7gASAT+J9w+rJw3tXxCipe0tMMdfGLSKqLJfGPdvcRlaanm9mn8QoontLNKFXmF5EUF0sff5mZHVQxYWYDgGZZ6Swtzdiws4jXF6xPdCgiIgkTS4v/F8CbZrYMMKAvcGVco4qTjDQDYPxjsxIciYhI4tSZ+N19mpkNAoYQJP5F7l4U98jiID1M/CIiqazGxG9mY919upmdV23RQWaGuz8b59gaXZop8YuI1NbiPxGYDpwVZZkDzS7xp6fUXQsiItHVmPjd/Zbw6e/cfXnlZWbWv64XNrMc4B0gO9zPf9z9lnDbfwMdgdnAZe5e3MD466WkTNfwi4jE0gZ+Jsq8/8SwXREwNrwU9HBgnJmNAf4A3OPug4BtwFWxBru/NPqWiEjtffxDgUOAdtX6+dsCOXW9sLs7sCuczAz/HBgL/Fc4fxJwK8ENYXFXVNIsr0IVEWlUtfXxDwG+AbSnaj9/AfD/YnlxM0sHZgEDgfuBL4Dt7l4arrIa6FnPmBtsV1Fp3SuJiCS52vr4JwOTzexod/+wIS/u7mXA4WbWHngOODjaatG2NbPxwHiAPn36NGT3+9hdrMQvIhLLDVxzzOxHBN0+kS4ed/9urDtx9+1m9hYwBmhvZhlhq78XsLaGbSYCEwHy8vIa5azsrqJ9u3rcHdNlniKSQmI5ufsY0A34OkFlzl4E3T21MrPcsKWPmbUATgUWAm8CF4SrXQ5Mrn/YDbOrcN+CoqrSLCKpJpbEP9DdbwZ2u/sk4Ezg0Bi2605Q6mEuMBOY6u4vAb8CrjOzpUAn4OGGhV5/l43pu8881ecXkVQTS1dPRTN5u5kNB9YD/erayN3nAiOjzF8GHFmPGBvNFcf2Z1DXNlzy0EeReeWqzy8iKSaWxD/RzDoANwEvAK2Bm+MaVRxlVrt9Vy1+EUk1tSZ+M0sDdrr7NoK7cAc0SVRxlJVRNfGrxS8iqabWPn53LweuaaJYmkRWtRa/xmURkVQTy8ndqWZ2vZn1NrOOFX9xjyxOqrf4NQaviKSaWBL/d4EfEXT1zAr/8uMZVDxlV0v8x945nQVrdyQoGhGRpldn4nf3/lH+mm1ff/WTu3tLyrh32pIERSMi0vRSrkJ99a4eUNVOEUktSvxAsRK/iKSQ1Ev8UYbhUuIXkVRSZ+K3wKVm9ptwuo+ZJeTO28aQmb5vQbb8ldsSEImISGLE0uL/H+Bo4OJwuoCgtn6zpEqcIpLqYinZcJS7jzKzOQDuvs3MsuIcl4iIxEksLf6ScCQth6DcMqBOcRGRZiqWxH8vwehZXczs98B7wO1xjSrOXvrxcTxx9VGJDkNEJCHq7Opx9yfMbBZwCmDAN919Ydwji6PhPduxcsvuRIchIpIQsfTxA2wA3g3Xb2Fmo9x9dvzCir/sjPREhyAikhB1Jn4zuw24AviCrwZGd2Bs/MKKv+o1ezT2roikilha/BcCB7l7cbyDaUrZmVUT/8J1BQzr0TZB0YiINJ1YTu7OB9rHO5CmVr2r54x7301QJCIiTSuWFv8dwBwzmw8UVcx097PjFlUTSE9Tt46IpKZYEv8k4A/APHT9vohIsxdL4t/s7vfGPRIREWkSsST+WWZ2B/ACVbt6mvXlnCIiqSqWxD8yfBxTaV6zv5xTRCRVxXLn7slNEciB4L7pS7hodB9y22QnOhQRkbipMfGb2aXu/riZXRdtubvfHb+wEuNPr3/OwnUF3H/JqESHIiISN7W1+FuFj22iLPMo85KCLvMUkWRXY+J397+HT99w9/crLzOzY+MaVQJ1ap3FrqJSWmfHWsZIRKR5ieXO3b/FOC8p5K/YxvBbpjBnlYZjFJHkVFsf/9HAMUButX7+tkBSlLb8w/mH8qtn5lWZN2/NDgBmrdzGyD4dEhGWiEhc1dafkQW0Dtep3M+/E7ggnkE1lYtG98EwfvnM3H2WlZYn7WkMEUlxtfXxvw28bWaPuvvKJoypSVWvxJyRZpSWOyWlqk4hIskpljOY2WY2EehXeX13r/UGLjPrDfwf0I2gxs9Ed/+rmXUEngxfbwVwobsnrEM9rVrmz85Io7S4jBK1+EUkScWS+J8GHgQeAsrq8dqlwM/dfbaZtSEo/TCVYFCXae5+p5lNACYAv6pf2I2n+uWbu4uDQywpU4tfRJJTLIm/1N0fqO8Lu/s6YF34vMDMFgI9gXOAk8LVJgFvkcDE7zXckqCuHhFJVrFczvmimf3QzLqbWceKv/rsxMz6EdT8+QjoGn4pVHw5dKlnzI2qtCx64tfJXRFJVrG0+C8PH39RaZ4DA2LZgZm1Bp4BfuruO2Md19bMxgPjAfr06RPTNg1RVkOCX755N7NWbuOIvrqkU0SSS50tfnfvH+Uv1qSfSZD0n3D3Z8PZG8yse7i8O7Cxhv1OdPc8d8/Lzc2N7WgaoMyjJ/63P9/E+Q98wIrNu+O2bxGRRKizxW9m34k2393/r47tDHgYWFitoNsLBL8i7gwfJ8ccbRyU19GlM3vVNvp1blXrOiIizUksXT2jKz3PAU4BZhNcqlmbY4HLgHlm9kk470aChP+UmV0FrAK+Va+IG1ldffm7ikqbKBIRkaYRSz3+H1eeNrN2wGMxbPceUFOH/ikxRdcEaurjr7BjT0kTRSIi0jRiuaqnuj3AoMYOJFHqavHvLFTiF5HkEksf/4t8VX8/DRhGcFNXUqirxb9zr7p6RCS5xNLH/6dKz0uBle6+Ok7xNLm6Ev+uYiV+EUkusfTxv1152szSzewSd38ifmE1nboSf11X/YiINDc19vGbWVszu8HM7jOz0yxwDbAMuLDpQoyvrw3rCsDdF46Iulx38IpIsqnt5O5jwBBgHnA18DrBpZfnuPs5TRBbkxjesx0r7jyT80b1irq8rl8EIiLNTW1dPQPc/VAAM3sI2Az0cfeCJoksgYZ0bcPiDcFhqsUvIsmmthZ/5DpGdy8DlqdC0gfISP/q9oN3Pt/Em4uiVpUQEWmWakv8I8xsZ/hXABxW8dzMdjZVgImQkV71bbny0ZkJikREpPHVNvRiUgyo3hAZ4eAsWRlpFId1+e9+fTHtW2bx3eP6JzI0EZH91pA7d5PeiF7tAejUKisy797pS/ndS58lKiQRkUajxB/FDWcM5ZkfHMPALq0THYqISKNT4o8iMz2NI/p2oIZS/SIizZoSfy3KlflFJAkp8deipry/t7gM15eCiDRTSvy1iNbi31NcysG/eY27p36egIhERPafEn8tojXqv9y6F4C/TV/axNGIiDSOWMoyp4wPJowlK+Or78JoLf412/cAX13rLyLS3CjxV9KjfYsq09ES/zX/nANAt3Y5TRKTiEhjU1dPLaKdvt1TXAZAh5ZZUZaKiBz4lPhrUVthTl3qKSLNlRJ/LXJb19yqV51+EWmulPhrcf3Xh9CvU8uoyxatL+DJmasAeH/pZuau3t6UoYmINJg1hxuR8vLyPD8/PyH7/tfHq7jh2Xl1rtelTTYf//rUJohIRCQ2ZjbL3fOqz1eLvw45mbG9RRsLili/oxB359H3l7N9T3GcIxMRaRgl/jrkZMQ+LMGYO6Zx3/Sl3PriZzH9ShARSQQl/jrkZNZvPJo/h6Uctuwu5sute7jp+XmUlpXHIzQRkQZR4q9DdoxdPdFc99QnPD5jFbNX6cSviBw4dOduHerb4q/w8fKtjRyJiEjjUIu/DvXp4xcRaQ6U+OsQ61U9tTHVcxORA4gSfx1i7eo5qn/HOEciItI44pb4zewfZrbRzOZXmtfRzKaa2ZLwsUO89t9YYk38E04fyrVjB0Zdtm5HYaTP/5V563hvyeZGi09EpL7i2eJ/FBhXbd4EYJq7DwKmhdMHtOyM2N6izPQ0MtOjr3vtv+Zw4d8/pLCkjB8+MZtLH/6oMUMUEamXuCV+d38HqH5pyznApPD5JOCb8dp/Y2mZlc7XhnWtc72sjDQy6/iSGHrza40VlohIgzV1H39Xd18HED52aeL915uZ8b/fySMzvfYztOlpVmOLX0TkQHLAZiozG29m+WaWv2nTpkSHU2ttfoDSMierji8HEZEDQVMn/g1m1h0gfNxY04ruPtHd89w9Lzc3t8kCrMl1XxsMwHM/PIabzjx4n+UdWmaqxS8izUJTZ6oXgMvD55cDk5t4/w32o5MHsuLOMxnZpwNXHz+AFXeeGVk2++av0aVtDhn1SPx7iktxd/aGQzmKiDSVuJVsMLN/AScBnc1sNXALcCfwlJldBawCvhWv/Teljq2CkbpaZtV86eeZh3bn5XnrItPDfjMl8vyVa49nWI+28QtQRKSSuCV+d7+4hkWnxGufiTaqT823JbRtUfNb/Z1/fETLrAz+ftkRHNxdXwAiEl/qlN4PL197HA9eOioy3a1dDlN+ekKVdSpKPrTNyazxdTbvKmbV1j2c/td3+fG/5tS43vY9xfzsyU/YsbdkPyMXkVSmxL8fDunRjnHDu1eZN6RbmyrTRnClT+fW2TG95oufrqXfhJdZtH7nPsv+Nn0pz81ZwzOzVjcwYhERJf64qyjQdlCXVlGX9+kYfTD3u15bzPcey6ewpIyZK4L74NbvLASgQ6uafz2IiNRFiT8OzhvVM/K84sr+/p1bR+aNP2FA5Pl3ju4btV9/2qKNTFmwgZuen8+3HvyQm5+fz7bdwTi+aSr3KSL7QYk/Du66YATv/vJkXv/ZCViYpFtnf3Vy98YzDuawXu0AGNW3A6/+5HhuP/fQqK/1n7Bb57EZK/ngiy0AugRURPaLEn8cpKcZvTu2ZHDXNpEWf/WSD3+56HDOPKw7h4SXcfbrFL3LJ5pbXlhAicbxFZEGUuKPN6t4qJr4B+S25v7/GkV2OMJXdj2GeCwqLWfKgvV8uXWPrvARkXrTmLtx9tB38njk/RW0yan9ra6rCFx11/wzuOxzYJfWXH/a4H2uLhIRqYla/HF21IBOPHjZEaSl1Z7Yq/8iiNXSjbv4/uOzmbt6O9c//SnPztalniJSO7X4m9CHN4ylrIYyn63r+EVQl7Pvex8ITgafO7Jn5KRyfby7ZBOj+nSgVbb+WYgkM7X4m1D3di3o1SH6Sdz+nVvxyJWjI9Nv/+KkGl/nyH61j+87+vdv0G/Cy5x933t8tnYne4vLcHe+fs87PD5jJdv3FPPl1j3sLiqNbLOpoIjLHv641juHRSQ5KPEfQE4e8tW4NH07Rb/ha8yAjjz1/aNrfZ3Nu4Lr/eeu3sEZ977LXVMWU1BUyuINBdz0/HwO/91Ujv/jm/zwidns2FvC4vUFbAhvDpuxLLhk1N25d9oSNobzRSR56Df9AaZtTgY7C0trXN6Qmv+TPlzBP95fvs/8tz/fxIjfvl5l3p7w18Hc1Tu4e+rnzFyxlceuOgp3b1D3kYgceNTiP8BMve5EnvnBMfvMn3D6UACKS+t//X5N5xVq8t7SzWwqKAJgV1EpNzw7l7F/fhuAJRsK2L6nmO17ivngi831jkVEEk8t/gNM17Y5dG2bA0Cb7AwKwn74nu1bALAxTMjnjuzJc3PWRLb73okD+Pvbyxolhsse/jjyfM6q7cxZtR2Af7y3nN+99Bk927egY6ss5q3ZwaLbxpFTj3sQRCTx1OI/gL187fGR5xXF3FZu2Q3AHy84rMq6rbNi/w7PqOPS0pr87qXPAFizfS/z1uwAIH/FNtbvKCR/xVY27yqKrLtux17eXLSx1l8b5eVeZRsRaRpq8R/A+nRqyfsTxrJhZyGH9GhL304tuTCvN7BvX/8Jg3P589TPY3rdg3Jbs3hDQY3Lc9tkR7p66nLpwx9FnmdlpHHK0C7cfu6hjP3T2+wtCWoKLf396aSZsWzzLnbsLeWIvsGANfe88Tl/m76U/JtOjblstYjsP7X4D3A927dgVJ8OZKSn8fYvTuZHJw+MLLvy2H6R5yN6t2fxf48DYHjP/RvFq6FJuLi0nFfnr2fkbVMjSR/g4feWM+DGVzj17nc4/4EPmLVyG+XlztP5wc1msZadKCt3Hp+xkqLS+hep27yrqMrlqyKpTC3+ZuyWsw5h595SvjEiKNeQnZHOI1eO5rCe7WiTk8m2PcUcdfu0fbarfHHOhNOHcueri6os79w6q8r00QM68WF4mWdD3FHt9c9/4IMq06f8+e0qg9fX5Pk5a7jp+fls2VXMT04dVK8Y8v77Dfp1aslbvzi5XtuJJCO1+Ju5P184osr1/ycP6UKn1tlkZaRFThIDXFPplwLAk+PHcPeFI/j+iQdxVP+qN4SdODiXV39yPP8eP4ZLjurDjWccXGV5m+wM2uRkcPVx/QH428Uj9/s4xv3lHTbuLGTZpl2cds/bnPLnt3h8xkrOuf99Pg+7pbbsDrqfdhaWUFJWjnv9rlZasWXPfscpkgzU4k9y15w8kOKycq49ZRAtstK5a8piDu7elqMGdIqs07bFVyN6PXLlaE4anBu5Zn/MgE58ubVqwpx762mR5VcfP4Bu7XL4/csLIyOENcSi9QUcWe3XyU3PzwfgtHveoXPrrMiNaQ+/t5yH31vO7845hJOHdGHdjkIGd21Nm5xM0tOMwpIylm3azZBubbjh2blccETvBsclkoyU+JPc9V8fEnn+o5MHMqpPBw7v3b7KOhUDwV9xTL8qvx4qpFe6CuiKY/pVuZGrW7vgV0VFa/yWs4bx2xc/a7wDCFUk/cp+M3kBsCAyPaRrGx687AgmfbCCRz9YEZn/VP5Xhet2F5VSWuZ8tm4nA3Jbkds6u0oBPXdnV1EpbXIaPrzlP95bzqkHd6VPPcZYEGlKVt+fy4mQl5fn+fn5iQ4jaW0sKOS2lxZyx3mHVhkprIK7c88bSzh3ZE/6d45eSuKm5+fx+IxVLLv9DNLSjOWbdzPuL+/QJiezyiWbD1wyih88MTtux9IQrbLSGdKtDeeO7MnNk4Mvkvd+dTKbCop4Kv9LLj6yDzv2llBQWMq4Q7qxt6SMVtkZuDvb95TQrkUmaWnGzBVbKS93Lpo4A4BBXVpz/yWjGNy1TZ0xfLRsC707tqRHeL+GSGMws1nunrfPfCV+aQxl5U5xaTktsqrezDVj2Ra+PXEGeX07cN1pgzl6QCcOuvEV6nkz8QGnTU4GBWFpjaP6d+TBS49g5G1T91nvmIM6cdHo3vz8qU95+IrRnDg4l8mfrOGxD1fy1PeOJi3NKCotY8hNrwHw7A+PYWTv9ixaXxB1LOb62rGnhKfyv+Sq4/rXWRpcko8SvyTE3uIyLnloBreefQiH9Qq6mJZu3MWkD1bw2IyVAJw/qhcvzV1LUWk5144dyCkHd+Wc+99vlP1nZaQ1qMxFvFw2pm/kuEf0aseI3u15fcGGyPmRNjkZjBnQiamfbeDiI/twy1nDWLy+gBZZ6fv8cnhr8UY6tsqKvK/APjWVfvH0pzw9azWPXXUkxw/KrTO+qZ9t4Mj+HWnXouFdXXLgUOKXA0ppWTkXTZzBtacM4sTBuWzeVcTe4jJ6h3coz1q5lYG5bfjupJnMWrkt6mvceMZQbn9l0T7zTxvWlb0lZby7ZDMDcluxbFNwt/NFeb2ZuXIryzbt5rxRPenfqRUdWmVFTiIf6H59xsGs3bGXHXtKeLZSuY5xh3TjtQXrI9M//9pgrji2H5npaYz47esUhV98vz93ONt2F2Nm9O/cipOG5PLl1r1c88/ZnH5od95ctJF5a3Zw3MDOdG2bw9ihXXjio5UsWl/Aff81ki827uLSMX0jXyzFpeX8e+YqvjmyJzc8M48rj+1HXqWS4ZM/WcPrCzZw/yWjALj1hQWM6N2Oc0f2atDxL9lQQO+OLVUipB6U+KVZ2lVUyh9fW8Q5h/dgWPd2tMhKp7CkjLJyp1V2Bht2FnLL5AWRxPfDkw7il+OGUlRaRkFhKWu3740MUvPaT48nKz2N5Zt3c+LgXDLS0yJdUdE8cuVojhvYmZKycob9Zkq9Y//m4T14/pO1UZf1bN+CNdv31vs1E+38Ub348IvNrN0R/Qqus0f04IVP13L8oM68uyQo4nf9aYPp2aEFP3vyUwCGdmvDBUf04vhBuQzu2po9xWXc/spC3lu6mT4dW/LIFaPZXVTG9x+fxeXH9GPc8G7sKS5l2G+mcMah3fjF14cy8Z1l/OvjVVXu+t5YUEhmWhodWmXtE1dxaTlpBp+t28nmXUWRq8G6t8uptersrqJSWmWl88Wm3Qzs0joyf1NBEY99uIJrTxlERgMq5tZm864ixv3lXR69cjTDe7bbr9dS4peUVVhSxrodhTWemL532hLuDstdvPTj41i3o5CxQ7tUuZrprcUbueKRmVG3f/na4zjz3vcA6NupJSvD+wWW33EGv395Iacd0o15a3ZwW1jrqGvbbJ7+3jGccNebAEz92Qm88Ola/jZ9KQDnjexJXr+O3PjcPAB6dWjB6m1VvyT6dGyJGZF97a+e7VswpFsb5qzaxrY9sd1JfSA4KLcVxw/KZcayLSxaH9zvcfygzqzZtpcBua1pkZXOhh2FfLxia9TtO7XKwsw4a0R3rj5+ACs37+b2VxeS17cjXdvm8IfXFjGid3s+/XI7N39jGK2y0jl9eHd++M9ZvL90C21yMrjua4OZ/MlazhrRg8FdW3Noz3a0b7nvl09N3J23Fm/i6IM6kZOZznNzVvOzJz/lrBE99vseGSV+kVpU/D+orfX30LvLaJuTyZmHdae4tJwPl22hU6ssjuzfkf43vALAu788mTteXcjuojImfffIyLZLNxZw6t3v8OI1x3For3aUlzsDbnylyt3ENz8/n8dmrOTDG8bSvV0L+k14GYBlt5/BgBtfibzW6H4dePr7x1BYUsbQm1+r9bju/69RlLvz6AcrauwyAyJ3Tl/60Ee8t/SrctvL7ziDyZ+s5adPfhJ1u/NG9eTZ2WuiLquv7Iy0SLdUc9e1bTbd27Vg5ZbdDOrShoXrd1JSVk5hSTmZ6cYpQ7tW6Z6D4Mt8/AkD+HLbnkil3b9fdgQnDMrd56KJWCnxi8TRq/PWcdfri3n9pyfE/NM/f/uc4OMAAAyqSURBVMVWBuS2pmOUrgkIqqC6O706tKSkrJx12wvp3bFFlS+n7XuK2bK7mE+/3M51T33KmYd25xuHdef2Vxfy5da9Vcpmb9hZGP5yCLrJzv7b+5wwOJd+nVpy0zeGATDpgxXc8sICbjh9KFv3FHPD6Qfj7pEvtupW3HkmD727jP9+eWFk3v9cMoofhpfsTvv5iZwSjuUAcOZh3SkqKeONhRu57ZxD2LanhL0lZXRomck5h/eMWmKkLjmZacz89amcdNdbbNm97/0eT3//aNLTjCdmrOKZ2cE9Hf06tdzvO7nTjCa5Om3KT09gSLe6LwmORolfROrk7uwtKaNltTLfJWXl/GnKYi44ohftW2bx4bIt7NxbwqVj+gLBZaNXTZrJ5cf046wRPZixbAuZ6cYRfTsyf80OWmal8/mGXYwb3g13p7isnOyM9H32/ccpixk7tAvfevBDAO4871AuGt2b+6YvZeK7yyKX0F58ZG+GdmvLIT3aRk4oz1m1jRc/XceLc9dGqsvectYwrjy2f+T1S8udJ2as5PRDu0e+ZCZedgTDe7bjmDunR2L59ujerNq6h4+Xb6W0UnZf/N/jWLu9kLcXb+Tio/pELsOtzZybv8biDQVkphvnP/DhPsvfnzCWCc/MjZwTqS6WOlY1UeIXkWZjZ2Fww1zPaje0lZSVxzT8qLtTUuZkZdS87nNzVjMwtw2H9moX2ab6SdxdRaUsWLOD4T3bsae4jNw2VSvXrtuxl5yMdJ6ZvZp3lmzmkqP6cMcrC1mxZQ9XH9efbx/Zp8rrrduxl227S3jio5WcNaIHGwuKOHtED4pLy9m+p3ifsiW3fXM4l4Vfrg1xQCV+MxsH/BVIBx5y9ztrW1+JX0Sak8KSMrLS0+p909yuolKmzF9Pq+x0xg3vvt9x1JT4m7xWj5mlA/cDXwNWAzPN7AV3b/wCLyIiCdDQew1aZ2dw/hENu8+hPhJRlvlIYKm7L3P3YuDfwDkJiENEJCUlIvH3BL6sNL06nFeFmY03s3wzy9+0aVOTBScikuwSkfijdXrtc6LB3Se6e5675+Xm1l1jREREYpOIxL8aqDwyRi8g+n3tIiLS6BKR+GcCg8ysv5llAd8GXkhAHCIiKanJr+px91IzuwaYQnA55z/cfUEdm4mISCNJyNCL7v4KEP0ecBERiatEdPWIiEgCNYuSDWa2CVjZwM07A9GLYCQvHXNq0DGnhv055r7uvs9lkc0i8e8PM8uPdstyMtMxpwYdc2qIxzGrq0dEJMUo8YuIpJhUSPwTEx1AAuiYU4OOOTU0+jEnfR+/iIhUlQotfhERqUSJX0QkxSR14jezcWa22MyWmtmERMfTGMyst5m9aWYLzWyBmf0knN/RzKaa2ZLwsUM438zs3vA9mGtmoxJ7BA1nZulmNsfMXgqn+5vZR+ExPxnWfsLMssPppeHyfomMu6HMrL2Z/cfMFoWf99HJ/jmb2c/Cf9fzzexfZpaTjJ+zmf3DzDaa2fxK8+r92ZrZ5eH6S8zs8lj3n7SJv9JIX6cDw4CLzWxYYqNqFKXAz939YGAM8KPwuCYA09x9EDAtnIbg+AeFf+OBB5o+5EbzE2Bhpek/APeEx7wNuCqcfxWwzd0HAveE6zVHfwVec/ehwAiCY0/az9nMegLXAnnuPpyglte3Sc7P+VFgXLV59fpszawjcAtwFMEAV7dUfFnUyd2T8g84GphSafoG4IZExxWH45xMMIzlYqB7OK87sDh8/nfg4krrR9ZrTn8E5bunAWOBlwjGddgMZFT/vAkKAB4dPs8I17NEH0M9j7ctsLx63Mn8OfPVIE0dw8/tJeDryfo5A/2A+Q39bIGLgb9Xml9lvdr+krbFT4wjfTVn4U/bkcBHQFd3XwcQPnYJV0uW9+EvwC+B8nC6E7Dd3UvD6crHFTnmcPmOcP3mZACwCXgk7N56yMxakcSfs7uvAf4ErALWEXxus0juz7my+n62Df7MkznxxzTSV3NlZq2BZ4CfuvvO2laNMq9ZvQ9m9g1go7vPqjw7yqoew7LmIgMYBTzg7iOB3Xz10z+aZn/MYTfFOUB/oAfQiqCbo7pk+pxjUdNxNvj4kznxJ+1IX2aWSZD0n3D3Z8PZG8yse7i8O7AxnJ8M78OxwNlmtgL4N0F3z1+A9mZWUVq88nFFjjlc3g7Y2pQBN4LVwGp3/yic/g/BF0Eyf86nAsvdfZO7lwDPAseQ3J9zZfX9bBv8mSdz4k/Kkb7MzICHgYXufnelRS8AFWf1Lyfo+6+Y/53wyoAxwI6Kn5PNhbvf4O693L0fwec43d0vAd4ELghXq37MFe/FBeH6zaol6O7rgS/NbEg46xTgM5L4cybo4hljZi3Df+cVx5y0n3M19f1spwCnmVmH8NfSaeG8uiX6BEecT56cAXwOfAH8OtHxNNIxHUfwc24u8En4dwZB3+Y0YEn42DFc3wiubvoCmEdwxUTCj2M/jv8k4KXw+QDgY2Ap8DSQHc7PCaeXhssHJDruBh7r4UB++Fk/D3RI9s8Z+C2wCJgPPAZkJ+PnDPyL4DxGCUHL/aqGfLbAd8PjXwpcGev+VbJBRCTFJHNXj4iIRKHELyKSYpT4RURSjBK/iEiKUeIXEUkxSvwSN2bWy8wmh5UDl5nZfWaWnei4koGZ3Wpm14fPrzCzHvXY9mxLkmq10jBK/BIX4Q04zwLPe1BtcBDQAvhjI71+egO2yah7rfiJ4/6vIChxEBN3f8Hd74xTLNIMKPFLvIwFCt39EQB3LwN+RnAHYuuwlXpfxcpm9pKZnRQ+P83MPjSz2Wb2dFiXCDNbYWa/MbP3gAlmNrvS9oPMrHItn4r5b5nZ7Wb2NvATMzsrrN0+x8zeMLOu4Xq3hjXS3wp/nVxb6TVutqAm/lQLasRXtLQPMrPXzGyWmb1rZkOj7P9WM5toZq8D/2fBmAJ3mdnMsLb698L1upvZO2b2iQW16I8P5++q9FoXmNmj1V7/AiAPeCLctkW15dea2Wfhvv4dzou89+E2FX97zexEM2sVvhczw/fpnNo/amluEtoCkqR2CEFlxQh33xnW2xlY00Zm1hm4CTjV3Xeb2a+A64DfhasUuvtx4bqnmtnh7v4JcCVBjfNo2rv7ieE2HYAx7u5mdjVBxc+fh+sNBU4G2gCLzewBgjr45xNUQc0AZlc6ronA9919iZkdBfwPwRdedUcAx7n7XjMbT3DL/eiw2+v98EvhPIJyw78Pf820rOk9qszd/2Nm1wDXu3t+lFUmAP3dvcjM2kfZ/vDwfTkrfC8+ILh7drq7fzfc5mMze8Pdd8cSkxz4lPglXozolQKjVRSsbAzBwDnvB71FZAEfVlr+ZKXnDwFXmtl1wEUEg1FEU3mbXsCTFhTByiKoeV/hZXcvAorMbCPQlaBExmR33wtgZi+Gj60JCog9HcYJQXmBaF6o2J6gnsphYUsdgsJigwhqS/3DggJ8z4dfZo1hLsGvgecJyj7sw8wGAXcBY929xMxOIyiKd324Sg7Qh6qD4EgzpsQv8bKAoKUcYWZtCZLpYmA4VbsacypWA6a6+8U1vG7lVuczBCMQTQdmufuWGLb5G3C3u78Qdi3dWmlZUaXnZQT/P2r6okojqBN/eA3La9q/AT92932KaZnZCcCZwGNmdpe7/x9Vvzxzqm8TgzOBE4CzgZvN7JBq+2wFPAX8P3evqOxowPnuvrgB+5NmQH38Ei/TgJZm9h2InIz9M3Bf2PpdARxuZmlm1puvWuszgGPNbGC4XUszGxxtB+5eSFCN8AHgkRjjagesCZ/HMkbpe8BZFoz92pogkeLBGAjLzexbYZxmZiNieL0pwA/Clj1mNjjsU+9LMObA/xJUX60YV3WDmR1sZmnAuTW8ZgFB91QV4Ta93f1Ngm6c9kDraqs9Ajzi7u9Wi/HHFv6UMbORMRyXNCNK/BIXHlT/Oxe4wMyWAFuAcnf/fbjK+wTdLPMIRl2aHW63ieAqlX+Z2VyCL4J9TppW8gRBq/j1GEO7laB75l2CofrqOo6ZBGVxPyW4SimfYKQngEuAq8zsU4JfOLGcBH2IoNTwbAsG2v47wS+Lk4BPzGwOwS+lv4brTyAYgnA6QTXHaB4FHoxycjcdeNzM5gFzCMat3V6xMPyyuQD4bqUTvHnAbUAmMDeM8bYYjkuaEVXnlCZhZscQlKI9z6uOpLW/r3s90M7db26s14yyj9buvsvMWgLvAOPdfXZd24kcqJT4pdkys+eAgwhOStbZet+P/fyT4IRzDjDJ3e+I175EmoISv4hIilEfv4hIilHiFxFJMUr8IiIpRolfRCTFKPGLiKSY/w8PpEU4c0xvdgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import time\n",
    "import csv\n",
    "\n",
    "dict_kv = DictKVStore()\n",
    "our_kv = KVStore()\n",
    "\n",
    "# Load the entries\n",
    "with open('entries.csv', 'r') as f:\n",
    "    rows = list(csv.reader(f))[1:]\n",
    "    for row in rows:\n",
    "        key = int(row[0])\n",
    "        value = int(row[1])\n",
    "        dict_kv[key] = value\n",
    "        our_kv[key] = value\n",
    "\n",
    "# Measure query times\n",
    "time_ratios = []\n",
    "with open('queries.csv', 'r') as f:\n",
    "    rows = list(csv.reader(f))[1:]\n",
    "    for row in rows:\n",
    "        range_start = int(row[0])\n",
    "        range_end = int(row[1])\n",
    "        \n",
    "        start = time.time()\n",
    "        dict_kv.range_query(range_start, range_end)\n",
    "        end = time.time()\n",
    "        time_dict = end - start\n",
    "\n",
    "        start = time.time()\n",
    "        our_kv.range_query(range_start, range_end)\n",
    "        end = time.time()\n",
    "        time_kv = end - start\n",
    "\n",
    "        time_ratios.append(time_dict / time_kv)\n",
    "\n",
    "# Plot results\n",
    "import matplotlib.pyplot as plt\n",
    "plt.plot(time_ratios)\n",
    "plt.xlabel('Query range result size')\n",
    "plt.ylabel('Runtime ratio')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion\n",
    "\n",
    "For 50,000 entries, we get a performance boost of at most 50 times. \n",
    "\n",
    "We see that the performance boost decreases as the size of the of query increases. This is expected since the more result we return the closer we get to having to iterate of all entries in the tree.\n",
    "\n",
    "With 100,000 entries the performance boost can go up to about 120 times."
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}