{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# Heap\n", "\n", "La structure *heap* ou [tas](https://fr.wikipedia.org/wiki/Tas_(informatique)) en fran\u00e7ais est utilis\u00e9e pour trier. Elle peut \u00e9galement servir \u00e0 obtenir les *k* premiers \u00e9l\u00e9ments d'une liste."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["<div id=\"my_id_menu_nb\">run previous cell, wait for 2 seconds</div>\n", "<script>\n", "function repeat_indent_string(n){\n", "    var a = \"\" ;\n", "    for ( ; n > 0 ; --n)\n", "        a += \"    \";\n", "    return a;\n", "}\n", "// look up into all sections and builds an automated menu //\n", "var update_menu_string = function(begin, lfirst, llast, sformat, send, keep_item, begin_format, end_format) {\n", "    var anchors = document.getElementsByClassName(\"section\");\n", "    if (anchors.length == 0) {\n", "        anchors = document.getElementsByClassName(\"text_cell_render rendered_html\");\n", "    }\n", "    var i,t;\n", "    var text_menu = begin;\n", "    var text_memo = \"<pre>\\nlength:\" + anchors.length + \"\\n\";\n", "    var ind = \"\";\n", "    var memo_level = 1;\n", "    var href;\n", "    var tags = [];\n", "    var main_item = 0;\n", "    var format_open = 0;\n", "    for (i = 0; i <= llast; i++)\n", "        tags.push(\"h\" + i);\n", "\n", "    for (i = 0; i < anchors.length; i++) {\n", "        text_memo += \"**\" + anchors[i].id + \"--\\n\";\n", "\n", "        var child = null;\n", "        for(t = 0; t < tags.length; t++) {\n", "            var r = anchors[i].getElementsByTagName(tags[t]);\n", "            if (r.length > 0) {\n", "child = r[0];\n", "break;\n", "            }\n", "        }\n", "        if (child == null) {\n", "            text_memo += \"null\\n\";\n", "            continue;\n", "        }\n", "        if (anchors[i].hasAttribute(\"id\")) {\n", "            // when converted in RST\n", "            href = anchors[i].id;\n", "            text_memo += \"#1-\" + href;\n", "            // passer \u00e0 child suivant (le chercher)\n", "        }\n", "        else if (child.hasAttribute(\"id\")) {\n", "            // in a notebook\n", "            href = child.id;\n", "            text_memo += \"#2-\" + href;\n", "        }\n", "        else {\n", "            text_memo += \"#3-\" + \"*\" + \"\\n\";\n", "            continue;\n", "        }\n", "        var title = child.textContent;\n", "        var level = parseInt(child.tagName.substring(1,2));\n", "\n", "        text_memo += \"--\" + level + \"?\" + lfirst + \"--\" + title + \"\\n\";\n", "\n", "        if ((level < lfirst) || (level > llast)) {\n", "            continue ;\n", "        }\n", "        if (title.endsWith('\u00b6')) {\n", "            title = title.substring(0,title.length-1).replace(\"<\", \"&lt;\")\n", "         .replace(\">\", \"&gt;\").replace(\"&\", \"&amp;\");\n", "        }\n", "        if (title.length == 0) {\n", "            continue;\n", "        }\n", "\n", "        while (level < memo_level) {\n", "            text_menu += end_format + \"</ul>\\n\";\n", "            format_open -= 1;\n", "            memo_level -= 1;\n", "        }\n", "        if (level == lfirst) {\n", "            main_item += 1;\n", "        }\n", "        if (keep_item != -1 && main_item != keep_item + 1) {\n", "            // alert(main_item + \" - \" + level + \" - \" + keep_item);\n", "            continue;\n", "        }\n", "        while (level > memo_level) {\n", "            text_menu += \"<ul>\\n\";\n", "            memo_level += 1;\n", "        }\n", "        text_menu += repeat_indent_string(level-2);\n", "        text_menu += begin_format + sformat.replace(\"__HREF__\", href).replace(\"__TITLE__\", title);\n", "        format_open += 1;\n", "    }\n", "    while (1 < memo_level) {\n", "        text_menu += end_format + \"</ul>\\n\";\n", "        memo_level -= 1;\n", "        format_open -= 1;\n", "    }\n", "    text_menu += send;\n", "    //text_menu += \"\\n\" + text_memo;\n", "\n", "    while (format_open > 0) {\n", "        text_menu += end_format;\n", "        format_open -= 1;\n", "    }\n", "    return text_menu;\n", "};\n", "var update_menu = function() {\n", "    var sbegin = \"\";\n", "    var sformat = '<a href=\"#__HREF__\">__TITLE__</a>';\n", "    var send = \"\";\n", "    var begin_format = '<li>';\n", "    var end_format = '</li>';\n", "    var keep_item = -1;\n", "    var text_menu = update_menu_string(sbegin, 2, 4, sformat, send, keep_item,\n", "       begin_format, end_format);\n", "    var menu = document.getElementById(\"my_id_menu_nb\");\n", "    menu.innerHTML=text_menu;\n", "};\n", "window.setTimeout(update_menu,2000);\n", "            </script>"], "text/plain": ["<IPython.core.display.HTML object>"]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Un tas est peut \u00eatre consid\u00e9r\u00e9 comme un tableau $T$ qui v\u00e9rifie une condition assez simple, pour tout indice $i$, alors $T[i] \\geqslant \\max(T[2i+1], T[2i+2])$. On en d\u00e9duit n\u00e9cessairement que le premier \u00e9l\u00e9ment du tableau est le plus grand. Maintenant comment transformer un tableau en un autre qui respecte cette contrainte ?"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": ["%matplotlib inline"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Transformer en tas"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"text/plain": ["[12, 11, 5, 10, 7, 3, 1, 6, 4, 3, 2]"]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["def swap(tab, i, j):\n", "    \"Echange deux \u00e9l\u00e9ments.\"\n", "    tab[i], tab[j] = tab[j], tab[i]\n", "\n", "\n", "def entas(heap):\n", "    \"Organise un ensemble selon un tas.\"\n", "    modif = 1\n", "    while modif > 0:\n", "        modif = 0\n", "        i = len(heap) - 1\n", "        while i > 0:\n", "            root = (i-1) // 2\n", "            if heap[root] < heap[i]:\n", "                swap(heap, root, i)\n", "                modif += 1\n", "            i -= 1\n", "    return heap\n", "\n", "ens = [1,2,3,4,7,10,5,6,11,12,3]\n", "entas(ens)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Comme ce n'est pas facile de v\u00e9rifer que c'est un tas, on le dessine."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Dessiner un tas"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAA0AAAAIICAIAAADIfRmgAABME0lEQVR4nO3dfXBc1X3/8XPu096rlaxd2U7N+FcmTTNtSoCEtE0LVkpNQv1AjfJU3DjttDOdBtcIx5VJCwQa48Rp6jgJk6EKzZQQOomT4kAQGAUoKaV13ZakcZoGSB+MkzJtbQm0et7V3ofz++P8fH+L/ICtlfbu2X2//vBIlrRz9u537/nsueecK5VSAgAAAOawsm4AAAAAzg8BDgAAwDAEOAAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADEOAAwAAMAwBDgAAwDAEOAAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADEOAAwAAMAwBDgAAwDAEOAAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADONk3YB6RVFk23bWrWhfcRw7jsFVRP1ki/pBPagf1MP0+pFKqazbAAAAgPNgavZUSkkpy+Xy4ODgli1bfN8niTaYlLJSqezfv3/btm1BEOhXJOtGnSvqJ3PUD+pB/aAeRtdPytQROH24x8fHi8XiqlWrHMcx9ImYS0oZRdHx48dLpVKhUDDrDUD9ZI76QT2oH9TD6PpJmToCpymlLrzwwqeeeqpYLPIGaDApZalUWrt2bZIkWbdlgaifDFE/qAf1g3q0QP2IFghwcRyvWLFi2bJlWbelHTmOE8exfgPoE5BZH2Kon2xRP6gH9YN6mF4/wvQAp4VhqJQydAjUUPpoh2EohIjjWJx8A2hmvRDUT+NRP6gH9YN6tEz9tEKAk1LqI27QcW8B6WGvVqtRFKXrsY17FaifTFA/qAf1g3q0Rv20QoBDhpRS5XK5Uqnob9M9dcx6GyAr1A/qQf2gHqbXDwEOdVFKTU1NzczM2LatP9PoL7JuF8xA/aAe1A/qYXr9mB3gWLmTOaVUqVTq7u72fd+2bcuyLMsyZUIo9ZM56gf1oH5QD6PrR7RGgDPiQLckKaVSamJiYmpqSinleZ7ruvptkHXTzgn1ky3qB/WgflAP0+tHcDN71Em/AaanpyuVShiGcRzrFVVZtwtmoH5QD+oH9TC9fghwqItSamZmplwuh2EYRVGSJAZVPzJH/aAe1A/qYXr9mB3gzDrWLUkpNTc3V61Waz++mPK6mNLOFkb9oB7UD+phdP0I0wMcmoHeR0d/djGo9NEkqB/Ug/pBPYyuH7MXMTSts8xOTUukBeau6qegXinrRrUC6gf1oH6wKFq7kFqgfghwS2JeTYdhaFmWbdun/uhM4ji2LCutsCiK0kdoNkmS1E4daM73gFIqSZLmPICnmlck+syi10YtoH7mPUKzoX4WXW2RzDt7cP7JhFn1k0qrJUkSfcspzXXdcykkfafRpq0czYj6ORMC3OILw7BUKk1NTfX09BQKBSml67pCiCRJpJQ//OEPhRDLly8/0w2MdTHVVnz6CE2ryT++RFHkOI5t282cY1K19VMsFnXj0650AfVT+wjNifpZRPPqp/bssYD6UUrVnsGa87lTP0thXiHNa/axY8fEWQtJCGHbdjNHt1ST189ZmFFJptA3x929e/eWLVuGhoa+//3vSymr1Wp/f/8jjzxiWValUhkeHt6/f/9ll102MTEhTjd+qz+vPP3006VSSQiRJMlLL73U398/NDRUrVZrPwY1iWaue9228fHxvr6+xx57TEppWZa+e3TWTTuNefXz7LPPCiEcxxkfH/+7v/s7IcQC6kcppR/h0KFDQogkSTJ8gqfVnK+F1gL1Mzo62t/f/+CDD4ZhuID6kVLGcdzf33/w4EHLsjj/nBez6ic1r5B+8IMfDA8Pb9u27YMf/OCOHTv+6I/+aGJi4uyFpM8zTzzxxPbt27/5zW+KpjzzaE3+WpwdAW7xjY6OXnLJJQMDA29729vGx8d/4zd+QwjxR3/0R8PDw0EQ3HDDDbfccsvs7Kw+FcpXEkL8wz/8w549e9773vdGUSSEiOP4yiuvFELceuutn/jEJ2zb1u+uppLOAG1OuVzu4MGDGzZsWL9+/RNPPOG6rmVZURSppnzrpvXT29tbLpc/97nP9fX1HThwQAjhOM6514/+hXK5PDg42NfXd//99wshmrADFtTPoqqtn+PHj//CL/yCEOLjH//47t27F3D+GR8ff9/73ieEuP3224eHh23bbsISon6WQlpIl19+uVJKl8eLL774zW9+M5fL3XDDDTfffPOZCsmyrJdeeum3fuu3Tpw4sWnTpqNHj0opyXCLjkuoi891Xb2wxbbtO+64w3Gcu+66a2ho6KMf/egv//Ive543NjaW3jR3bGysVCrpLaEty7rwwgvf8IY3eJ43ODioh6zvueeeK6644q677rr//vvvueeeSqXSbJdTHcfJ5XK+7/u+HwRBEATNc41An3RyuVx3d/f4+Pjjjz/+5JNP3n777f39/cuXL/c8rwnfumn96EkzGzZs+Pu//3t9SJVSURSdY/3oixe2bW/cuPHw4cPN86LMQ/0srrR+LMv67Gc/+yu/8it33XXXzp07T5w4IYQ49/rRz33Xrl2u66ZnsLVr1+pn3TxX5KmfJZIWUhzH11xzzTXXXCOE+MxnPvPiiy/6vh9FUalUOrWQhBBxHL/+9a+//fbbN2zY8IUvfOHJJ588duzYT/7kTzbzkzUUAW7x6bObruy5ubmVK1eGYXjVVVddf/31MzMzHR0dejKE/jjy3HPPHT58WH+uzeVyW7duLRaLP/MzP5PekW3FihXXXHNNHMfPPfdcoVDwPC+O4+aZWKCUGh0dffHFF+fm5iYnJ7u7u4Mg0DckqedhdY9i23Yul5udndXfLvjRpqen9WULx3GiKNq1a9fg4ODWrVs3b97sum6znVbS+tFDra997WtXrFiRDrs6juM4zrnXj5Ry3iM0Fepn0dXWz2233aaUmpycHB8fX758uTif+tG/MDc3p4tHn8FmZ2eDIGiep0z9LJ20kJRScRxHUVQul4eGhrZt2yaESGf1nVpIvu+/733vGxoa+uxnP7t169YtW7b80i/9UtNOoDQaAW5p6Sueruu+9NJLnufVVrA+xfT29vb29s77q3K5rE7OdX3ve98rhAjD8Omnn96xY0faMTeJJEmef/75UqnU1dXV1dUVBIHneYt1O7lSqfSDH/zg8ssvr/PNX6lU0uvR+hQzMjKyZ8+eiy++2Pf9ph3Y1/So26kDHq9aP6/6CM2A+llSrus6jrNv376vfvWrL7zwQu2PzrF+5p3Bmq2KqJ/GsCwrl8slSfLd735306ZNtT86bSHpu4v+y7/8i23b73znO5999tlVq1Y11cBtayDALS0ppf6Y4rruvLkj+ttDhw7N+wScy+Vqq1xvEr1mzZorr7yyr69Pn0wb/TTOzLbtt7/97W984xtXr159wQUX9PT0pIPq9RsdHT1w4ID+wFenvXv36g/BcRz39PRs3759586dSqkdO3Y0z3DmaZ3plHeO9XOWR2gG1M+S0ueKG2644YUXXti7d+++ffvSYjjH+jnLGawZUD+NoadzHDx48Od+7uf0liJps08tpCAI3ve+942Ojv78z//8tddeW61WP/3pT3/yk59sts6rBRDgltbMzIye1BmGoW3b886MQoiLLrroggsuSOegpGef9Dc9z7v99tt93//MZz4jhFjE09NimZmZmZyczOfz+iNaR0eH/hBcT27Qn9VKpdLs7GwURXod/oIfZ2pqSpw80WzatOnee+/Vl5NOnDjRzOEmddpGnmP9nOURmgT1s0Qsy3rkkUe6urp++Zd/ed++fa997WtvueWWFStWpNfWxTnUz8zMjN4Q7tQzWJOgfhpAJ7a//du//dmf/dl8Pl+tVtMAd2ohSSl933/Xu9711re+VQhRLBZHRkaybH3raro00AJqt1B6z3ve8+u//ut79+7dtWtXX19fsVgUQuiJBbrue3p6enp60r9Nr1yka5T+53/+57777nvmmWcmJyeTJNGP0FT0vgOac9KinED1pRB96qznBCqlrFQqV1999c6dO9etWyeEqFarei3Yglu4dE79RH7qyMe51M/ZH6F5UD+LK60f27afeOKJhx9++MiRIw899NDP/dzP5fN5cc7nH/0L73nPe973vvelZ7BCodBs4yjUzxKpPRE5jlMul//7v/973759ouZonKmQhBA//dM//Qd/8Ad33nnnN7/5zVtvvVUI0eTP10QEuMWn98URQszNzW3cuPEv//IvL7300re+9a333XefHohWSp04cUKfK/XuvvMeQUrZ3d2t50bs37+/UqlceeWVYRh2dXU988wzXV1dTCY4X8PDw1dddZU42UWd407imUjrJ9XR0VH77TnWT+3/z3sEnC8T66dare7du/fo0aOXXnrpm9/85oceesjzPHHO9aM76Wuuuab2DKZn4jf2CbUCg+onlRaSHp2dnZ3953/+5xUrVqS/cKZC0pun7Ny58/rrr7/00kvf9KY3vec97zHxRhTNj7fiYtKfMK677jr9red5SZJs2LDhe9/7nv50omu9o6Njz549uk9Nt1+qVSgUvv3tb+uPy/39/R/4wAfiONahrbOzUzT3FbGmog9UoVDQZ8906kZTLQRJzauf9BY0H/vYx/T/6JGP86of3WfPewScI9Prx/O84eHhsbExff7Rvex51c+pZzBOPufOrPpJzSsk3eaenp7nn3/e931x8nmdqZD0hdRisXj//ffr2qNslggBbjHpQt+4caP+Vr8NkiSZd+4LgmBgYED/zpmmN+mgJoTQ+xstfdtbmTp5I8Im/wg4r37S1qYFsID6mfcIWABD60dvACGlTM8/+ox0XvWj9xMhvdXDlPpJnfZEpKO//p9XPRGlk+F05VA2S4Rr0osvjuPaKUe1O3Kl/zlvitKp5m0DkVrsxrYFPZ0l61acq3n1I04WQO3/nFf9nPYRcO7MrR958ha6oo7zz2nPYDh3ZtVP6rQnonm/c5ZCqq09LBFG4Bbfqe/VU098rzqP5NT1qmgTi14/p30EtCrqB4tiKQoJi4sROAAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOi4DNflAP6gf1oH5QD3PrpxU28uUuBY2nj3Zr7M9O/TQe9YN6UD+oR8vUj/EBTkrped5pb8mMpaOPtuu6+gt5UtbtOm/UTyaoH9SD+kE9WqZ+jA9wYRiOjo6GYZjeqtnEl8E4+kbFk5OTURRZlmVZVnrYzTr+1E8mqB/Ug/pBPVqmfswOcI7j2La9Zs0aKWWSJEop/W/tACmWiJRSKRVFkeu6+v1g3IcY6idD1A/qQf2gHi1QP8LcAKePfmdn55EjR6anpycmJkZHR0dGRo4fPz4yMlIqlWZmZubm5uI4juM4SZKs29s6LMuybdu27Vwul8/nV65c2dXVZdu2/hBjyhuA+skK9YN6UD+oR2vUT8rUAKdZllUsFoMgyOVytm3rd4Vt277vT09P6zdAFEV8oFkU6XQB/cExl8t1dnYWCoUgCDzPc11XvwQGvQ2on0aifrJur9mon6zba7bWqx9heoATQujPKHoCgeu6uVyuo6MjjmPbtvUboHaBD++BBaudIiClTD/BaPo94DhO7WQCI1A/jUH9COqnDtSPoH7q0Kr1Y3aAk1JaluU4jud5vu/n8/lCoSCE0K9NGIZJkuhZBVm3tHXoY65PN0EQdHR0dHd35/N53/drP8Rk3cxzQv00HvWDelA/qEcr1Y8wPcAJIfT1bP1iRFEkhPA8r1wuV6vVKIqYE7qI0iHo2vNOEAT5fL6rqysIAv0G0GupTEH9NAz1k3VjzUb9ZN1Ys7Vk/Rgc4PTroScNuK7r+74QwnGcIAiq1ar++MIeiYsunSWgP8Toz45BEPi+73meQdMIqJ9MUD+oB/WDerRM/WgGBzhNX892XVcIkY6LRlFUO3uAN8Aiqv0cY9u24ziu6+p3gp4cakrpa9RPg1E/qAf1g3q0WP2YHeDSY+04TvpO0Ouu+eyypGo/x9g1zPr4Qv1khfpBPagf1KM16keYHuA0fbj1EhLbtueVPu+BRZfWd+3bwNxtxKmfBqN+UA/qB/VopfoxPsDVHnH9MjDs3DDpcPS8fw1C/WSI+kE9qB/UowXqx/gAp9Ue91NfA94Mi+hMJW5c6deifhqG+kE9qB/Uo8Xqp0UCnNZirw0ajPpBPagf1IP6wfkyacsTAAAACAIcAACAcQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYxsm6AQAAtKMoimzbzroV7SuOY8cxOAUZ3HQAAMxldHpoAaYff7NbDwCAWZRSUspyuTw4OLhlyxbf95VSWTeqvUgpK5XK/v37t23bFgSBfkWybtR5I8ABANBoc3NzN9100759+xzHIcA1mJQyiqLjx4//zu/8ThAEWTdngQhwAAA0mlLqwgsvfOqpp4rFIgGuwaSUpVJp7dq1SZJk3ZaFI8ABANBoSqk4jlesWLFs2bKs29KOHMeJ41gHOB2gjbuKSoADACAbYRgqpQydg2UofbTDMBRCxHEsTgY4zaAXggAHAEA2pJQ6MRiUG1pAetir1WoURel+Ima9CgQ4AADQdpRS5XK5Uqnob9NdRUyJcQQ4AADQdpRSU1NTMzMztm3rMTn9RdbtOlcEOAAAGo2Vp5lTSpVKpe7ubt/3bdu2LMuyLIMWNBDgAABoNIOCQkuSUiqlJiYmpqamlFKe57muq2Nc1k07V8Y0FAAAYLHoADc9PV2pVMIwjONYrwjOul3nigAHAADajlJqZmamXC6HYRhFUZIkBqU3QYADAKDxzMoKLUkpNTc3V61Wa4ffDHpdCHAAAKAd6X3g9NibQdFNYxEDAACY7yzLLNKsY+4iDN1y9UpZN+r8MAIHAMAS0rc9zboV5y29XYEQQimlrzPW/uhV01scx03+xJMkqZ36ZlaGYwQOAIClEkWR4zi2besxHlN2qQjDsFQqTU1N9fT0FItFKaXrukKIJEmklD/84Q+FEMuXL1+2bNlZHsS27ca0th6GDr8JRuAAAFgKOhOMj4/39fU99thjUkrLsvTd67Nu2tnou7zv3r17y5YtQ0NDzz77rBBidHS0v7//kUcesSyrUqkMDw/v37//sssum5iYEKe7EKnXBDz11FOPPvqoOHnP+CbU5K/F2RHgAAA4PVW3XC538ODBDRs2rF+//oknnnBd17KsKIqaPDqMjo5ecsklAwMDvb29L7300i/+4i8qpW677bavfe1rQRDccMMNt9xyy+zsrE5m8pX0I0gpb7zxxocfflgIkSRJlk/mrJr8hTgLAhwAAKfheZ6+dCgXxLIsKWUul+vu7pZSPv744xs3brzjjjtefvllx3E8z2vm6OC6rl6hqZT68Ic//I53vONP//RPP/rRjx4+fFgIEUXRSy+9lN79fWxs7OjRoy+88MLRo0ePHTsWhqFt23/7t3/77LPPvva1r83yabQ05sABAHAax44dO3r0aBzH9czlmp6e1pdNHceJomjXrl2Dg4Nbt27dvHmz67pNm+GUUlJKx3GUUm9/+9u/+MUvzs7OhmH4Yz/2Y0IIx3H0j/TQ2nPPPXf48GHbtuM4zuVyH/jAB4QQd99995vf/OapqamMn0nrIsABADDf6tWrV69ePTQ0VOfjVCqVKIqEEDoIxnE8MjKyZ8+eiy++2Pf9Zr62qFUqleuuu254ePjaa6/9/ve//61vfav2pzra9vb29vb21v7/gQMHent7L730Ur3cAUuBAAcAwP+nZ3H5vj8wMLAoD7h37149CBfHcU9Pz/bt23fu3KmU2rFjR/Ov0/R9/4EHHjhx4sSXvvSlJ5988sYbb/zKV74SBIH+qZ4Dd+jQodoRuN/+7d++++6777vvvj/+4z+OoqhcLqcXW7GIOKYAAJyGHjlbMH0VUl9D1EFn06ZN99577/Lly4UQJ06cMGIXXCnl0NDQW97yllWrVv3Gb/zGtm3bpqamgiCo3eb3oosuuuCCC6SUSinbtpMk+dd//dc1a9ZMTU2FYXjRRRf9/u//vt5OJetn01I4mgAAnEadgUMHOCllpVK5+uqrd+7cuW7dOiFEtVrVa1EXqZlLonZo8MILL3zwwQd37tw5NDT0pje9qaurSwihZ8jpANfT09PT01P75//+7/+eJMmHPvQhpdTv/d7vRVGkt5HDIiLAAQCwhIaHh6+66ipxcscKvaw160a9Cr3BmxCiWq3efPPN//RP//SmN71pdnZWbyMihFBKnThxQj8jvbtv+rdSSr3wVo81BkGg95bD4iLAAQCw+HSmKRQKOr2lq1mbduWppocGr7vuuvTbzs7Ov/qrvxobG8vlcvl8Xo8sdnR07Nmzp6OjQ7zyplsppdTu3bv11wy/LQUCHAAAS0XvtWHbdvOvV9B0Ozdu3Ki/1duFSCn1RdIkSXTCC4IgXeRxanpLF4I0rNltqKmvwQMAYDQppSnRrVbtfeh1Gjv1Xq6vusjD0HuMmoIROAAA8Aqnhs5Th9ledZFH80/1MxojcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAABoU+ZuVsdGvgAAZEOdlHVD2og+2vpfc9ObIMABAJAJKaXneae9EzyWjj7aruvqL+RJWbfrvBHgAADIQBiGo6OjYRim9xg1MUYYRyklpZycnIyiyLIsy7LSw27W8SfAAQDQaI7j2La9Zs0aKWWSJEop/W/tBT4sESmlUiqKItd1dZ4zcRCOAAcAQOPo9NDZ2XnkyJHp6emJiYnR0dGRkZHjx4+PjIyUSqWZmZm5ubk4juM4TpIk6/a2DsuybNu2bTuXy+Xz+ZUrV3Z1ddm2rQfhCHAAAOBVWJZVLBaDIMjlcrZt61Rn27bv+9PT0zrARVHEgNyiSKe76YHPXC7X2dlZKBSCIPA8z3Vd/RKYFeMIcAAAZECPsekJcK7r5nK5jo6OOI5t29YBrnaBKhluwWqnuEkp0xE4TWc4x3FqJ8MZgQAHAECjSSkty3Icx/M83/fz+XyhUBBC6GwRhmGSJHpWXNYtbR36mOu4HARBR0dHd3d3Pp/3fb92EC7rZp4rAhwAABnQ87F0mIiiSAjheV65XK5Wq1EUsaZhEdXuGJLm5iAI8vl8V1dXEAQ6wOm1wKYgwAEA0FA6T+hJb67r+r4vhHAcJwiCarWqh9/Y43fRpbPc9CCcHvsMgsD3fc/zjJsGR4ADACADej6W67pCiPS6XhRFtbPfCHCLqHYczrZtx3Fc19VJTi9uMCW6aQQ4AAAaLc0KjuOkSU7vG8LY25KqHYeza5g1/CYIcAAAZEXHBb0E0rbtedGNDLfo5q1ITZc1CNNuwyAIcAAAZKI2MegYwWXThkkvp8771yAEOAAAMlObG07NEIS5RXSmiGZcdNMIcAAAZKzFsgUawKQtTwAAACAIcAAAAMYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgn6wYAgKmiKLJtO+tWtK84jh3H4F6M+smW6fVjcNMBIFtGn/1bgOnH3/T2m87042926wGg8ZRSUspyuTw4OLhlyxbf95VSWTeqvUgpK5XK/v37t23bFgSBfkWybtS5on4yZ3T9pCR1gyak305Hjx4dGhoaGBiIosj0j0popKWuH/344+PjxWJx1apVjuNwIm0wKWUURcePHy+VSoVCwawOmPrJnNH1k6JTBICFUEpdeOGFTz31VLFYpANuMCllqVRau3ZtkiRZt2WBqJ8MtUD9CAIcACyMUiqO4xUrVixbtizrtrQjx3HiONYdsA5AZg2iUD/ZMr1+BAEOAOoRhqFSytBLMIbSRzsMQyFEHMfiZAesmfVCUD+N1zL1Q4ADgIWTUuozvkHn/RaQHvZqtRpFUbofhHGvAvWTidaoHwIcAMBISqlyuVypVPS36VIVs7phZMX0+iHAAQCMpJSampqamZmxbVuPqegvsm4XzGB6/RDgAGAhWDmYOaVUqVTq7u72fd+2bcuyLMsyZUI69ZM5o+tHEOAAYGEMOtG3JCmlUmpiYmJqakop5Xme67q6G866aeeE+smW6fUjuJk9AMBQugOenp6uVCphGMZxrFd0Zt0umMH0+iHAAQCMpJSamZkpl8thGEZRlCSJQb0vMmd6/RDgAGAhzDrXtySl1NzcXLVarR0+MeV1MaWdLczo+hEEOACAufQ+XnrsxKCuF03C6PphEQMAtKazTJNP+ypzJ9HrlqtXyrpRLYX6aXIEOAB4FUqpJEls2866Iefn1M41iqJz3HFe32hIa+aleUmS1E5das4+uAXqRykVRZFlWfpZnEtu03cadRynmUOeEfVzJgQ4ADgbHXps29af0Zs2yswThmGpVJqamurp6SkWi7pn0uktSZIf/ehHQojly5ef6U7qrus2srX1aPLhk9aoHymlLokkSaSUP/zhD8VZ60cIYdu2EZm1yevnLMyoJABoPH1OHx8f7+vre+yxx6SUlmXpu49n3bSz0YNnu3fv3rJly9DQ0LPPPitO9lJ33nnn7OxsFEXDw8P79++/7LLLJiYmRE0fpkcjKpXKTTfd1N/f/8EPfvAP//APH3vsMXHytt/Npplfi1aqn9HR0f7+/qGhIcuyKpXKmeonraI4jh944IH+/v6xsbGMn89ZNflrcXYEOACtTNUtl8sdPHhww4YN69evf+KJJ1zXtSwriqImP/WPjo5ecsklAwMDvb29cRxLKZ9++unf//3fD8PQ87wbbrjhlltumZ2d1bFMnmRZVnrBS3fD3/jGN15++eVMn8qrSGegN6cWqJ+RkZHLL79cCPHHf/zHDz30UBAEZ6qf1M033/zpT39aKfWWt7wlDXkZP6UzaNqGvSouoQJoWZ7npZd+FkBHmVwu193dPT4+/vjjjz/55JO33357f3//8uXLPc9r5lO/67p6hV0cx3oe0k033eQ4jud5QogoisbGxtK7d4+NjZVKJf18pZQ/8RM/sW/fPv2jiy+++F3vepcQojmv/TmOk8vlfN/3fT8IgiAImqedrVE/lmV98pOfXLNmzV133XXLLbc88MADfX19cRyftn6UUpZldXd3P/LII9/5znc6OjoOHDgQRVG2z6VVEeAAtKxjx44dPXo0juN65uJMT0/ry16O40RRtGvXrsHBwa1bt27evNl13abtg5VSUkrHccIwtG378ccfj6Lo//yf/zM7OxsEgeM4juMopZIkEUI899xzhw8ftm07juNcLrd161YhhGVZX/va117zmteIkzOfMn5Kp1BKjY6Ovvjii3Nzc5OTk93d3UEQ6Bsi1fOwOojYtp3L5WZnZ/W3C3400+tHCDE6Ovqa17ymUqn87u/+7jve8Y5SqdTT06Nn9Z22fq6//vpvfetbQRD827/927Jly5onUrcYAhyA1rR69erVq1cPDQ3V+TiVSkUPIeggGMfxyMjInj17Lr74Yt/3dQfWzHRQ++IXv/jggw9u3LhxXrjR3/b29vb29tb+f7VadV336aef/qmf+qmOjo5qtaqH7ppKkiTPP/98qVTq6urq6uoKgsDzvMVaM1sqlX7wgx9cfvnlSZLU84Cm148Q4pprrtm7d6/v+3ffffexY8dyuVz6ozPVTy6Xq1Qqa9eu3bx5c7FYTJc/YxFxQAG0Gj1W5Pv+wMDAojzg3r179SBKHMc9PT3bt2/fuXOnUmrHjh3Nv87Odd2/+Iu/0GsJS6VSqVTq7u5Oh9P0HKZDhw7NG4FzXXdmZuY///M/r7/+enGyn242tm2//e1vf+Mb37h69eoLLrigp6dnEVPC6OjogQMHtm3bVv9DGV0/YRj+2q/92le+8pWPfOQjR44ced3rXletVvP5vP7paetn27ZtruvmcrlDhw6tX7/+1ltvXblypR7Sy/SptBoCHICWVefkG93lTE1NiZMd1aZNm+69997ly5cLIU6cOGFKh/Tv//7vBw4cGB4eHhsbW79+/be//e2uri5Vs03rRRdddMEFF6RzmBzH0WNO//Ef/9HX1yeadQKcEGJmZmZycjKfz+dyuSRJOjo69CBcPS+Nft1LpZJesbvg0aPWqB+l1Msvv/zAAw8cP348juMf//Ef7+7uFicr57T1Mzc3Nzg4uH379te97nXr1q27/fbb77777iiKDNqbxggEOAAtq87xGN0BSykrlcrVV1+9c+fOdevWiZOXF5s202jp0E4Yhh/5yEc+9KEPvfTSS1dcccU3vvGNzs5OIYSe4aQ74J6enp6envRvddr4+te/vnnzZtu2m/n6l95aVnNOWpQApy/F6ideT4AzvX48zzt8+PC+ffu++tWvPvHEE3/wB3+QtvxM9TM5Obljx45Vq1a94x3v+N73vnfjjTcqczbAM0iTvicBoHkMDw9fddVV4uSOA67rNv/Yid67QXNdt7u727Ksnp6elStXpjcROnHihH5G89Yo6NsGHD58OAgC27Zr78qABTC6fqrV6qZNmz73uc+9+c1v/vmf//n3vve9ejLfmeonjuNly5YdPHjwN3/zN7u7uz/1qU+9+93vrnMhEU6LAAcAp6f7pEKhoHvftBNq2pWDmh7quO666/S3uq8VQuTz+W9961sdHR16ZKijo2PPnj0dHR3i5D5e6SPoS1133nmnnmLPla+FaY36sSxLKTU8PDw+Pl4oFNKxtDPVjx6tvOaaa/7rv/4riqJCoWDibcSMQIADgLNRJ29kaUonpNu5ceNG/W166UpKqS+eakEQpIs8Tjsg1ITLTk1kev2kl48LhYKoKZWz10+SJLrY6lzDi7PgsALA2ejpUFm34rzFcXzqza/mjf2cfZGHvpHA4reszbRM/ZxaDGepHz1ux9S3JcUIHAC0oNOGhnkjJWefm9/887SwdE6tn1PrgfrJFtEYAADAMAQ4AAAAwxDgAAAADEOAAwAAMAwBDgAAwDAEOAAAAMMQ4AAAAAxDgAMAGIz9xlAPc+uHjXwBYOHUSVk3pI3oo63/Nbf31aifxmuZ+iHAAcACSSk9z5t3J3gsNX20XdfVX8iTsm7XeaN+MtEy9UOAA4AFCsNwdHQ0DMP0no8mdgPGUUpJKScnJ6MosizLsqz0sJt1/KmfTLRM/RDgAGAhHMexbXvNmjVSyiRJlFL639oLNFgiUkqlVBRFruvq/ti4QRTqJ0MtUD+CAAcA50uf/Ts7O48cOTI9PT0xMTE6OjoyMnL8+PGRkZFSqTQzMzM3NxfHcRzHSZJk3d7WYVmWbdu2bedyuXw+v3Llyq6uLtu29SCKKR0w9ZOV1qifFAEOABbCsqxisRgEQS6Xs21b98q2bfu+Pz09rTvgKIoYUFkU6XQlPXCVy+U6OzsLhUIQBJ7nua6rXwKDumHqp5Far34EAQ4AFkyPkegJTK7r5nK5jo6OOI5t29YdcO0CQ/rgBaudoiSlTEdQNN0HO45TO5nJCNRPY7Rq/RDgAGAhpJSWZTmO43me7/v5fL5QKAghdN8QhmGSJHpWU9YtbR36mOu4EwRBR0dHd3d3Pp/3fb92ECXrZp4T6qfxWql+BAEOABZMz6fRnUEURUIIz/PK5XK1Wo2iiDnpi6h2x4c09wRBkM/nu7q6giDQHbBey2kK6qdhWrJ+CHAAcN50f6AnLbmu6/u+EMJxnCAIqtWqHj5hj9ZFl85S0oMoeuwqCALf9z3PM2gaE/WTiZapH40ABwALpOfTuK4rhEivy0RRVDt7iQ54EdWOo9i27TiO67q6J9aT003pejXqp8FarH4IcACwEOm53nGctCfW+z4wdrKkasdR7BpmDZ9QP1lpjfoRBDgAqIc+3eslbLZtz+t66YMX3bwVhem09NofGYT6abBWqh8CHAAsUO0ZX3cDXPZqmPRy2Lx/DUL9ZKgF6ocABwB1qT3vn9oH0BkvojN1scZ1vbWon4ZpsfohwAHAImixvgENRv3gfJm05QkAAAAEAQ4AAMA4BDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADEOAAwAAMAwBDgAAwDAEOAAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADEOAAwAAMAwBDgAAwDAEOAAAAMMQ4AAAAAzjZN0AAADaURRFtm1n3Yr2Fcex4xicggxuOgAA5jI6PbQA04+/2a0HAMAsSikpZblcHhwc3LJli+/7SqmsG9VepJSVSmX//v3btm0LgkC/Ilk36rwR4AAAaLS5ubmbbrpp3759juMQ4BpMShlF0fHjx3/nd34nCIKsm7NABDgAABpNKXXhhRc+9dRTxWKRANdgUspSqbR27dokSbJuy8IR4AAAaDSlVBzHK1asWLZsWdZtaUeO48RxrAOcDtDGXUUlwAEAkI0wDJVShs7BMpQ+2mEYCiHiOBYnA5xm0AtBgAMAIBtSSp0YDMoNLSA97NVqNYqidD8Rs14FAhwAAGg7SqlyuVypVPS36a4ipsQ4AhwAAGg7SqmpqamZmRnbtvWYnP4i63adKwIcAACNxsrTzCmlSqVSd3e37/u2bVuWZVmWQQsaCHAAADSaQUGhJUkplVITExNTU1NKKc/zXNfVMS7rpp0rYxoKAACwWHSAm56erlQqYRjGcaxXBGfdrnNFgAMAAG1HKTUzM1Mul8MwjKIoSRKD0psgwAEA0HhmZYWWpJSam5urVqu1w28GvS4EOAAA0I70PnB67M2g6KYR4AAAwP9zXlHGxNyj6eUj6pWybtT5IcABALCE9G1Ps27FuUrvUqAppWrv+B7Hsb4J1Wl/+VRKKX2BcimaWr8kSWqnvpmV4dhGBACApRJFkeM4tm3rMZ4m36UiDMNSqTQ1NdXT01MsFnXj04gWx7Ft27Zt629LpdLY2FhXV1exWHRd97QPKKU804+ahKHDb4IROAAAloLOBOPj4319fY899piU0rIsfff6rJt2Gnpcbffu3Vu2bBkaGnr22WeFEI7jjI+PHzp0SAgRRZFt21//+tf7+/v1lP/vf//7Q0NDW7Zs2b17t36EeVckkyR56aWX+vv7h4aGqtVqE47DNedrcY4IcAAAnJ6qWy6XO3jw4IYNG9avX//EE0+4rmtZVhRFzRkdRkdHL7nkkoGBgd7e3nK5/LnPfa6vr+/+++8XQkgpDxw48Kd/+qdJkvT19Ukp3/a2tw0MDFxyySWjo6P6z+UrxXF85ZVXCiFuvfXWT3ziE7Zt115+bRLN+UKcCwIcAACn4XmevgIoF8SyLCllLpfr7u6WUj7++OMbN2684447Xn75ZcdxPM9rwujguq5emFmtVm3b3rBhw4//+I/ry76lUmnbtm1f+9rXBgcHX3755a997WtKKf2b+iJpkiTHjh07evToCy+88B//8R+Tk5Nf/OIXL7/88rvuuusjH/nI3//931cqlSa/gmwW5sABAHAaOo7oiV8LfpDp6Wl9bdFxnCiKdu3aNTg4uHXr1s2bN7uu22wZTiklpXQcRw+Vvfa1r12xYkW1WhVCJEni+76Od2vWrBkeHn7ve9+rZ8jpZxFF0cMPPzw3N2fbdhzH69atW7169caNG+M4fu655wqFgud5dR5M1CLAAQAw3+rVq1evXj00NFTn41QqlSiKxMkVAHEcj4yM7Nmz5+KLL/Z9v3aBZxPSY2zpIgZ9UdhxnJmZma6urnm/7Pv+Bz/4wdr/edOb3iSECMPw6aef3rFjR3qreCwKAhwAAP+fziu+7w8MDCzKA+7du1cPwsVx3NPTs3379p07dyqlduzY0eTDUfO2CNH3etcZ7tTZbJVK5c///M/TEbg1a9a89a1vrVQqb3vb26688sq+vr4wDJt8RapZCHAAAJyGHjlbMH05cmpqSgihF2Bu2rTp3nvvXb58uRDixIkTZ99BrUmkV0iVUhMTE/pJVavVzs7Oeb/pOM61116bJIn+k66uLtd1b7vtNt/3P/OZz+hfyOAJtC6OJgAAp1Fn4NBZR0pZqVSuvvrqnTt3rlu3TgihZ/0353T+U0cE9Y4hQohCoXDppZd+7GMf27Vr19DQ0He/+139BNM/sW37J37iJ2r/9n//93/vu+++Z555ZnJyMkmSYrHYmGfRJghwAAAsoeHh4auuukqc3LFCL2vNulGnNzExMe9/Ojo69Be2bT/55JObN2++9NJLv/CFL6xatapSqfi+n/5J7Xa4URS5rvvlL3+5UqlceeWVYRh2dXU988wzXV1dOvY17Bm1MAIcAACLT8eUQqGg01u6ALM5J/LrEcHrrrsu/Va39mMf+1j6P47jfP3rXx8bG+vp6RFCeJ4370/SZKbnuvX393/gAx/QY3hSSn3VlfS2WAhwAAAsFX1Dgto7UDUn3byNGzfWfiuE8H1ff6GXL0gpe3p6kiSxLEtnvlP/JOX7fvrnWHQEOAAAlkrtLLHmpxdb1DZYjxfqYTP977w7up76J7VqhxsZe1tcBDgAACDE6XLYqanr1L1FzvKAhLal04yrYAAAAHAWBDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADEOAAwAAbcrcnerYyBcAgGyok7JuSBvRR7v2DhOGIsABAJABKaXneVJKo2OEcfTRdl03vT+YoS8BAQ4AgAyEYTg6OhqGYXp3URNjhHGUUlLKycnJKIosy7IsKz3sZh1/AhwAAI3mOI5t22vWrJFSJkmilNL/1l7gwxKRUiqloihyXVfnORMH4QhwAAA0jk4PnZ2dR44cmZ6enpiYGB0dHRkZOX78+MjISKlUmpmZmZubi+M4juMkSbJub+uwLMu2bdu2c7lcPp9fuXJlV1eXbdt6EI4ABwAAXoVlWcViMQiCXC5n27ZOdbZt+74/PT2tA1wURQzILYp0upse+Mzlcp2dnYVCIQgCz/Nc19UvgVkxjgAHAEAG9BibngDnum4ul+vo6Ijj2LZtHeBqF6iS4RasdoqblDIdgdN0hnMcp3YynBEIcAAANJqU0rIsx3E8z/N9P5/PFwoFIYTOFmEYJkmiZ8Vl3dLWoY+5jstBEHR0dHR3d+fzed/3awfhsm7muSLAAQCQAT0fS4eJKIqEEJ7nlcvlarUaRRFrGhZR7Y4haW4OgiCfz3d1dQVBoAOcXgtsCgIcAAANpfOEnvTmuq7v+0IIx3GCIKhWq3r4jT1+F106y00PwumxzyAIfN/3PM+4aXAEOAAAMqDnY7muK4RIr+tFUVQ7+40At4hqx+Fs23Ycx3VdneT04gZToptGgAMAoNHSrOA4Tprk9L4hjL0tqdpxOLuGWcNvggAHAEBWdFzQSyBt254X3chwi27eitR0WYMw7TYMggAHAEAmahODjhFcNm2Y9HLqvH8NQoADACAztbnh1AxBmFtEZ4poxkU3jQAHAEDGWixboAFM2vIEAAAAggAHAABgHAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGcbJuAJClKIps2866Fe0rjmPHMfgsRP1ky/T6AepB6aOtcfbPlunH3/T2m47jj3ZG9aMdKaWklOVyeXBwcMuWLb7vK6WyblR7kVJWKpX9+/dv27YtCAL9imTdqHNF/WTO6PoBFoXkvIMmpE/HR48eHRoaGhgYiKJocT9q68cfHx8vFourVq1yHIc3QoNJKaMoOn78eKlUKhQKZnXA1E/mjK4fYFEwAof2pZS68MILn3rqqWKxSAfcYFLKUqm0du3aJEmybssCUT8ZaoH6AepEgEP7UkrFcbxixYply5Zl3ZZ25DhOHMe6A9YByKxBFOonW6bXD1AnAhzaXRiGSikuwTSSPtphGAoh4jgWJztgzawXgvppvFaqH2DBCHBod1JKfcbnvN9I6WGvVqtRFKX7QRj3KlA/mWiZ+gEWjAAHIDNKqXK5XKlU9LfpUhW6YZwL6gftjAAHIDNKqampqZmZGdu29ZiK/iLrdsEM1A/aGQEO7YuVg5lTSpVKpe7ubt/3bdu2LMuyLFMmpFM/mTO6foA6EeDQvjjRZ0tKqZSamJiYmppSSnme57qu7oazbto5oX6yZXr9AHWi0AFkRnfA09PTlUolDMM4jvWKzqzbBTNQP2hnBDgAmVFKzczMlMvlMAyjKEqShN4X5476QTsjwKF9ca7PnFJqbm6uWq3WDp+Y8rqY0s4WZnT9AHUiwAHIkt7HS4+d0PXifFE/aFssYgCa11mmyad9lbmT6HXL1Stl3aiWQv0ALYwAh7aglEqSxLbtrBtyfmo7V6VUFEWWZeln8ar9bpIk+i5DQgjXdZeukXVKkqR26lJz9sEtUD9RFOljq9dpnktu03cadRynmUOeEfUDLAUCHFpfFEWO49i2rT+jm7LLQBiGpVJpamqqp6enWCxKKdMcppT64Q9/KIRYvnz5me6krvfEalhr69HkwyetUT/pXQqEEEmS/OhHPxJnrR8hhG3bRmTWJq8fYImYcSYCFkaf08fHx/v6+h577DEppWVZ+u7jWTftbPRdunfv3r1ly5ahoaFnn302SZKRkZH+/v6HHnqoWq1WKpXh4eH9+/dfdtllExMT4pUXkvTA29/8zd/ceuut/f39N910k77XUHM+6+ZsldYa9fP888+Xy+WPf/zj27dvv+GGG4aHh6MoOkv96OHGOI4feOCB/v7+sbGxrJ/Q2TT5awEsHQIcmp2qWy6XO3jw4IYNG9avX//EE0+4rmtZVnpFqWmNjo5ecsklAwMDvb29SZKsXbtWCHHbbbd94hOfCILghhtuuOWWW2ZnZ3VckzX0qMnDDz/8+c9/PoqiarWa8TN5NekM9OZkev1cccUVtm1/+MMfHh8f11dFPc87S/1oN99886c//Wml1Fve8pY05GX9nE6vaRsGLCkuoaKpeZ5Xe+nwfOm5O7lcrru7e3x8/PHHH3/yySdvv/32/v7+5cuXe57XzKd+13X1Cjvbtu+5554rrrjirrvuuv/++++5555yuey67tjYWHpdbGxsrFQq6b3ppZSrVq3613/914MHD/7iL/5i+oDNOZPJcZxcLuf7vu/7QRAEQdA81yhbo34sy3rkkUd+9Vd/9S/+4i/0j5RScRyfqX4sy+ru7n7kkUe+853vdHR0HDhwIIqi7J4HgNMjwKGpHTt27OjRo3Ec1zMXZ3p6Wl/2chwniqJdu3YNDg5u3bp18+bNrus2bR+so5jjOHEcr1ix4pprronj+LnnnisUCrlczrIsx3GUUkmSCCGee+65w4cP27Ydx3EQBO9+97uff/75F1988cEHH3zb2962adOmJEmaJxillFKjo6Mvvvji3Nzc5ORkd3d3EAT6hkj1PKwOIrZt53K52dlZ/e2CH830+hFCDA8Pv+Y1r/mTP/mTEydO3HHHHV1dXY7jnKl+crnc9ddf/61vfSsIgn/7t39btmxZE1YOAAIcmtfq1atXr149NDRU5+NUKhU9hKCDYBzHIyMje/bsufjii33f1x1YM0uS5D3veY8QIgzDp59+eseOHbUdqs46vb29vb296X/Ozs7Ozs5+6Utfuvbaa9///ve/8MILy5cv1z1649t/FkmSPP/886VSqaurq6urKwgCz/MW63aWpVLpBz/4weWXX15neDW9foQQP/mTP/mJT3ziz/7sz7761a9KKfft25dWwmnrRwiRy+UqlcratWs3b95cLBb1So4Mmg7gDHhDohnp3sX3/YGBgUV5wL179+pBlDiOe3p6tm/fvnPnTqXUjh07mn+dnVIqDMNqtbpmzZorr7yyr6+vWq16nqd/qucwHTp0qHYEZdu2bWNjY7rT/c53vvOxj33szjvvDMOw2fYTsW377W9/+xvf+MbVq1dfcMEFPT09i5gSRkdHDxw4sG3btvofyuj6CcPw1ltv/dCHPuS6bl9f30//9E9/+MMf7unp0WOHZ6of13VzudyhQ4fWr19/6623rly5sgk/AADtjACHplbn5Bvd5UxNTYmTHdWmTZvuvffe5cuXCyFOnDhhRIekr4redtttvu9/5jOfEULUphz9FC666KILLrggncM0Nzf3Z3/2Z/39/UKIJEma+WnOzMxMTk7m8/lcLpckSUdHhx6Eq6fN+nUvlUqzs7NRFC149Kg16seyrEcffbS7u7u3t3dycnJem89UP4ODg9u3b3/d6163bt2622+//e67746iqNk+AADtjACHplbneIzugKWUlUrl6quv3rlz57p164QQ1WpVryVcpGYuiXRoJwiC//3f/73vvvueeeaZycnJJEkKhYL+UbrJak9PT09PT/q3k5OTN95446pVq3p7ex966KEjR47oKVwNfxKvTm9NrDknLUqA05di9bOuJ8CZXj+2bT/22GMPPfTQv/zLv9xyyy3vfOc7i8WiEELPkDtT/ezYsWPVqlXveMc7vve97914443KnA3wgDbRjCd0YNENDw9fddVV4uSOA67rNv/Yid67QQihlPryl79cqVSuvPLKMAy7urr+6Z/+admyZUmSnDhxQj+j2mG2OI6XLVv26KOPvv/97y8Wi5///OdXrVpV50KQNmd0/VSr1b17977wwguXXnrp5Zdf/tnPflbfVUIpdZb6OXjw4G/+5m92d3d/6lOfeve73039AM2GAIdWpvukQqGge9+0E2ralYOaHuq47rrr9LdKqf7+/g984ANxHOsxoa6uLiFEPp/fs2dPR0eHOLmPl/59Pdq0cePGF198MYoiPVxH77sArVE/lmV5nvfoo4+OjY3pYTbd/o6OjrPUzzXXXPNf//Vfun5MvI0Y0PIIcGh96uSNLE3phHQ7N27cqL+1LEtvkzbv14IgSBd5nDoglCRJZ2en/oKLX/UwvX70diFSyjS96WqhfgCj8bZE60tvTmCWOI7Tu9GLV96RIv3PsyzysCxL/zK9b51aoH50PtOVM+8O92f6c+oHaHKMwAFNal5oOO2kq7PPzW/+eVpYOqeGzlPrgfoBzMVHKwAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOQMbYbwz1oH7QntjIF+3u1NsbYKnpo33qjQFMRP00XivVD7BgBDi0NSml53m1d/JGA+ij7bqu/kKelHW7zhv1k4mWqR+gHgQ4tLUwDEdHR8MwTO/5SDfQAPp+6pOTk1EUWZZlWVZ62M06/tRPJlqmfoB6EODQvhzHsW17zZo1UsokSZRS+t/aCzRYIlJKpVQURa7r6v7YuEEU6idDLVA/QJ0IcGhH+uzf2dl55MiR6enpiYmJ0dHRkZGR48ePj4yMlEqlmZmZubm5OI7jOE6SJOv2tg7Lsmzbtm07l8vl8/mVK1d2dXXZtq0HUUzpgKmfrLRG/QCLggCH9mVZVrFYDIIgl8vZtq17Zdu2fd+fnp7WHXAURQyoLIp0upIeuMrlcp2dnYVCIQgCz/Nc19UvgUHdMPXTSK1XP0CdCHBoa3qMRE9gcl03l8t1dHTEcWzbtu6AaxcY0gcvWO0UJSllOoKi6T7YcZzayUxGoH4ao1XrB6gHAQ7tS0ppWZbjOJ7n+b6fz+cLhYIQQvcNYRgmSaJnNWXd0tahj7mOO0EQdHR0dHd35/N53/drB1GybuY5oX4ar5XqB6gTAQ5tTc+n0Z1BFEVCCM/zyuVytVqNoog56YuodseHNPcEQZDP57u6uoIg0B2wXstpCuqnYVqyfoB6EODQpnR/oCctua7r+74QwnGcIAiq1aoePmGP1kWXzlLSgyh67CoIAt/3Pc8zaBoT9ZOJlqkfoH4EOLQ1PZ/GdV0hRHpdJoqi2tlLdMCLqHYcxbZtx3Fc19U9sZ6cblbXS/00WIvVD1APAhzaV3qudxwn7Yn1vg+MnSyp2nEUu4ZZwyfUT1Zao36AOhHg0O706V4vYbNte17XSx+86OatKEynpdf+yCDUT4O1WP0AC0aAQ1urPePrboDLXg2TXg6b969BqJ8MtUD9APUgwAGvOO+f2gfQGS+iM3WxRne91E/DtGT9AAtDgAP+H/oG1IP6AdBIbJkDAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYxsm6AQBgqiiKbNvOuhXtK45jx6EXQ5ui9AFggUgP2eL4o51R/QBwfpRSUspyuTw4OLhlyxbf95VSWTeqvUgpK5XK/v37t23bFgSBfkWybhTQUJLzDoAWo7vzo0ePDg0NDQwMRFG0uEM1+vHHx8eLxeKqVascx+FE2mBSyiiKjh8/XiqVCoUCAQ5tiBE4AFgIpdSFF1741FNPFYtFAlyDSSlLpdLatWuTJMm6LUA2CHAAsBBKqTiOV6xYsWzZsqzb0o4cx4njWAc4HaAZhENbIcABwMKFYaiU4hJeI+mjHYahECKOY3EywGm8EGgTBDgAWDgppU4M5IZGSg97tVqNoijdT4RXAe2DAAcAMJJSqlwuVyoV/W26VIUYh3ZAgAMAGEkpNTU1NTMzY9u2HpPTX2TdLqARCHAAsBCsPM2cUqpUKnV3d/u+b9u2ZVmWZbGgAW2CAAcAC0FQyJaUUik1MTExNTWllPI8z3VdHeOybhrQCBQ6AMBIOsBNT09XKpUwDOM41iuCs24X0AgEOACAkZRSMzMz5XI5DMMoipIkIb2hfRDgAGAhyAqZU0rNzc1Vq9Xa4TdeF7QJAhwAwFR6Hzg99kZ0Q1thEQMAtKazLLNIs465izB0y9UrZd0ooHEYgQOAV6Fve5p1K85bersCLQxDfeOv9Eevmt70dcmlbWV9kiSpnfrW5K0FFhEjcABwNlEUOY5j27Ye4zFll4owDEul0tTUVE9PT7FYFEK4rqt/lCTJj370IyHE8uXLly1bdto/16nItu2GNXjBGH5DezLjTAQAjaczwfj4eF9f32OPPSaltCwrHcRqWvou77t3796yZcvQ0ND3v/99IcT09PTNN99888036wWbw8PD+/fvv+yyyyYmJsTpLkRalmXb9tNPP10qlUQTj2w1bcOApcYIHIBWVs/wjP6rXC538ODBhx9+eN26dQMDA7/yK78ihIiiqMmjw+jo6CWXXDIwMKDb+dGPfvTJJ5+M4/jEiRP33HPPDTfcEMfxXXfdpS8Nn3ot9R/+4R/++q//+s4773z++eczaP35aPIXAlgijMABaFme50kpXdeVC2JZlpQyl8t1d3dLKR9//PGNGzfecccdL7/8suM4nuc1c3RwXVev0FRKjY6O3n333f/8z//83e9+99JLL52bm4uiSD8L/ctjY2NHjx594YUXjh49euzYsTiO3/CGN6xfv97zPCOuogJtiBE4AC3r2LFjR48ejeO4nhQyPT2tL5s6jhNF0a5duwYHB7du3bp582bXdZs2wymlpJQ6ou3bt2/NmjUPPvjgP/7jP+7du1f/guM4SqkkSYQQzz333OHDh23bjuM4l8tt3bq1WCz+zM/8THprUQDNhgAHoDWtXr169erVQ0NDdT5OpVKJokgIoYNgHMcjIyN79uy5+OKLfd/XAajJKaVOnDjx3//9348++mgcx/v27Uuvmepo29vb29vbO++vyuUy6Q1oWgQ4AK1GpxPf9wcGBhblAffu3asH4eI47unp2b59+86dO5VSO3bsMOIKY7lcrlQqN95442/91m9dfPHFH/7wh3t6enQ403PgDh06NG8ELpfLmbtFHNAOCHAAWpYeOVswfRVyampKnAw6mzZtuvfee5cvXy6EOHHihCkR561vfeuKFSuEEJ7nzc3N1e5pp5/CRRdddMEFF0gp9T4p6dw4U54g0IYIcABaVhpEFkYHOCllpVK5+uqrd+7cuW7dOiFEtVp1XbfJN4RLhwaVUr/2a7/2+te//vrrr//rv/7r17/+9Z2dnUIIPUNOR7Senp6enp70b9Mrp3UmYABLhwAHAK9ieHj4qquuEieTjV7WmnWjXoXe4E0IMTc357ru4ODgFVdc8dJLLz388MNBEIiTE+P0M0qS5NRnJKXUy28b3HIA54IABwCnp7NLoVDQ6S1dzdrkU/v10OB1112nv/U8z7Ksa6+99pd+6Zccx+ns7NQjix0dHXv27Ono6BCn3HRLKxQK3/72t/P5vOBaKtB8CHAAcDZ6rw3bto1YryBOXjzduHGj/lbnuSRJCoWC/kL/TxAE6SKP0+YzKaW+2AqgCTX1HA4AyJyU0pToViuO49rFCnpHt3n3cn3VKW5NPtYItDNG4ACgBZ0aOk8dZnvVRR5cOQWaFiNwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAwGBsVof2xEa+ALBw6qSsG9JG9NHW/5Le0LYIcACwQFJKz/NOeyd4LB19tF3X1V/Ik7JuF9BQBDgAWKAwDEdHR8MwTO8xSoxoAKWUlHJycjKKIsuyLMtKDzvHH+2DAAcAC+E4jm3ba9askVImSaKU0v/WXuDDEpFSKqWiKHJdV+c5BuHQbghwAHB+dHro7Ow8cuTI9PT0xMTE6OjoyMjI8ePHR0ZGSqXSzMzM3NxcHMdxHCdJknV7W4dlWbZt27ady+Xy+fzKlSu7urps29aDcAQ4tBUCHAAshGVZxWIxCIJcLmfbtk51tm37vj89Pa0DXBRFDMgtinS6mx74zOVynZ2dhUIhCALP81zX1S8BMQ7tgwAHAAukx9j0BDjXdXO5XEdHRxzHtm3rAFe7QJUMt2C1U9yklOkInKYznOM4tZPhgJZHgAOAhZBSWpblOI7neb7v5/P5QqEghNDZIgzDJEn0rLisW9o69DHXcTkIgo6Oju7u7nw+7/t+7SBc1s0EGoEABwALpOdj6TARRZEQwvO8crlcrVajKGJNwyKq3TEkzc1BEOTz+a6uriAIdIDTa4GBdkCAA4DzpvOEnvTmuq7v+0IIx3GCIKhWq3r4jT1+F106y00PwumxzyAIfN/3PI9pcGgrBDgAWCA9H8t1XSFEel0viqLa2W8EuEVUOw5n27bjOK7r6iSnFzcQ3dA+JCcXAFiYdIwtrsHY21KrHYezazD8hrZCgAOABaodY0uXLLDydEnNW5GaLmsQNeNzWbYPaBQCHADUpTbGcdm0YWrjGtENbYgABwCL4EznUs6xi+hMEY3ohjZEgAMAADAMW+YAAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYf4vas93uLHRSe4AAAAASUVORK5CYII=\n", "text/plain": ["<PIL.PngImagePlugin.PngImageFile image mode=RGB size=832x520 at 0x1A099AFE9E8>"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["from pyensae.graphhelper import draw_diagram\n", "\n", "def dessine_tas(heap):\n", "    rows = [\"blockdiag {\"]\n", "    for i, v in enumerate(heap):\n", "        if i*2+1 < len(heap):\n", "            rows.append('\"[{}]={}\" -> \"[{}]={}\";'.format(\n", "                i, heap[i], i * 2 + 1, heap[i*2+1]))\n", "            if i*2+2 < len(heap):\n", "                rows.append('\"[{}]={}\" -> \"[{}]={}\";'.format(\n", "                    i, heap[i], i * 2 + 2, heap[i*2+2]))\n", "    rows.append(\"}\")\n", "    return draw_diagram(\"\\n\".join(rows))\n", "\n", "ens = [1,2,3,4,7,10,5,6,11,12,3]\n", "dessine_tas(entas(ens))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le nombre entre crochets est la position, l'autre nombre est la valeur \u00e0 cette position. Cette repr\u00e9sentation fait appara\u00eetre une structure d'arbre binaire."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Premi\u00e8re version"]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["1 [1]\n", "2 [2, 1]\n", "3 [3, 2, 1]\n", "4 [3, 3, 1, 2]\n", "5 [4, 3, 1, 3, 2]\n", "6 [5, 4, 3, 3, 2, 1]\n", "7 [5, 6, 3, 4, 2, 3, 1]\n", "8 [5, 7, 3, 6, 2, 3, 1, 4]\n", "9 [5, 10, 3, 7, 2, 3, 1, 6, 4]\n"]}], "source": ["def swap(tab, i, j):\n", "    \"Echange deux \u00e9l\u00e9ments.\"\n", "    tab[i], tab[j] = tab[j], tab[i]\n", "\n", "\n", "def _heapify_max_bottom(heap):\n", "    \"Organise un ensemble selon un tas.\"\n", "    modif = 1\n", "    while modif > 0:\n", "        modif = 0\n", "        i = len(heap) - 1\n", "        while i > 0:\n", "            root = (i-1) // 2\n", "            if heap[root] < heap[i]:\n", "                swap(heap, root, i)\n", "                modif += 1\n", "            i -= 1\n", "\n", "\n", "def _heapify_max_up(heap):\n", "    \"Organise un ensemble selon un tas.\"\n", "    i = 0\n", "    while True:\n", "        left = 2*i + 1\n", "        right = left+1\n", "        if right < len(heap):\n", "            if heap[left] > heap[i] >= heap[right]:\n", "                swap(heap, i, left)\n", "                i = left\n", "            elif heap[right] > heap[i]:\n", "                swap(heap, i, right)\n", "                i = right\n", "            else:\n", "                break\n", "        elif left < len(heap) and heap[left] > heap[i]:\n", "            swap(heap, i, left)\n", "            i = left\n", "        else:\n", "            break\n", "\n", "\n", "def topk_min(ens, k):\n", "    \"Retourne les k plus petits \u00e9l\u00e9ments d'un ensemble.\"\n", "    \n", "    heap = ens[:k]\n", "    _heapify_max_bottom(heap)\n", "    \n", "    for el in ens[k:]:\n", "        if el < heap[0]:\n", "            heap[0] = el\n", "            _heapify_max_up(heap)\n", "    return heap\n", "\n", "    \n", "ens = [1,2,3,4,7,10,5,6,11,12,3]\n", "for k in range(1, len(ens)-1):\n", "    print(k, topk_min(ens, k))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## M\u00eame chose avec les indices au lieu des valeurs"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["1 [0] [1]\n", "2 [1, 0] [2, 1]\n", "3 [2, 1, 0] [3, 2, 1]\n", "4 [10, 2, 0, 1] [3, 3, 1, 2]\n", "5 [5, 10, 0, 2, 1] [4, 3, 1, 3, 2]\n", "6 [6, 5, 2, 10, 1, 0] [5, 4, 3, 3, 2, 1]\n", "7 [5, 7, 10, 6, 1, 2, 0] [4, 6, 3, 5, 2, 3, 1]\n", "8 [5, 3, 10, 7, 1, 2, 0, 6] [4, 7, 3, 6, 2, 3, 1, 5]\n", "9 [5, 4, 10, 3, 1, 2, 0, 7, 6] [4, 10, 3, 7, 2, 3, 1, 6, 5]\n"]}], "source": ["def _heapify_max_bottom_position(ens, pos):\n", "    \"Organise un ensemble selon un tas.\"\n", "    modif = 1\n", "    while modif > 0:\n", "        modif = 0\n", "        i = len(pos) - 1\n", "        while i > 0:\n", "            root = (i-1) // 2\n", "            if ens[pos[root]] < ens[pos[i]]:\n", "                swap(pos, root, i)\n", "                modif += 1\n", "            i -= 1\n", "\n", "\n", "def _heapify_max_up_position(ens, pos):\n", "    \"Organise un ensemble selon un tas.\"\n", "    i = 0\n", "    while True:\n", "        left = 2*i + 1\n", "        right = left+1\n", "        if right < len(pos):\n", "            if ens[pos[left]] > ens[pos[i]] >= ens[pos[right]]:\n", "                swap(pos, i, left)\n", "                i = left\n", "            elif ens[pos[right]] > ens[pos[i]]:\n", "                swap(pos, i, right)\n", "                i = right\n", "            else:\n", "                break\n", "        elif left < len(pos) and ens[pos[left]] > ens[pos[i]]:\n", "            swap(pos, i, left)\n", "            i = left\n", "        else:\n", "            break\n", "\n", "\n", "def topk_min_position(ens, k):\n", "    \"Retourne les positions des k plus petits \u00e9l\u00e9ments d'un ensemble.\"\n", "    \n", "    pos = list(range(k))\n", "    _heapify_max_bottom_position(ens, pos)\n", "    \n", "    for i, el in enumerate(ens[k:]):\n", "        if el < ens[pos[0]]:\n", "            pos[0] = k + i\n", "            _heapify_max_up_position(ens, pos)\n", "    return pos\n", "\n", "    \n", "ens = [1,2,3,7,10,4,5,6,11,12,3]\n", "for k in range(1, len(ens)-1):\n", "    pos = topk_min_position(ens, k)\n", "    print(k, pos, [ens[i] for i in pos])"]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["5.59 ms \u00b1 728 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 100 loops each)\n"]}], "source": ["import numpy.random as rnd\n", "\n", "X = rnd.randn(10000)\n", "\n", "%timeit topk_min(X, 20)"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["7.85 ms \u00b1 544 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 100 loops each)\n"]}], "source": ["%timeit topk_min_position(X, 20)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Co\u00fbt de l'algorithme"]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"name": "stderr", "output_type": "stream", "text": ["100%|\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588| 20/20 [00:23<00:00,  1.78s/it]\n"]}, {"data": {"text/html": ["<div>\n", "<style scoped>\n", "    .dataframe tbody tr th:only-of-type {\n", "        vertical-align: middle;\n", "    }\n", "\n", "    .dataframe tbody tr th {\n", "        vertical-align: top;\n", "    }\n", "\n", "    .dataframe thead th {\n", "        text-align: right;\n", "    }\n", "</style>\n", "<table border=\"1\" class=\"dataframe\">\n", "  <thead>\n", "    <tr style=\"text-align: right;\">\n", "      <th></th>\n", "      <th>average</th>\n", "      <th>deviation</th>\n", "      <th>min_exec</th>\n", "      <th>max_exec</th>\n", "      <th>repeat</th>\n", "      <th>number</th>\n", "      <th>context_size</th>\n", "      <th>size</th>\n", "    </tr>\n", "  </thead>\n", "  <tbody>\n", "    <tr>\n", "      <th>0</th>\n", "      <td>0.003916</td>\n", "      <td>0.000363</td>\n", "      <td>0.003336</td>\n", "      <td>0.004570</td>\n", "      <td>10</td>\n", "      <td>10</td>\n", "      <td>240</td>\n", "      <td>1000</td>\n", "    </tr>\n", "    <tr>\n", "      <th>1</th>\n", "      <td>0.005436</td>\n", "      <td>0.001039</td>\n", "      <td>0.004235</td>\n", "      <td>0.007412</td>\n", "      <td>10</td>\n", "      <td>10</td>\n", "      <td>240</td>\n", "      <td>2000</td>\n", "    </tr>\n", "    <tr>\n", "      <th>2</th>\n", "      <td>0.005306</td>\n", "      <td>0.001051</td>\n", "      <td>0.004090</td>\n", "      <td>0.007401</td>\n", "      <td>10</td>\n", "      <td>10</td>\n", "      <td>240</td>\n", "      <td>3000</td>\n", "    </tr>\n", "    <tr>\n", "      <th>3</th>\n", "      <td>0.005341</td>\n", "      <td>0.000830</td>\n", "      <td>0.004376</td>\n", "      <td>0.007003</td>\n", "      <td>10</td>\n", "      <td>10</td>\n", "      <td>240</td>\n", "      <td>4000</td>\n", "    </tr>\n", "    <tr>\n", "      <th>4</th>\n", "      <td>0.007047</td>\n", "      <td>0.001786</td>\n", "      <td>0.005223</td>\n", "      <td>0.012082</td>\n", "      <td>10</td>\n", "      <td>10</td>\n", "      <td>240</td>\n", "      <td>5000</td>\n", "    </tr>\n", "  </tbody>\n", "</table>\n", "</div>"], "text/plain": ["    average  deviation  min_exec  max_exec  repeat  number  context_size  size\n", "0  0.003916   0.000363  0.003336  0.004570      10      10           240  1000\n", "1  0.005436   0.001039  0.004235  0.007412      10      10           240  2000\n", "2  0.005306   0.001051  0.004090  0.007401      10      10           240  3000\n", "3  0.005341   0.000830  0.004376  0.007003      10      10           240  4000\n", "4  0.007047   0.001786  0.005223  0.012082      10      10           240  5000"]}, "execution_count": 10, "metadata": {}, "output_type": "execute_result"}], "source": ["from cpyquickhelper.numbers import measure_time\n", "from tqdm import tqdm\n", "from pandas import DataFrame\n", "\n", "rows = []\n", "for n in tqdm(list(range(1000, 20001, 1000))):\n", "    X = rnd.randn(n)\n", "    res = measure_time('topk_min_position(X, 100)', \n", "                       {'X': X, 'topk_min_position': topk_min_position},\n", "                       div_by_number=True,\n", "                       number=10)\n", "    res[\"size\"] = n\n", "    rows.append(res)\n", "    \n", "df = DataFrame(rows)\n", "df.head()"]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAZAAAAEWCAYAAABIVsEJAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deXwU9fnA8c+Tm5AQIASUMxwRCCAq4VCkolgOq6JWK554olV7Wa1aj1prq7a2HtVqrfhTtAJKPWhFUQHrUQQCiiRcCQEkCUcIkBAg9/P7Yya4hE2yWXazOZ7365VXZme+M/PM7O48+535zndEVTHGGGMaKyzUARhjjGmZLIEYY4zxiyUQY4wxfrEEYowxxi+WQIwxxvjFEogxxhi/WAIJIRG5SkT2ikhSiOO4RkQ+D8F624nIv0WkSETebML1jhORDU20ri0icrYf840XkdxgxORlXUfsD8+YReRBEXktQOt5WUQeDsSyfFhXvXH7+76YI1kCOQYicrmIpItIiYhsF5H3ReR0H+eNBW4Frgd+W2tag180EVERGeB38M3DxUA3IFFVLwnWSmrvK1X9TFUHBmt9odbYg35L2B8i8omI3BDqOMyRIkIdQEslIrcDdwM3AwuBcmAyMBXw5df8AOAOVf1cRDqKSKSqVgQt4OapD7BRVStDHYgxxg+qan+N/AMSgBLgknrKRANPAvnu35NAtDvtGuDzWuUVJ6nMACpwElIJ8G8vy/7ULX/ALXOpO/5GIBvYA8wHutda/k+BHGA38CcgzFs87rTPgQQv6w7DSZybgELgDaCzOy3ZXc904Ft3PffWsX9+625jhbsN17vLvg/YCuwCZtXE0NCygXDg125c+4GVQC9v+woYD+R6zDsY+ATYB2QC53tMexl4FnjPXe4yoH897/tVbvyFwL3AFuDshvadl+XUjrFmvv3AWuDCOuabXGu/rnbHXwusc+fPAW6qZ12eMT8IvOYxbQzwP3dfrQbG17MvTgZWueucC8wBHm7oO+BlOb8HqoBSd5ueccc/BWwDit33e5zHPA8C89z17nfjGF7HNtb7vgBvAjuAIvfzNMRj2ifADR6vj9qu1vwX8gBa4p/7Ja0EIuop8xDwJdAVSHK/dL9zp9X75cE5aD3cQAxHfNmAs3AOqqfgJK+/Ap/WKr8E6Az0BjbWfPBr4nG/SP/AqVHF1rHen7vb1dNdz9+B2e60ZHc9/wDaAcOBMmBwHct6kCMPTtfhJMB+QBzwFvCqL8sG7gTWAAMBcacn1rGvxuMeMIFId52/BqLc/bgfGOjxXuwBRuHU2P8JzKlje1JxDnDfc/fNX9zPydkN7Tsvyzoco/v6EqC7+x5dipMQj/dlv7rjfgD0d/fNGcBB4JQ61rUFLwkE6IFzgD3HjeP77uskLzFE4STSX7j7+GKcpNboBOJO+wSPA7U77kog0X1ffolzkI/xiLvCXW8kcAewGYj0so31vi84n8t4vvtR+HVdcXnbrtb8F/IAWuIfcAWwo4Eym4BzPF5PAra4w/V+efAvgcwE/ujxOs79AiV7lJ/sMf0WYJFHPMtwfq39C4iqZ73rgAker4931xPBdwf5nh7TlwPT6ljWgxyZQBYBt3i8HujrsoENwFQf99V4vksg49wDT5jH9NnAgx7vxYse084B1texngfwSC5Ae5zaQM2Bqs5952VZh2OsY11f17O9R+zXOsq8A/zM27qoO4HchZvQPcouBKZ7Wf73cGre4jHufwQwgXgpsxe3luHG/aXHtDBgO24tpdY2NuZ96ejGmeAtLm/b1Zr/7BqIfwqBLiISoXWfv++O8wusxlZ3XLB0x6mmA6CqJSJSiPOrcYs7els98QzA+dU+SlXL61lPH+BtEan2GFeFczG8xg6P4YM4yczXbai9zyJ8XHYvnKTdWN2BbarquT1bcfZbQ+v0uqyaF6p6wH0PatS37/LqC1JErgZux0mkuDF0qW+eWvNPAX4DnIBzMI3FqbE1Rh/gEhE5z2NcJE7NtrbuQJ66R1XXVi/l/CYivwRucNelQAeO3Cee70W126rN23ewzvdFRHbgnEK7BOdMQk2ZLjintNo0a4Xln6U452MvqKdMPs4Hs0Zvdxw4px9iayaIyHG15lUa74j1iUh7nOq954GpVx3xgPMr7FrgfRGpr0XONmCKqnb0+ItR1XoPgD7yts8qgZ0+zLsN5xSNP+vsJSKe34XeNHBAr8N2PPax29IusVaMjd53ItIH59TdbTin5ToCGTino7w54vMjItE4NcvHgW7u/Avqmb8u23BqIJ7xt1fVR72U3Q70EBHPdfT2GG7oO1Bb7W0ah1Mj+hHQyd2mIo7cJs/3IgznFJXnZ95zu+p6Xy7HaRhzNs61z+SaRXrbDqCh7WhVLIH4QVWLcE5XPCsiF4hIrIhEisgUEfmjW2w2cJ+IJIlIF7d8TdPK1cAQETlJRGJwqtueduJcB6hP7TKvA9e6y4wG/gAsU9UtHmXuFJFOItIL+BnOKSvP7ZqNcy3gYxGp62D8PPB796CGu31TG4jVV7OBX4hIXxGJc7dhbj21PE8vAr8TkRRxnCgiNQfv+vbnMpyDwK/c93A8cB7OBd/GmgecKyKni0gUznUwz++Yv/uuPc4BtMCd71pgaD3ldwLJHkkxCuf8fQFQ6dZGJvq+WYe9BpwnIpNEJFxEYtz7VXp6KbsUJ/n/VEQiROQinOtINRr6DnjbJs/3MN5dfgEQISIP4NRAPI0QkYtEJALnOkcZzrWO2up7X+Ld+QpxEsUfas37NXCRewwYgNMYpM2wBOInVf0LzimF+3A+xNtwfiG+4xZ5GEgHvsE5VbDKHYeqbsQ5uHwMZHF0s9+ZQKqI7BORd/DuQeAVt8yPVHURcD/OL83tOL/Gp9Wa512c1ipf47Qqmullu15xY1ssIsle1vsUTguvD0VkP84XcnQdMTbWS8CrOC1dNuPU8n7i47x/wWk98yFOq5yZOBfboda+8pzJPV13PjAFpxHC34CrVXV9Y4NX1Uyce3tex3kP9gKeNwP6te9UdS3wZ5yD8k5gGPBFPbPU3JRZKCKrVHU/Tgu8N9yYLnfjaBRV3Ybza/zXfPeZvxMvxxF3v16Ec01gL86F/7c8pjf0HajtKeBicW68fRrn2sv7OI1BtuJ8VrbVmuddd717cVrHXaTem8rX977Mcpefh9P6rXYCegLnOtdO4BWcRhZthhx5itK0ViKiQIqqZoc6FmNM62A1EGOMMX6xBGKMMcYvdgrLGGOMX3yqgYjIZBHZICLZInK3l+nRIjLXnb6s5uKriHxfRFaKyBr3/1ke84xwx2eLyNO1mvsZY4xp5hqsgYhIOE5Lh+/jtChZAVzmtgypKXMLcKKq3iwi03D66blURE4GdqpqvogMBRaqag93nuU4TUm/xGmT/rSqvl9fLF26dNHk5GQ/N9UYY9qmlStX7lbVgD82wpc70UcB2aqaAyAic3Ca8q31KDOV79pxzwOeERFR1a88ymQCMe49Cp2BDqq61F3mLJyb8upNIMnJyaSnp/sQsjHGmBoiEtBeAGr4cgqrB0e2r87lyG4ejijj3vRVxJF34AL8EPhKVcvc8p7t470tEwARmSHOMzfSCwoKfAjXGGNMU/AlgXi7NlH7vFe9ZURkCPAYcFMjlumMVH1BVdNUNS0pKaQP7jPGGOPBlwSSy5F9KHnrT+ZwGbfbgAScLrBxuzl4G+fu3k0e5T27P6irjxpjjDHNlC/XQFYAKSLSF+d2/mk4XSF4mo/zoJ+lOP3vL1ZVFZGOOF1m3KOqh7teUNXtIrJfRMbg9EV0Nc7zKxqtoqKC3NxcSktL/Zm9zYmJiaFnz55ERkaGOhRjTAvXYAJR1UoRuQ2n75lw4CVVzRSRh4B0VZ2P0+/QqyJS8zS8mj6YbsPpJvx+EbnfHTdRVXcBP8Z51kI7nIvn9V5Ar0tubi7x8fEkJydjLYHrp6oUFhaSm5tL3759Qx2OMaaFa1E3EqalpWntVljr1q1j0KBBljx8pKqsX7+ewYMHhzoUY0wTEZGVqpoW6OW2iq5MLHn4zvaVMSZQWkUCMcY0vQVrtrNtz8FQh2FCyBKIMabRSsoqufX1Vdz+xte0pNPgJrAsgTRDVVVVoQ7BmHqtzS9GFVZs2cvi9btCHY4JEUsgAXDBBRcwYsQIhgwZwgsvvMBzzz3Hr371q8PTX375ZX7yE+fBeq+99hqjRo3ipJNO4qabbjqcLOLi4njggQcYPXo0S5cu5aGHHmLkyJEMHTqUGTNmHP6Vt2LFCk488UROPfVU7rzzToYOdZ5sWlVVxZ133snIkSM58cQT+fvf/97Ee8G0JRl5RQAc1yGGP36wgapqq4W0Rb7cB9Ji/PbfmazNLw7oMlO7d+A35w2pt8xLL71E586dOXToECNHjmTRokWMHTuWP/7ReTz63Llzuffee1m3bh1z587liy++IDIykltuuYV//vOfXH311Rw4cIChQ4fy0EMPOetNTeWBBx4A4KqrruI///kP5513Htdeey0vvPACp512Gnff/V3HyDNnziQhIYEVK1ZQVlbG2LFjmThxojXXNUGRkV9E1/ho7j83lVtfX8XbX+Vx8Qhvj0Y3rZnVQALg6aefZvjw4YwZM4Zt27axefNm+vXrx5dffklhYSEbNmxg7NixLFq0iJUrVzJy5EhOOukkFi1aRE5ODgDh4eH88Ic/PLzMJUuWMHr0aIYNG8bixYvJzMxk37597N+/n9NOOw2Ayy//7n7ODz/8kFmzZnHSSScxevRoCgsLycrKatodYdqMzLxihvZI4Jxhx3FizwSe+GgjpRV26rWtaVU1kIZqCsHwySef8PHHH7N06VJiY2MZP348paWlXHrppbzxxhsMGjSICy+8EBFBVZk+fTqPPPLIUcuJiYkhPDwcgNLSUm655RbS09Pp1asXDz74IKWlpfVerFRV/vrXvzJp0qSgbasxAIfKq8jatZ9JQ7ohItw9eRCXv7iM177cyg3j+oU6PNOErAZyjIqKiujUqROxsbGsX7+eL7/8EoCLLrqId955h9mzZ3PppZcCMGHCBObNm8euXc5Fxz179rB169G9LNd0y9KlSxdKSkqYN28eAJ06dSI+Pv7wOubMmXN4nkmTJvHcc89RUVEBwMaNGzlw4ECQttq0Zet2FFOtMLRHAgCnDejCuJQuPLMkm+LSihBHZ5pSq6qBhMLkyZN5/vnnOfHEExk4cCBjxowBnIN9amoqa9euZdSoUYBzXePhhx9m4sSJVFdXExkZybPPPkufPn2OWGbHjh258cYbGTZsGMnJyYwcOfLwtJkzZ3LjjTfSvn17xo8fT0KC8yW+4YYb2LJlC6eccgqqSlJSEu+8804T7QXTlmS6F9BrEgjAXZMHce5fP+fv/93EnZMGhSq0ZqGiqppNBSVUVilV1UqVKtXVnsN4Gef8r6pWqlWpqobqaiUmKpyO7SLpFBtFx9hIEmIjiY+OaDY3BLeKrkzaUrccJSUlxMXFAfDoo4+yfft2nnrqqUYto63tMxNYd837ho/W7WTlfWcfcSD76eyv+HDtDj6980y6dogJYYShoaq8t2Y7jy/cwJbC4N1gGR4mJLSLpGNsJB3bRdIxNoqO7Zzk0rFdFJ3aR7rTo9zpkSR3iQtKVyZWA2lh3nvvPR555BEqKyvp06cPL7/8cqhDMm1MRn4RQ7p3OOpX8C8nnsCCNdt5clEWf7hwWIiiC43/Ze/m0Q/W801uEQO7xfPHi08koV0k4SKEhwlhYUK4CGFhEC5CRLgQVjPN/X/EsFu2tKKKvQcr2Hewgn0Hyyk65A4fKmfvwQqKDlawa38pG3fup+hgBfvLKpt0uy2BtDCXXnrp4WsqxjS1ssoqNu7c7/VieZ/E9lwxujevLfuWG07vS7+kuBBE2LQy8op47IP1fJa1m+4JMTx+yXAuPLkH4WGhOcVUUVV9OMkUHSpn38EK9h6s4JLHgrO+VpFAVLXZnBNs7lrSKUvT/GTtLKGiShnaPcHr9NvOSuHNlbk8/uEG/nbFiCaOrul8W3iQP3+0gXe/zqdjbCT3/WAwV47pQ0xkeEjjigwPo0tcNF3ioptkfS0+gcTExFBYWEhiYqIlkQbUPA8kJqbtnZ82gbHGvYA+rIf3BJIUH82N4/rx1KIsvt62j5N6dWzK8IJud0kZzyzO5p/LthIeJtwyvj83ndGfhHZt8wFtLT6B9OzZk9zcXAoKCkIdSotQ80RCY/yRkVdEfEwEvTq3q7PMjd/rx2tfbuWx99fz+o2jW8UPu5KySl78LId/fJpDaWU1P0rrxc/PTqFbG2ws4KnFJ5DIyEjrrsOYJpKRX8zQ7gn1JoW46Ah+ctYAHvz3Wj7N2s0ZJyQ1YYSBVV5Zzezl3/LXxVnsLilnytDjuGPSQPq3ges7vvDpRkIRmSwiG0QkW0Tu9jI9WkTmutOXiUiyOz5RRJaISImIPFNrnstEZI2IfCMiH4hIl0BskDEmOCqqqlm3vZihPTo0WPby0X3o1bkdj76/nuoW2NFidbUyf3U+Z//lv/xmfib9k+J4+5bTeO7KEZY8PDSYQEQkHHgWmAKkApeJSGqtYtcDe1V1APAEUHPNvxS4H7ij1jIjgKeAM1X1ROAbnOenG2OaqU0FJZRXVh9xA2FdoiLCuGPiQNZtL+bf3+Q3QXSB81lWAec98zk/nf0VsVHh/N+1I5kzYwwn9+4U6tCaHV9qIKOAbFXNUdVyYA4wtVaZqcAr7vA8YIKIiKoeUNXPcRKJJ3H/2otTF+4AtKxPmTFtTEae09P1kDpaYNV23ondST2+A49/uIHyyupghhYQxaUVXP3Scq6auZx9Byt44tLhLPjpOM4c2LVVXMcJBl8SSA9gm8frXHec1zKqWgkUAYl1LVBVK4AfA2twEkcqMNNbWRGZISLpIpJuF8qNCZ2MvCJio8Lp26W9T+XDwoS7pgxi255DvL7s6D7fmpOyyipumrWSpZt2c98PBrP4jjO48OSehIXofo6WwpcE4m0P1j6p6UuZ7wqLROIkkJOB7jinsO7xVlZVX1DVNFVNS0pquRfjjGnpMvKcO9Abc5Pc91K6cGq/RP66OJuSJr5L2lfV1codb37D0pxC/nTxcG4Y14/oiNDez9FS+JJAcoFeHq97cvTppsNl3OsbCcCeepZ5EoCqblLnzrY3gNN8jNkY08SqqpW124t9Pn1VQ0S4e8ogCg+U849Pc4IU3bF55P11/Ht1PndPGcQFJ9c+uWLq40sCWQGkiEhfEYkCpgHza5WZD0x3hy8GFmv9tzznAakiUlOl+D6wzvewjTFNafPuAxwsr/LpAnptw3t15Jxhx/HiZzkU7C8LQnT+m/n5Zv7x2WauOS2Zm75nzzJprAYTiHtN4zZgIc5B/g1VzRSRh0TkfLfYTCBRRLKB24HDTX1FZAvwF+AaEckVkVRVzQd+C3wqIt/g1Ej+EMDtMsYEUGZ+TRfuDTfh9eaOiQMprazmmcXN5ymZ//kmn4ffW8uUocdx/7mpdqHcDz7dSKiqC4AFtcY94DFcClxSx7zJdYx/Hnje10CNMaGTkVdEdEQYA/y8B6JfUhyXjuzF68u/5brT+9In0bcL8cHyZU4ht89dzcg+nXni0pNC1vlhS2dPJDTGNGhNXhGDju9ARLj/h4yfTUghPEz484cbAxhZ423YsZ8bZ6XTJzGWf1ydFvIOEFsySyDGmHpVVyuZecUM8/P0VY1uHWK4/vS+zF+dT4bbKWNTy993iOkvLSc2KpyXrxtFQmzb7AQxUCyBGGPqtW3vQfaXVdbZhXtj3HRGfzrGRvLYB+sDEFnjFB2q4Jr/W86BskpevnYUPTrW3SGk8Y0lEGNMvWruQPenBVZtHWIiue3MAXyWtZsvsncf8/J8VVZZxYxZ6WzefYC/XzWCwccfW23KOCyBGGPqlZFfRGS4kNItMJ0IXjmmD90TYnjsg/VN8oCz6mrl9jdWs2zzHh6/ZDinDbB+WwPFEogxpl4ZeUWc0C0+YHdnx0SGc/vEgXyTW8SCNTsCssz6/H7BOt77Zjv3njOYqSfZjYKBZAnEGFMnVSXTfQZIIF14cg8GdovnTwvXU1EVvI4WX/wsh5mfb+a6sX25YZw9NyjQLIEYY+qUX1TKngPlDO0Z2AQSHib8avJAthQeZO6KbQ3P4If5q/N5+L11/GDY8dz3g8F2o2AQtPgnEhpjgqemue3Q7oG/6HzWoK6MTO7Ekx9vpFqVcSlJJCfGBuRA/79Nu/nlG18zqm9n/vyj4darbpBYAjHG1Ckzr4jwMAlKqyUR4cHzh3DLP1fxwLuZAPTo2I7vndCFcSlJnNY/kY6xUY1e7vodxdw0ayV9u7TnH1fZjYLBZAnEGFOnjPxiBiTFBe0gPKR7Av+980y2Fh7g06zdfLaxgP+s3s7s5dsQgRN7dmTcgC6MS+nCyb07ERVR/1n3PPdGwfbREbx8rd0oGGyWQIwxdcrIK+L0lOA3e+2T2J6rEttz1Zg+VFZVszp3H59u3M3n2bt57r+beGZJNu2jwhnTL5FxKV04PSWJ/kntjzjdVXSwgmteWs7B8irevPlUutuNgkFnCcQY49Wu4lJ27S8LeAushkSEhzGiT2dG9OnML75/AsWlFSzdVMhnWQV8lrWbRet3AdA9IYZxKUmcntKFkcmd+ensr9haeJBXrhvFoOPsRsGmYAnEGONVxuEu3Js2gdTWISaSSUOOY9KQ4wD4tvAgn2UX8NnG3SzI2M7c9O9acf31spM5tX+dT9M2AWYJxBjjVUZeMSKQGoQWWMeid2IsVyT24YrRzumub/KK+DxrN30SYzlvePdQh9emWAIxxniVkVdE3y7tiYtuvoeJiPAwTundiVN6dwp1KG2STzcSishkEdkgItkicreX6dEiMtedvkxEkt3xiSKyRERKROSZWvNEicgLIrJRRNaLyA8DsUHGmMAIxh3opnVpMIGISDjwLDAFSAUuE5HUWsWuB/aq6gDgCeAxd3wpcD9wh5dF3wvsUtUT3OX+168tMMYE3J4D5eTtO+T3I2xN2+BLDWQUkK2qOapaDswBptYqMxV4xR2eB0wQEVHVA6r6OU4iqe064BEAVa1W1abr29kYU6/Dz0C3Goiphy8JpAfg2VlNrjvOaxlVrQSKgDqbQohIR3fwdyKySkTeFJFudZSdISLpIpJeUFDgQ7jGmGNV8wyQIZZATD18SSDeOpGp3Ym/L2U8RQA9gS9U9RRgKfC4t4Kq+oKqpqlqWlJSkg/hGmOOVUZeEb07x9qd3KZeviSQXKCXx+ueQH5dZUQkAkgA9tSzzELgIPC2+/pN4BQfYjHGNIGM/CK7/mEa5EsCWQGkiEhfEYkCpgHza5WZD0x3hy8GFms9jxpzp/0bGO+OmgCsbUTcxpggKTpUwdbCg3b6yjSowQbeqlopIrcBC4Fw4CVVzRSRh4B0VZ0PzAReFZFsnJrHtJr5RWQL0AGIEpELgImquha4y53nSaAAuDawm2aM8cfa/MA9A920bj7dIaSqC4AFtcY94DFcClxSx7zJdYzfCnzP10CNMU2jpgXWkGZ2B7ppfuyJhMaYI2TkFXF8Qgxd4qJDHYpp5iyBGGOOsCavyE5fGZ9YAjHGHHagrJKc3QfsBkLjE0sgxpjD1m0vRhVrwmt8YgnEGHNYRl7zeAaIaRksgRhjDsvIL6ZLXDRd4+0CummYJRBjzGEZec4d6J7PGjemLpZAjDEAlFZUkbWrxC6gG59ZAjHGALB+x36qqtWufxifWQIxxgCeF9CtBZbxjSUQYwzgdGHSMTaSHh3bhToU00JYAjHGAM5DpIZ2T7AL6MZnlkCMMZRXVrNhx36G2Okr0wiWQIwxZO3aT3lVtbXAMo1iCcQYc/gC+jBrgWUawRKIMYaMvGLioyPo3Tk21KGYFsQSiDGGjPwiUrt3ICzMLqAb3/mUQERksohsEJFsEbnby/RoEZnrTl8mIsnu+EQRWSIiJSLyTB3Lni8iGceyEcYY/1VWVbNue7HdQGgarcEEIiLhwLPAFCAVuExEUmsVux7Yq6oDgCeAx9zxpcD9wB11LPsioMS/0I0xgZCz+wClFdV2A6FpNF9qIKOAbFXNUdVyYA4wtVaZqcAr7vA8YIKIiKoeUNXPcRLJEUQkDrgdeNjv6I0xx+zwHejWAss0ki8JpAewzeN1rjvOaxlVrQSKgMQGlvs74M/AwfoKicgMEUkXkfSCggIfwjXGNMaavCLaRYbTLyku1KGYFsaXBOLtqpr6Uea7wiInAQNU9e2GVq6qL6hqmqqmJSUlNVTcGNNImXnFpHbvQLhdQDeN5EsCyQV6ebzuCeTXVUZEIoAEYE89yzwVGCEiW4DPgRNE5BPfQjbGBEp1tZKZX8TQ7nb9wzSeLwlkBZAiIn1FJAqYBsyvVWY+MN0dvhhYrKp11kBU9TlV7a6qycDpwEZVHd/Y4I0xx2ZL4QEOlFcxxFpgGT9ENFRAVStF5DZgIRAOvKSqmSLyEJCuqvOBmcCrIpKNU/OYVjO/W8voAESJyAXARFVdG/hNMcY0VkZ+MWAX0I1/GkwgAKq6AFhQa9wDHsOlwCV1zJvcwLK3AEN9icMYE1iZeUVEhYeR0s0uoJvGszvRjWnD1uQVMej4eCLD7VBgGs8+Nca0UapKRl6R3YFu/ObTKSxjjP9UlVv+uYr1O/bTr0t7+iW1p19SHP26tKd/1zgS20eF5CFOuXsPUVxaadc/jN8sgRgTZF9kF/J+xg5G9OlE3r5DfJa9m/LK6sPTO8REOAklqT39PRJLn8RYoiPCgxaXPQPdHCtLIMYEkary1KKNHNchhtdvHE10RDhV1Ur+vkNsKighp+AAObtL2LTrAF9k7+atVXmH5w0T6Nkp1qmxdHESzAnd4knr0ykgveZm5BcRESac0C3+mJdl2iZLIMYE0dJNhazYspffnj/kcG0iPEzo1TmWXp1jGT/wyPIlZZVsPpxUSti0+wA5BQf4MqeQ0gqn1jK0Rwd+PWUwpw3ockyxZeQVk9ItnpjI4NVyTOtmCcSYIHpyURbdOkRz6cheDRcG4qIjGNYzgWE9j7wuUV2tbC8u5X/Zu3ny4ywuf1JYV+sAACAASURBVHEZ4wcmcc+UwQw8rvE1iJoL6GcN6troeY2pYa2wjAmSpZsKWb55Dzef0f+Yf+WHhQk9OrbjkrReLPrlGfz6nEGs2rqXKU99yq/mrWZH0VEdXtdrR3EphQfKj0pUxjSGJRBjguSpRRtJio/mslG9A7rcmMhwZnyvP/+980yuG9uXd77KZ/zjS3h84Qb2l1b4tIyMPOcO9CHWAsscA0sgxgTBspxCvswJTO2jLp3aR3Hfuaks+uUZTEw9jmeWZDP+T58wa+kWKqqq6503I6+IMIHBx9sFdOM/SyDGBMHTi7PoEhfNFaMDW/vwplfnWJ6+7GTevXUsA7rG8cC7mUx84lM+yNhOXX2aZuYX0T8pjtgouwxq/GcJxJgAS9+yhy+yC7n5jH5N2sJpeK+OzJkxhpnT0wgPE25+bRUXP7+UlVuPfrJCRp49A90cO0sgxgTYU4uySGwfxeVNUPuoTUSYMLgbH/xsHI9cNIxv9xzkh88t5cevrWTz7gMAFOwvY0dxKUPsGSDmGFn91ZgAWrl1L59l7eaeKYNCenooIjyMy0b1ZupJ3fnHp5v5+6eb+GjtTq4Y3ZvhvToCMMxqIOYYWQIxJoCeWpRF5/ZRXHVqn1CHAkBsVAQ/OzuFy0f35smPN/Lasm95ZelWAFKtBmKOkSUQYwLkq2/38unGAu6aHNrahzdJ8dH8/sJhXDu2L48v3EB4mBAfExnqsEwL59M1EBGZLCIbRCRbRO72Mj1aROa605eJSLI7PlFElohIiYg841E+VkTeE5H1IpIpIo8GaoOMCZWnF2XRKTaSq5tJ7cObAV3jeP6qETx7xSmhDsW0Ag0mEBEJB54FpgCpwGUiklqr2PXAXlUdADwBPOaOLwXuB+7wsujHVXUQcDIwVkSm+LcJxoTe6m37WLKhgBvG9aN9dPOqfRgTLL7UQEYB2aqao6rlwBxgaq0yU4FX3OF5wAQREVU9oKqf4ySSw1T1oKoucYfLgVVAz2PYDmNC6ulFWXSMjWT6acmhDsWYJuNLAukBbPN4neuO81pGVSuBIiDRlwBEpCNwHrCojukzRCRdRNILCgp8WaQxTWpNbhGL1u/i+rF9ibPah2lDfEkg3h48UPv2Vl/KHL1gkQhgNvC0quZ4K6OqL6hqmqqmJSUlNRisMU3tqUVZdIiJYPrY5FCHYkyT8iWB5AKefVH3BPLrKuMmhQTg6Ntfj/YCkKWqT/pQ1phmJyOviI/X7eT60/vRwVo1mTbGlwSyAkgRkb4iEgVMA+bXKjMfmO4OXwws1ro64XGJyMM4iebnjQvZmObj6UVZxMdEcI3VPkwb1OAJW1WtFJHbgIVAOPCSqmaKyENAuqrOB2YCr4pINk7NY1rN/CKyBegARInIBcBEoBi4F1gPrBIRgGdU9cVAbpwxwbQ2v5gP1+7kZxNSSGhntQ/T9vh0xU9VFwALao17wGO4FLikjnmT61jssT/U2ZgQ+uviLOKjI7hubN9Qh2JMSFhnisb4Yf2OYt7P2MG1Y5NJiLXah2mbLIEY44e/LsomLjqC60632odpuyyBGNNIG3fuZ0HGdqaf1oeOsVGhDseYkLEEYkwjPb0oi9jIcG44vV+oQzEmpCyBGNMIWTv3896a7Vx9WjKd2lvtw7RtlkCMaYRnlmTTLjKcG8dZ7cMYSyDG+GhTQQn/Xp3PVaf2obPVPoyxBGKMr55ZnE10RDgzrPZhDGAJxBif5BSU8O7XeVx1ah8S46JDHY4xzYIlEGN88MySbKIiwuzahzEeLIGYZmdNbhHLcgpDHcZhW3Yf4N2v87lidB+S4q32YUwNSyCmWdldUsZVLy3jmv9bwY6i0oZnaALPLMkmIky46QyrfRjjyRKIaVYe+vdaDpZVUVWt/HHh+lCHw9bCA7z9VR6Xj+5N1/iYUIdjTLNiCcQ0G0s27GL+6nxuObM/153el7dW5bF6276QxvTYB+uJCBNuPqN/SOMwpjmyBGKahQNlldz3dgYDusbx4/H9ufXM/nSJi+Kh/6ylgWeTBc0nG3axYM0ObjtzAN06WO3DmNosgZhm4c8fbiRv3yEeuWgY0RHhxMdEcsfEgazcupf/fLO9yeMprajigXcz6ZfUnhl27cMYryyBmJBbvW0fL/9vM1eM7s3I5M6Hx1+S1ovBx3fg0ffXU1pR1aQx/e2TTXy75yC/mzqU6IjwJl23MS2FTwlERCaLyAYRyRaRu71MjxaRue70ZSKS7I5PFJElIlIiIs/UmmeEiKxx53la3Ofamraloqqau99aQ1J8NHdNGXTEtPAw4f5zB5O37xAzP9/cZDHlFJTw/CebOH94d8YO6NJk6zWmpWkwgYhIOPAsMAVIBS4TkdRaxa4H9qrqAOAJ4DF3fClwP3CHl0U/B8wAUty/yf5sgGnZXvxsM+u2F/Pb84fSIeboJ/ud1r8Lk4Z049kl2ewqDn6zXlXlgXcziY4I475zBwd9fca0ZL7UQEYB2aqao6rlwBxgaq0yU4FX3OF5wAQREVU9oKqf4ySSw0TkeKCDqi5V5wrpLOCCY9kQ0/Js2X2AJz/eyKQh3Zg89Lg6y/36nMFUVFXzp4Ubgh7Tv7/ZzufZu7lj0kBrtmtMA3xJID2AbR6vc91xXsuoaiVQBCQ2sMzcBpYJgIjMEJF0EUkvKCjwIVzTEqgq976zhqjwMB6aOrTesn0S23Pd2L7MW5XLmtyioMVUXFrB7/6zlmE9ErhyTJ+grceY1sKXBOLt2kTtdpW+lPGrvKq+oKppqpqWlJRUzyJNSzJvZS5fZBdy15RBPjWRvfWsAXSOjeJ3QWzW+5cPN7K7pIyHLxhKeJhdkjOmIb4kkFygl8frnkB+XWVEJAJIAPY0sMyeDSzTtFK7S8r4/YJ1pPXpxOWjevs0T4eYSH45cSDLt+zh/YwdAY8pI6+IWUu3cMXo3gzv1THgyzemNfIlgawAUkSkr4hEAdOA+bXKzAemu8MXA4u1np+Jqrod2C8iY9zWV1cD7zY6etMi/e4/azlQVskjFw0jrBG/9C8d2YtBx8XzhwXrAtqst6paufedDDq3j+LOSYMansEYA/iQQNxrGrcBC4F1wBuqmikiD4nI+W6xmUCiiGQDtwOHm/qKyBbgL8A1IpLr0YLrx8CLQDawCXg/MJtkmrMlG3bx7tf53DJ+ACnd4hs1b3iY8MC5qeTuPcRLXwSuWe/s5d+yets+7v3BYBLaHd0SzBjjnYSqmwh/pKWlaXp6eqjDMH46UFbJxCc+pV1UOO/99HS/b9C7cVY6/8vezZI7xx9zS6ndJWWc9fgnDOmewOs3jsZuRzKtkYisVNW0QC/X7kQ3TeYvHx3ZXYm/fn3OYMqrqvnzwo3HHNMfFqzjUEUVv7tgiCUPYxrJEohpEqu37eP/vji6uxJ/9O3SnmtOS+aNldvIyPO/We+XOYW8tSqPG8f1Y0DXxp1OM8ZYAjFNoL7uSvx121kpdDqGZr3lldXc904GPTu14ydnpQQkJmPaGksgJuga6q7EHwntIvnF909g2eY9LMxsfLPeFz/PIXtXCb89fwjtoqyzRGP8YQnEBNXWQqe7komp9XdX4o/LRvbihG5x/H7BOsoqfW/Wm7v3IE8vymJiajcmDO4W0JiMaUssgZigUVV+/bZv3ZX4IyI8jPvPTWXbnkP83xdbfJ7vwflrEYTfnD8k4DEZ05ZYAjFB869VeXyRXcivpgziuITgdEw4LiWJCYO68szibAr2lzVY/qO1O/l43U5+dnYKPTq2C0pMxrQVlkBMUOwuKePh99aS1qcTV/jYXYm/fv2DwZRWVPGXj+pv1nuwvJIH52dyQrc4rj+9b1BjMqYtsARigsLf7kr80T8pjqtPTWbuim9Zm19cZ7mnF2WTt+8QD18wjMhw++gbc6zsW2QC7li6K/HXzyak0KFdZJ3NerN27ufFz3K4eERPRvU9tvtQjDEOSyAmoA6UVXLf2xn0T2rPLWf2b7L1JsRGcvv3T2BpTiEfrd15xDRV5b53MmgfHcE9AboPxRhjCcQE2BNudyWP/vDEY+quxB+Xj+pNStejm/W+tSqPZZv3cNfkQSTGRTdpTMa0ZpZATMCs+nYvL32xmcsD0F2JPyLCw7jv3FS2Fh5k1v+2ArDvYDl/WLCOk3t3ZNrIXg0swRjTGJZATEAU7C/jltdW0b1jO+6aHLrTRGeckMSZA5N4elEWhSVl/HHhBvYeLOfhC4YG/WK+MW2NJRBzzCqqqrnt9VXsPVjO368aEfJnatz7g1QOVlRx2+tfMXv5t1xzWl+GdE8IaUzGtEaWQMwxe/T99SzbvIdHfzisWRyoB3SN46oxfViaU0jX+Gh+8X3rLNGYYIgIdQCmZXv36zxmfr6Za05L5sKTezY8QxP5+dkpbNixnxln9CM+QB04GmOO5FMNREQmi8gGEckWkbu9TI8Wkbnu9GUikuwx7R53/AYRmeQx/hcikikiGSIyW0SC09eFCZp124u561/fMDK5E78+Z3CowzlCx9goZs8Yw5kDu4Y6FGNarQYTiIiEA88CU4BU4DKP55rXuB7Yq6oDgCeAx9x5U4FpwBBgMvA3EQkXkR7AT4E0VR0KhLvlTAtRdLCCm19bSYeYSJ69/BSiIuxsqDFtjS/f+lFAtqrmqGo5MAeYWqvMVOAVd3geMEGc54NOBeaoapmqbgay3eWBc/qsnYhEALFA/rFtimkq1dXKz+d+Rf6+Qzx35Sl07WCVR2PaIl8SSA9gm8frXHec1zKqWgkUAYl1zauqecDjwLfAdqBIVT/0tnIRmSEi6SKSXlBQ4EO4JtieWpTFkg0FPHBuKiP6WLcgxrRVviQQb43na3c2VFcZr+NFpBNO7aQv0B1oLyJXelu5qr6gqmmqmpaUlORDuCaYFq3byVOLsvjhKT25ckyfUIdjjAkhXxJILuB5C29Pjj7ddLiMe0oqAdhTz7xnA5tVtUBVK4C3gNP82QDTdDbvPsDP537NkO4d+P2FQ3HOUhpj2ipfEsgKIEVE+opIFM7F7vm1yswHprvDFwOL1ekSdT4wzW2l1RdIAZbjnLoaIyKx7rWSCcC6Y98cEywHyiq5+dWVhIcJz185gphIe464MW1dg/eBqGqliNwGLMRpLfWSqmaKyENAuqrOB2YCr4pINk7NY5o7b6aIvAGsBSqBW1W1ClgmIvOAVe74r4AXAr95JhBUlbv+9Q1Zu/bzynWj6NU5NtQhGWOaAfH27ITmKi0tTdPT00MdRpvz4mc5PPzeOn41eSC3jB8Q6nCMMY0kIitVNS3Qy7XG+6Ze/9u0m0feX8+kId348RlN93wPY0zzZwnE1Cl/3yF+8vpXJCfG8vglw+2iuTHmCJZAjFelFVX8+LWVlFVW8/er0qw/KWPMUawzRePVb/+dyercIp6/cgQDusaFOhxjTDNkNRBzlNnLv2X28m3cMr4/k4ceF+pwjDHNlNVAWri//3cTb67MZeBx8QztnsDQHh0Y0j2Bzu2j/Fre19v28Zt3MxmX0oVfThwY4GiNMa2JJZAWbGHmDh55fz2Djotn9bZ9vPfN9sPTuifEMKRHAkO6d3ATSwLdOkTXeyF8d0kZP35tJUnx0Tw97WTC7RGwxph6WAJpobJ27uf2uV8zvGcCc286lZjIcPYdLCczv5jM/CIy8orJyC/i43U7qbnVJ7F9VK2k0oHenWMRESrdx9LuOVDOv358Gp38rMEYY9oOSyAtUNHBCm6clU67qAiev+q7bkU6xkYxdkAXxg7ocrjsgbJK1m0vJjO/mIy8IjLyi/nHpzlUVjtZJT46gtTuHYiKCOPLnD08fslwhvYI/WNpjTHNnyWQFqaqWvnpnK/I23eI2TeO4fiEdvWWbx8dQVpyZ9KSv+t2vayyio07SsjILzpcW1mdu4/rxvbl4hHN57G0xpjmzRJIC/OnhRv478YC/nDhsCOSQmNER4QzrGcCw3p+V9NQVbtR0BjTKNaMtwWZvzqf5/+7iStG9+by0b0DumxLHsaYxrIE0kJk5hfxq3mrGZncid+cNyTU4RhjjCWQlqCwpIwZs1bSKTaKv10xgqgIe9uMMaFn10CauYqqam57/SsKSsqYd/OpJMVHhzokY4wBrAbS7P3+vXUszSnk0YuGcWLPjqEOxxhjDvMpgYjIZBHZICLZInK3l+nRIjLXnb5MRJI9pt3jjt8gIpM8xncUkXkisl5E1onIqYHYoNbkjfRtvPy/LVx/el8uOsWa1xpjmpcGE4iIhAPPAlOAVOAyEUmtVex6YK+qDgCeAB5z503FebztEGAy8Dd3eQBPAR+o6iBgOPZM9CN89e1e7ns7g7EDErlnyqBQh2OMMUfxpQYyCshW1RxVLQfmAFNrlZkKvOIOzwMmiNMudCowR1XLVHUzkA2MEpEOwPdwnqWOqpar6r5j35zWYVdxKTe/tpJuCdE8c9kpRITbmUZjTPPjy5GpB7DN43WuO85rGVWtBIqAxHrm7QcUAP8nIl+JyIsi0t7bykVkhoiki0h6QUGBD+G2bGWVVdz82kqKD1XywlVp1ieVMabZ8iWBeLvDTH0sU9f4COAU4DlVPRk4ABx1bQVAVV9Q1TRVTUtKSvIh3JZLVfnNu5ms+nYfj18ynMHHdwh1SMYYUydfEkgu0MvjdU8gv64yIhIBJAB76pk3F8hV1WXu+Hk4CaVNe23Zt8xZsY1bz+zPD048PtThGGNMvXxJICuAFBHpKyJROBfF59cqMx+Y7g5fDCxWVXXHT3NbafUFUoDlqroD2CYiNU8smgCsPcZtadGWb97Db+dnctagrtz+fXuQkzGm+WvwRkJVrRSR24CFQDjwkqpmishDQLqqzse5GP6qiGTj1DymufNmisgbOMmhErhVVavcRf8E+KeblHKAawO8bS1G/r5D3PLPlfTuHMuT006yBzkZY1oEUa19OaP5SktL0/T09FCHEVClFVVc/Pz/2LL7IO/cOpYBXeNCHZIxppURkZWqmhbo5baprkzKK6v5ets+4mMi6BofTafYKMJC+GtfVbnnrTVk5hfzj6vSLHkYY1qUNpNAKqqquenVdJZs+K4pcHiY0CUuiqT4aLrGx5AUF01S/Hd/XT2GY6MCt6sqq6qpqFJe/XILb3+Vxy+/fwJnp3YL2PKNMaYptIkEoqrc9a9vWLKhgDsnDSQ5sT0F+0spKCmjYH8Zu/aXsbO4lIy8InaXlFHt5axe+6hwunb4LslER4RRVlVNRWU15VXVVFRVU15ZTXmVUl753evvxn/32nP5U4Yex21nDWi6nWGMMQHSJhLIox+s561Vefzi7BO49cz6D9ZV1creg+WHE0uB519JGQX7S1m3o5iKqmoiw8OICg8jKsL5HxkeRmyU8z86IozIcHHKRHiO++51QrtILjy5hz3MyRjTIrX6BPLiZzn8/b85XDmmNz+d0PAvfee0VjRd4qIZbLdiGGNMnVp1J0vvfJXHw++tY8rQ4/jt+UPtl74xxgRQq00gn24s4I43VzOmX2eeuNTurTDGmEBrlQlk9bZ93PzaSlK6xfPC1WnERIY3PJMxxphGaXUJJKeghGtfXkFiXBSvXDuSDjGRoQ7JGGNapVaVQHYWl3LVzOUIMOu60XTtEBPqkIwxptVqNQmk6FAF019azr6D5bx87Sj6dvH6eBFjjDEB0iqa8ZZWVHHjrHQ2FZTw0jUjGdYzIdQhGWNMq9fiE0hVtfKzOV+xfPMenr7sZMaltO6HThljTHPRok9hqSr3vZPBwsyd/Oa8VM4f3j3UIRljTJvRohPIkx9nMXv5t9wyvj/Xju0b6nCMMaZNabEJ5NUvt/LUoix+lNaTOyfZE/yMMaaptcgEsmDNdh54N4MJg7ryhwuHWRclxhgTAj4lEBGZLCIbRCRbRO72Mj1aROa605eJSLLHtHvc8RtEZFKt+cJF5CsR+Y+vAS/dVMjP53zNKb078czlpxAR3iJzoDHGtHgNHn1FJBx4FpgCpAKXiUhqrWLXA3tVdQDwBPCYO28qzvPRhwCTgb+5y6vxM2Cdr8Eeqqhixqx0+iTGMnN6Gu2irIsSY4wJFV9+vo8CslU1R1XLgTnA1FplpgKvuMPzgAninFeaCsxR1TJV3Qxku8tDRHoCPwBe9DXYLbsPEBcTwSvXjaJjbJSvsxljjAkCXxJID2Cbx+tcd5zXMqpaCRQBiQ3M+yTwK6C6vpWLyAwRSReR9KpqZdZ1o+jesZ0PYRtjjAkmXxKItyvUtR/6WlcZr+NF5Fxgl6qubGjlqvqCqqapalq/pPakdItvOGJjjDFB50sCyQV6ebzuCeTXVUZEIoAEYE89844FzheRLTinxM4SkdcaCiQ2qsXfOG+MMa2GLwlkBZAiIn1FJArnovj8WmXmA9Pd4YuBxaqq7vhpbiutvkAKsFxV71HVnqqa7C5vsapeGYDtMcYY00Qa/EmvqpUichuwEAgHXlLVTBF5CEhX1fnATOBVEcnGqXlMc+fNFJE3gLVAJXCrqlYFaVuMMcY0IXEqCi1DWlqapqenhzoMY4xpUURkpaqmBXq5dheeMcYYv1gCMcYY4xdLIMYYY/xiCcQYY4xfLIEYY4zxS4tqhSUiBcDWJlhVF2B3E6wnUCze4LJ4g8viDb6Bqhrwbjxa1K3dqtokDzwXkfRgNHkLFos3uCze4LJ4g09EgnL/g53CMsYY4xdLIMYYY/xiCcS7F0IdQCNZvMFl8QaXxRt8QYm5RV1EN8YY03xYDcQYY4xfLIEYY4zxS5tIICLSS0SWiMg6EckUkZ+54x8UkTwR+dr9O8djnntEJFtENojIJI/xk91x2SJydxBj3iIia9y40t1xnUXkIxHJcv93cseLiDztxvSNiJzisZzpbvksEZle1/qOMdaBHvvwaxEpFpGfN7f9KyIvicguEcnwGBewfSoiI9z3LNud19sTOY813j+JyHo3prdFpKM7PllEDnns6+cbiquubQ9wvAH7DIjzTKJlbrxzxXk+UaDjnesR6xYR+dod3xz2b13HsdB9hlW11f8BxwOnuMPxwEYgFXgQuMNL+VRgNRAN9AU24TwLJdwd7gdEuWVSgxTzFqBLrXF/BO52h+8GHnOHzwHex3mE8BhgmTu+M5Dj/u/kDncK8r4OB3YAfZrb/gW+B5wCZARjnwLLgVPded4HpgQh3olAhDv8mEe8yZ7lai3Ha1x1bXuA4w3YZwB4A5jmDj8P/DjQ8daa/mfggWa0f+s6joXsM9wmaiCqul1VV7nD+4F1QI96ZpkKzFHVMlXdDGQDo9y/bFXNUdVynMfxTg1u9EfF9Yo7/Apwgcf4Wer4EugoIscDk4CPVHWPqu4FPgImBznGCcAmVa2vx4CQ7F9V/RTngWe1YznmfepO66CqS9X5Js7yWFbA4lXVD1W10n35Jc5jouvUQFx1bXvA4q1Hoz4D7i/hs4B5TRGvu74fAbPrW0YT79+6jmMh+wy3iQTiSUSSgZOBZe6o29zq3UseVcwewDaP2XLdcXWNDwYFPhSRlSIywx3XTVW3g/NhAro2o3hrTOPIL11z3b81ArVPe7jDtccH03U4vxJr9BWRr0TkvyIyzh1XX1x1bXugBeIzkAjs80iewd6/44CdqprlMa7Z7N9ax7GQfYbbVAIRkTjgX8DPVbUYeA7oD5wEbMepsoJTfatN6xkfDGNV9RRgCnCriHyvnrLNIV7cc9LnA2+6o5rz/m1IY2Ns6n19L85jov/pjtoO9FbVk4HbgddFpENTx+VFoD4DTb0dl3HkD6Fms3+9HMfqLOplXED3cZtJICISibPT/6mqbwGo6k5VrVLVauAfONVncDJvL4/ZewL59YwPOFXNd//vAt52Y9vpVjNrqs67mku8rinAKlXd6cbebPevh0Dt01yOPJ0UtNjdi57nAle4pxpwTwUVusMrca4jnNBAXHVte8AE8DOwG+cUTESt8QHnruMiYK7HdjSL/evtOFbPeoL+GW4TCcQ9nzkTWKeqf/EYf7xHsQuBmtYY84FpIhItIn2BFJyLSyuAFLc1SBTO6Zr5QYi3vYjE1wzjXDjNcNdV02JiOvCuR7xXu60uxgBFblV2ITBRRDq5pw4muuOC5Yhfbc11/9YSkH3qTtsvImPcz9vVHssKGBGZDNwFnK+qBz3GJ4lIuDvcD2ef5jQQV13bHsh4A/IZcBPlEuDiYMbrOhtYr6qHT+c0h/1b13GsnvUE/zNc3xX21vIHnI5TFfsG+Nr9Owd4FVjjjp8PHO8xz704vzI24NESwZ1vozvt3iDF2w+n9clqILNmPTjngRcBWe7/zu54AZ51Y1oDpHks6zqcC5TZwLVB3MexQCGQ4DGuWe1fnOS2HajA+bV1fSD3KZCGc4DcBDyD29NDgOPNxjl/XfM5ft4t+0P3s7IaWAWc11BcdW17gOMN2GfA/V4sd/fBm0B0oON1x78M3FyrbHPYv3Udx0L2GbauTIwxxvilTZzCMsYYE3iWQIwxxvjFEogxxhi/WAIxxhjjF0sgxhhj/GIJxBg/iMiLIpIa6jiMCSVrxmuMMcYvVgMxpgFuzwDvichqEckQkUtF5BMRSROR8+W7Z0RsEJHN7jwj3E73VorIwlp3ZBvTKlgCMaZhk4F8VR2uqkOBD2omqOp8VT1JVU/CuUv5cbe/or8CF6vqCOAl4PehCNyYYIpouIgxbd4anMTwGPAfVf1Maj2oTUR+BRxS1WdFZCgwFPjILReO02WGMa2KJRBjGqCqG0VkBE6/Q4+IyIee00VkAnAJzhPuwOmDKFNVT23aSI1pWnYKy5gGiEh34KCqvgY8jvMY1JppfYC/AT9S1UPu6A1Akoic6paJFJEhTRy2MUFnNRBjGjYM+JOIVOP03PpjnEQCcA1Ob6hvu6er8lX1HBG5GHhaRBJwvmdP4vTmakyrYc14jTHG+MVOYRljjPGLJRBjjDF+sQRijDHGL5ZAjDHGlSNJmQAAABtJREFU+MUSiDHGGL9YAjHGGOMXSyDGGGP88v9oujNnSHhwmQAAAABJRU5ErkJggg==\n", "text/plain": ["<Figure size 432x288 with 1 Axes>"]}, "metadata": {"needs_background": "light"}, "output_type": "display_data"}], "source": ["import matplotlib.pyplot as plt\n", "df[['size', 'average']].set_index('size').plot()\n", "plt.title(\"Co\u00fbt topk en fonction de la taille du tableau\");"]}, {"cell_type": "markdown", "metadata": {}, "source": ["A peu pr\u00e8s lin\u00e9aire comme attendu."]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [{"name": "stderr", "output_type": "stream", "text": ["\n", "  0%|          | 0/11 [00:00<?, ?it/s]\n", "  9%|\u2589         | 1/11 [00:00<00:09,  1.11it/s]\n", " 18%|\u2588\u258a        | 2/11 [00:02<00:09,  1.05s/it]\n", " 27%|\u2588\u2588\u258b       | 3/11 [00:03<00:09,  1.20s/it]\n", " 36%|\u2588\u2588\u2588\u258b      | 4/11 [00:05<00:09,  1.34s/it]\n", " 45%|\u2588\u2588\u2588\u2588\u258c     | 5/11 [00:07<00:08,  1.44s/it]\n", " 55%|\u2588\u2588\u2588\u2588\u2588\u258d    | 6/11 [00:08<00:07,  1.54s/it]\n", " 64%|\u2588\u2588\u2588\u2588\u2588\u2588\u258e   | 7/11 [00:10<00:06,  1.64s/it]\n", " 73%|\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u258e  | 8/11 [00:13<00:05,  1.86s/it]\n", " 82%|\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u258f | 9/11 [00:15<00:03,  1.93s/it]\n", " 91%|\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588 | 10/11 [00:17<00:01,  1.98s/it]\n", "100%|\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588| 11/11 [00:19<00:00,  2.16s/it]"]}, {"data": {"text/html": ["<div>\n", "<style scoped>\n", "    .dataframe tbody tr th:only-of-type {\n", "        vertical-align: middle;\n", "    }\n", "\n", "    .dataframe tbody tr th {\n", "        vertical-align: top;\n", "    }\n", "\n", "    .dataframe thead th {\n", "        text-align: right;\n", "    }\n", "</style>\n", "<table border=\"1\" class=\"dataframe\">\n", "  <thead>\n", "    <tr style=\"text-align: right;\">\n", "      <th></th>\n", "      <th>average</th>\n", "      <th>deviation</th>\n", "      <th>min_exec</th>\n", "      <th>max_exec</th>\n", "      <th>repeat</th>\n", "      <th>number</th>\n", "      <th>context_size</th>\n", "      <th>k</th>\n", "    </tr>\n", "  </thead>\n", "  <tbody>\n", "    <tr>\n", "      <th>0</th>\n", "      <td>0.018026</td>\n", "      <td>0.002823</td>\n", "      <td>0.015226</td>\n", "      <td>0.025344</td>\n", "      <td>10</td>\n", "      <td>5</td>\n", "      <td>240</td>\n", "      <td>500</td>\n", "    </tr>\n", "    <tr>\n", "      <th>1</th>\n", "      <td>0.027577</td>\n", "      <td>0.008949</td>\n", "      <td>0.018939</td>\n", "      <td>0.043367</td>\n", "      <td>10</td>\n", "      <td>5</td>\n", "      <td>240</td>\n", "      <td>650</td>\n", "    </tr>\n", "    <tr>\n", "      <th>2</th>\n", "      <td>0.031409</td>\n", "      <td>0.011282</td>\n", "      <td>0.020159</td>\n", "      <td>0.056507</td>\n", "      <td>10</td>\n", "      <td>5</td>\n", "      <td>240</td>\n", "      <td>800</td>\n", "    </tr>\n", "    <tr>\n", "      <th>3</th>\n", "      <td>0.032973</td>\n", "      <td>0.007518</td>\n", "      <td>0.025192</td>\n", "      <td>0.047946</td>\n", "      <td>10</td>\n", "      <td>5</td>\n", "      <td>240</td>\n", "      <td>950</td>\n", "    </tr>\n", "    <tr>\n", "      <th>4</th>\n", "      <td>0.033467</td>\n", "      <td>0.007725</td>\n", "      <td>0.025187</td>\n", "      <td>0.051844</td>\n", "      <td>10</td>\n", "      <td>5</td>\n", "      <td>240</td>\n", "      <td>1100</td>\n", "    </tr>\n", "  </tbody>\n", "</table>\n", "</div>"], "text/plain": ["    average  deviation  min_exec  max_exec  repeat  number  context_size     k\n", "0  0.018026   0.002823  0.015226  0.025344      10       5           240   500\n", "1  0.027577   0.008949  0.018939  0.043367      10       5           240   650\n", "2  0.031409   0.011282  0.020159  0.056507      10       5           240   800\n", "3  0.032973   0.007518  0.025192  0.047946      10       5           240   950\n", "4  0.033467   0.007725  0.025187  0.051844      10       5           240  1100"]}, "execution_count": 12, "metadata": {}, "output_type": "execute_result"}], "source": ["rows = []\n", "X = rnd.randn(10000)\n", "for k in tqdm(list(range(500, 2001, 150))):\n", "    res = measure_time('topk_min_position(X, k)', \n", "                       {'X': X, 'topk_min_position': topk_min_position, 'k': k},\n", "                       div_by_number=True,\n", "                       number=5)\n", "    res[\"k\"] = k\n", "    rows.append(res)\n", "    \n", "df = DataFrame(rows)\n", "df.head()"]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAY0AAAEWCAYAAACaBstRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deXwV5fX48c/JThIIIQn7EpawBBSFgIhirSLiAthqC3XDFVurbe1XLdWqSG2rtD+trVRFsbgrxWpRqgLuCyBBBUnCEiBA2LIAIQvZz++PO6HXmJCbcJPJTc779bqve2fmmWfOTG7m3HmeWURVMcYYY3wR5HYAxhhjAoclDWOMMT6zpGGMMcZnljSMMcb4zJKGMcYYn1nSMMYY4zNLGsavROQqETkkIgkux3GNiHzqwnI7iMibIlIgIv9qweVOEJHNLbSsLBGZ2IT5zhaR7OaIybQcSxrmW0TkchFJFZEiEdknIm+LyJk+zhsJ/By4Hri/1rRFIvJAA/OriAxqcvCtw2VANyBOVX/UXAupva1U9RNVHdJcyzOmRojbAZjWQ0R+DcwGfgq8C5QDk4FpgC+/2gcBt6vqpyLSWURCVbWi2QJunfoBW1S10u1AjGkWqmovewHEAEXAj45TJhz4K7DXef0VCHemXQN8Wqu84kkks4AKPEmoCHizjro/dsoXO2WmO+NvBDKBg8BSoGet+n8BbAfygD8DQXXF40z7FIipY9lBeJLlNiAfWAx0caYlOsuZCexylnN3PdvnfmcdK5x1uN6p+3fATiAHeK4mhobqBoKBu5y4CoF1QJ+6thVwNpDtNe8w4EPgMJAGTPWatgiYDyxz6l0DDDzO3/0qJ/584G4gC5jY0Laro57aMf4CSAd6u/39t5fvL9cDsFfreOE5oqgEQo5TZi6wGugKJACfA793pn1rJ+2MU2CQ83kR8EADMRwr7wyf4+xIR+FJWH8HPq5V/gOgC9AX2ALc4B2Ps1N7Cs+RU2Q9y/2Vs169neU8CbzsTKvZsT8FdABGAmXAsHrqmgO84DV8HZ6kNwCIBv4NPO9L3cAdwDfAEECc6XH1bKtjO2Qg1FnmXUCYsx0LgSFef4uDwFg8rQ0vAq/Usz7JeBLTWc62edj5nkxsaNvVUZd3jPcAXwIJbn/37dW4l+sB2Kt1vIArgP0NlNkGXOg1fD6Q5Xy+Bv8njYXAPK/haDy/4hO9yk/2mn4z8J5XPGuAV4HXgLDjLDcDONdruIeznBCvHXtvr+lfADPqqWsO304a7wE3ew0P8bVuYDMwzcdt5b1DngDsxznqcsa9DMzx+ls87TXtQmBTPcu51zuhAFF4jqZqkka9266Ous4G9uBJPHUe9dmr9b+sT8PUyAfiRSRE62+P74mnmaLGTmdcc+mJ59coAKpaJCL5QC88TSQAu48TzyA8v87Hqmr5cZbTD3hdRKq9xlXh6dCusd/rcwmeBObrOtTeZiE+1t0HT6JurJ7AblX1Xp+deLZbQ8uss66aAVUtdv4GNY637fbUUV9nPM2V01W1oKEVMa2PnT1laqwCSoFLjlNmL56dRI2+zjjwtK9H1kwQke615m3K7ZS/tTwRiQLi+PbOqE898YDnV/C1wNsicrwzi3YDF6hqZ69XhKrWtdNrrLq2WSVwwId5dwMDm7jMPiLi/f/dl7p34g3Zh9c2ds6Qi6sVY2O23SHgYuCfInJGE+IxLrOkYQBwfvXdC8wXkUtEJFJEQkXkAhGZ5xR7GfidiCSISLxT/gVn2npguIicIiIReJppvB3A065/PLXLvARc69QZDvwRWKOqWV5l7hCRWBHpA/wST3OU93q9jKdtf6WI1LcDfgL4g4j0A3DWb1oDsfrqZeA2EekvItHOOrx6nKM5b08DvxeRJPE4WURqdtjH255r8CTxO52/4dnAFOCVJsS/BLhYRM4UkTA8/Vre+41GbztV/RBPc+jrInJaE2IyLrKkYY5R1YeBX+M52ycXz6/IW4A3nCIPAKnABjwdtF8641DVLXh2KCuBrXz3FN2FQLKIHBaRN6jbHOBZp8yPVfU9PB2mr+H5xTsQmFFrnv/gOavoazxnAy2sY72edWJ7X0QS61juo3jOzFouIoV4Onb9tTN7BngezxlPO/Aczd3q47wP4zkbaTlwBM+6dXCmzcFrW3nP5DTFTQUuwHMiwT+Aq1V1U2ODV9U0PNfevITnb3AI8L5Ar0nbTlVX4DkKXCoioxsbl3GPqNpDmExgEhEFklQ10+1YjGkv7EjDGGOMzyxpGGOM8Zk1TxljjPGZHWkYY4zxWUBd3BcfH6+JiYluh2GMMQFl3bp1earql8cVBFTSSExMJDU11e0wjDEmoIjIzoZL+caap4wxxvjMkoYxxhifWdIwxhjjs4Dq06hLRUUF2dnZlJaWuh1KQIiIiKB3796Ehoa6HYoxJgAFfNLIzs6mY8eOJCYmIiJuh9OqqSr5+flkZ2fTv39/t8MxxgSggG+eKi0tJS4uzhKGD0SEuLg4OyozxjRZwCcNwBJGI9i2MsaciIBvnjLGGFO34rJK/vzuZr/W2SaONIwxxnzXYx9ksujzLL/WaUmjFaqqqnI7BGNMgNuRV8zTn2znh6N6NVy4ESxp+MEll1zC6NGjGT58OAsWLODxxx/nzjvvPDZ90aJF3Hqr52FtL7zwAmPHjuWUU07hpptuOpYgoqOjuffeeznttNNYtWoVc+fOZcyYMYwYMYJZs2ZRczfitWvXcvLJJ3P66adzxx13MGLECMCTaO644w7GjBnDySefzJNPPtnCW8EY05rMfTON8JBgZl8w1K/1tqk+jfvfTCN97xG/1pncsxP3TRl+3DLPPPMMXbp04ejRo4wZM4b33nuPM844g3nzPI/WfvXVV7n77rvJyMjg1Vdf5bPPPiM0NJSbb76ZF198kauvvpri4mJGjBjB3LlzPctNTubee+8F4KqrruKtt95iypQpXHvttSxYsIDx48cze/bsYzEsXLiQmJgY1q5dS1lZGWeccQaTJk2yU2uNaYfeyzjAB5tzufvCYXTtGOHXuttU0nDL3/72N15//XUAdu/ezY4dOxgwYACrV68mKSmJzZs3c8YZZzB//nzWrVvHmDFjADh69Chdu3YFIDg4mEsvvfRYnR988AHz5s2jpKSEgwcPMnz4cCZMmEBhYSHjx48H4PLLL+ett94CYPny5WzYsIElS5YAUFBQwNatWy1pGNPOlFZUMfetdAYmRDFzfKLf6/cpaYjIZDwPkA8GnlbVB2tNDweeA0YD+cB0Vc0SkUQgA6jpvl+tqj915hkNLAI6AP8Ffqkn+ESoho4ImsOHH37IypUrWbVqFZGRkZx99tmUlpYyffp0Fi9ezNChQ/nBD36AiKCqzJw5kz/96U/fqSciIoLg4GDAc+3JzTffTGpqKn369GHOnDmUlpZyvM2jqvz973/n/PPPb7Z1Nca0fgs/3cHO/BKev34sYSH+74FosEYRCQbmAxcAycBPRCS5VrHrgUOqOgh4BHjIa9o2VT3Fef3Ua/zjwCwgyXlNbvpquKegoIDY2FgiIyPZtGkTq1evBuCHP/whb7zxBi+//DLTp08H4Nxzz2XJkiXk5OQAcPDgQXbu/O4di2suvouPj6eoqOjY0UNsbCwdO3Y8toxXXnnl2Dznn38+jz/+OBUVFQBs2bKF4uLiZlprY0xrtPfwUR57P5Pzh3djQpJfHp/xHb4caYwFMlV1O4CIvAJMA9K9ykwD5jiflwCPyXGuIhORHkAnVV3lDD8HXAK83dgVcNvkyZN54oknOPnkkxkyZAjjxo0DPDv45ORk0tPTGTt2LODpp3jggQeYNGkS1dXVhIaGMn/+fPr16/etOjt37syNN97ISSedRGJi4rHmLPD0Xdx4441ERUVx9tlnExMTA8ANN9xAVlYWo0aNQlVJSEjgjTfeaKGtYIxpDf7w3wyqVfndRbV/1/tPg88IF5HLgMmqeoMzfBVwmqre4lVmo1Mm2xneBpwGRANpwBbgCPA7Vf1ERFKAB1V1olN+AvAbVb24juXPwnNEQt++fUfX/mWekZHBsGHDmrLuAamoqIjo6GgAHnzwQfbt28ejjz7aqDra2zYzpj34fFselz+1hl9NTOJXEwd/a5qIrFPVFH8sx5cjjbqOGGpnmvrK7AP6qmq+04fxhogM97FOz0jVBcACgJSUlBPq82gLli1bxp/+9CcqKyvp168fixYtcjskY4zLKququX9pOr1jO/DT7w1s1mX5kjSygT5ew72BvfWUyRaRECAGOOh0bJcBqOo65whksFO+dwN1mjpMnz79WB+JMcYAPL96J5sPFPLElaOJCA1u1mX50rW+FkgSkf4iEgbMAJbWKrMUmOl8vgx4X1VVRBKcjnREZACeDu/tqroPKBSRcU7fx9XAf5q6Eid40lW7YtvKmLYlr6iMh1dsYUJSPOcP79bsy2vwSENVK0XkFuBdPKfcPqOqaSIyF0hV1aXAQuB5EckEDuJJLABnAXNFpBKoAn6qqgedaT/jf6fcvk0TO8EjIiLIz8+326P7oOZ5GhER/r3Yxxjjnj+/s5mj5VXcN2V4i+wDG+wIb01SUlI0NTX1W+PsyX2NY0/uM6btWL/7MJf84zNuOLM/dx/njKmW7ghv1UJDQ+2qZ2NMu1Ndrdy7NI346HB+cW5Siy3XblhojDEBaMmX2azffZjZk4fSMaLlWg4saRhjTIA5UlrBvHc2MapvZ35wqn9vfd6QgG+eMsaY9uavK7aSX1zOomvHEhTUsicA2ZGGMcYEkC0HCnl2VRYzxvRlRK+YFl++JQ1jjAkQqsqcpWlEh4dwx/lDXInBkoYxxgSItzfu5/Nt+fzfpMF0iQpzJQZLGsYYEwBKyit54K10hvXoxOVj+7oWhyUNY4wJAI9/uI29BaXcP3U4IcHu7botaRhj/Oa5VVn8/q10Kqqq3Q6lTdmVX8KTH29n2ik9Gdu/i6ux2Cm3xhi/2JZbxNw306msVvYcOsrffnJqszxutD2a+1Y6IUHCby9w/zk49hc1xvjF799Kp0NoML88N4l30vZz84vrKKuscjusgPfh5hxWZhzg1nOS6B7j/s1GLWkYY07Y+5sO8OHmXH5xbhK3nTeY318ygpUZOdz43DpKKyxxNFV5ZTVz30ynf3wU152Z6HY4gCUNY8wJKq+s5vdvZTAgIYqZ4xMBuGpcP+ZdejKfbM3lukVrKSmvdDfIAPXMZzvYnlfMvVOSCQ9p3ocr+cqShjHmhPzzsx3syCvmnouTv9WH8eMxfXj4xyNZvT2fa55ZS1GZJY7GOHCklL+/t5WJw7ry/SFd3Q7nGEsaxpgmyyks5e/vZ3LO0Lp3bD84tTePzjiVdbsOcdXCNRQcrXAhysD0p/9mUFGt3HNx/c/JcIMlDWNMk817ZzNllVXH3bFNGdmT+ZePYuOeAq58eg2HS8pbMMLAtDbrIG98vZdZEwbQLy7K7XC+xZKGMaZJvt59mCXrsrnujP70jz/+jm3yiO48ceVoNu8v5CdPrSG/qKyFogw8VdXKff9Jo2dMBDd/f6Db4XyHJQ1jTKNVV3tunBcfHc4t5wzyaZ5zh3Xj6ZkpbM8t4idPrSan0B7RXJeXvthF+r4j3HXRMCLDWt+ldJY0jDGN9sbXe/h692HunDykUU+NO2twAv+8dgy7Dx5lxoLV7C+wxOHtUHE5/2/5Zk4fEMdFJ/VwO5w6WdIwxjRKUVklD769iZG9Y7hsVO9Gzz9+YDzPXT+WnCNlTF+wij2HjzZDlIHpL8s3U1hayZypwxFp2Ycr+cqnpCEik0Vks4hkisjsOqaHi8irzvQ1IpJYa3pfESkSkdu9xmWJyDci8rWIpJ7oihhjWsb8DzLJKSzjvqnDm/zUuDGJXXj++rEcLC7nx0+sYld+iZ+jDDwb9xTw0he7uPr0fgzp3tHtcOrVYNIQkWBgPnABkAz8RERqnypxPXBIVQcBjwAP1Zr+CPB2HdV/X1VPUdWURkdujGlxWXnFLPxkBz88tRej+saeUF2n9o3lpRvGUVxeyfQFq9iRV+ynKAOPqnLf0jS6RIbxq4mD3Q7nuHw50hgLZKrqdlUtB14BptUqMw141vm8BDhXnGMrEbkE2A6k+SdkY4xbHliWQUiw8JsLhvqlvpN6x/DSDeMoq6zmx0+uIjOn0C/1BprXv9rDup2H+M3kocR08L2PyA2+JI1ewG6v4WxnXJ1lVLUSKADiRCQK+A1wfx31KrBcRNaJyKz6Fi4is0QkVURSc3NzfQjXGNMcPt6Sy8qMA9xyziC6dfLfjfOSe3bilVnjUIXpT65m0/4jfqs7EBSWVvCntzcxsk9nLhvd+D6iluZL0qir0VJ9LHM/8IiqFtUx/QxVHYWn2evnInJWXQtX1QWqmqKqKQkJCT6Ea4zxt4qqaua+lU6/uEiuP7O/3+sf3K0ji28aR2hwED9ZsJqNewr8vozW6u/vZ5JbWMb9J9BH1JJ8SRrZQB+v4d7A3vrKiEgIEAMcBE4D5olIFvAr4C4RuQVAVfc67znA63iawYwxrdBzq3aSmVPE7y5qvhvnDUiI5tWbxhEZFsLlT63m692Hm2U5rUlmThHPfLqDH6f05pQ+nd0Oxye+JI21QJKI9BeRMGAGsLRWmaXATOfzZcD76jFBVRNVNRH4K/BHVX1MRKJEpCOA04Q1Cdjoh/UxxvhZflEZf125hQlJ8Uwc1rw3zusXF8WrN42jc2QYVz69htSsg826PDepKve/mUaHsGDunOyfPqKW0GDScPoobgHeBTKAxaqaJiJzRWSqU2whnj6MTODXwHdOy62lG/CpiKwHvgCWqeo7TV0JY0zz+cvyLRwtr+K+Kcktcu1A79hIXr1pHF07hnP1M1+walt+sy/TDcvTD/DJ1jxumziY+Ohwt8PxmajW7p5ovVJSUjQ11S7pMKalbNxTwJTHPuXa8f25d0rL3m0150gpVzy9ht2HSnj66jGcmRTfostvTqUVVUx8+CMiw4JZ9osJhAY373XWIrLOX5c22BXhxpg61TSfxEaG8cuJSS2+/K6dInh51jgS46K47tm1fLApp8VjaC5PfrSd7ENHmTN1eLMnDH8LrGiNMS3mzQ37WJt1iNsnDXHt2oH46HBevnEcg7tFM+v5VJan7XclDn/KPlTCPz7M5KKTejB+YOAdPVnSMMZ8R0l5JX/6bwbDe3Zi+pg+Dc/QjGKjwnjxhnEM7xnDzS9+ybIN+1yN50T9YVkGInDXRcPcDqVJLGkYY77jiQ+3sa+glPumDCe4FVw7ENMhlOevH8upfTtz68tf8sZXe9wOqUk+y8zj7Y37ueX7g+jVuYPb4TSJJQ1jzLfsPljCkx9vZ8rInozt38XtcI7pGBHKomvHclr/OG5b/DWLU3c3PFMrUlFVzX1L0+jbJZIbJgxwO5wms6RhjPmWP/7X03zyWz/dX8qfosJDeOaaMZw5KJ47l2zgxTU73Q7JZ89+nkVmThH3XpxMRGjzXCDZEixpGGOO+Xybp/nk5rMH0bOVNp90CAvmqatTOGdoV+5+fSOLPtvhdkgNyiks5dGVWzl7SALnNvMFks3NkoYxBoDKqmrmvplO79gOzDqrdTefRIQG88SVo5mU3I05b6az4ONtbod0XA+9vZnSyiruvbhlLpBsTpY0jDEAvPzFLjbtL+TuC4cFRPNJWEgQ868YxUUn9+CP/93EY+9vdTukOq3beYjXvszm+jMHMCAh2u1wTljre2q5MabFHS4p5/+t2MLpA+KYPKK72+H4LDQ4iEenn0JYcBB/Wb6F8spqbjtvcKv5NV9VrcxZmka3TuHces4gt8PxC0saxhgeXrGFI0cruG9q4DWfhAQH8ZcfjSQ0WPjb+5mUVVUze/LQVrEei1N3882eAh6dcQpR4W1jd9s21sIY02Sb9h/hhdU7uXJcP4Z27+R2OE0SHCQ8+MOTCQsJ4smPtlNaXsUlp/YiOEgIEiEkWAgWITiojpcIIUFBBAXx7XfhhBJPQUkFf353M2MTuzB1ZE8/rq27LGkY046pKvcvTadjRCi3tfJnUzckKEj4/bQRhAYH8c/Psnh21YmfjluTVOpLNjWfQ4KEoFrjjpRWcLiknDlTh7eKox5/saRhTDv2zsb9rNqez9xpw4mNCnM7nBMmItx7cTJTRvak4GgFVVVKlSpV1Z5XtSqVtcZ96+U1vrJaqa6uu2zNtMqaOo8NV1NVDVXV1cRGhTHrrAEk9wzMo7f6WNIwpp0qrajigWUZDO3ekcvH9nU7HL8REUb1jXU7jDbLTrk1pp1a8PF29hw+yr1TkgkJsNtzG/fYN8WYdmjv4aP848NMLhjRPSBvz23cY0nDmHbowbc3oQp3XRiYt+c27rGkYUw7szbrIEvX7+WmswbQp0uk2+GYAGNJw5h2pOYK5R4xEfz07IFuh2MCkE9JQ0Qmi8hmEckUkdl1TA8XkVed6WtEJLHW9L4iUiQit/tapzHG/xan7iZt7xF+e+EwIsPs5EnTeA0mDREJBuYDFwDJwE9EJLlWseuBQ6o6CHgEeKjW9EeAtxtZpzHGjwqO/u8K5Skn93A7HBOgfDnSGAtkqup2VS0HXgGm1SozDXjW+bwEOFecSyBF5BJgO5DWyDqNMX706MqtHCop594pgXd/KdN6+JI0egHez1XMdsbVWUZVK4ECIE5EooDfAPc3oU4ARGSWiKSKSGpubq4P4RpjasvMKeS5VVnMGNOHEb1i3A7HBDBfkkZdP0nUxzL3A4+oalET6vSMVF2gqimqmpKQkNBgsMaYb1NV7n8znQ5hwdw+aYjb4ZgA50tPWDbQx2u4N7C3njLZIhICxAAHgdOAy0RkHtAZqBaRUmCdD3UaY/xgZUYOn2zN456Lk4mLDnc7HBPgfEkaa4EkEekP7AFmAJfXKrMUmAmsAi4D3ldVBSbUFBCROUCRqj7mJJaG6jTGnKCyyioeWJbOoK7RXH16P7fDMW1Ag0lDVStF5BbgXSAYeEZV00RkLpCqqkuBhcDzIpKJ5whjRlPqPMF1McbU8synWezML+G568YSaveXMn4gngOCwJCSkqKpqaluh2FMQMg5Usr3//Ihpw+M5+mZKW6HY1wkIutU1S9fAvvpYUwb9eA7m6ioUu652O4vZfzHkoYxbdBXuw7x7y/3cP2E/vSLi3I7HNOGWNIwpo2pdu4v1bVjOD///iC3wzFtjCUNY9qY177MZn12AbMvGEp0uN1fyviXJQ1j2pDC0goeemczp/btzCWn1HmTBWNOiP0MMaYNeez9TPKKylg4M4WgILu/lPE/O9Iwpo3YnlvEM5/t4LLRvRnZp7Pb4Zg2ypKGMW2AqvLAsgzCQ4K5c7LdX8o0H2ueMiaAFZdV8u+v9vDs51lk5hRx14VD6doxwu2wTBtmScOYALT7YAnPrcrilbW7KSytZESvTvy/H43kB6da57dpXpY0jAkQqsqqbfn88/MsVmYcIEiEC0Z059ozEhnVN9YerGRahCUNY1q5o+VVvP7VHhZ9voMtB4roEhXGz88exBXj+tIjpoPb4Zl2xpKGMa1U9qESnl+9k1e+2E3B0QqSe3Tiz5edzJSRPYkIDXY7PNNOWdIwphVRVdbsOMiiz7JYnr4fEeH84d24Znx/xiRaE5RxnyUNY1qB0ooq/vP1Hv75WRab9hfSOTKUm743kCvH9aNXZ2uCMq2HJQ1jXLT38FFeWL2Tl7/YxaGSCoZ278hDl57EtFN6WROUaZUsaRjTwlSV1J2HWPRZFu+k7UdVOS/Z0wQ1bkAXa4IyrZolDWNaSGlFFW+u38uiz7NI23uEThEh3HBmf64c148+XSLdDs8Yn1jSMKaZ7S8o5cU1O3lpzS7yi8sZ3C2aP/7gJC45tSeRYfYvaAKLfWONaQaqype7DrPo8yze/mYfVapMHNaNa8YnMn5gnDVBmYBlScMYPyqrrGLZhn0s+jyLDdkFdIwI4ZrxiVx9eiJ946wJygQ+n5KGiEwGHgWCgadV9cFa08OB54DRQD4wXVWzRGQssKCmGDBHVV935skCCoEqoFJVU058dYxxR86RUl5Ys4uX1uwkr6icgQlR/P6SEfzw1F5E2dPzTBvS4LdZRIKB+cB5QDawVkSWqmq6V7HrgUOqOkhEZgAPAdOBjUCKqlaKSA9gvYi8qaqVznzfV9U8f66QMS3lYHE572UcYEX6AT7YnENltXLOkK5cc0YiZw6KtyYo0yb58hNoLJCpqtsBROQVYBrgnTSmAXOcz0uAx0REVLXEq0wEoCccsTEu2plfzIr0AyxPO0DqzoNUK/SIieCqcYlcfXo/EuOj3A7RmGblS9LoBez2Gs4GTquvjHNUUQDEAXkichrwDNAPuMrrKEOB5SKiwJOquoA6iMgsYBZA3759fVopY/ylulrZsKeAFen7WZF+gC0HigAY2r0jt3x/EOcld2dEr052VGHaDV+SRl3/DbWPGOoto6prgOEiMgx4VkTeVtVS4AxV3SsiXYEVIrJJVT/+TiWeZLIAICUlxY5UTLMrq6xi1bZ8VqQfYGXGAQ4cKSM4SBiTGMs9FyczKbmbXVdh2i1fkkY20MdruDewt54y2SISAsQAB70LqGqGiBQDI4BUVd3rjM8RkdfxNIN9J2kY0xIKSir4YHMOK9IP8NGWXIrKKokMC+Z7gxM4L7kb5wztSufIMLfDNMZ1viSNtUCSiPQH9gAzgMtrlVkKzARWAZcB76uqOvPsdpqs+gFDgCwRiQKCVLXQ+TwJmOufVTLGN9mHSliZfoDl6Qf4YsdBKquV+OhwpozswaTk7pw+MM7u/2RMLQ0mDWeHfwvwLp5Tbp9R1TQRmYvniGEpsBB4XkQy8RxhzHBmPxOYLSIVQDVws6rmicgA4HWnHTgEeElV3/H3yhnjTVVJ23uEFemeM57S9x0BYFDXaG48awDnJXfjlN6dCQqy/glj6iOqgdNNkJKSoqmpqW6HYQJIRVU1X+w4yPK0/azMyGHP4aOIwOi+sUwa3o3zkrvT3854Mm2ciKzz17VwdtWRaXMKSyv4aEuu5/qJTTkcKa0kPCSICUkJ/PLcJM4Z1pX46HC3wzQmIFnSMG3CgSOlnusn0g+wevq9DuUAABXVSURBVFs+5VXVdIkKY9Lw7kxK7saEpAQ6hFn/hDEnypKGCRilFVXkFpaRX1xOflEZeUVl7Dlcykebc1ifXQBAYlwkM8f347zk7ozuF0uw9U8Y41eWNIxrqquVI6UV5BWVkVdUTl5RGfnOe17R/xJDfnE5eYVlFJdX1VnPyD6dueP8IUxK7sagrtF2oZ0xzciShvGr8spq8os9O/9crySQX/TdcQeLy6ms/u6JGEECXaLCiIsKJ75jGCNjOxMfHU5cdBgJzntcdDjx0WHER4fbabHGtCBLGqbRdh8s4eOtuWzaV1jr6KCMI6WVdc4THhJEfHQ48R3D6RETwUm9Yohzdvo17zWfYyPDrFnJmFbKkoZpUEl5Jau35/Pxljw+3pLL9rxiADpFhNC1UwRxUWEM69mJ+KiaIwDvROB5jwwLtmYjY9oASxrmO1SVjH2FfLw1l4+35JKadYjyqmoiQoM4rX8cV4zrx/cGxzMwwfoPjGlvLGkYAPKLyvg0M4+PtuTyydY8cgvLABjSrSMzx/fjrMEJjEnsYv0HxrRzljTaqYqqar7cecg5mshj494CVKFzZChnDornrMEJnJWUQPeYCLdDNca0IpY02pFd+SV85DQ5rdqWT1FZJcFBwql9OnPbxMGcNTiBk3rFWCe0MaZeljTasKKySlZty+fjLbl8vDWXnfmeByn2ju3A1FN6clZSAuMHxdEpItTlSI0xgcKSRhtSXa2k7zvCR1s8RxNf7jpERZXSITSY0wfGce34RM4anED/+CjrwDbGNIkljQCXW1jGJ06T06eZeeQVlQMwrEcnrjuzP99LSmB0YizhIdaBbYw5cZY0AtC6nQdZkZ7Dx1tyjz0ToktUGBOS4jkrKYEJSfF07WQd2MYY/7OkEUAKSiq4b+lG3vh6LyFBwqh+sdxx/hDOSkpgeM9O9vAgY0yzs6QRID7YnMPs1zaQV1TOL85N4sYJ/eloHdjGmBZmSaOVKyqr5A/L0nn5i90kdY3m6avHcFLvGLfDMsa0U5Y0WrFV2/K5Y8l69hw+yk3fG8BtEwfbFdnGGFdZ0miFjpZXMe/dTfzzsyz6xUXyr5tOJyWxi9thGWOMJY3W5stdh7h98Xq25xVz9en9mH3BUCLD7M9kjGkdgnwpJCKTRWSziGSKyOw6poeLyKvO9DUikuiMHysiXzuv9SLyA1/rbG/KKquY984mLnv8c0orqnjxhtOYO22EJQxjTKvS4B5JRIKB+cB5QDawVkSWqmq6V7HrgUOqOkhEZgAPAdOBjUCKqlaKSA9gvYi8CagPdbYbG/cUcPu/1rNpfyE/TunN7y5Otlt7GGNaJV9+xo4FMlV1O4CIvAJMA7x38NOAOc7nJcBjIiKqWuJVJgJPsvC1zjavsqqaf3y4jb+9t5XYqDAWzkzh3GHd3A7LGGPq5UvS6AXs9hrOBk6rr4xzVFEAxAF5InIa8AzQD7jKme5LnQCIyCxgFkDfvn19CDcwZOYU8n+L17M+u4ApI3syd+pwYqPC3A7LGGOOy5ekUddlxuprGVVdAwwXkWHAsyLyto914sy/AFgAkJKSUmeZQFJVrTzz6Q7+vHwzUWHBzL98FBed3MPtsIwxxie+JI1soI/XcG9gbz1lskUkBIgBDnoXUNUMESkGRvhYZ5uzM7+Y2/+1nrVZh5g4rBt//OEIuna0e0QZYwKHL0ljLZAkIv2BPcAM4PJaZZYCM4FVwGXA+6qqzjy7nSapfsAQIAs47EOdbYaq8sKaXfxxWQYhQcJffjSSS0f1stuTG2MCToNJw9nh3wK8CwQDz6hqmojMBVJVdSmwEHheRDLxHGHMcGY/E5gtIhVANXCzquYB1FWnn9etVdh7+Ci/eW0Dn2zNY0JSPA9dejI9O3dwOyxjjGkSUQ2cboKUlBRNTU11OwyfqCqvfbmH+5emUaXKXRcO44rT+trRhTGmxYnIOlVN8UddduVYM8gpLOWuf29kZcYBxiTG8pcfjaRfXJTbYRljzAmzpOFnyzbs43dvfENxeRW/u2gY157Rn2B7zoUxpo2wpOEnh4rLuec/G3lrwz5O7h3Dwz8eyaCuHd0Oyxhj/MqShh+8l3GA2f/+hkPF5fzfeYP52dkDCQn26bZexhgTUCxpnIAjpRU88FY6i1OzGdq9I4uuHcPwnvaAJGNM22VJo4k+y8zjjn+tZ/+RUm4+eyC/nJhEeIg9IMkY07ZZ0mikkvJKHnx7E8+t2smA+CiW/Gw8o/rGuh2WMca0CEsajZC+9wg/e3EdO/NLuPaMRO48fygdwuzowhjTfljS8FFFVTW/eOUrjpZX8fKN4zh9YJzbIRljTIuzpOGjZz/PIjOniKeuTrGEYYxpt+y8UB/kFJby6MqtnD0kgYnDurodjjHGuMaShg8eenszpZVV3Htxst07yhjTrlnSaMC6nYd47ctsrj9zAAMSot0OxxhjXGVJ4ziqqpU5S9Po1imcW88Z5HY4xhjjOksax7E4dTff7CngrguHERVu5wwYY4wljXocLiln3jubGJvYhakje7odjjHGtAqWNOrx8IotFBytYM7U4db5bYwxDksadUjfe4QXVu/kynH9SO7Zye1wjDGm1bCkUYuqp/M7pkMovz5vsNvhGGNMq2JJo5al6/fyRdZB7jh/KJ0jw9wOxxhjWhWfkoaITBaRzSKSKSKz65geLiKvOtPXiEiiM/48EVknIt847+d4zfOhU+fXzsv1S62Lyyr5438zOKlXDNPH9HE7HGOMaXUaPI9URIKB+cB5QDawVkSWqmq6V7HrgUOqOkhEZgAPAdOBPGCKqu4VkRHAu0Avr/muUNVUP63LCfv7+5kcOFLG41eOtud6G2NMHXw50hgLZKrqdlUtB14BptUqMw141vm8BDhXRERVv1LVvc74NCBCRML9Ebi/bc8tYuGn27l0VG97PoYxxtTDl6TRC9jtNZzNt48WvlVGVSuBAqD2rWAvBb5S1TKvcf90mqbuERfPa1VV5r6VTnhIML+5YIhbYRhjTKvnS9Koa2eujSkjIsPxNFnd5DX9ClU9CZjgvK6qc+Eis0QkVURSc3NzfQi38d7LyOHDzbn8amISXTtGNMsyjDGmLfAlaWQD3r3CvYG99ZURkRAgBjjoDPcGXgeuVtVtNTOo6h7nvRB4CU8z2Heo6gJVTVHVlISEBF/WqVFKK6qY+1Y6SV2jmTk+0e/1G2NMW+JL0lgLJIlIfxEJA2YAS2uVWQrMdD5fBryvqioinYFlwG9V9bOawiISIiLxzudQ4GJg44mtStM89fF2dh0sYc7U4YQG2xnIxhhzPA3uJZ0+ilvwnPmUASxW1TQRmSsiU51iC4E4EckEfg3UnJZ7CzAIuKfWqbXhwLsisgH4GtgDPOXPFfPFnsNHmf9hJheM6M4Zg+JbevHGGBNwRLV290TrlZKSoqmp/jtD9+cvfsl7mw6w8tffo3dspN/qNcaY1kRE1qlqij/qarftMZ9n5rHsm33cfPYgSxjGGOOjdpk0KqqquW9pGn26dGDWWQPcDscYYwJGu0waz63aydacIu65KJmI0GC3wzHGmIDR7pJGbmEZf12xhbMGJ3Becje3wzHGmIDS7pLGvHc2UVpZxX1Tku3hSsYY00jtKml8tesQ/1qXzXVn9mdgQrTb4RhjTMBpN0mjulq5b2kaXTuGc+s5SW6HY4wxAandJI3FqbvZkF3AXRcOIzq8wTvCG2OMqUO7SBoFJRXMe3czYxJjmXZKT7fDMcaYgNUuksYjK7dwuKScOVOHW+e3McacgDafNDL2HeG5VVlccVo/hveMcTscY4wJaG06aah6Or9jOoTyf5MGux2OMcYEvDadNN7csI8vdhzk9vOH0DkyzO1wjDEm4LXZpFFcVskfl2UwolcnZozp63Y4xhjTJrTZc0/nf5DJ/iOlzL/iVIKDrPPbGGP8oU0eaezIK+apT7bzw1G9GN2vi9vhGGNMm9Emk8bcN9MIDwlm9gVD3Q7FGGPalDaXNN7LOMAHm3P55blJdO0Y4XY4xhjTprSppFFaUcXct9IZmBDFzPGJbodjjDFtTpvqCF/46Q525pfw/PVjCQtpU/nQGGNahTazZ917+CiPvZ/J5OHdmZCU4HY4xhjTJvmUNERksohsFpFMEZldx/RwEXnVmb5GRBKd8eeJyDoR+cZ5P8drntHO+EwR+Zuc4E2h/vDfDKpVufuiYSdSjTHGmONoMGmISDAwH7gASAZ+IiLJtYpdDxxS1UHAI8BDzvg8YIqqngTMBJ73mudxYBaQ5LwmN3UlPt+Wx7IN+/jZ2QPp0yWyqdUYY4xpgC9HGmOBTFXdrqrlwCvAtFplpgHPOp+XAOeKiKjqV6q61xmfBkQ4RyU9gE6qukpVFXgOuKQpK1BZVc39S9PpHduBn35vYFOqMMYY4yNfkkYvYLfXcLYzrs4yqloJFABxtcpcCnylqmVO+ewG6gRARGaJSKqIpObm5n5n+vOrd7L5QCH3XJxMRGiwD6tjjDGmqXxJGnX1NWhjyojIcDxNVjc1ok7PSNUFqpqiqikJCd/u4M4rKuPhFVuYkBTPpORu9cVvjDHGT3xJGtlAH6/h3sDe+sqISAgQAxx0hnsDrwNXq+o2r/K9G6izQfPe2cTR8irum2IPVzLGmJbgS9JYCySJSH8RCQNmAEtrlVmKp6Mb4DLgfVVVEekMLAN+q6qf1RRW1X1AoYiMc86auhr4T2MC/3r3YRanZnPdmf0Z1DW6MbMaY4xpogaThtNHcQvwLpABLFbVNBGZKyJTnWILgTgRyQR+DdSclnsLMAi4R0S+dl5dnWk/A54GMoFtwNu+Bl1drdz3n4107RjOrecM8nU2Y4wxJ0g8Jy8FhpSUFE1NTWXx2t3c+doGHpk+kh+c2rvhGY0xph0TkXWqmuKPugLuivCCoxU89M4mUvrFcskpdZ5wZYwxppkE3L2nHlmxhYMl5Tw7dax1fhtjTAsLqCON0opqnl+9k8vH9mVErxi3wzHGmHYnoJLG3sNH6RgRwu2ThrgdijHGtEsBlTSKyyu5fdIQYqPC3A7FGGPapYBKGhGhwfxkbF+3wzDGmHYroJJGr84RBAdZ57cxxrgloJJGZFjAnexljDFtSkAlDWOMMe6ypGGMMcZnljSMMcb4zJKGMcYYn1nSMMYY4zNLGsYYY3xmScMYY4zPLGkYY4zxWUA9hElEcoGdzVB1PJDXDPU2p0CLOdDiBYu5JQRavBCYMQ9R1Y7+qCigLrFW1YTmqFdEUv31VKuWEmgxB1q8YDG3hECLFwI3Zn/VZc1TxhhjfGZJwxhjjM8saXgscDuAJgi0mAMtXrCYW0KgxQvtPOaA6gg3xhjjLjvSMMYY4zNLGsYYY3zWLpKGiHQWkSUisklEMkTkdBHpIiIrRGSr8x7rlBUR+ZuIZIrIBhEZ5VLMt4lImohsFJGXRSRCRPqLyBon5ldFJMwpG+4MZzrTE1soxmdEJEdENnqNa/R2FZGZTvmtIjKzheP9s/O92CAir4tIZ69pv3Xi3Swi53uNn+yMyxSR2c0Vb30xe027XURUROKdYde38fFiFpFbne2WJiLzvMa7up3r+V6cIiKrReRrEUkVkbHO+NayjfuIyAfO/ixNRH7pjG/+/z9VbfMv4FngBudzGNAZmAfMdsbNBh5yPl8IvA0IMA5Y40K8vYAdQAdneDFwjfM+wxn3BPAz5/PNwBPO5xnAqy0U51nAKGCj17hGbVegC7DdeY91Pse2YLyTgBDn80Ne8SYD64FwoD+wDQh2XtuAAc53aT2Q3JLb2BnfB3gXz8Wu8a1lGx9nO38fWAmEO8NdW8t2rife5cAFXtv1w1a2jXsAo5zPHYEtzrZs9v+/Nn+kISKd8HwpFgKoarmqHgam4UkmOO+XOJ+nAc+px2qgs4j0aOGwwXPhZQcRCQEigX3AOcASZ3rtmGvWZQlwrog0+8PUVfVj4GCt0Y3drucDK1T1oKoeAlYAk1sqXlVdrqqVzuBqoLdXvK+oapmq7gAygbHOK1NVt6tqOfCKU7ZZ1LONAR4B7gS8z2RxfRsfJ+afAQ+qaplTJscrZle3cz3xKtDJ+RwD7PWKtzVs432q+qXzuRDIwPNjs9n//9p80sDzSyUX+KeIfCUiT4tIFNBNVfeB5w8AdHXK9wJ2e82f7YxrMaq6B/gLsAtPsigA1gGHvXZw3nEdi9mZXgDEtWTMXhq7XV3f3l6uw/NrDFpxvCIyFdijqutrTWq1MQODgQlO8+lHIjLGGd9aY/4V8GcR2Y3nf/G3zvhWF694mqNPBdbQAv9/7SFphOA59HxcVU8FivEcttWnrl/oLXpestMOOQ3P4XpPIAq44DhxuR6zD+qLsVXELiJ3A5XAizWj6ijmerwiEgncDdxb1+Q6xrkesyMET/PHOOAOYLFzNNxaY/4ZcJuq9gFuw2mpoJXFKyLRwGvAr1T1yPGK1jGuSXG3h6SRDWSr6hpneAmeJHKgptnJec/xKt/Ha/7e/O/QtKVMBHaoaq6qVgD/BsbjOaSsuV+Yd1zHYnamx1B3k0ZLaOx2dX17O51/FwNXqNPQe5y43I53IJ4fE+tFJMtZ/pci0v04sbkdM04M/3aaR74AqvHc+K+1xjwTz/8dwL/wNJdxnLhaPF4RCcWTMF5U1ZpYm/3/r80nDVXdD+wWkSHOqHOBdGApni8Gzvt/nM9Lgaudsw3GAQU1h3staBcwTkQinV9jNTF/AFxWT8w163IZ8L7Xzq+lNXa7vgtMEpFY5whrkjOuRYjIZOA3wFRVLfGatBSYIZ4z0/oDScAXwFogSTxnsoXhOfFgaUvFq6rfqGpXVU1U1UQ8//SjnO95q9zGjjfw9MkhIoPxdG7n0Uq3M54d5/ecz+cAW53PrWIbO/uFhUCGqj7sNan5//+aq3e/Nb2AU4BUYAOeL28snjb/9/B8Gd4DujhlBZiP58yNb4AUl2K+H9gEbASex3N2yQA8/1CZeH791JyJEuEMZzrTB7RQjC/j6XOpwLPzur4p2xVPX0Km87q2hePNxNOm+7XzesKr/N1OvJtxzqRxxl+I52yVbcDdLb2Na03P4n9nT7m+jY+zncOAF5zv85fAOa1lO9cT75l4+hHX4+krGN3KtvGZeJqRNnh9dy9sif8/u42IMcYYn7X55iljjDH+Y0nDGGOMzyxpGGOM8ZklDWOMMT6zpGGMMcZnljSMOQEikih13IHWmLbKkoYxxhifWdIwxk9EZIBzU8wxDZc2JjBZ0jDGD5zb1LyG54ratW7HY0xzCWm4iDGmAQl47vFzqaqmuR2MMc3JjjSMOXEFeO5fdYbbgRjT3OxIw5gTV47nCWnvikiRqr7kdkDGNBdLGsb4gaoWi8jFwAoRKVbV/zQ4kzEByO5ya4wxxmfWp2GMMcZnljSMMcb4zJKGMcYYn1nSMMYY4zNLGsYYY3xmScMYY4zPLGkYY4zx2f8Hmhm8u7A+8AsAAAAASUVORK5CYII=\n", "text/plain": ["<Figure size 432x288 with 1 Axes>"]}, "metadata": {"needs_background": "light"}, "output_type": "display_data"}], "source": ["df[['k', 'average']].set_index('k').plot()\n", "plt.title(\"Co\u00fbt topk en fonction de k\");"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Pas \u00e9vident, au pire en $O(n\\ln n)$, au mieux en $O(n)$."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Version simplifi\u00e9e\n", "\n", "A-t-on vraiment besoin de `_heapify_max_bottom_position` ?"]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["1 [0] [1]\n", "2 [1, 0] [2, 1]\n", "3 [2, 1, 0] [3, 2, 1]\n", "4 [10, 2, 1, 0] [3, 3, 2, 1]\n", "5 [5, 10, 2, 1, 0] [4, 3, 3, 2, 1]\n", "6 [5, 6, 10, 2, 1, 0] [4, 5, 3, 3, 2, 1]\n", "7 [6, 7, 10, 5, 2, 1, 0] [5, 6, 3, 4, 3, 2, 1]\n", "8 [5, 4, 10, 7, 6, 2, 1, 0] [4, 10, 3, 6, 5, 3, 2, 1]\n", "9 [3, 4, 6, 5, 7, 10, 2, 1, 0] [7, 10, 5, 4, 6, 3, 3, 2, 1]\n"]}], "source": ["def _heapify_max_up_position_simple(ens, pos, first):\n", "    \"Organise un ensemble selon un tas.\"\n", "    i = first\n", "    while True:\n", "        left = 2*i + 1\n", "        right = left+1\n", "        if right < len(pos):\n", "            if ens[pos[left]] > ens[pos[i]] >= ens[pos[right]]:\n", "                swap(pos, i, left)\n", "                i = left\n", "            elif ens[pos[right]] > ens[pos[i]]:\n", "                swap(pos, i, right)\n", "                i = right\n", "            else:\n", "                break\n", "        elif left < len(pos) and ens[pos[left]] > ens[pos[i]]:\n", "            swap(pos, i, left)\n", "            i = left\n", "        else:\n", "            break\n", "\n", "\n", "def topk_min_position_simple(ens, k):\n", "    \"Retourne les positions des k plus petits \u00e9l\u00e9ments d'un ensemble.\"\n", "    \n", "    pos = list(range(k))\n", "    pos[k-1] = 0\n", "    \n", "    for i in range(1, k):\n", "        pos[k-i-1] = i\n", "        _heapify_max_up_position_simple(ens, pos, k-i-1)\n", "        \n", "    for i, el in enumerate(ens[k:]):\n", "        if el < ens[pos[0]]:\n", "            pos[0] = k + i\n", "            _heapify_max_up_position_simple(ens, pos, 0)\n", "    return pos\n", "\n", "    \n", "ens = [1,2,3,7,10,4,5,6,11,12,3]\n", "for k in range(1, len(ens)-1):\n", "    pos = topk_min_position_simple(ens, k)\n", "    print(k, pos, [ens[i] for i in pos])"]}, {"cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["7.5 ms \u00b1 810 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 100 loops each)\n"]}], "source": ["X = rnd.randn(10000)\n", "\n", "%timeit topk_min_position_simple(X, 20)"]}, {"cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}}, "nbformat": 4, "nbformat_minor": 2}