{ "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": 10, "metadata": {}, "outputs": [], "source": [ "class KVStore(BTree):\n", " \n", " def __init__(self):\n", " super().__init__(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.\n", "\n", "To call the `__find_node()` method we need to use a special syntax because it is private. This syntax is `self._BTree__find_node()`." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "class KVStore(BTree):\n", " \n", " def __init__(self, split_threshold=2):\n", " super().__init__(split_threshold)\n", " \n", " def add(self, key, value):\n", " # The find_node method is private\n", " # We need to call it using _BTree__find_node\n", " node = self._BTree__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": 12, "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": 13, "metadata": {}, "outputs": [], "source": [ "class KVStore(BTree):\n", " \n", " def __init__(self, split_threshold=2):\n", " super().__init__(split_threshold)\n", " \n", " def add(self, key, value):\n", " # The find_node method is private\n", " # We need to call it using _BTree__find_node\n", " node = self._BTree__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": 14, "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": 2, "metadata": {}, "outputs": [], "source": [ "class KVStore(BTree):\n", " \n", " def __init__(self, split_threshold=2):\n", " super().__init__(split_threshold)\n", " \n", " def add(self, key, value):\n", " # The find_node method is private\n", " # We need to call it using _BTree__find_node\n", " node = self._BTree__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": 4, "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 private 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": 15, "metadata": {}, "outputs": [], "source": [ "class KVStore(BTree):\n", " \n", " def __init__(self, split_threshold=2):\n", " super().__init__(split_threshold)\n", " \n", " def add(self, key, value):\n", " # The find_node method is private\n", " # We need to call it using _BTree__find_node\n", " node = self._BTree__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 __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": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\n", "1\n", "2\n", "3\n", "4\n", "5\n", "6\n", "7\n", "8\n", "9\n" ] } ], "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\n", "\n", "x = DictKVStore()\n", "for i in range(10):\n", " x[i] = i\n", "\n", "for i in x:\n", " print(i)" ] }, { "cell_type": "code", "execution_count": 13, "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": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Inserting\n", "done\n" ] }, { "ename": "KeyboardInterrupt", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 25\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0m_\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mNUM_CONTAINS\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 26\u001b[0m \u001b[0mkey\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mrandom\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrandint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1000\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 27\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mkey\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mentries\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mkey\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mkv\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"Contains method did not return the correct value for key {}.\"\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 28\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 29\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"contains done\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36m__getitem__\u001b[0;34m(self, key)\u001b[0m\n\u001b[1;32m 20\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 21\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0m__getitem__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 22\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget_value\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 23\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 24\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0m__range_query\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mrange_start\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mrange_end\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcurrent_node\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmin_key\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmax_key\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m~/dataquest/content/530/btree.py\u001b[0m in \u001b[0;36mget_value\u001b[0;34m(self, key)\u001b[0m\n\u001b[1;32m 119\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 120\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mget_value\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 121\u001b[0;31m \u001b[0mnode\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__find_node\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mroot\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 122\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mnode\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 123\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m~/dataquest/content/530/btree.py\u001b[0m in \u001b[0;36m__find_node\u001b[0;34m(self, current_node, key)\u001b[0m\n\u001b[1;32m 94\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 95\u001b[0m \u001b[0mchild_index\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mcurrent_node\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget_insert_index\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 96\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__find_node\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcurrent_node\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mchildren\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mchild_index\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 97\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 98\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mcontains\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m~/dataquest/content/530/btree.py\u001b[0m in \u001b[0;36m__find_node\u001b[0;34m(self, current_node, key)\u001b[0m\n\u001b[1;32m 94\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 95\u001b[0m \u001b[0mchild_index\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mcurrent_node\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget_insert_index\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 96\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__find_node\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcurrent_node\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mchildren\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mchild_index\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 97\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 98\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mcontains\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mKeyboardInterrupt\u001b[0m: " ] } ], "source": [ "import random\n", "random.seed(0)\n", "\n", "NUM_INSERTS = 1000\n", "NUM_CONTAINS = 1000\n", "NUM_RANGE_QUERIES = 1000\n", "\n", "dict_kv = DictKVStore()\n", "\n", "kv = KVStore()\n", "\n", "print(\"Inserting\")\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(\"done\")\n", "assert len(entries) == len(kv), \"Wrong length. Length should be {} but is {}.\".format(len(entries), len(kv))\n", " \n", "for key in dict_kv:\n", " assert dict_kv[key] == kv[key], \"Wrong value for key {}. Expected value {} but found value {}.\".format(key, entries[key], kv[key])\n", "\n", "for _ in range(NUM_CONTAINS):\n", " key = random.randint(0, 1000)\n", " assert (key in entries) == (key in kv), \"Contains method did not return the correct value for key {}.\".format(key)\n", "\n", "print(\"contains done\")\n", " \n", "def dict_range_query(dictionary, range_start, range_end):\n", " result = []\n", " for key in dictionary:\n", " if range_start <= key and key <= range_end:\n", " result.append(dictionary[key])\n", " return result\n", "\n", "print(\"Starting 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_range_query(entries, 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": 34, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEGCAYAAABiq/5QAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deXhU1fnA8e+bnZCwBwhrCIvIIqBhUxSxiAhS61blV6t1Ka3VWtcWrWtt1dbWrVotrrjUvdYFXNhUNsWwr8q+Rgj7mpBk3t8f906YyUySIclkkpn38zzzZOYuc8+dgXfOPefc94iqYowxJnbERboAxhhjapcFfmOMiTEW+I0xJsZY4DfGmBhjgd8YY2JMQqQLEIoWLVpoVlZWpIthjDH1yvz583eqakbZ5fUi8GdlZZGbmxvpYhhjTL0iIhuDLbemHmOMiTEW+I0xJsZY4DfGmBgTtsAvIikiMk9EFovIchG5313+soisF5FF7qNvuMpgjDEmUDg7dwuBs1T1oIgkArNE5BN33e2q+m4Yj22MMaYcYQv86mR/O+i+THQflhHOGGMiLKxt/CISLyKLgB3AFFX9xl31FxFZIiKPiUhyOfuOE5FcEcnNz88PZzGNMSamhDXwq2qJqvYF2gEDRKQXcAfQHegPNAP+UM6+E1Q1R1VzMjIC7j8I2ffbD/Dtht1V3t8YY6JNrYzqUdW9wBfASFXNU0ch8BIwIJzHHvHYV1zy7NxwHsIYY+qVcI7qyRCRJu7zBsBwYJWIZLrLBPgJsCxcZTDGGBMonKN6MoGJIhKP8wPztqp+LCLTRSQDEGAR8OswlsEYY0wZ4RzVswToF2T5WeE6pjHGmMrZnbvGGBNjLPAbY0yMscBvjDExxgK/McbEGAv8xhgTYyzwG2NMjLHAb4wxMSZmAv+Dk1ey40BBpIthjDERFzOBf8JX67jjvaWRLoYxxkRczAR+gCNFJZEugjHGRFxMBf4Sj80DY4wxMRX4PWqB3xhjYirwF1uN3xhjYivwW1OPMcZY4DfGmJhjgd8YY2KMBX5jjIkxsRX4bVSPMcbEWOC3Gr8xxsRW4C8uscBvjDFhC/wikiIi80RksYgsF5H73eWdROQbEVktIm+JSFK4ylCW1fiNMSa8Nf5C4CxV7QP0BUaKyCDgr8BjqtoV2ANcE8Yy+Beo2HL1GGNM2AK/Og66LxPdhwJnAe+6yycCPwlXGcrac7iotg5ljDF1Vljb+EUkXkQWATuAKcBaYK+qFrubbAHalrPvOBHJFZHc/Pz8cBbTGGNiSlgDv6qWqGpfoB0wADgx2Gbl7DtBVXNUNScjIyOcxTTGmJhSK6N6VHUv8AUwCGgiIgnuqnbAttoogzHGGEc4R/VkiEgT93kDYDiwEpgBXOxudiXwQbjKYIwxJlBC5ZtUWSYwUUTicX5g3lbVj0VkBfCmiPwZWAi8EMYyGGOMKSNsgV9VlwD9gixfh9PeHxGPfv4dt4w4IVKHN8aYiIupO3cBnpy+JtJFMMaYiIq5wG+MMbHOAr8xxsQYC/zGGBNjLPAbY0yMscBvjDExxgK/McbEGAv8xhgTYyzwG2NMjLHAb4wxMSaqA7/Hplo0xpgAUR34izyeSBfBGGPqnKgO/MUlVuM3xpiyojvwW1OPMcYEiO7AX2JNPcYYU1Z0B36r8RtjTICoDvxFVuM3xpgAUR34S6zGb4wxAaI68BfZqB5jjAkQ1YG/2MbxG2NMgLAFfhFpLyIzRGSliCwXkd+5y+8Tka0issh9jApXGWwcvzHGBEoI43sXA7eq6gIRSQfmi8gUd91jqvr3MB7bKYC18RtjTICwBX5VzQPy3OcHRGQl0DZcxwvGxvEbY0ygWmnjF5EsoB/wjbvoBhFZIiIvikjTcvYZJyK5IpKbn59fpeNa564xxgQKe+AXkTTgPeAmVd0PPAN0BvriXBH8I9h+qjpBVXNUNScjI6NKx7bhnMYYEyisgV9EEnGC/uuq+l8AVd2uqiWq6gGeAwaE6/je7JyXD+rAiZmNwnUYY4ypV8I5qkeAF4CVqvqoz/JMn80uAJaFqwzeUT2X5nTgopNrtXvBGGPqrHCO6jkN+DmwVEQWucvuBMaKSF9AgQ3Ar8JVgBK3xp8QL+E6hDHG1DvhHNUzCwgWcSeH65hleTt3Ey3wG2NMqZi4czchLvA0H5y8km53fVLbRTLGmIgLZ1NPxHnb+OPjBPUZ4HP/R8t5afaGyBTKGGMiLMpr/N6mHv/TtKBvjIll0R34S6xz1xhjyorqwO/t3E2Is8BvjDFelbbxuzdhXQec4S76EnhWVYvCWbCa4L1zNyE+qn/fjDHmuITSufsMkAj8y339c3fZteEqVE0pKh3VIyiWvsEYYyC0wN9fVfv4vJ4uIovDVaCaVFwSvHPXGGNiWSgRsUREOntfiEg2UBK+ItUc76ieipr4Ve1KwBgTW0Kp8d8OzBCRdTh34nYErgprqWpIcYmHxHhBxH8cvy+Pgg36McbEkkoDv6pOE5GuwAk4gX+VqhaGvWQ1oNijQe/a9eVRJT5oZgljjIlO5QZ+ETlLVaeLyIVlVnV2atBOmuW6rKjEUzqGX8qJ7R5r6jHGxJiKavxDgenAmCDrFKjzgb/Eo6Vj+Mtt6rHZGY0xMabcwK+q97pP/6Sq633XiUinsJaqhgw7oSXtmjYAYFTvTB76ZFXANlbjN8bEmlBG9bwXZNm7NV2QcBjWvSXjznAGJLVvlspLV/UP2MYCvzEm1lTUxt8d6Ak0LtPO3whICXfBwiFY6gZr6jHGxJqK2vhPAM4DmuDfzn8A+GU4CxUuwUb4fLthN698vZEXr8yx1A7GmJhQURv/B8AHIjJYVefWYpnCJliWzt++sZAjRSXk7SugfbPUCJTKGGNqVyg3cC0Uketxmn1Km3hU9eqwlSpM4oM09ZRYG78xJsaE0rbxKtAaOAcnM2c7nOaeeid4G78T+Msb52+MMdEmlMDfRVXvBg6p6kRgNNC7sp1EpL2IzBCRlSKyXER+5y5vJiJTRGS1+7dp9U4hdMFq/MWlgd8ivzEmNoQS+L159/eKSC+gMZAVwn7FwK2qeiIwCLheRHoA44FpqtoVmOa+rhWVpW8wxphYEEoknODWyu8CPgRWAH+tbCdVzVPVBe7zA8BKoC1wPjDR3Wwi8JMqlLtKgtX4vSxLpzEmVlTYuSsiccB+Vd0DfAVkV+UgIpIF9AO+AVqpah44Pw4i0rKcfcYB4wA6dOhQlcMGqGgKRov7xphYUWGNX1U9wA3VOYCIpOHc/XuTqu4PdT9VnaCqOaqak5GRUZ0ilKqoxu+dptEYY6JdKE09U0TkNreztpn3Ecqbu/P1vge87pPNc7uIZLrrM4EdVSp5FVQ0E5c3dcOUFdvZX1DnpxM2xpgqCyXwXw1cj9PUM9995Fa2kzjDZF4AVqrqoz6rPgSudJ9fCXxwPAWujopq/B5Vtuw5zC9fyeWmNxfVVpGMMabWhTIRS1UzcZ6GMzH7UhHxRtI7gYeBt0XkGmATcEkV3/+4VdTG71EoKHIS92zYeai2imSMMbUulDt3q0RVZ0G5U1v9KFzHrUh8BXMsLt68l5M71totBcYYEzExNbC9ohr/7e8uKX1u3bzGmGgWU4E/rpK7c71rbUy/MSaaVRr4xXG5iNzjvu4gIgPCX7SaV9GoHnDa+Y0xJtqFUuP/FzAYGOu+PgA8HbYShVF8nDD91qE0b5gUdH1RidO5a/HfGBPNQgn8A1X1eqAAwL2LN3jkrAeyM9JITwnep3202A38FvmNMVEspCRtIhKPWxEWkQygXk9YmJQQ/LTX7TwIgFqd3xgTxUIJ/E8C7wMtReQvwCzgwbCWKsy8bf3XDvG/ReHmtxYDVuM3xkS3UG7gel1E5uOMvRfgJ6q6MuwlCyNv4O/drnGES2KMMbUv1Bu4tgMz3e0biMjJ3pTL9VGSG/jLS+FgNX5jTDSrNPCLyAPAL4C1HBvwosBZ4StWeB11R+80TK749A8fLSYlIZ64Cm78MsaY+iaUGv9Pgc6qejTchaktefuOANAlI63cbQqLS+hxz2dcM6QTd5/Xo7aKZowxYRdK5+4yoEm4C1KbnrysH6N6t6ZtkwZB16sqhwpLAHh3/pbaLJoxxoRdKDX+h4CFIrIMKPQuVNUfh61UYTYwuzkDs5sD8No1A7n8hW/81ivHbuZKrCCxmzHG1EehBP6JOHPsLqWej98PplmQu3hVoaDIqfHbBO3GmGgTSuDfqapPhr0kERIsrivKETfwVzR5izHG1EehBP75IvIQzsxZvk099XY4p6/4IBk71WdSFmvqMcZEm1ACfz/37yCfZfV6OKcvCRL4Szxa2tRjNX5jTLQJ5c7dYbVRkEgJFtgLiz2lTT3Wxm+MiTblBn4RuVxVXxORW4KtLzOBer1V4gnsry4oKqHQDfzfbT/AB4u2cn7ftrVdNGOMCYuKqrMN3b/pQR7l3/lUz2S3SKN3W/+cPcUeZfPuI6Wvf/fmorK7GWNMvVVujV9V/+0+naqqs33Xichplb2xiLwInAfsUNVe7rL7gF8C+e5md6rq5CqUu8bExQl/GNk9YCz/XybX6zx0xhhTrlAasP8Z4rKyXgZGBln+mKr2dR8RDfpe1oxvjIklFbXxDwZOBTLKtPM3AuIre2NV/UpEsqpbwNpgHbjGmFhSUcRLwmnLT8C/fX8/cHE1jnmDiCwRkRdFpGl5G4nIOBHJFZHc/Pz88jarEZXMwW6MMVGlojb+L4EvReRlVd1YQ8d7BngA5z6AB4B/AFeXc/wJwASAnJycsGbIjwsylt8YY6JVKDdwJYvIBCDLd3tVPe4buFR1u/e5iDwHfHy87xEO1tRjjIkloQT+d4BngeeBkuocTEQyVTXPfXkBTsrniLO4b4yJJaEE/mJVfeZ431hE3gDOBFqIyBbgXuBMEemL09SzAfjV8b5vOFhaBmNMLAkl8H8kIr8B3sc/SdvuinZS1bFBFr9wfMWrHcEStRljTLQKpZHjSuB2YA4w333khrNQtc23xj/1ljOCblPisRnYjTHRodLAr6qdgjyya6NwtcU38Hdpmc6zl58csI13Ri5jjKnvKm3qEZErgi1X1VdqvjiRUXY4Z3JC4P1pRSUeUhIrvW/NGGPqvFDa+Pv7PE8BfgQsAKIm8CeUmWwlKSHwQqioxJp6jDHRIZR8/L/1fS0ijYFXw1aiCCjbudskNTFgG29Tz7Kt+/jXF2u457yetG6cUivlM8aYmhRKjb+sw0DXmi5IJMWVGc6Z2bhBwDZHi53AP+apWajC5KU/sOHh0bVSPmOMqUmhtPF/hDPuHpzO4B44N3VFjbI1/qYV1PjVWnyMMfVcKDX+v/s8LwY2quqWMJUnIuLLtPGLCG+OG8RrX2/k4yXOjcaFxR48ZYZ0Xv/6Ap7+WeAIIGOMqctCaeP/0ve1iMSLyM9U9fXwFat2BbuBa1B2c6av2lH6evSTMwNy+kxamsfTYS+dMcbUrHLH8YtIIxG5Q0SeEpER4rgBWAf8tPaKGH7lpWzw/T3wKBwt8ZCd0TDotsYYU19UVON/FdgDzAWuxbl7Nwk4X1WjahLa8gJ/sHTN6/IP+b0u8ajl+jHG1CsVBf5sVe0NICLPAzuBDqp6oFZKVovKy9UTSjzfd6SI+Djh63W7GNGjFWJ5f4wxdVxFgb/I+0RVS0RkfTQGfQgczlm6PIQgXlhcwm//s5DcjXvon9WUJy7rR5smgcNBjTGmrqgoV08fEdnvPg4AJ3mfi8j+2ipgJKUmVT7oqbhEWbZtHwDfbtjj1yFsjDF1UbmBX1XjVbWR+0hX1QSf541qs5CR0q5p5TX3ohKP3w/EXf+rE3PLGGNMuWzuqQoM6NSs0m3mrttFSpncPqt+cC6I1uYfpMudk1m/81CwXY0xJiIs8FegVaMUZv5+WIXb/PH9ZWzbV+C3bOTjMwF4b/4Wij3KR4u3ha2MxhhzvCzwVyJYps5QrN95iH99sbaGS2OMMdVngb8SifGhfUSje2f6vV6ZFxP938aYeqgq2TmjUrdWaZzbKzNgeWJ8aOPyy14Z+O5lid2MMXVJ2Gr8IvKiiOwQkWU+y5qJyBQRWe3+bRqu4x+vz28eys1ndwtYHmqNPzkhjnvH9Ch9fe+Hy2usbMYYU5PC2dTzMjCyzLLxwDRV7QpMc1/XaaEG/qSEOBJ8tt1xoDBcRTLGmGoJW+BX1a+A3WUWnw9MdJ9PBH4SruPXlFDz8CQnxJEQQrK3yUvzeGXuhuoXzBhjqqi22/hbqWoegKrmiUjL8jYUkXHAOIAOHTrUUvGqLqmCwA+wv6CIzbsP85vXFwBwxeCsWiqZMcb4q7Odu6o6AZgAkJOTU+e7R5MT4gMmbfdShStemMeizXtruVTGGBOotodzbheRTAD3b71MbNM/qykdmqX6LUtKiCM+rvyP04K+MaauqO3A/yFwpfv8SuCDWj5+jWjduAEvX9Xfb1lyQhyJlpffGFMPhHM45xs4k7icICJbROQa4GHgbBFZDZztvq7zlt9/DoOzm5e+9niU4jLz7zo1/uCB/7Gp34e1fMYYczzC1savqmPLWfWjcB0zXBomJ/i135d4lK4t0/y2SYqPC3nop6+3vt3EaV1a0K5pauUbG2NMDaiznbt1mUc1YKYtETmuKRifnLaajs1T+cN7S2nfrAGje7fhujM707hBYk0X1xhj/Fjgr4JgwbmoxFPuqJ5gHp1yrPln8+4jPPvlWvYXFPHgBb1rpIzGGFMeS9IWIm++neEntuQen9QMXkUlnmrn5Nl3uKjyjYwxppos8IdIcaL6ladmkZ4SWOM/WuyhZXpytY4xaWkeFz8zp1rvYYwxlbHAX0MGZTena6t0zu/bxm/5Se0aH9f75G7cU5PFMsaYABb4Q+RtxhEC2/EX3n02vdo6Ab5BYrzfuso6fIOtzho/ie+3H6haQY0xphIW+EP027O60jApnt5BavDxPp26Zdv5K8rfA9C3fZOgyx/4eAUA107M5ffvLj7O0tae+Rt3s2aH/UgZU59Y4A/R4M7NWf6nkUFH9MT7DO309gWUrnMD/18u6BX0fTu1SAu6fN763WSNn8TUldt5O3cLa3YcZH9B3ev8veiZuQx/9KtIF8MYcxws8FeDN977NueM6NHabxvvuuYNg3f8ajlDgQqLPX6vhz/6JZf9+2t2HSzk/Kdns3n34aoW2xgT4yzwV0OcG/l9A//wHq0YlN0sYBtfqUnH+gEuPLkd1w7pFNLxVuTt55Q/T2Xx5r08P3NdVYtdI/IPFLJpl/34GFMfWeCvhmd+djL9s5oGtOP7dgAnJ8SX3a10+8k3ns6Qri2467zA+wIqM3HuRuas2UlBUQmPTvmegqISvvhuB/NraVRQ/79M5YxHZtTKsYwxNcvu3K2GET1bM6Jn64DlHrf55qVf9OeNeZsC1nuvEFqkJ1Xr+P/3/DfccW53npy2GgGemLYagA0Pj67W+xpjopvV+MPA22pfXtI27/qECvL3h6qgyOkL8AZ9Y4ypjAX+cHAje3m5e0b3zgQCx/wfr/bNGhCkC8EYYypkgT8MvEM6y8bkFmlO0879P+7J/LuG0yCpeoE/ToLdTmaMMRWzNv4w8M7RIiI+o/qVz28eyu5DR0mIj6N5WvXy+qQmxbNx12GKPHVjOuINOw+R1aJhpIthjAmB1fjDwDs2XwSucYdqntKxGc0aJtGlZfAbto7XiB6tACevf217d/6WgGWvfb2x1sthjKkaC/xh4K2Dx4mTvG3Dw6PJqGbmzrK8nbpBj6/KwcJiNu8+zM1vLWLy0jwANu06zKgnZrLzYGG1jn3bO4EpJMpORWmMqbss8IfBsZtxw9cCX1RSfuB/7euN9Lr3M07/2wzeX7iV37y+AICnZqxmRd5+Plv+Q9D9/rtgC6urmBzOU93JCIwxtcYCfxgkJTgf63HMxOjnlrO7Mbp3ZrnTMD53RU6Fbft3f7A8YNm/v1xL3r4CANKSE5i9ZidHiz0s27qPg4XFznHfXszZjzl5dw4VFrN9f0HIZS6xGr8x9UZEOndFZANwACgBilU1JxLlCJfHL+3LK3M30qdd8MyblbnxR10BeGn2eu7/yMnSGR8nlHiUUzs35+werXhx1vqA/QZ0asa89buDvudDn6wqff67NxcB8ItTs3h5zgZuGt41oCnqgn/N5vvtB0O+Gcxq/MbUH5Gs8Q9T1b7RFvQB2jRpwPhzuxNX1Sq/66rTOtHQHfJ59+gTAWemLyBgKOjvR57APy7pc1zv//KcDQB8tnw7f3x/md+677cfPK73shq/MfWHNfXUcd5w2iTVuQfAm7Xz4Yv8J2X/zZldaJ5WtRQQK/P2+70e+ODU0uePfLbKb52nnABfQZeDMaaOiVTgV+BzEZkvIuOCbSAi40QkV0Ry8/Pza7l4kdO7rf9EL94WFG97v7fG3zI9hfRk/5a6lCAJ4api+/5jo36enrGWfUeOzQMw7B9fBN3HmnqMqT8idQPXaaq6TURaAlNEZJWq+s3moaoTgAkAOTk5UR9VGjdIZN+RIl7/5UC/5d67gBs1cL4q39E8ZZuSqtu0VJ4HPl7B/I17WL/zULnbWFOPMfVHRAK/qm5z/+4QkfeBAUBMT+M05ZYz2L6vkEYp/iN5vBXptGRnue8ELZXN51tVifFCUcmxQB7shq2ySqzGb0y9UetNPSLSUETSvc+BEcCyiveKfi3TU4LO59u6cQoADZOdZhzfSVw6BUmR8PnNZ1S7LI0bHH9fwaQlefywL/Thn8aYyIlEG38rYJaILAbmAZNU9dMIlKNeeOOXg3j0p31o1zSVu8/rwYu/6F+6bsLPTwnYvlur9Nosnp+LnpnDzW8tIm/fEQCWbd3HPz7/jn2Hi3h3/hYKi0tQVR75bBXnPPYV328/wIadh1i2dV/EymxMLJLy5nytS3JycjQ3NzfSxaiTssZPAvwnX/EuK0+jlAT2Fzg3bV19Wifeyd3MAfcmLnCyiD45th//99w31Sqbt99i+IktmbpyBwAzbjuTYX//AnCuWLz9BhseHs3RYg/xccLho8X86tX5NG2YxOUDOzK4c/NqlcOYWCUi84MNmbfhnPVct1ZpjB3QIeTt05MTmHTj6ZzW5VgwHeXOD+DlUTi1c4sK3yenY9NKj+UdDeQN+kBp0AfYuudI6fNNuw7T7a5PuO61+Tw3cz1z1u5i0pI8xj73daXHMcYcHwv89dznNw/loQt7V7jNK1cP4NxezhSRN5zVhfbNUhl2QsvS9WUnAvNeBd5+zgkAXDm4Y8B7pqVUf1zAUZ8RSt75ez9fsT0g46iq4vEoy7ftoz5coVbm8NFissZP4u3czZEuiolRlo8/Ck2/dSgHCoo5/+nZAJzRLYMzumWwYNMe+gZJI1F2dJC403pdP6wL1w/rQkFRCRPnHku7fPEp7bh8UEe++K527q/ode9ntG3agO+3H+ShC3uzYOMeLjqlHe2aNqB1oxQ27zlCs9QkGqcmst7tMxjTp02tlK0qtu11OsH/NWMNP81pH+HSmFhkgT8KZWc4Of+fvfwUPlq8rXT5yR2ONc+MPimTZ79cy88GdfDbZnTvTH4zrLPf+yUnHLskGDugPQ+c34uNuw8HPfZDF/bm9K4tGPLXGTVyLgCHjpaUppB49su1bNx1mHeCDDFtmBTPoaMlAIzp0wZVZcxTsxic3Zw7RzkpL6SSuSq/++EAj035nifG9iW5hm6IK8t7E15COXMyGxNuFvij2MherRnpNvGUldm4Abl3nQ1A+6apAFx1Whb3jukZsK1vsHzowpMASCoTtLwJ4oad0JLWjVO4/ZwTeOSz72rkPHwdKiwpf93RY+veyd3M5KV5LNu6n2Vb9/PS7A0Ue5RrhnRiVO/WbNlzhPwDhfRu25g+7Zu4713MOY87t5Ns2nWYrlUcIZU1fhKX5rTnrxefFHS9NxtqQpjuwzCmMhb4DT/u24Z1Ow/yy9Ozy93mDyO7c4pPh27ZieRfuDKHtOSE0h+JET1a8chn3/F/Azvwn282ATD1lqE8/Mkqpq7cXuWyhjqJzO3vLvF77Z0o5oVZ63khSGbTsryjnnYfOsrJD0xhTJ823DCsCx2apbJu50Ey0pLZsOsw3TPTSUtKKL1r2pvL6K3czWRnNGREz9YB91scKHA6vROtxm8ixAK/ITE+jtvP6V7hNted6d/8U3aa9/g48bsy6NoqnY9/O4SurdL4zzebaN0ohS4t07h3TA+WbNnLjgPVmwUs3C56Zg7gNH0BfLR4m1+TmK+uLdN47dqBpCTEs2HXsbQWD32yioc+WcUrVw/gihfn8fdL+nDxKe1KRzuV/fE0prZY4DdVkpLoX1uNC9J23stNOPfPsf3o18FpTmnfLJV5fxzO5KV5pTOD+Xrn14MBuOTZuYAzqc3R4sil/pzkTltZkdU7DjLwwWmAM89yWVe8OA9wpqxs26QBS7Y4N6yt2OafFXX19gN0aZmGiDBzdT4Z6cl0b92ommcAW/ceoW2TBtV+HxM97FrTVEmT1CQeu/RY/v+K8gaN6dOGdm4/gleHZv6vP73pdD6/+Qz6ZzWjf1az0uVn+Qw79frT+YH9EOXx/uB4n3dr5T/Z/UtX9S+7S7VUNtp07HNfs3DzXsDJu5Q1fhJZ4ycxfdV2zn7sK8Y8NYus8ZP4+QvzGPn4TD5dlsfIx7/iiamrKSrxoKr855tNPD9zHXPW7GSXT9PX7kNHKS6TH3vO2p2c9vB0Xpq93m/dzoOF5Ae56vrntNV+k/moKi/NXl96N7aJDlbjN1V2Qb923PyWM/F6fCWjZcrq2aYR153ZmQFZzRjWPTC4e2cHU/wjaWbjFK4YnMXCTXt5f+FWhnRpwaw1O8s9zrVDsrn+P86VxQmt0jlYWMz32w/yj0v6kBAvdGoemO+orLTkhNIO2Zqw2A38vq5+2bkzfdlW/6uAX7/mlH3VDwd4bOr3Qd/vujM7838DOnD6346NpMpIT+a/153K0zPWAHD/RyuYOGcDTVKTyM5oyH8XbAVg3p0/4tsNe+jYPJUXZ68vXT6kSwuuOb0ThwqLuf+jFXy2/AfeHDfY77h7Dh3lSFEJbZo0IPuOSVwxOMVhHAMAABJOSURBVIv7fnzsR3ne+t08NWMNL1yZ49efsetgIekpiaVTlJraZykbTLUESxlRE+7/aDkvzd7AH0edyL4jRYzqnUlWi1RSk/zrKrPX7ORnz/unlmiRlszEq/uzLv8QY/q04e1vN/P795ZwQb+2PPCTXhwqLKZVIyf53f6CIk667/OA42dnNORvF53Exc/OpWFSPMmJ8ew+dLTK5+OdOtPr9yNP4G+f1vyop3A6tXNz7hnTg+mrnDuxH5vyPUUlysK7z6bfA1MA59/Bmh0HyW7RkOw7JwMw6cYh9GzTmE+X/cDREg83vrGQnI5Nefe6U/3e/4d9BXy//QBndMuo3ROLYuWlbLAav6mTvJ3HInCbewdxMKd1acHUW4Yy/NEvS5dNvnEILRul0LON08dwdo9WdJ+dzoUntyUtOYE0nwlsGqUkcsXgjrzi3qDWp11j/vyT3nRtlVbafHXT8G788ozscnMg9chsxAp3FrNnLz+5tJb+z7H9uO2dxQzKbs6vhmb75T7q275q8zF7ndW9ZWkAri1z1u5i5OMzA5Z7gz4EzxM1+slZnNOzFZ8tPzaaK3fjHm57ZzHZGQ2Zu3YXNw3vykXPOP06o0/K5PKBHVmwaQ8/OrElHZqlIggNkuLZvPsw89bv5tZ3FnPtkE7cMepEdhwoIDkhnv8t3EpivPDzwVnlnsP8jbuZsSq/wn9Ty7buo2PzVNLLpEj3VVTi4dv1u5kwcx1PXNqPoyWegHmrj9dX3+fTICner6kzXCzwm2qp6WYQL2/LUSgXpF1aprH+oVHc9+FyJs7dSKMG/v9hmzZM4tObyk9Xff+Pe3JW95YM7NQ8YC5j3yuZ07u2YNnWfUy5ZSgbdh7ik2U/sPNgIU9c1o/T/zadq0/rxMhemVx9Wic+WZbHmD5tOO+kTFRhuU9H7uOX9mVwdmDiufSUBA4UFDPrD8MoKCph+KNfcfs5J7Bx1yHezvW/Ye2hC3uz6+BRRj0ZGIh9Xda/PevyDzFvw+4KtwPnx6h9s1S/0UuvXjOAz5dv59WvN1awZ+V8g76X7zwPM1cfa66btCSPSUucTvWK7gV5ftZ6ng8yNHfehj18tHgbPds0Yvm2/Qzs1Iy9h4vYffhoab9GUkIczdOS6N46nRXb9pOWkkB2izQ+X/EDT89Yy4mZjfjkd6fz1rebSIiLo2urNDLSk8nbV0Dvto15aPIqXpztHPtPH6/gvQVbGH9ud87u0YoZq3awcPNenri0L+CkJklNSqDEo359YVv3HkFw5uj2eLR0EEBNXz0HY009plo27TrMsm37AhK9VdefP17B87PWc+eo7ow7o3PlO+CMoT9SVELD5LpXn1m2dR/n/XMWQ7tlMPHqAUBg7XjqLUNZs+MAI3sFfpbf/XCABz5ewXVndmbrniP8tL+T6uGTpXl8suwHpq/aEfQH+KVf9GfNjoP8ZfLKCsu39sFRCPD0jDX8Y8qxvoTF94ygcWpiuVc795zXgz99vKLC9zbOwIKFm/YiAoOzmzN2QAd++8ZCANo0TmGbz1wWL1yZQ6+2jXl17kYaJMUz5qQ2dGieWt5bV8iaekxYdGieWuV/lBU5zr5iwJl6si4GfXA6s+8c1Z2LTm5XumzarUNJio/j9L/NoHvrdLq0TKNLy7Sg+5/QOp3Xrh0YsPzc3pmc2zsTVeXt3M0UFnu4rH8H4gQ27DpEl5bpnHlCBkO6tqBRg0T2HynCo0pW84bc/NYixp2RTYu05NKa6MGjzo/H2AHtyUhPoXFq+c0dAJcP6khhsYe/frqqdNmNZ3XhyelOp/KS+0b49aFc0K8t7y90OpD/dvFJnNyhKX98fynfrN/NY5f2KR0scDyyWzRk2q1Duerlb4Pmj3r/N6fSt30TXv16I/d8sPy4378mLNzkdOirOk1mc9buKl23rcwERtdM9K/k9shsVOP/x+rm/xJjXPXggjQkIhJw5dLZzan0/BU59O1QvTZ/EeHS/v7pubu0TC9dd2Kmcz+A73j+CVcEVAQZd3o2cSLcNLyrX66ihXefzbvztzAwuxkntWvCrW8v5r0FW0hKiOO6MzvTqEECf3x/GY9cfBKX5LTn5I5N2bLnCI1SEnn4wt4cKChm4twN3H9+Tx6+qDczVu3gnJ6tERFeu3YgJR4lJTGer9fuZvGWvaz64UBpef98QS8mL8kLmp/prxf15pJT2iMiZLdICxr42zRpgIhwxeAsLuvfgd73fcbYAR14ec4GAH5zZmfO6dm6NKlhRZ4c24/Hp3zPup2HuOjkdry3oPJpSc87KZOjxR6yM9J49su1lW5fVrBRb9VlTT2mTnpw8komfLWOO87tzq+GhtbUY2qPN25479ZWVbbsOUL7ZjVTM12Xf5Avvsvn6iGdANixv4AVefv5fMV22jVtwBldM2jZKJmW6Sml+xQWl/DNut20bpxCekoC6SmJHCwoLp2+1OtosYeEOOH9hVtJTozjvJOcTK6bdx/moU9WcvPwbjRPS+aSZ+eQf6CQ/QXFvHrNAPL2FfDTnPZ4PMpzM9dxaf/2TFmxnfU7D/GvL44F9EtOaVf6I3XL2d24YViX0pQed/1vKavyDpC7cU/p9nPvOIvNu4/w03/PDfgcUhLjWPXAuVX+HMtr6rHAb+okb+Aff253fm2B30SQx6Olgbs8c9bsZNaandz4o66kJMYzdcV2slqkll51lTVzdT7dWqVzqLC4NJtuYXEJHyzcRtOGSew5dJTt+wvo1a6x39wZx8va+E29YllsTF1RWdAHOLVLC07tcmzWuuE9WlW4/eldA+9VSE6IL+20Dze7dc7USd67Oi11sTE1LyI1fhEZCTwBxAPPq+rDkSiHqbuuO7MzhcUeLh8UOO2jMaZ6ar3GLyLxwNPAuUAPYKyI9Kjtcpi6LTUpgTtHnUhKYnhmwTImlkWiqWcAsEZV16nqUeBN4PwIlMMYY2JSJAJ/W2Czz+st7jI/IjJORHJFJDc/v3Ym9TbGmFgQicAfrLcuYEypqk5Q1RxVzcnIsGx9xhhTUyIR+LcAvmOW2gHB57QzxhhT4yIR+L8FuopIJxFJAi4DPoxAOYwxJibV+nBOVS0WkRuAz3CGc76oqpHJnGSMMTEoIuP4VXUyMDkSxzbGmFhnd+4aY0yMqRdJ2kQkH6jqFEAtgPJn445Ods6xwc45NlTnnDuqasCwyHoR+KtDRHKDZaeLZnbOscHOOTaE45ytqccYY2KMBX5jjIkxsRD4J0S6ABFg5xwb7JxjQ42fc9S38RtjjPEXCzV+Y4wxPizwG2NMjInqwC8iI0XkOxFZIyLjI12emiAi7UVkhoisFJHlIvI7d3kzEZkiIqvdv03d5SIiT7qfwRIROTmyZ1B1IhIvIgtF5GP3dScR+cY957fc3E+ISLL7eo27PiuS5a4qEWkiIu+KyCr3+x4c7d+ziNzs/rteJiJviEhKNH7PIvKiiOwQkWU+y477uxWRK93tV4vIlaEeP2oDfxTP9FUM3KqqJwKDgOvd8xoPTFPVrsA09zU459/VfYwDnqn9IteY3wErfV7/FXjMPec9wDXu8muAParaBXjM3a4+egL4VFW7A31wzj1qv2cRaQvcCOSoai+cXF6XEZ3f88vAyDLLjuu7FZFmwL3AQJwJru71/lhUSlWj8gEMBj7zeX0HcEekyxWG8/wAOBv4Dsh0l2UC37nP/w2M9dm+dLv69MBJ3z0NOAv4GGdeh51AQtnvGycB4GD3eYK7nUT6HI7zfBsB68uWO5q/Z45N0tTM/d4+Bs6J1u8ZyAKWVfW7BcYC//ZZ7rddRY+orfET4kxf9Zl7adsP+AZopap5AO7flu5m0fI5PA78HvC4r5sDe1W12H3te16l5+yu3+duX59kA/nAS27z1vMi0pAo/p5VdSvwd2ATkIfzvc0nur9nX8f73Vb5O4/mwB/STF/1lYikAe8BN6nq/oo2DbKsXn0OInIesENV5/suDrKphrCuvkgATgaeUdV+wCGOXfoHU+/P2W2mOB/oBLQBGuI0c5QVTd9zKMo7zyqffzQH/qid6UtEEnGC/uuq+l938XYRyXTXZwI73OXR8DmcBvxYRDYAb+I09zwONBERb2px3/MqPWd3fWNgd20WuAZsAbao6jfu63dxfgii+XseDqxX1XxVLQL+C5xKdH/Pvo73u63ydx7NgT8qZ/oSEQFeAFaq6qM+qz4EvL36V+K0/XuXX+GODBgE7PNeTtYXqnqHqrZT1Syc73G6qv4MmAFc7G5W9py9n8XF7vb1qiaoqj8Am0XkBHfRj4AVRPH3jNPEM0hEUt1/595zjtrvuYzj/W4/A0aISFP3ammEu6xyke7gCHPnySjge2At8MdIl6eGzmkIzuXcEmCR+xiF07Y5DVjt/m3mbi84o5vWAktxRkxE/Dyqcf5nAh+7z7OBecAa4B0g2V2e4r5e467PjnS5q3iufYFc97v+H9A02r9n4H5gFbAMeBVIjsbvGXgDpx+jCKfmfk1Vvlvgavf81wBXhXp8S9lgjDExJpqbeowxxgRhgd8YY2KMBX5jjIkxFviNMSbGWOA3xpgYY4HfhI2ItBORD9zMgetE5CkRSY50uaKBiNwnIre5z38hIm2OY98fS5RkqzVVY4HfhIV7A85/gf+pk22wK9AA+FsNvX98FfZJqHyr8Anj8X+Bk+IgJKr6oao+HKaymHrAAr8Jl7OAAlV9CUBVS4Cbce5ATHNrqU95NxaRj0XkTPf5CBGZKyILROQdNy8RIrJBRO4RkVnAeBFZ4LN/VxHxzeXjXf6FiDwoIl8CvxORMW7u9oUiMlVEWrnb3efmSP/CvTq50ec97hYnJ/4UcXLEe2vanUXkUxGZLyIzRaR7kOPfJyITRORz4BVx5hR4RES+dXOr/8rdLlNEvhKRReLkoj/dXX7Q570uFpGXy7z/xUAO8Lq7b4My628UkRXusd50l5V+9u4+3scRERkqIg3dz+Jb93M6v+Kv2tQ3Ea0BmajWEyezYilV3e/m2+lS3k4i0gK4CxiuqodE5A/ALcCf3E0KVHWIu+1wEemrqouAq3BynAfTRFWHuvs0BQapqorItTgZP291t+sODAPSge9E5BmcPPgX4WRBTQAW+JzXBODXqrpaRAYC/8L5wSvrFGCIqh4RkXE4t9z3d5u9Zrs/ChfipBv+i3s1k1reZ+RLVd8VkRuA21Q1N8gm44FOqlooIk2C7N/X/VzGuJ/FHJy7Z6er6tXuPvNEZKqqHgqlTKbus8BvwkUInikwWEZBX4NwJs6Z7bQWkQTM9Vn/ls/z54GrROQW4FKcySiC8d2nHfCWOEmwknBy3ntNUtVCoFBEdgCtcFJkfKCqRwBE5CP3bxpOArF33HKCk14gmA+9++PkUznJramDk1isK05uqRfFScD3P/fHrCYswbka+B9O2ocAItIVeAQ4S1WLRGQETlK829xNUoAO+E+CY+oxC/wmXJbj1JRLiUgjnGD6HdAL/6bGFO9mwBRVHVvO+/rWOt/DmYFoOjBfVXeFsM8/gUdV9UO3aek+n3WFPs9LcP5/lPdDFYeTJ75vOevLO74Av1XVgGRaInIGMBp4VUQeUdVX8P/xTCm7TwhGA2cAPwbuFpGeZY7ZEHgb+KWqejM7CnCRqn5XheOZesDa+E24TANSReQKKO2M/QfwlFv73QD0FZE4EWnPsdr618BpItLF3S9VRLoFO4CqFuBkI3wGeCnEcjUGtrrPQ5mjdBYwRpy5X9NwAinqzIGwXkQuccspItInhPf7DLjOrdkjIt3cNvWOOHMOPIeTfdU7r+p2ETlRROKAC8p5zwM4zVN+3H3aq+oMnGacJkBamc1eAl5S1ZllyvhbcS9lRKRfCOdl6hEL/CYs1Mn+dwFwsYisBnYBHlX9i7vJbJxmlqU4sy4tcPfLxxml8oaILMH5IQjoNPXxOk6t+PMQi3YfTvPMTJyp+io7j29x0uIuxhmllIsz0xPAz4BrRGQxzhVOKJ2gz+OkGl4gzkTb/8a5sjgTWCQiC3GulJ5wtx+PMwXhdJxsjsG8DDwbpHM3HnhNRJYCC3Hmrd3rXen+2FwMXO3TwZsDPAAkAkvcMj4QwnmZesSyc5paISKn4qSivVD9Z9Kq7vveBjRW1btr6j2DHCNNVQ+KSCrwFTBOVRdUtp8xdZUFflNvicj7QGecTslKa+/VOM5/cDqcU4CJqvpQuI5lTG2wwG+MMTHG2viNMSbGWOA3xpgYY4HfGGNijAV+Y4yJMRb4jTEmxvw/n1Jwm5jK9V0AAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "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 }