2019-spring/homeworks-practice/homework-practice-11-knn.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Машинное обучение, ФКН ВШЭ\n",
    "\n",
    "# Практическое задание 11. Поиск ближайших соседей\n",
    "\n",
    "## Общая информация\n",
    "\n",
    "Дата выдачи: 6.06.2020\n",
    "\n",
    "Жёсткий дедлайн: 12.06.2020 07:00 MSK\n",
    "\n",
    "## Оценивание и штрафы\n",
    "\n",
    "Каждая из задач имеет определенную «стоимость» (указана в скобках около задачи). Задание является дополнительным, то есть само по себе не учитывается в накопленной оценке. Все полученные за задание баллы являются бонусными, то есть их можно прибавить к оценке за любое теоретическое или практическое домашнее задание из курса. Максимальная оценка за работу — 13 баллов.\n",
    "\n",
    "Сдавать задание после указанного жёсткого срока сдачи нельзя. При выставлении неполного балла за задание в связи с наличием ошибок на усмотрение проверяющего предусмотрена возможность исправить работу на указанных в ответном письме условиях.\n",
    "\n",
    "Задание выполняется самостоятельно. «Похожие» решения считаются плагиатом и все задействованные студенты (в том числе те, у кого списали) не могут получить за него больше 0 баллов (подробнее о плагиате см. на странице курса). Если вы нашли решение какого-то из заданий (или его часть) в открытом источнике, необходимо указать ссылку на этот источник в отдельном блоке в конце вашей работы (скорее всего вы будете не единственным, кто это нашел, поэтому чтобы исключить подозрение в плагиате, необходима ссылка на источник).\n",
    "\n",
    "Неэффективная реализация кода может негативно отразиться на оценке.\n",
    "\n",
    "## Формат сдачи\n",
    "\n",
    "Задания сдаются через систему anytask. Посылка должна содержать:\n",
    "\n",
    "* Ноутбук homework-practice-11-knn-Username.ipynb\n",
    "\n",
    "Username — ваша фамилия и имя на латинице именно в таком порядке.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Часть 0. Введение в Cython\n",
    "\n",
    "Как вы уже могли понять из предыдущих заданий курса и практического опыта, язык Python сам по себе не отличается высокой производительностью. Причин этому много (в частности, Global Interpreter Lock, динамическая типизация и накладные расходы интерпретатора), и обойти их зачастую получается посредством использования функций из компилируемых языков (например, C или C++). \n",
    "\n",
    "Благодаря NumPy и другим библиотекам, которые имеют Python-интерфейс к таким функциям, часто получается перенести вычислительно трудоёмкие операции на другой язык программирования, получая сильный прирост скорости кода при минимальном вреде для читаемости. Избегать циклов средствами Python по большому числу элементов рекомендуется только потому что пресловутая векторизация чаще всего заключается в таких же циклах, но на более быстрых языках (хотя иногда возможно дополнительное ускорение за счёт SIMD/тредов/BLAS и аналогов). \n",
    "\n",
    "Однако иногда в вычислительно трудоёмком коде может потребоваться использование структур данных, отличных от многомерных массивов (например, очередь или стек), либо использование кода на NumPy становится сложным из-за трудоёмкой и неинтуитивной векторизации операций. К тому же, может случиться, что ни одна из встроенных функций NumPy не подходит под решаемую задачу, но требования к производительности всё ещё высоки.\n",
    "\n",
    "В таких ситуациях имеет смысл использовать [Cython](https://cython.readthedocs.io/en/latest/index.html) — надмножество языка Python, поддерживающее указание C-подобных типов для переменных в коде, использование функций напрямую из C и компиляцию Python-кода. У него достаточно подробная [документация](https://cython.readthedocs.io/en/latest/src/tutorial/index.html), но мы разберём пару наглядных примеров, демонстрирующих, как простыми методами заметно ускорить выполнение Python-программ. Сначала загрузим это расширение, чтобы компилировать напрямую в Jupyter:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext cython"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Допустим, нам зачем-то захотелось написать с нуля бинарный поиск. Его реализация на обычном Python иожет выглядеть так (честно взято из https://github.com/python/cpython/blob/master/Lib/bisect.py#L50):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binarySearch(arr, x):\n",
    "    lo = 0\n",
    "    hi = len(arr)\n",
    "\n",
    "    while lo < hi:\n",
    "        mid = (lo+hi)//2\n",
    "        \n",
    "        if arr[mid] < x:\n",
    "            lo = mid+1\n",
    "        else:\n",
    "            hi = mid\n",
    "    return lo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Создадим тестовый массив и протестируем результаты данной реализации, встроенного в модуль `bisect` бинарного поиска и `np.searchsorted`, а также сравним время работы всех функций."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.random.seed(0xDEADF00D)\n",
    "\n",
    "arr = np.random.randint(0, 500, size=10000, dtype=np.int32)\n",
    "arr.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import bisect\n",
    "\n",
    "binarySearch(arr,4) == np.searchsorted(arr, 4) == bisect.bisect_left(arr,4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27.8 µs ± 688 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit binarySearch(arr,4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24.8 µs ± 498 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit bisect.bisect_left(arr,4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7.55 µs ± 66.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit np.searchsorted(arr, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Заметим, что наш код работает медленнее реализации из `bisect`, а функция `searchsorted` из NumPy оказалась быстрее всего. Попробуем просто скомпилировать функцию в Cython и посмотреть на результаты. Это можно сделать посредством [jupyter magic](https://cython.readthedocs.io/en/latest/src/quickstart/build.html#using-the-jupyter-notebook):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html>\n",
       "<!-- Generated by Cython 0.29.17 -->\n",
       "<html>\n",
       "<head>\n",
       "    <meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\" />\n",
       "    <title>Cython: _cython_magic_7098a1a61ec6bdd475680813644fce91.pyx</title>\n",
       "    <style type=\"text/css\">\n",
       "    \n",
       "body.cython { font-family: courier; font-size: 12; }\n",
       "\n",
       ".cython.tag  {  }\n",
       ".cython.line { margin: 0em }\n",
       ".cython.code { font-size: 9; color: #444444; display: none; margin: 0px 0px 0px 8px; border-left: 8px none; }\n",
       "\n",
       ".cython.line .run { background-color: #B0FFB0; }\n",
       ".cython.line .mis { background-color: #FFB0B0; }\n",
       ".cython.code.run  { border-left: 8px solid #B0FFB0; }\n",
       ".cython.code.mis  { border-left: 8px solid #FFB0B0; }\n",
       "\n",
       ".cython.code .py_c_api  { color: red; }\n",
       ".cython.code .py_macro_api  { color: #FF7000; }\n",
       ".cython.code .pyx_c_api  { color: #FF3000; }\n",
       ".cython.code .pyx_macro_api  { color: #FF7000; }\n",
       ".cython.code .refnanny  { color: #FFA000; }\n",
       ".cython.code .trace  { color: #FFA000; }\n",
       ".cython.code .error_goto  { color: #FFA000; }\n",
       "\n",
       ".cython.code .coerce  { color: #008000; border: 1px dotted #008000 }\n",
       ".cython.code .py_attr { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_attr  { color: #0000FF; }\n",
       ".cython.code .py_call { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_call  { color: #0000FF; }\n",
       "\n",
       ".cython.score-0 {background-color: #FFFFff;}\n",
       ".cython.score-1 {background-color: #FFFFe7;}\n",
       ".cython.score-2 {background-color: #FFFFd4;}\n",
       ".cython.score-3 {background-color: #FFFFc4;}\n",
       ".cython.score-4 {background-color: #FFFFb6;}\n",
       ".cython.score-5 {background-color: #FFFFaa;}\n",
       ".cython.score-6 {background-color: #FFFF9f;}\n",
       ".cython.score-7 {background-color: #FFFF96;}\n",
       ".cython.score-8 {background-color: #FFFF8d;}\n",
       ".cython.score-9 {background-color: #FFFF86;}\n",
       ".cython.score-10 {background-color: #FFFF7f;}\n",
       ".cython.score-11 {background-color: #FFFF79;}\n",
       ".cython.score-12 {background-color: #FFFF73;}\n",
       ".cython.score-13 {background-color: #FFFF6e;}\n",
       ".cython.score-14 {background-color: #FFFF6a;}\n",
       ".cython.score-15 {background-color: #FFFF66;}\n",
       ".cython.score-16 {background-color: #FFFF62;}\n",
       ".cython.score-17 {background-color: #FFFF5e;}\n",
       ".cython.score-18 {background-color: #FFFF5b;}\n",
       ".cython.score-19 {background-color: #FFFF57;}\n",
       ".cython.score-20 {background-color: #FFFF55;}\n",
       ".cython.score-21 {background-color: #FFFF52;}\n",
       ".cython.score-22 {background-color: #FFFF4f;}\n",
       ".cython.score-23 {background-color: #FFFF4d;}\n",
       ".cython.score-24 {background-color: #FFFF4b;}\n",
       ".cython.score-25 {background-color: #FFFF48;}\n",
       ".cython.score-26 {background-color: #FFFF46;}\n",
       ".cython.score-27 {background-color: #FFFF44;}\n",
       ".cython.score-28 {background-color: #FFFF43;}\n",
       ".cython.score-29 {background-color: #FFFF41;}\n",
       ".cython.score-30 {background-color: #FFFF3f;}\n",
       ".cython.score-31 {background-color: #FFFF3e;}\n",
       ".cython.score-32 {background-color: #FFFF3c;}\n",
       ".cython.score-33 {background-color: #FFFF3b;}\n",
       ".cython.score-34 {background-color: #FFFF39;}\n",
       ".cython.score-35 {background-color: #FFFF38;}\n",
       ".cython.score-36 {background-color: #FFFF37;}\n",
       ".cython.score-37 {background-color: #FFFF36;}\n",
       ".cython.score-38 {background-color: #FFFF35;}\n",
       ".cython.score-39 {background-color: #FFFF34;}\n",
       ".cython.score-40 {background-color: #FFFF33;}\n",
       ".cython.score-41 {background-color: #FFFF32;}\n",
       ".cython.score-42 {background-color: #FFFF31;}\n",
       ".cython.score-43 {background-color: #FFFF30;}\n",
       ".cython.score-44 {background-color: #FFFF2f;}\n",
       ".cython.score-45 {background-color: #FFFF2e;}\n",
       ".cython.score-46 {background-color: #FFFF2d;}\n",
       ".cython.score-47 {background-color: #FFFF2c;}\n",
       ".cython.score-48 {background-color: #FFFF2b;}\n",
       ".cython.score-49 {background-color: #FFFF2b;}\n",
       ".cython.score-50 {background-color: #FFFF2a;}\n",
       ".cython.score-51 {background-color: #FFFF29;}\n",
       ".cython.score-52 {background-color: #FFFF29;}\n",
       ".cython.score-53 {background-color: #FFFF28;}\n",
       ".cython.score-54 {background-color: #FFFF27;}\n",
       ".cython.score-55 {background-color: #FFFF27;}\n",
       ".cython.score-56 {background-color: #FFFF26;}\n",
       ".cython.score-57 {background-color: #FFFF26;}\n",
       ".cython.score-58 {background-color: #FFFF25;}\n",
       ".cython.score-59 {background-color: #FFFF24;}\n",
       ".cython.score-60 {background-color: #FFFF24;}\n",
       ".cython.score-61 {background-color: #FFFF23;}\n",
       ".cython.score-62 {background-color: #FFFF23;}\n",
       ".cython.score-63 {background-color: #FFFF22;}\n",
       ".cython.score-64 {background-color: #FFFF22;}\n",
       ".cython.score-65 {background-color: #FFFF22;}\n",
       ".cython.score-66 {background-color: #FFFF21;}\n",
       ".cython.score-67 {background-color: #FFFF21;}\n",
       ".cython.score-68 {background-color: #FFFF20;}\n",
       ".cython.score-69 {background-color: #FFFF20;}\n",
       ".cython.score-70 {background-color: #FFFF1f;}\n",
       ".cython.score-71 {background-color: #FFFF1f;}\n",
       ".cython.score-72 {background-color: #FFFF1f;}\n",
       ".cython.score-73 {background-color: #FFFF1e;}\n",
       ".cython.score-74 {background-color: #FFFF1e;}\n",
       ".cython.score-75 {background-color: #FFFF1e;}\n",
       ".cython.score-76 {background-color: #FFFF1d;}\n",
       ".cython.score-77 {background-color: #FFFF1d;}\n",
       ".cython.score-78 {background-color: #FFFF1c;}\n",
       ".cython.score-79 {background-color: #FFFF1c;}\n",
       ".cython.score-80 {background-color: #FFFF1c;}\n",
       ".cython.score-81 {background-color: #FFFF1c;}\n",
       ".cython.score-82 {background-color: #FFFF1b;}\n",
       ".cython.score-83 {background-color: #FFFF1b;}\n",
       ".cython.score-84 {background-color: #FFFF1b;}\n",
       ".cython.score-85 {background-color: #FFFF1a;}\n",
       ".cython.score-86 {background-color: #FFFF1a;}\n",
       ".cython.score-87 {background-color: #FFFF1a;}\n",
       ".cython.score-88 {background-color: #FFFF1a;}\n",
       ".cython.score-89 {background-color: #FFFF19;}\n",
       ".cython.score-90 {background-color: #FFFF19;}\n",
       ".cython.score-91 {background-color: #FFFF19;}\n",
       ".cython.score-92 {background-color: #FFFF19;}\n",
       ".cython.score-93 {background-color: #FFFF18;}\n",
       ".cython.score-94 {background-color: #FFFF18;}\n",
       ".cython.score-95 {background-color: #FFFF18;}\n",
       ".cython.score-96 {background-color: #FFFF18;}\n",
       ".cython.score-97 {background-color: #FFFF17;}\n",
       ".cython.score-98 {background-color: #FFFF17;}\n",
       ".cython.score-99 {background-color: #FFFF17;}\n",
       ".cython.score-100 {background-color: #FFFF17;}\n",
       ".cython.score-101 {background-color: #FFFF16;}\n",
       ".cython.score-102 {background-color: #FFFF16;}\n",
       ".cython.score-103 {background-color: #FFFF16;}\n",
       ".cython.score-104 {background-color: #FFFF16;}\n",
       ".cython.score-105 {background-color: #FFFF16;}\n",
       ".cython.score-106 {background-color: #FFFF15;}\n",
       ".cython.score-107 {background-color: #FFFF15;}\n",
       ".cython.score-108 {background-color: #FFFF15;}\n",
       ".cython.score-109 {background-color: #FFFF15;}\n",
       ".cython.score-110 {background-color: #FFFF15;}\n",
       ".cython.score-111 {background-color: #FFFF15;}\n",
       ".cython.score-112 {background-color: #FFFF14;}\n",
       ".cython.score-113 {background-color: #FFFF14;}\n",
       ".cython.score-114 {background-color: #FFFF14;}\n",
       ".cython.score-115 {background-color: #FFFF14;}\n",
       ".cython.score-116 {background-color: #FFFF14;}\n",
       ".cython.score-117 {background-color: #FFFF14;}\n",
       ".cython.score-118 {background-color: #FFFF13;}\n",
       ".cython.score-119 {background-color: #FFFF13;}\n",
       ".cython.score-120 {background-color: #FFFF13;}\n",
       ".cython.score-121 {background-color: #FFFF13;}\n",
       ".cython.score-122 {background-color: #FFFF13;}\n",
       ".cython.score-123 {background-color: #FFFF13;}\n",
       ".cython.score-124 {background-color: #FFFF13;}\n",
       ".cython.score-125 {background-color: #FFFF12;}\n",
       ".cython.score-126 {background-color: #FFFF12;}\n",
       ".cython.score-127 {background-color: #FFFF12;}\n",
       ".cython.score-128 {background-color: #FFFF12;}\n",
       ".cython.score-129 {background-color: #FFFF12;}\n",
       ".cython.score-130 {background-color: #FFFF12;}\n",
       ".cython.score-131 {background-color: #FFFF12;}\n",
       ".cython.score-132 {background-color: #FFFF11;}\n",
       ".cython.score-133 {background-color: #FFFF11;}\n",
       ".cython.score-134 {background-color: #FFFF11;}\n",
       ".cython.score-135 {background-color: #FFFF11;}\n",
       ".cython.score-136 {background-color: #FFFF11;}\n",
       ".cython.score-137 {background-color: #FFFF11;}\n",
       ".cython.score-138 {background-color: #FFFF11;}\n",
       ".cython.score-139 {background-color: #FFFF11;}\n",
       ".cython.score-140 {background-color: #FFFF11;}\n",
       ".cython.score-141 {background-color: #FFFF10;}\n",
       ".cython.score-142 {background-color: #FFFF10;}\n",
       ".cython.score-143 {background-color: #FFFF10;}\n",
       ".cython.score-144 {background-color: #FFFF10;}\n",
       ".cython.score-145 {background-color: #FFFF10;}\n",
       ".cython.score-146 {background-color: #FFFF10;}\n",
       ".cython.score-147 {background-color: #FFFF10;}\n",
       ".cython.score-148 {background-color: #FFFF10;}\n",
       ".cython.score-149 {background-color: #FFFF10;}\n",
       ".cython.score-150 {background-color: #FFFF0f;}\n",
       ".cython.score-151 {background-color: #FFFF0f;}\n",
       ".cython.score-152 {background-color: #FFFF0f;}\n",
       ".cython.score-153 {background-color: #FFFF0f;}\n",
       ".cython.score-154 {background-color: #FFFF0f;}\n",
       ".cython.score-155 {background-color: #FFFF0f;}\n",
       ".cython.score-156 {background-color: #FFFF0f;}\n",
       ".cython.score-157 {background-color: #FFFF0f;}\n",
       ".cython.score-158 {background-color: #FFFF0f;}\n",
       ".cython.score-159 {background-color: #FFFF0f;}\n",
       ".cython.score-160 {background-color: #FFFF0f;}\n",
       ".cython.score-161 {background-color: #FFFF0e;}\n",
       ".cython.score-162 {background-color: #FFFF0e;}\n",
       ".cython.score-163 {background-color: #FFFF0e;}\n",
       ".cython.score-164 {background-color: #FFFF0e;}\n",
       ".cython.score-165 {background-color: #FFFF0e;}\n",
       ".cython.score-166 {background-color: #FFFF0e;}\n",
       ".cython.score-167 {background-color: #FFFF0e;}\n",
       ".cython.score-168 {background-color: #FFFF0e;}\n",
       ".cython.score-169 {background-color: #FFFF0e;}\n",
       ".cython.score-170 {background-color: #FFFF0e;}\n",
       ".cython.score-171 {background-color: #FFFF0e;}\n",
       ".cython.score-172 {background-color: #FFFF0e;}\n",
       ".cython.score-173 {background-color: #FFFF0d;}\n",
       ".cython.score-174 {background-color: #FFFF0d;}\n",
       ".cython.score-175 {background-color: #FFFF0d;}\n",
       ".cython.score-176 {background-color: #FFFF0d;}\n",
       ".cython.score-177 {background-color: #FFFF0d;}\n",
       ".cython.score-178 {background-color: #FFFF0d;}\n",
       ".cython.score-179 {background-color: #FFFF0d;}\n",
       ".cython.score-180 {background-color: #FFFF0d;}\n",
       ".cython.score-181 {background-color: #FFFF0d;}\n",
       ".cython.score-182 {background-color: #FFFF0d;}\n",
       ".cython.score-183 {background-color: #FFFF0d;}\n",
       ".cython.score-184 {background-color: #FFFF0d;}\n",
       ".cython.score-185 {background-color: #FFFF0d;}\n",
       ".cython.score-186 {background-color: #FFFF0d;}\n",
       ".cython.score-187 {background-color: #FFFF0c;}\n",
       ".cython.score-188 {background-color: #FFFF0c;}\n",
       ".cython.score-189 {background-color: #FFFF0c;}\n",
       ".cython.score-190 {background-color: #FFFF0c;}\n",
       ".cython.score-191 {background-color: #FFFF0c;}\n",
       ".cython.score-192 {background-color: #FFFF0c;}\n",
       ".cython.score-193 {background-color: #FFFF0c;}\n",
       ".cython.score-194 {background-color: #FFFF0c;}\n",
       ".cython.score-195 {background-color: #FFFF0c;}\n",
       ".cython.score-196 {background-color: #FFFF0c;}\n",
       ".cython.score-197 {background-color: #FFFF0c;}\n",
       ".cython.score-198 {background-color: #FFFF0c;}\n",
       ".cython.score-199 {background-color: #FFFF0c;}\n",
       ".cython.score-200 {background-color: #FFFF0c;}\n",
       ".cython.score-201 {background-color: #FFFF0c;}\n",
       ".cython.score-202 {background-color: #FFFF0c;}\n",
       ".cython.score-203 {background-color: #FFFF0b;}\n",
       ".cython.score-204 {background-color: #FFFF0b;}\n",
       ".cython.score-205 {background-color: #FFFF0b;}\n",
       ".cython.score-206 {background-color: #FFFF0b;}\n",
       ".cython.score-207 {background-color: #FFFF0b;}\n",
       ".cython.score-208 {background-color: #FFFF0b;}\n",
       ".cython.score-209 {background-color: #FFFF0b;}\n",
       ".cython.score-210 {background-color: #FFFF0b;}\n",
       ".cython.score-211 {background-color: #FFFF0b;}\n",
       ".cython.score-212 {background-color: #FFFF0b;}\n",
       ".cython.score-213 {background-color: #FFFF0b;}\n",
       ".cython.score-214 {background-color: #FFFF0b;}\n",
       ".cython.score-215 {background-color: #FFFF0b;}\n",
       ".cython.score-216 {background-color: #FFFF0b;}\n",
       ".cython.score-217 {background-color: #FFFF0b;}\n",
       ".cython.score-218 {background-color: #FFFF0b;}\n",
       ".cython.score-219 {background-color: #FFFF0b;}\n",
       ".cython.score-220 {background-color: #FFFF0b;}\n",
       ".cython.score-221 {background-color: #FFFF0b;}\n",
       ".cython.score-222 {background-color: #FFFF0a;}\n",
       ".cython.score-223 {background-color: #FFFF0a;}\n",
       ".cython.score-224 {background-color: #FFFF0a;}\n",
       ".cython.score-225 {background-color: #FFFF0a;}\n",
       ".cython.score-226 {background-color: #FFFF0a;}\n",
       ".cython.score-227 {background-color: #FFFF0a;}\n",
       ".cython.score-228 {background-color: #FFFF0a;}\n",
       ".cython.score-229 {background-color: #FFFF0a;}\n",
       ".cython.score-230 {background-color: #FFFF0a;}\n",
       ".cython.score-231 {background-color: #FFFF0a;}\n",
       ".cython.score-232 {background-color: #FFFF0a;}\n",
       ".cython.score-233 {background-color: #FFFF0a;}\n",
       ".cython.score-234 {background-color: #FFFF0a;}\n",
       ".cython.score-235 {background-color: #FFFF0a;}\n",
       ".cython.score-236 {background-color: #FFFF0a;}\n",
       ".cython.score-237 {background-color: #FFFF0a;}\n",
       ".cython.score-238 {background-color: #FFFF0a;}\n",
       ".cython.score-239 {background-color: #FFFF0a;}\n",
       ".cython.score-240 {background-color: #FFFF0a;}\n",
       ".cython.score-241 {background-color: #FFFF0a;}\n",
       ".cython.score-242 {background-color: #FFFF0a;}\n",
       ".cython.score-243 {background-color: #FFFF0a;}\n",
       ".cython.score-244 {background-color: #FFFF0a;}\n",
       ".cython.score-245 {background-color: #FFFF0a;}\n",
       ".cython.score-246 {background-color: #FFFF09;}\n",
       ".cython.score-247 {background-color: #FFFF09;}\n",
       ".cython.score-248 {background-color: #FFFF09;}\n",
       ".cython.score-249 {background-color: #FFFF09;}\n",
       ".cython.score-250 {background-color: #FFFF09;}\n",
       ".cython.score-251 {background-color: #FFFF09;}\n",
       ".cython.score-252 {background-color: #FFFF09;}\n",
       ".cython.score-253 {background-color: #FFFF09;}\n",
       ".cython.score-254 {background-color: #FFFF09;}\n",
       ".cython .hll { background-color: #ffffcc }\n",
       ".cython  { background: #f8f8f8; }\n",
       ".cython .c { color: #408080; font-style: italic } /* Comment */\n",
       ".cython .err { border: 1px solid #FF0000 } /* Error */\n",
       ".cython .k { color: #008000; font-weight: bold } /* Keyword */\n",
       ".cython .o { color: #666666 } /* Operator */\n",
       ".cython .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       ".cython .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       ".cython .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       ".cython .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       ".cython .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       ".cython .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       ".cython .gd { color: #A00000 } /* Generic.Deleted */\n",
       ".cython .ge { font-style: italic } /* Generic.Emph */\n",
       ".cython .gr { color: #FF0000 } /* Generic.Error */\n",
       ".cython .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       ".cython .gi { color: #00A000 } /* Generic.Inserted */\n",
       ".cython .go { color: #888888 } /* Generic.Output */\n",
       ".cython .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       ".cython .gs { font-weight: bold } /* Generic.Strong */\n",
       ".cython .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       ".cython .gt { color: #0044DD } /* Generic.Traceback */\n",
       ".cython .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       ".cython .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       ".cython .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       ".cython .kp { color: #008000 } /* Keyword.Pseudo */\n",
       ".cython .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       ".cython .kt { color: #B00040 } /* Keyword.Type */\n",
       ".cython .m { color: #666666 } /* Literal.Number */\n",
       ".cython .s { color: #BA2121 } /* Literal.String */\n",
       ".cython .na { color: #7D9029 } /* Name.Attribute */\n",
       ".cython .nb { color: #008000 } /* Name.Builtin */\n",
       ".cython .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       ".cython .no { color: #880000 } /* Name.Constant */\n",
       ".cython .nd { color: #AA22FF } /* Name.Decorator */\n",
       ".cython .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       ".cython .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       ".cython .nf { color: #0000FF } /* Name.Function */\n",
       ".cython .nl { color: #A0A000 } /* Name.Label */\n",
       ".cython .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       ".cython .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       ".cython .nv { color: #19177C } /* Name.Variable */\n",
       ".cython .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       ".cython .w { color: #bbbbbb } /* Text.Whitespace */\n",
       ".cython .mb { color: #666666 } /* Literal.Number.Bin */\n",
       ".cython .mf { color: #666666 } /* Literal.Number.Float */\n",
       ".cython .mh { color: #666666 } /* Literal.Number.Hex */\n",
       ".cython .mi { color: #666666 } /* Literal.Number.Integer */\n",
       ".cython .mo { color: #666666 } /* Literal.Number.Oct */\n",
       ".cython .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       ".cython .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       ".cython .sc { color: #BA2121 } /* Literal.String.Char */\n",
       ".cython .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       ".cython .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       ".cython .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       ".cython .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       ".cython .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       ".cython .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       ".cython .sx { color: #008000 } /* Literal.String.Other */\n",
       ".cython .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       ".cython .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       ".cython .ss { color: #19177C } /* Literal.String.Symbol */\n",
       ".cython .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       ".cython .fm { color: #0000FF } /* Name.Function.Magic */\n",
       ".cython .vc { color: #19177C } /* Name.Variable.Class */\n",
       ".cython .vg { color: #19177C } /* Name.Variable.Global */\n",
       ".cython .vi { color: #19177C } /* Name.Variable.Instance */\n",
       ".cython .vm { color: #19177C } /* Name.Variable.Magic */\n",
       ".cython .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "    </style>\n",
       "</head>\n",
       "<body class=\"cython\">\n",
       "<p><span style=\"border-bottom: solid 1px grey;\">Generated by Cython 0.29.17</span></p>\n",
       "<p>\n",
       "    <span style=\"background-color: #FFFF00\">Yellow lines</span> hint at Python interaction.<br />\n",
       "    Click on a line that starts with a \"<code>+</code>\" to see the C code that Cython generated for it.\n",
       "</p>\n",
       "<div class=\"cython\"><pre class=\"cython line score-0\">&#xA0;<span class=\"\">01</span>: <span class=\"c\"># cython: language_level=3</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">02</span>: </pre>\n",
       "<pre class=\"cython line score-42\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">03</span>: <span class=\"k\">def</span> <span class=\"nf\">binarySearch_v1</span><span class=\"p\">(</span><span class=\"n\">arr</span><span class=\"p\">,</span> <span class=\"n\">x</span><span class=\"p\">):</span></pre>\n",
       "<pre class='cython code score-42 '>/* Python wrapper */\n",
       "static PyObject *__pyx_pw_46_cython_magic_7098a1a61ec6bdd475680813644fce91_1binarySearch_v1(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/\n",
       "static PyMethodDef __pyx_mdef_46_cython_magic_7098a1a61ec6bdd475680813644fce91_1binarySearch_v1 = {\"binarySearch_v1\", (PyCFunction)(void*)(PyCFunctionWithKeywords)__pyx_pw_46_cython_magic_7098a1a61ec6bdd475680813644fce91_1binarySearch_v1, METH_VARARGS|METH_KEYWORDS, 0};\n",
       "static PyObject *__pyx_pw_46_cython_magic_7098a1a61ec6bdd475680813644fce91_1binarySearch_v1(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {\n",
       "  PyObject *__pyx_v_arr = 0;\n",
       "  PyObject *__pyx_v_x = 0;\n",
       "  PyObject *__pyx_r = 0;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"binarySearch_v1 (wrapper)\", 0);\n",
       "  {\n",
       "    static PyObject **__pyx_pyargnames[] = {&amp;__pyx_n_s_arr,&amp;__pyx_n_s_x,0};\n",
       "    PyObject* values[2] = {0,0};\n",
       "    if (unlikely(__pyx_kwds)) {\n",
       "      Py_ssize_t kw_args;\n",
       "      const Py_ssize_t pos_args = <span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args);\n",
       "      switch (pos_args) {\n",
       "        case  2: values[1] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 1);\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  1: values[0] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 0);\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  0: break;\n",
       "        default: goto __pyx_L5_argtuple_error;\n",
       "      }\n",
       "      kw_args = <span class='py_c_api'>PyDict_Size</span>(__pyx_kwds);\n",
       "      switch (pos_args) {\n",
       "        case  0:\n",
       "        if (likely((values[0] = <span class='pyx_c_api'>__Pyx_PyDict_GetItemStr</span>(__pyx_kwds, __pyx_n_s_arr)) != 0)) kw_args--;\n",
       "        else goto __pyx_L5_argtuple_error;\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  1:\n",
       "        if (likely((values[1] = <span class='pyx_c_api'>__Pyx_PyDict_GetItemStr</span>(__pyx_kwds, __pyx_n_s_x)) != 0)) kw_args--;\n",
       "        else {\n",
       "          <span class='pyx_c_api'>__Pyx_RaiseArgtupleInvalid</span>(\"binarySearch_v1\", 1, 2, 2, 1); <span class='error_goto'>__PYX_ERR(0, 3, __pyx_L3_error)</span>\n",
       "        }\n",
       "      }\n",
       "      if (unlikely(kw_args &gt; 0)) {\n",
       "        if (unlikely(<span class='pyx_c_api'>__Pyx_ParseOptionalKeywords</span>(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, \"binarySearch_v1\") &lt; 0)) <span class='error_goto'>__PYX_ERR(0, 3, __pyx_L3_error)</span>\n",
       "      }\n",
       "    } else if (<span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args) != 2) {\n",
       "      goto __pyx_L5_argtuple_error;\n",
       "    } else {\n",
       "      values[0] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 0);\n",
       "      values[1] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 1);\n",
       "    }\n",
       "    __pyx_v_arr = values[0];\n",
       "    __pyx_v_x = values[1];\n",
       "  }\n",
       "  goto __pyx_L4_argument_unpacking_done;\n",
       "  __pyx_L5_argtuple_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_RaiseArgtupleInvalid</span>(\"binarySearch_v1\", 1, 2, 2, <span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args)); <span class='error_goto'>__PYX_ERR(0, 3, __pyx_L3_error)</span>\n",
       "  __pyx_L3_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_7098a1a61ec6bdd475680813644fce91.binarySearch_v1\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return NULL;\n",
       "  __pyx_L4_argument_unpacking_done:;\n",
       "  __pyx_r = __pyx_pf_46_cython_magic_7098a1a61ec6bdd475680813644fce91_binarySearch_v1(__pyx_self, __pyx_v_arr, __pyx_v_x);\n",
       "\n",
       "  /* function exit code */\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "static PyObject *__pyx_pf_46_cython_magic_7098a1a61ec6bdd475680813644fce91_binarySearch_v1(CYTHON_UNUSED PyObject *__pyx_self, PyObject *__pyx_v_arr, PyObject *__pyx_v_x) {\n",
       "  PyObject *__pyx_v_lo = NULL;\n",
       "  PyObject *__pyx_v_hi = NULL;\n",
       "  PyObject *__pyx_v_mid = NULL;\n",
       "  PyObject *__pyx_r = NULL;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"binarySearch_v1\", 0);\n",
       "/* … */\n",
       "  /* function exit code */\n",
       "  __pyx_L1_error:;\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_t_2);\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_t_4);\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_7098a1a61ec6bdd475680813644fce91.binarySearch_v1\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  __pyx_r = NULL;\n",
       "  __pyx_L0:;\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_v_lo);\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_v_hi);\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_v_mid);\n",
       "  <span class='refnanny'>__Pyx_XGIVEREF</span>(__pyx_r);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "/* … */\n",
       "  __pyx_tuple_ = <span class='py_c_api'>PyTuple_Pack</span>(5, __pyx_n_s_arr, __pyx_n_s_x, __pyx_n_s_lo, __pyx_n_s_hi, __pyx_n_s_mid);<span class='error_goto'> if (unlikely(!__pyx_tuple_)) __PYX_ERR(0, 3, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_tuple_);\n",
       "  <span class='refnanny'>__Pyx_GIVEREF</span>(__pyx_tuple_);\n",
       "/* … */\n",
       "  __pyx_t_1 = PyCFunction_NewEx(&amp;__pyx_mdef_46_cython_magic_7098a1a61ec6bdd475680813644fce91_1binarySearch_v1, NULL, __pyx_n_s_cython_magic_7098a1a61ec6bdd475);<span class='error_goto'> if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 3, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  if (<span class='py_c_api'>PyDict_SetItem</span>(__pyx_d, __pyx_n_s_binarySearch_v1, __pyx_t_1) &lt; 0) <span class='error_goto'>__PYX_ERR(0, 3, __pyx_L1_error)</span>\n",
       "  <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_1); __pyx_t_1 = 0;\n",
       "</pre><pre class=\"cython line score-1\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">04</span>:     <span class=\"n\">lo</span> <span class=\"o\">=</span> <span class=\"mf\">0</span></pre>\n",
       "<pre class='cython code score-1 '>  <span class='pyx_macro_api'>__Pyx_INCREF</span>(__pyx_int_0);\n",
       "  __pyx_v_lo = __pyx_int_0;\n",
       "</pre><pre class=\"cython line score-10\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">05</span>:     <span class=\"n\">hi</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">arr</span><span class=\"p\">)</span></pre>\n",
       "<pre class='cython code score-10 '>  __pyx_t_1 = <span class='py_c_api'>PyObject_Length</span>(__pyx_v_arr);<span class='error_goto'> if (unlikely(__pyx_t_1 == ((Py_ssize_t)-1))) __PYX_ERR(0, 5, __pyx_L1_error)</span>\n",
       "  __pyx_t_2 = <span class='py_c_api'>PyInt_FromSsize_t</span>(__pyx_t_1);<span class='error_goto'> if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 5, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_2);\n",
       "  __pyx_v_hi = __pyx_t_2;\n",
       "  __pyx_t_2 = 0;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">06</span>: </pre>\n",
       "<pre class=\"cython line score-8\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">07</span>:     <span class=\"k\">while</span> <span class=\"n\">lo</span> <span class=\"o\">&lt;</span> <span class=\"n\">hi</span><span class=\"p\">:</span></pre>\n",
       "<pre class='cython code score-8 '>  while (1) {\n",
       "    __pyx_t_2 = <span class='py_c_api'>PyObject_RichCompare</span>(__pyx_v_lo, __pyx_v_hi, Py_LT); <span class='refnanny'>__Pyx_XGOTREF</span>(__pyx_t_2);<span class='error_goto'> if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 7, __pyx_L1_error)</span>\n",
       "    __pyx_t_3 = <span class='pyx_c_api'>__Pyx_PyObject_IsTrue</span>(__pyx_t_2); if (unlikely(__pyx_t_3 &lt; 0)) <span class='error_goto'>__PYX_ERR(0, 7, __pyx_L1_error)</span>\n",
       "    <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_2); __pyx_t_2 = 0;\n",
       "    if (!__pyx_t_3) break;\n",
       "</pre><pre class=\"cython line score-9\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">08</span>:         <span class=\"n\">mid</span> <span class=\"o\">=</span> <span class=\"p\">(</span><span class=\"n\">lo</span><span class=\"o\">+</span><span class=\"n\">hi</span><span class=\"p\">)</span><span class=\"o\">//</span><span class=\"mf\">2</span></pre>\n",
       "<pre class='cython code score-9 '>    __pyx_t_2 = <span class='py_c_api'>PyNumber_Add</span>(__pyx_v_lo, __pyx_v_hi);<span class='error_goto'> if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 8, __pyx_L1_error)</span>\n",
       "    <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_2);\n",
       "    __pyx_t_4 = <span class='pyx_c_api'>__Pyx_PyInt_FloorDivideObjC</span>(__pyx_t_2, __pyx_int_2, 2, 0, 0);<span class='error_goto'> if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 8, __pyx_L1_error)</span>\n",
       "    <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_4);\n",
       "    <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_2); __pyx_t_2 = 0;\n",
       "    <span class='pyx_macro_api'>__Pyx_XDECREF_SET</span>(__pyx_v_mid, __pyx_t_4);\n",
       "    __pyx_t_4 = 0;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">09</span>: </pre>\n",
       "<pre class=\"cython line score-11\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">10</span>:         <span class=\"k\">if</span> <span class=\"n\">arr</span><span class=\"p\">[</span><span class=\"n\">mid</span><span class=\"p\">]</span> <span class=\"o\">&lt;</span> <span class=\"n\">x</span><span class=\"p\">:</span></pre>\n",
       "<pre class='cython code score-11 '>    __pyx_t_4 = <span class='pyx_c_api'>__Pyx_PyObject_GetItem</span>(__pyx_v_arr, __pyx_v_mid);<span class='error_goto'> if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 10, __pyx_L1_error)</span>\n",
       "    <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_4);\n",
       "    __pyx_t_2 = <span class='py_c_api'>PyObject_RichCompare</span>(__pyx_t_4, __pyx_v_x, Py_LT); <span class='refnanny'>__Pyx_XGOTREF</span>(__pyx_t_2);<span class='error_goto'> if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 10, __pyx_L1_error)</span>\n",
       "    <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_4); __pyx_t_4 = 0;\n",
       "    __pyx_t_3 = <span class='pyx_c_api'>__Pyx_PyObject_IsTrue</span>(__pyx_t_2); if (unlikely(__pyx_t_3 &lt; 0)) <span class='error_goto'>__PYX_ERR(0, 10, __pyx_L1_error)</span>\n",
       "    <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_2); __pyx_t_2 = 0;\n",
       "    if (__pyx_t_3) {\n",
       "/* … */\n",
       "      goto __pyx_L5;\n",
       "    }\n",
       "</pre><pre class=\"cython line score-3\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">11</span>:             <span class=\"n\">lo</span> <span class=\"o\">=</span> <span class=\"n\">mid</span><span class=\"o\">+</span><span class=\"mf\">1</span></pre>\n",
       "<pre class='cython code score-3 '>      __pyx_t_2 = <span class='pyx_c_api'>__Pyx_PyInt_AddObjC</span>(__pyx_v_mid, __pyx_int_1, 1, 0, 0);<span class='error_goto'> if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 11, __pyx_L1_error)</span>\n",
       "      <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_2);\n",
       "      <span class='pyx_macro_api'>__Pyx_DECREF_SET</span>(__pyx_v_lo, __pyx_t_2);\n",
       "      __pyx_t_2 = 0;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">12</span>:         <span class=\"k\">else</span><span class=\"p\">:</span></pre>\n",
       "<pre class=\"cython line score-2\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">13</span>:             <span class=\"n\">hi</span> <span class=\"o\">=</span> <span class=\"n\">mid</span></pre>\n",
       "<pre class='cython code score-2 '>    /*else*/ {\n",
       "      <span class='pyx_macro_api'>__Pyx_INCREF</span>(__pyx_v_mid);\n",
       "      <span class='pyx_macro_api'>__Pyx_DECREF_SET</span>(__pyx_v_hi, __pyx_v_mid);\n",
       "    }\n",
       "    __pyx_L5:;\n",
       "  }\n",
       "</pre><pre class=\"cython line score-2\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">14</span>:     <span class=\"k\">return</span> <span class=\"n\">lo</span></pre>\n",
       "<pre class='cython code score-2 '>  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_r);\n",
       "  <span class='pyx_macro_api'>__Pyx_INCREF</span>(__pyx_v_lo);\n",
       "  __pyx_r = __pyx_v_lo;\n",
       "  goto __pyx_L0;\n",
       "</pre></div></body></html>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%cython -a\n",
    "# cython: language_level=3\n",
    "\n",
    "def binarySearch_v1(arr, x):\n",
    "    lo = 0\n",
    "    hi = len(arr)\n",
    "\n",
    "    while lo < hi:\n",
    "        mid = (lo+hi)//2\n",
    "        \n",
    "        if arr[mid] < x:\n",
    "            lo = mid+1\n",
    "        else:\n",
    "            hi = mid\n",
    "    return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "26.4 µs ± 265 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit binarySearch_v1(arr,4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Опция `-a` позволит увидеть, как много в результирующем коде взаимодействия с Python (чем интенсивнее жёлтый цвет, тем больше). С помощью такой аннотации можно понять, какие сегменты программы и по какой причине не генерируют оптимизированный код.\n",
    "\n",
    "Как мы видим, код на Python — это валидный код для Cython, однако компиляция конкретно в этом случае почти ничего нам не дала. Если посмотреть на инструкции, которые генерирует компилятор, можно увидеть большое количество взаимодействий с garbage collector и вызовов неспецифичных методов объектов. Давайте типизируем все переменные в функции и посмотрим на результат. Подробнее можно посмотреть [здесь](https://cython.readthedocs.io/en/latest/src/quickstart/cythonize.html) (там есть ещё пример с ускорением кода) и [про NumPy здесь](https://cython.readthedocs.io/en/latest/src/tutorial/numpy.html) и [здесь](https://cython.readthedocs.io/en/latest/src/userguide/memoryviews.html). Если вы не используете функции NumPy напрямую, то лучше применять memoryview (как в примере ниже) из-за быстрой индексации и отсутствия оверхеда от взаимодействия через Python API; если вам нужны оптимизированные примитивы линейной алгебры наподобие умножения матриц или скалярного произведения, они есть в [SciPy](https://docs.scipy.org/doc/scipy/reference/linalg.cython_blas.html) напрямую для Cython."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html>\n",
       "<!-- Generated by Cython 0.29.17 -->\n",
       "<html>\n",
       "<head>\n",
       "    <meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\" />\n",
       "    <title>Cython: _cython_magic_8027e87a9c85416e086a5b9ea1617be6.pyx</title>\n",
       "    <style type=\"text/css\">\n",
       "    \n",
       "body.cython { font-family: courier; font-size: 12; }\n",
       "\n",
       ".cython.tag  {  }\n",
       ".cython.line { margin: 0em }\n",
       ".cython.code { font-size: 9; color: #444444; display: none; margin: 0px 0px 0px 8px; border-left: 8px none; }\n",
       "\n",
       ".cython.line .run { background-color: #B0FFB0; }\n",
       ".cython.line .mis { background-color: #FFB0B0; }\n",
       ".cython.code.run  { border-left: 8px solid #B0FFB0; }\n",
       ".cython.code.mis  { border-left: 8px solid #FFB0B0; }\n",
       "\n",
       ".cython.code .py_c_api  { color: red; }\n",
       ".cython.code .py_macro_api  { color: #FF7000; }\n",
       ".cython.code .pyx_c_api  { color: #FF3000; }\n",
       ".cython.code .pyx_macro_api  { color: #FF7000; }\n",
       ".cython.code .refnanny  { color: #FFA000; }\n",
       ".cython.code .trace  { color: #FFA000; }\n",
       ".cython.code .error_goto  { color: #FFA000; }\n",
       "\n",
       ".cython.code .coerce  { color: #008000; border: 1px dotted #008000 }\n",
       ".cython.code .py_attr { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_attr  { color: #0000FF; }\n",
       ".cython.code .py_call { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_call  { color: #0000FF; }\n",
       "\n",
       ".cython.score-0 {background-color: #FFFFff;}\n",
       ".cython.score-1 {background-color: #FFFFe7;}\n",
       ".cython.score-2 {background-color: #FFFFd4;}\n",
       ".cython.score-3 {background-color: #FFFFc4;}\n",
       ".cython.score-4 {background-color: #FFFFb6;}\n",
       ".cython.score-5 {background-color: #FFFFaa;}\n",
       ".cython.score-6 {background-color: #FFFF9f;}\n",
       ".cython.score-7 {background-color: #FFFF96;}\n",
       ".cython.score-8 {background-color: #FFFF8d;}\n",
       ".cython.score-9 {background-color: #FFFF86;}\n",
       ".cython.score-10 {background-color: #FFFF7f;}\n",
       ".cython.score-11 {background-color: #FFFF79;}\n",
       ".cython.score-12 {background-color: #FFFF73;}\n",
       ".cython.score-13 {background-color: #FFFF6e;}\n",
       ".cython.score-14 {background-color: #FFFF6a;}\n",
       ".cython.score-15 {background-color: #FFFF66;}\n",
       ".cython.score-16 {background-color: #FFFF62;}\n",
       ".cython.score-17 {background-color: #FFFF5e;}\n",
       ".cython.score-18 {background-color: #FFFF5b;}\n",
       ".cython.score-19 {background-color: #FFFF57;}\n",
       ".cython.score-20 {background-color: #FFFF55;}\n",
       ".cython.score-21 {background-color: #FFFF52;}\n",
       ".cython.score-22 {background-color: #FFFF4f;}\n",
       ".cython.score-23 {background-color: #FFFF4d;}\n",
       ".cython.score-24 {background-color: #FFFF4b;}\n",
       ".cython.score-25 {background-color: #FFFF48;}\n",
       ".cython.score-26 {background-color: #FFFF46;}\n",
       ".cython.score-27 {background-color: #FFFF44;}\n",
       ".cython.score-28 {background-color: #FFFF43;}\n",
       ".cython.score-29 {background-color: #FFFF41;}\n",
       ".cython.score-30 {background-color: #FFFF3f;}\n",
       ".cython.score-31 {background-color: #FFFF3e;}\n",
       ".cython.score-32 {background-color: #FFFF3c;}\n",
       ".cython.score-33 {background-color: #FFFF3b;}\n",
       ".cython.score-34 {background-color: #FFFF39;}\n",
       ".cython.score-35 {background-color: #FFFF38;}\n",
       ".cython.score-36 {background-color: #FFFF37;}\n",
       ".cython.score-37 {background-color: #FFFF36;}\n",
       ".cython.score-38 {background-color: #FFFF35;}\n",
       ".cython.score-39 {background-color: #FFFF34;}\n",
       ".cython.score-40 {background-color: #FFFF33;}\n",
       ".cython.score-41 {background-color: #FFFF32;}\n",
       ".cython.score-42 {background-color: #FFFF31;}\n",
       ".cython.score-43 {background-color: #FFFF30;}\n",
       ".cython.score-44 {background-color: #FFFF2f;}\n",
       ".cython.score-45 {background-color: #FFFF2e;}\n",
       ".cython.score-46 {background-color: #FFFF2d;}\n",
       ".cython.score-47 {background-color: #FFFF2c;}\n",
       ".cython.score-48 {background-color: #FFFF2b;}\n",
       ".cython.score-49 {background-color: #FFFF2b;}\n",
       ".cython.score-50 {background-color: #FFFF2a;}\n",
       ".cython.score-51 {background-color: #FFFF29;}\n",
       ".cython.score-52 {background-color: #FFFF29;}\n",
       ".cython.score-53 {background-color: #FFFF28;}\n",
       ".cython.score-54 {background-color: #FFFF27;}\n",
       ".cython.score-55 {background-color: #FFFF27;}\n",
       ".cython.score-56 {background-color: #FFFF26;}\n",
       ".cython.score-57 {background-color: #FFFF26;}\n",
       ".cython.score-58 {background-color: #FFFF25;}\n",
       ".cython.score-59 {background-color: #FFFF24;}\n",
       ".cython.score-60 {background-color: #FFFF24;}\n",
       ".cython.score-61 {background-color: #FFFF23;}\n",
       ".cython.score-62 {background-color: #FFFF23;}\n",
       ".cython.score-63 {background-color: #FFFF22;}\n",
       ".cython.score-64 {background-color: #FFFF22;}\n",
       ".cython.score-65 {background-color: #FFFF22;}\n",
       ".cython.score-66 {background-color: #FFFF21;}\n",
       ".cython.score-67 {background-color: #FFFF21;}\n",
       ".cython.score-68 {background-color: #FFFF20;}\n",
       ".cython.score-69 {background-color: #FFFF20;}\n",
       ".cython.score-70 {background-color: #FFFF1f;}\n",
       ".cython.score-71 {background-color: #FFFF1f;}\n",
       ".cython.score-72 {background-color: #FFFF1f;}\n",
       ".cython.score-73 {background-color: #FFFF1e;}\n",
       ".cython.score-74 {background-color: #FFFF1e;}\n",
       ".cython.score-75 {background-color: #FFFF1e;}\n",
       ".cython.score-76 {background-color: #FFFF1d;}\n",
       ".cython.score-77 {background-color: #FFFF1d;}\n",
       ".cython.score-78 {background-color: #FFFF1c;}\n",
       ".cython.score-79 {background-color: #FFFF1c;}\n",
       ".cython.score-80 {background-color: #FFFF1c;}\n",
       ".cython.score-81 {background-color: #FFFF1c;}\n",
       ".cython.score-82 {background-color: #FFFF1b;}\n",
       ".cython.score-83 {background-color: #FFFF1b;}\n",
       ".cython.score-84 {background-color: #FFFF1b;}\n",
       ".cython.score-85 {background-color: #FFFF1a;}\n",
       ".cython.score-86 {background-color: #FFFF1a;}\n",
       ".cython.score-87 {background-color: #FFFF1a;}\n",
       ".cython.score-88 {background-color: #FFFF1a;}\n",
       ".cython.score-89 {background-color: #FFFF19;}\n",
       ".cython.score-90 {background-color: #FFFF19;}\n",
       ".cython.score-91 {background-color: #FFFF19;}\n",
       ".cython.score-92 {background-color: #FFFF19;}\n",
       ".cython.score-93 {background-color: #FFFF18;}\n",
       ".cython.score-94 {background-color: #FFFF18;}\n",
       ".cython.score-95 {background-color: #FFFF18;}\n",
       ".cython.score-96 {background-color: #FFFF18;}\n",
       ".cython.score-97 {background-color: #FFFF17;}\n",
       ".cython.score-98 {background-color: #FFFF17;}\n",
       ".cython.score-99 {background-color: #FFFF17;}\n",
       ".cython.score-100 {background-color: #FFFF17;}\n",
       ".cython.score-101 {background-color: #FFFF16;}\n",
       ".cython.score-102 {background-color: #FFFF16;}\n",
       ".cython.score-103 {background-color: #FFFF16;}\n",
       ".cython.score-104 {background-color: #FFFF16;}\n",
       ".cython.score-105 {background-color: #FFFF16;}\n",
       ".cython.score-106 {background-color: #FFFF15;}\n",
       ".cython.score-107 {background-color: #FFFF15;}\n",
       ".cython.score-108 {background-color: #FFFF15;}\n",
       ".cython.score-109 {background-color: #FFFF15;}\n",
       ".cython.score-110 {background-color: #FFFF15;}\n",
       ".cython.score-111 {background-color: #FFFF15;}\n",
       ".cython.score-112 {background-color: #FFFF14;}\n",
       ".cython.score-113 {background-color: #FFFF14;}\n",
       ".cython.score-114 {background-color: #FFFF14;}\n",
       ".cython.score-115 {background-color: #FFFF14;}\n",
       ".cython.score-116 {background-color: #FFFF14;}\n",
       ".cython.score-117 {background-color: #FFFF14;}\n",
       ".cython.score-118 {background-color: #FFFF13;}\n",
       ".cython.score-119 {background-color: #FFFF13;}\n",
       ".cython.score-120 {background-color: #FFFF13;}\n",
       ".cython.score-121 {background-color: #FFFF13;}\n",
       ".cython.score-122 {background-color: #FFFF13;}\n",
       ".cython.score-123 {background-color: #FFFF13;}\n",
       ".cython.score-124 {background-color: #FFFF13;}\n",
       ".cython.score-125 {background-color: #FFFF12;}\n",
       ".cython.score-126 {background-color: #FFFF12;}\n",
       ".cython.score-127 {background-color: #FFFF12;}\n",
       ".cython.score-128 {background-color: #FFFF12;}\n",
       ".cython.score-129 {background-color: #FFFF12;}\n",
       ".cython.score-130 {background-color: #FFFF12;}\n",
       ".cython.score-131 {background-color: #FFFF12;}\n",
       ".cython.score-132 {background-color: #FFFF11;}\n",
       ".cython.score-133 {background-color: #FFFF11;}\n",
       ".cython.score-134 {background-color: #FFFF11;}\n",
       ".cython.score-135 {background-color: #FFFF11;}\n",
       ".cython.score-136 {background-color: #FFFF11;}\n",
       ".cython.score-137 {background-color: #FFFF11;}\n",
       ".cython.score-138 {background-color: #FFFF11;}\n",
       ".cython.score-139 {background-color: #FFFF11;}\n",
       ".cython.score-140 {background-color: #FFFF11;}\n",
       ".cython.score-141 {background-color: #FFFF10;}\n",
       ".cython.score-142 {background-color: #FFFF10;}\n",
       ".cython.score-143 {background-color: #FFFF10;}\n",
       ".cython.score-144 {background-color: #FFFF10;}\n",
       ".cython.score-145 {background-color: #FFFF10;}\n",
       ".cython.score-146 {background-color: #FFFF10;}\n",
       ".cython.score-147 {background-color: #FFFF10;}\n",
       ".cython.score-148 {background-color: #FFFF10;}\n",
       ".cython.score-149 {background-color: #FFFF10;}\n",
       ".cython.score-150 {background-color: #FFFF0f;}\n",
       ".cython.score-151 {background-color: #FFFF0f;}\n",
       ".cython.score-152 {background-color: #FFFF0f;}\n",
       ".cython.score-153 {background-color: #FFFF0f;}\n",
       ".cython.score-154 {background-color: #FFFF0f;}\n",
       ".cython.score-155 {background-color: #FFFF0f;}\n",
       ".cython.score-156 {background-color: #FFFF0f;}\n",
       ".cython.score-157 {background-color: #FFFF0f;}\n",
       ".cython.score-158 {background-color: #FFFF0f;}\n",
       ".cython.score-159 {background-color: #FFFF0f;}\n",
       ".cython.score-160 {background-color: #FFFF0f;}\n",
       ".cython.score-161 {background-color: #FFFF0e;}\n",
       ".cython.score-162 {background-color: #FFFF0e;}\n",
       ".cython.score-163 {background-color: #FFFF0e;}\n",
       ".cython.score-164 {background-color: #FFFF0e;}\n",
       ".cython.score-165 {background-color: #FFFF0e;}\n",
       ".cython.score-166 {background-color: #FFFF0e;}\n",
       ".cython.score-167 {background-color: #FFFF0e;}\n",
       ".cython.score-168 {background-color: #FFFF0e;}\n",
       ".cython.score-169 {background-color: #FFFF0e;}\n",
       ".cython.score-170 {background-color: #FFFF0e;}\n",
       ".cython.score-171 {background-color: #FFFF0e;}\n",
       ".cython.score-172 {background-color: #FFFF0e;}\n",
       ".cython.score-173 {background-color: #FFFF0d;}\n",
       ".cython.score-174 {background-color: #FFFF0d;}\n",
       ".cython.score-175 {background-color: #FFFF0d;}\n",
       ".cython.score-176 {background-color: #FFFF0d;}\n",
       ".cython.score-177 {background-color: #FFFF0d;}\n",
       ".cython.score-178 {background-color: #FFFF0d;}\n",
       ".cython.score-179 {background-color: #FFFF0d;}\n",
       ".cython.score-180 {background-color: #FFFF0d;}\n",
       ".cython.score-181 {background-color: #FFFF0d;}\n",
       ".cython.score-182 {background-color: #FFFF0d;}\n",
       ".cython.score-183 {background-color: #FFFF0d;}\n",
       ".cython.score-184 {background-color: #FFFF0d;}\n",
       ".cython.score-185 {background-color: #FFFF0d;}\n",
       ".cython.score-186 {background-color: #FFFF0d;}\n",
       ".cython.score-187 {background-color: #FFFF0c;}\n",
       ".cython.score-188 {background-color: #FFFF0c;}\n",
       ".cython.score-189 {background-color: #FFFF0c;}\n",
       ".cython.score-190 {background-color: #FFFF0c;}\n",
       ".cython.score-191 {background-color: #FFFF0c;}\n",
       ".cython.score-192 {background-color: #FFFF0c;}\n",
       ".cython.score-193 {background-color: #FFFF0c;}\n",
       ".cython.score-194 {background-color: #FFFF0c;}\n",
       ".cython.score-195 {background-color: #FFFF0c;}\n",
       ".cython.score-196 {background-color: #FFFF0c;}\n",
       ".cython.score-197 {background-color: #FFFF0c;}\n",
       ".cython.score-198 {background-color: #FFFF0c;}\n",
       ".cython.score-199 {background-color: #FFFF0c;}\n",
       ".cython.score-200 {background-color: #FFFF0c;}\n",
       ".cython.score-201 {background-color: #FFFF0c;}\n",
       ".cython.score-202 {background-color: #FFFF0c;}\n",
       ".cython.score-203 {background-color: #FFFF0b;}\n",
       ".cython.score-204 {background-color: #FFFF0b;}\n",
       ".cython.score-205 {background-color: #FFFF0b;}\n",
       ".cython.score-206 {background-color: #FFFF0b;}\n",
       ".cython.score-207 {background-color: #FFFF0b;}\n",
       ".cython.score-208 {background-color: #FFFF0b;}\n",
       ".cython.score-209 {background-color: #FFFF0b;}\n",
       ".cython.score-210 {background-color: #FFFF0b;}\n",
       ".cython.score-211 {background-color: #FFFF0b;}\n",
       ".cython.score-212 {background-color: #FFFF0b;}\n",
       ".cython.score-213 {background-color: #FFFF0b;}\n",
       ".cython.score-214 {background-color: #FFFF0b;}\n",
       ".cython.score-215 {background-color: #FFFF0b;}\n",
       ".cython.score-216 {background-color: #FFFF0b;}\n",
       ".cython.score-217 {background-color: #FFFF0b;}\n",
       ".cython.score-218 {background-color: #FFFF0b;}\n",
       ".cython.score-219 {background-color: #FFFF0b;}\n",
       ".cython.score-220 {background-color: #FFFF0b;}\n",
       ".cython.score-221 {background-color: #FFFF0b;}\n",
       ".cython.score-222 {background-color: #FFFF0a;}\n",
       ".cython.score-223 {background-color: #FFFF0a;}\n",
       ".cython.score-224 {background-color: #FFFF0a;}\n",
       ".cython.score-225 {background-color: #FFFF0a;}\n",
       ".cython.score-226 {background-color: #FFFF0a;}\n",
       ".cython.score-227 {background-color: #FFFF0a;}\n",
       ".cython.score-228 {background-color: #FFFF0a;}\n",
       ".cython.score-229 {background-color: #FFFF0a;}\n",
       ".cython.score-230 {background-color: #FFFF0a;}\n",
       ".cython.score-231 {background-color: #FFFF0a;}\n",
       ".cython.score-232 {background-color: #FFFF0a;}\n",
       ".cython.score-233 {background-color: #FFFF0a;}\n",
       ".cython.score-234 {background-color: #FFFF0a;}\n",
       ".cython.score-235 {background-color: #FFFF0a;}\n",
       ".cython.score-236 {background-color: #FFFF0a;}\n",
       ".cython.score-237 {background-color: #FFFF0a;}\n",
       ".cython.score-238 {background-color: #FFFF0a;}\n",
       ".cython.score-239 {background-color: #FFFF0a;}\n",
       ".cython.score-240 {background-color: #FFFF0a;}\n",
       ".cython.score-241 {background-color: #FFFF0a;}\n",
       ".cython.score-242 {background-color: #FFFF0a;}\n",
       ".cython.score-243 {background-color: #FFFF0a;}\n",
       ".cython.score-244 {background-color: #FFFF0a;}\n",
       ".cython.score-245 {background-color: #FFFF0a;}\n",
       ".cython.score-246 {background-color: #FFFF09;}\n",
       ".cython.score-247 {background-color: #FFFF09;}\n",
       ".cython.score-248 {background-color: #FFFF09;}\n",
       ".cython.score-249 {background-color: #FFFF09;}\n",
       ".cython.score-250 {background-color: #FFFF09;}\n",
       ".cython.score-251 {background-color: #FFFF09;}\n",
       ".cython.score-252 {background-color: #FFFF09;}\n",
       ".cython.score-253 {background-color: #FFFF09;}\n",
       ".cython.score-254 {background-color: #FFFF09;}\n",
       ".cython .hll { background-color: #ffffcc }\n",
       ".cython  { background: #f8f8f8; }\n",
       ".cython .c { color: #408080; font-style: italic } /* Comment */\n",
       ".cython .err { border: 1px solid #FF0000 } /* Error */\n",
       ".cython .k { color: #008000; font-weight: bold } /* Keyword */\n",
       ".cython .o { color: #666666 } /* Operator */\n",
       ".cython .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       ".cython .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       ".cython .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       ".cython .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       ".cython .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       ".cython .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       ".cython .gd { color: #A00000 } /* Generic.Deleted */\n",
       ".cython .ge { font-style: italic } /* Generic.Emph */\n",
       ".cython .gr { color: #FF0000 } /* Generic.Error */\n",
       ".cython .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       ".cython .gi { color: #00A000 } /* Generic.Inserted */\n",
       ".cython .go { color: #888888 } /* Generic.Output */\n",
       ".cython .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       ".cython .gs { font-weight: bold } /* Generic.Strong */\n",
       ".cython .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       ".cython .gt { color: #0044DD } /* Generic.Traceback */\n",
       ".cython .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       ".cython .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       ".cython .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       ".cython .kp { color: #008000 } /* Keyword.Pseudo */\n",
       ".cython .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       ".cython .kt { color: #B00040 } /* Keyword.Type */\n",
       ".cython .m { color: #666666 } /* Literal.Number */\n",
       ".cython .s { color: #BA2121 } /* Literal.String */\n",
       ".cython .na { color: #7D9029 } /* Name.Attribute */\n",
       ".cython .nb { color: #008000 } /* Name.Builtin */\n",
       ".cython .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       ".cython .no { color: #880000 } /* Name.Constant */\n",
       ".cython .nd { color: #AA22FF } /* Name.Decorator */\n",
       ".cython .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       ".cython .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       ".cython .nf { color: #0000FF } /* Name.Function */\n",
       ".cython .nl { color: #A0A000 } /* Name.Label */\n",
       ".cython .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       ".cython .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       ".cython .nv { color: #19177C } /* Name.Variable */\n",
       ".cython .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       ".cython .w { color: #bbbbbb } /* Text.Whitespace */\n",
       ".cython .mb { color: #666666 } /* Literal.Number.Bin */\n",
       ".cython .mf { color: #666666 } /* Literal.Number.Float */\n",
       ".cython .mh { color: #666666 } /* Literal.Number.Hex */\n",
       ".cython .mi { color: #666666 } /* Literal.Number.Integer */\n",
       ".cython .mo { color: #666666 } /* Literal.Number.Oct */\n",
       ".cython .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       ".cython .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       ".cython .sc { color: #BA2121 } /* Literal.String.Char */\n",
       ".cython .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       ".cython .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       ".cython .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       ".cython .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       ".cython .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       ".cython .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       ".cython .sx { color: #008000 } /* Literal.String.Other */\n",
       ".cython .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       ".cython .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       ".cython .ss { color: #19177C } /* Literal.String.Symbol */\n",
       ".cython .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       ".cython .fm { color: #0000FF } /* Name.Function.Magic */\n",
       ".cython .vc { color: #19177C } /* Name.Variable.Class */\n",
       ".cython .vg { color: #19177C } /* Name.Variable.Global */\n",
       ".cython .vi { color: #19177C } /* Name.Variable.Instance */\n",
       ".cython .vm { color: #19177C } /* Name.Variable.Magic */\n",
       ".cython .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "    </style>\n",
       "</head>\n",
       "<body class=\"cython\">\n",
       "<p><span style=\"border-bottom: solid 1px grey;\">Generated by Cython 0.29.17</span></p>\n",
       "<p>\n",
       "    <span style=\"background-color: #FFFF00\">Yellow lines</span> hint at Python interaction.<br />\n",
       "    Click on a line that starts with a \"<code>+</code>\" to see the C code that Cython generated for it.\n",
       "</p>\n",
       "<div class=\"cython\"><pre class=\"cython line score-8\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">01</span>: <span class=\"c\"># cython: language_level=3</span></pre>\n",
       "<pre class='cython code score-8 '>  __pyx_t_1 = <span class='pyx_c_api'>__Pyx_PyDict_NewPresized</span>(0);<span class='error_goto'> if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 1, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  if (<span class='py_c_api'>PyDict_SetItem</span>(__pyx_d, __pyx_n_s_test, __pyx_t_1) &lt; 0) <span class='error_goto'>__PYX_ERR(0, 1, __pyx_L1_error)</span>\n",
       "  <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_1); __pyx_t_1 = 0;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">02</span>: </pre>\n",
       "<pre class=\"cython line score-46\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">03</span>: <span class=\"k\">cpdef</span> <span class=\"kt\">Py_ssize_t</span> <span class=\"nf\">binarySearch_v2</span><span class=\"p\">(</span><span class=\"nb\">int</span><span class=\"p\">[::</span><span class=\"mf\">1</span><span class=\"p\">]</span> <span class=\"n\">arr</span><span class=\"p\">,</span><span class=\"nb\">int</span> <span class=\"n\">x</span><span class=\"p\">):</span></pre>\n",
       "<pre class='cython code score-46 '>static PyObject *__pyx_pw_46_cython_magic_8027e87a9c85416e086a5b9ea1617be6_1binarySearch_v2(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/\n",
       "static Py_ssize_t __pyx_f_46_cython_magic_8027e87a9c85416e086a5b9ea1617be6_binarySearch_v2(__Pyx_memviewslice __pyx_v_arr, int __pyx_v_x, CYTHON_UNUSED int __pyx_skip_dispatch) {\n",
       "  Py_ssize_t __pyx_v_lo;\n",
       "  Py_ssize_t __pyx_v_hi;\n",
       "  Py_ssize_t __pyx_v_mid;\n",
       "  Py_ssize_t __pyx_r;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"binarySearch_v2\", 0);\n",
       "/* … */\n",
       "  /* function exit code */\n",
       "  __pyx_L1_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_WriteUnraisable</span>(\"_cython_magic_8027e87a9c85416e086a5b9ea1617be6.binarySearch_v2\", __pyx_clineno, __pyx_lineno, __pyx_filename, 1, 0);\n",
       "  __pyx_r = 0;\n",
       "  __pyx_L0:;\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "/* Python wrapper */\n",
       "static PyObject *__pyx_pw_46_cython_magic_8027e87a9c85416e086a5b9ea1617be6_1binarySearch_v2(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/\n",
       "static PyObject *__pyx_pw_46_cython_magic_8027e87a9c85416e086a5b9ea1617be6_1binarySearch_v2(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {\n",
       "  __Pyx_memviewslice __pyx_v_arr = { 0, 0, { 0 }, { 0 }, { 0 } };\n",
       "  int __pyx_v_x;\n",
       "  PyObject *__pyx_r = 0;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"binarySearch_v2 (wrapper)\", 0);\n",
       "  {\n",
       "    static PyObject **__pyx_pyargnames[] = {&amp;__pyx_n_s_arr,&amp;__pyx_n_s_x,0};\n",
       "    PyObject* values[2] = {0,0};\n",
       "    if (unlikely(__pyx_kwds)) {\n",
       "      Py_ssize_t kw_args;\n",
       "      const Py_ssize_t pos_args = <span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args);\n",
       "      switch (pos_args) {\n",
       "        case  2: values[1] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 1);\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  1: values[0] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 0);\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  0: break;\n",
       "        default: goto __pyx_L5_argtuple_error;\n",
       "      }\n",
       "      kw_args = <span class='py_c_api'>PyDict_Size</span>(__pyx_kwds);\n",
       "      switch (pos_args) {\n",
       "        case  0:\n",
       "        if (likely((values[0] = <span class='pyx_c_api'>__Pyx_PyDict_GetItemStr</span>(__pyx_kwds, __pyx_n_s_arr)) != 0)) kw_args--;\n",
       "        else goto __pyx_L5_argtuple_error;\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  1:\n",
       "        if (likely((values[1] = <span class='pyx_c_api'>__Pyx_PyDict_GetItemStr</span>(__pyx_kwds, __pyx_n_s_x)) != 0)) kw_args--;\n",
       "        else {\n",
       "          <span class='pyx_c_api'>__Pyx_RaiseArgtupleInvalid</span>(\"binarySearch_v2\", 1, 2, 2, 1); <span class='error_goto'>__PYX_ERR(0, 3, __pyx_L3_error)</span>\n",
       "        }\n",
       "      }\n",
       "      if (unlikely(kw_args &gt; 0)) {\n",
       "        if (unlikely(<span class='pyx_c_api'>__Pyx_ParseOptionalKeywords</span>(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, \"binarySearch_v2\") &lt; 0)) <span class='error_goto'>__PYX_ERR(0, 3, __pyx_L3_error)</span>\n",
       "      }\n",
       "    } else if (<span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args) != 2) {\n",
       "      goto __pyx_L5_argtuple_error;\n",
       "    } else {\n",
       "      values[0] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 0);\n",
       "      values[1] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 1);\n",
       "    }\n",
       "    __pyx_v_arr = <span class='pyx_c_api'>__Pyx_PyObject_to_MemoryviewSlice_dc_int</span>(values[0], PyBUF_WRITABLE);<span class='error_goto'> if (unlikely(!__pyx_v_arr.memview)) __PYX_ERR(0, 3, __pyx_L3_error)</span>\n",
       "    __pyx_v_x = <span class='pyx_c_api'>__Pyx_PyInt_As_int</span>(values[1]); if (unlikely((__pyx_v_x == (int)-1) &amp;&amp; <span class='py_c_api'>PyErr_Occurred</span>())) <span class='error_goto'>__PYX_ERR(0, 3, __pyx_L3_error)</span>\n",
       "  }\n",
       "  goto __pyx_L4_argument_unpacking_done;\n",
       "  __pyx_L5_argtuple_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_RaiseArgtupleInvalid</span>(\"binarySearch_v2\", 1, 2, 2, <span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args)); <span class='error_goto'>__PYX_ERR(0, 3, __pyx_L3_error)</span>\n",
       "  __pyx_L3_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_8027e87a9c85416e086a5b9ea1617be6.binarySearch_v2\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return NULL;\n",
       "  __pyx_L4_argument_unpacking_done:;\n",
       "  __pyx_r = __pyx_pf_46_cython_magic_8027e87a9c85416e086a5b9ea1617be6_binarySearch_v2(__pyx_self, __pyx_v_arr, __pyx_v_x);\n",
       "\n",
       "  /* function exit code */\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "static PyObject *__pyx_pf_46_cython_magic_8027e87a9c85416e086a5b9ea1617be6_binarySearch_v2(CYTHON_UNUSED PyObject *__pyx_self, __Pyx_memviewslice __pyx_v_arr, int __pyx_v_x) {\n",
       "  PyObject *__pyx_r = NULL;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"binarySearch_v2\", 0);\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_r);\n",
       "  if (unlikely(!__pyx_v_arr.memview)) { <span class='pyx_c_api'>__Pyx_RaiseUnboundLocalError</span>(\"arr\"); <span class='error_goto'>__PYX_ERR(0, 3, __pyx_L1_error)</span> }\n",
       "  __pyx_t_1 = <span class='py_c_api'>PyInt_FromSsize_t</span>(__pyx_f_46_cython_magic_8027e87a9c85416e086a5b9ea1617be6_binarySearch_v2(__pyx_v_arr, __pyx_v_x, 0));<span class='error_goto'> if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 3, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  __pyx_r = __pyx_t_1;\n",
       "  __pyx_t_1 = 0;\n",
       "  goto __pyx_L0;\n",
       "\n",
       "  /* function exit code */\n",
       "  __pyx_L1_error:;\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_t_1);\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_8027e87a9c85416e086a5b9ea1617be6.binarySearch_v2\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  __pyx_r = NULL;\n",
       "  __pyx_L0:;\n",
       "  __PYX_XDEC_MEMVIEW(&amp;__pyx_v_arr, 1);\n",
       "  <span class='refnanny'>__Pyx_XGIVEREF</span>(__pyx_r);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">04</span>:     <span class=\"k\">cdef</span><span class=\"p\">:</span></pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">05</span>:         <span class=\"n\">Py_ssize_t</span> <span class=\"n\">lo</span> <span class=\"o\">=</span> <span class=\"mf\">0</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_v_lo = 0;\n",
       "</pre><pre class=\"cython line score-2\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">06</span>:         <span class=\"n\">Py_ssize_t</span> <span class=\"n\">hi</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">arr</span><span class=\"p\">)</span></pre>\n",
       "<pre class='cython code score-2 '>  __pyx_t_1 = <span class='pyx_c_api'>__Pyx_MemoryView_Len</span>(__pyx_v_arr); \n",
       "  __pyx_v_hi = __pyx_t_1;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">07</span>:         <span class=\"n\">Py_ssize_t</span> <span class=\"n\">mid</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">08</span>: </pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">09</span>:     <span class=\"k\">while</span> <span class=\"n\">lo</span> <span class=\"o\">&lt;</span> <span class=\"n\">hi</span><span class=\"p\">:</span></pre>\n",
       "<pre class='cython code score-0 '>  while (1) {\n",
       "    __pyx_t_2 = ((__pyx_v_lo &lt; __pyx_v_hi) != 0);\n",
       "    if (!__pyx_t_2) break;\n",
       "</pre><pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">10</span>:         <span class=\"n\">mid</span> <span class=\"o\">=</span> <span class=\"p\">(</span><span class=\"n\">lo</span><span class=\"o\">+</span><span class=\"n\">hi</span><span class=\"p\">)</span><span class=\"o\">//</span><span class=\"mf\">2</span></pre>\n",
       "<pre class='cython code score-0 '>    __pyx_v_mid = __Pyx_div_Py_ssize_t((__pyx_v_lo + __pyx_v_hi), 2);\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">11</span>: </pre>\n",
       "<pre class=\"cython line score-2\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">12</span>:         <span class=\"k\">if</span> <span class=\"n\">arr</span><span class=\"p\">[</span><span class=\"n\">mid</span><span class=\"p\">]</span> <span class=\"o\">&lt;</span> <span class=\"n\">x</span><span class=\"p\">:</span></pre>\n",
       "<pre class='cython code score-2 '>    __pyx_t_3 = __pyx_v_mid;\n",
       "    __pyx_t_4 = -1;\n",
       "    if (__pyx_t_3 &lt; 0) {\n",
       "      __pyx_t_3 += __pyx_v_arr.shape[0];\n",
       "      if (unlikely(__pyx_t_3 &lt; 0)) __pyx_t_4 = 0;\n",
       "    } else if (unlikely(__pyx_t_3 &gt;= __pyx_v_arr.shape[0])) __pyx_t_4 = 0;\n",
       "    if (unlikely(__pyx_t_4 != -1)) {\n",
       "      <span class='pyx_c_api'>__Pyx_RaiseBufferIndexError</span>(__pyx_t_4);\n",
       "      <span class='error_goto'>__PYX_ERR(0, 12, __pyx_L1_error)</span>\n",
       "    }\n",
       "    __pyx_t_2 = (((*((int *) ( /* dim=0 */ ((char *) (((int *) __pyx_v_arr.data) + __pyx_t_3)) ))) &lt; __pyx_v_x) != 0);\n",
       "    if (__pyx_t_2) {\n",
       "/* … */\n",
       "      goto __pyx_L5;\n",
       "    }\n",
       "</pre><pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">13</span>:             <span class=\"n\">lo</span> <span class=\"o\">=</span> <span class=\"n\">mid</span><span class=\"o\">+</span><span class=\"mf\">1</span></pre>\n",
       "<pre class='cython code score-0 '>      __pyx_v_lo = (__pyx_v_mid + 1);\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">14</span>:         <span class=\"k\">else</span><span class=\"p\">:</span></pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">15</span>:             <span class=\"n\">hi</span> <span class=\"o\">=</span> <span class=\"n\">mid</span></pre>\n",
       "<pre class='cython code score-0 '>    /*else*/ {\n",
       "      __pyx_v_hi = __pyx_v_mid;\n",
       "    }\n",
       "    __pyx_L5:;\n",
       "  }\n",
       "</pre><pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">16</span>:     <span class=\"k\">return</span> <span class=\"n\">lo</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_r = __pyx_v_lo;\n",
       "  goto __pyx_L0;\n",
       "</pre></div></body></html>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%cython -a\n",
    "# cython: language_level=3\n",
    "\n",
    "cpdef Py_ssize_t binarySearch_v2(int[::1] arr,int x):\n",
    "    cdef:\n",
    "        Py_ssize_t lo = 0\n",
    "        Py_ssize_t hi = len(arr)\n",
    "        Py_ssize_t mid\n",
    "\n",
    "    while lo < hi:\n",
    "        mid = (lo+hi)//2\n",
    "        \n",
    "        if arr[mid] < x:\n",
    "            lo = mid+1\n",
    "        else:\n",
    "            hi = mid\n",
    "    return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "654 ns ± 1.42 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit binarySearch_v2(arr,4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мы получили ускорение почти в 40 раз за счёт простого добавления типов переменных. Можно добиться ещё ряда оптимизаций даже в случае бинарного поиска: во-первых, при индексировании отрицательным числом компилятору требуется переходить в другую ветку кода и прибавлять к индексу длину массива, что может быть лишней операцией в нашем случае. Для отключения таких проверок (и, соответственно, отрицательных индексов) есть специальная [директива компилятора](https://cython.readthedocs.io/en/latest/src/userguide/source_files_and_compilation.html#compiler-directives) `wraparound=False`. Также мы отключим проверки на `None`, проверки на выход за границы массива и проверки на деление на 0:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html>\n",
       "<!-- Generated by Cython 0.29.17 -->\n",
       "<html>\n",
       "<head>\n",
       "    <meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\" />\n",
       "    <title>Cython: _cython_magic_0f6259adb0185f4ee53abc0f79ce9417.pyx</title>\n",
       "    <style type=\"text/css\">\n",
       "    \n",
       "body.cython { font-family: courier; font-size: 12; }\n",
       "\n",
       ".cython.tag  {  }\n",
       ".cython.line { margin: 0em }\n",
       ".cython.code { font-size: 9; color: #444444; display: none; margin: 0px 0px 0px 8px; border-left: 8px none; }\n",
       "\n",
       ".cython.line .run { background-color: #B0FFB0; }\n",
       ".cython.line .mis { background-color: #FFB0B0; }\n",
       ".cython.code.run  { border-left: 8px solid #B0FFB0; }\n",
       ".cython.code.mis  { border-left: 8px solid #FFB0B0; }\n",
       "\n",
       ".cython.code .py_c_api  { color: red; }\n",
       ".cython.code .py_macro_api  { color: #FF7000; }\n",
       ".cython.code .pyx_c_api  { color: #FF3000; }\n",
       ".cython.code .pyx_macro_api  { color: #FF7000; }\n",
       ".cython.code .refnanny  { color: #FFA000; }\n",
       ".cython.code .trace  { color: #FFA000; }\n",
       ".cython.code .error_goto  { color: #FFA000; }\n",
       "\n",
       ".cython.code .coerce  { color: #008000; border: 1px dotted #008000 }\n",
       ".cython.code .py_attr { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_attr  { color: #0000FF; }\n",
       ".cython.code .py_call { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_call  { color: #0000FF; }\n",
       "\n",
       ".cython.score-0 {background-color: #FFFFff;}\n",
       ".cython.score-1 {background-color: #FFFFe7;}\n",
       ".cython.score-2 {background-color: #FFFFd4;}\n",
       ".cython.score-3 {background-color: #FFFFc4;}\n",
       ".cython.score-4 {background-color: #FFFFb6;}\n",
       ".cython.score-5 {background-color: #FFFFaa;}\n",
       ".cython.score-6 {background-color: #FFFF9f;}\n",
       ".cython.score-7 {background-color: #FFFF96;}\n",
       ".cython.score-8 {background-color: #FFFF8d;}\n",
       ".cython.score-9 {background-color: #FFFF86;}\n",
       ".cython.score-10 {background-color: #FFFF7f;}\n",
       ".cython.score-11 {background-color: #FFFF79;}\n",
       ".cython.score-12 {background-color: #FFFF73;}\n",
       ".cython.score-13 {background-color: #FFFF6e;}\n",
       ".cython.score-14 {background-color: #FFFF6a;}\n",
       ".cython.score-15 {background-color: #FFFF66;}\n",
       ".cython.score-16 {background-color: #FFFF62;}\n",
       ".cython.score-17 {background-color: #FFFF5e;}\n",
       ".cython.score-18 {background-color: #FFFF5b;}\n",
       ".cython.score-19 {background-color: #FFFF57;}\n",
       ".cython.score-20 {background-color: #FFFF55;}\n",
       ".cython.score-21 {background-color: #FFFF52;}\n",
       ".cython.score-22 {background-color: #FFFF4f;}\n",
       ".cython.score-23 {background-color: #FFFF4d;}\n",
       ".cython.score-24 {background-color: #FFFF4b;}\n",
       ".cython.score-25 {background-color: #FFFF48;}\n",
       ".cython.score-26 {background-color: #FFFF46;}\n",
       ".cython.score-27 {background-color: #FFFF44;}\n",
       ".cython.score-28 {background-color: #FFFF43;}\n",
       ".cython.score-29 {background-color: #FFFF41;}\n",
       ".cython.score-30 {background-color: #FFFF3f;}\n",
       ".cython.score-31 {background-color: #FFFF3e;}\n",
       ".cython.score-32 {background-color: #FFFF3c;}\n",
       ".cython.score-33 {background-color: #FFFF3b;}\n",
       ".cython.score-34 {background-color: #FFFF39;}\n",
       ".cython.score-35 {background-color: #FFFF38;}\n",
       ".cython.score-36 {background-color: #FFFF37;}\n",
       ".cython.score-37 {background-color: #FFFF36;}\n",
       ".cython.score-38 {background-color: #FFFF35;}\n",
       ".cython.score-39 {background-color: #FFFF34;}\n",
       ".cython.score-40 {background-color: #FFFF33;}\n",
       ".cython.score-41 {background-color: #FFFF32;}\n",
       ".cython.score-42 {background-color: #FFFF31;}\n",
       ".cython.score-43 {background-color: #FFFF30;}\n",
       ".cython.score-44 {background-color: #FFFF2f;}\n",
       ".cython.score-45 {background-color: #FFFF2e;}\n",
       ".cython.score-46 {background-color: #FFFF2d;}\n",
       ".cython.score-47 {background-color: #FFFF2c;}\n",
       ".cython.score-48 {background-color: #FFFF2b;}\n",
       ".cython.score-49 {background-color: #FFFF2b;}\n",
       ".cython.score-50 {background-color: #FFFF2a;}\n",
       ".cython.score-51 {background-color: #FFFF29;}\n",
       ".cython.score-52 {background-color: #FFFF29;}\n",
       ".cython.score-53 {background-color: #FFFF28;}\n",
       ".cython.score-54 {background-color: #FFFF27;}\n",
       ".cython.score-55 {background-color: #FFFF27;}\n",
       ".cython.score-56 {background-color: #FFFF26;}\n",
       ".cython.score-57 {background-color: #FFFF26;}\n",
       ".cython.score-58 {background-color: #FFFF25;}\n",
       ".cython.score-59 {background-color: #FFFF24;}\n",
       ".cython.score-60 {background-color: #FFFF24;}\n",
       ".cython.score-61 {background-color: #FFFF23;}\n",
       ".cython.score-62 {background-color: #FFFF23;}\n",
       ".cython.score-63 {background-color: #FFFF22;}\n",
       ".cython.score-64 {background-color: #FFFF22;}\n",
       ".cython.score-65 {background-color: #FFFF22;}\n",
       ".cython.score-66 {background-color: #FFFF21;}\n",
       ".cython.score-67 {background-color: #FFFF21;}\n",
       ".cython.score-68 {background-color: #FFFF20;}\n",
       ".cython.score-69 {background-color: #FFFF20;}\n",
       ".cython.score-70 {background-color: #FFFF1f;}\n",
       ".cython.score-71 {background-color: #FFFF1f;}\n",
       ".cython.score-72 {background-color: #FFFF1f;}\n",
       ".cython.score-73 {background-color: #FFFF1e;}\n",
       ".cython.score-74 {background-color: #FFFF1e;}\n",
       ".cython.score-75 {background-color: #FFFF1e;}\n",
       ".cython.score-76 {background-color: #FFFF1d;}\n",
       ".cython.score-77 {background-color: #FFFF1d;}\n",
       ".cython.score-78 {background-color: #FFFF1c;}\n",
       ".cython.score-79 {background-color: #FFFF1c;}\n",
       ".cython.score-80 {background-color: #FFFF1c;}\n",
       ".cython.score-81 {background-color: #FFFF1c;}\n",
       ".cython.score-82 {background-color: #FFFF1b;}\n",
       ".cython.score-83 {background-color: #FFFF1b;}\n",
       ".cython.score-84 {background-color: #FFFF1b;}\n",
       ".cython.score-85 {background-color: #FFFF1a;}\n",
       ".cython.score-86 {background-color: #FFFF1a;}\n",
       ".cython.score-87 {background-color: #FFFF1a;}\n",
       ".cython.score-88 {background-color: #FFFF1a;}\n",
       ".cython.score-89 {background-color: #FFFF19;}\n",
       ".cython.score-90 {background-color: #FFFF19;}\n",
       ".cython.score-91 {background-color: #FFFF19;}\n",
       ".cython.score-92 {background-color: #FFFF19;}\n",
       ".cython.score-93 {background-color: #FFFF18;}\n",
       ".cython.score-94 {background-color: #FFFF18;}\n",
       ".cython.score-95 {background-color: #FFFF18;}\n",
       ".cython.score-96 {background-color: #FFFF18;}\n",
       ".cython.score-97 {background-color: #FFFF17;}\n",
       ".cython.score-98 {background-color: #FFFF17;}\n",
       ".cython.score-99 {background-color: #FFFF17;}\n",
       ".cython.score-100 {background-color: #FFFF17;}\n",
       ".cython.score-101 {background-color: #FFFF16;}\n",
       ".cython.score-102 {background-color: #FFFF16;}\n",
       ".cython.score-103 {background-color: #FFFF16;}\n",
       ".cython.score-104 {background-color: #FFFF16;}\n",
       ".cython.score-105 {background-color: #FFFF16;}\n",
       ".cython.score-106 {background-color: #FFFF15;}\n",
       ".cython.score-107 {background-color: #FFFF15;}\n",
       ".cython.score-108 {background-color: #FFFF15;}\n",
       ".cython.score-109 {background-color: #FFFF15;}\n",
       ".cython.score-110 {background-color: #FFFF15;}\n",
       ".cython.score-111 {background-color: #FFFF15;}\n",
       ".cython.score-112 {background-color: #FFFF14;}\n",
       ".cython.score-113 {background-color: #FFFF14;}\n",
       ".cython.score-114 {background-color: #FFFF14;}\n",
       ".cython.score-115 {background-color: #FFFF14;}\n",
       ".cython.score-116 {background-color: #FFFF14;}\n",
       ".cython.score-117 {background-color: #FFFF14;}\n",
       ".cython.score-118 {background-color: #FFFF13;}\n",
       ".cython.score-119 {background-color: #FFFF13;}\n",
       ".cython.score-120 {background-color: #FFFF13;}\n",
       ".cython.score-121 {background-color: #FFFF13;}\n",
       ".cython.score-122 {background-color: #FFFF13;}\n",
       ".cython.score-123 {background-color: #FFFF13;}\n",
       ".cython.score-124 {background-color: #FFFF13;}\n",
       ".cython.score-125 {background-color: #FFFF12;}\n",
       ".cython.score-126 {background-color: #FFFF12;}\n",
       ".cython.score-127 {background-color: #FFFF12;}\n",
       ".cython.score-128 {background-color: #FFFF12;}\n",
       ".cython.score-129 {background-color: #FFFF12;}\n",
       ".cython.score-130 {background-color: #FFFF12;}\n",
       ".cython.score-131 {background-color: #FFFF12;}\n",
       ".cython.score-132 {background-color: #FFFF11;}\n",
       ".cython.score-133 {background-color: #FFFF11;}\n",
       ".cython.score-134 {background-color: #FFFF11;}\n",
       ".cython.score-135 {background-color: #FFFF11;}\n",
       ".cython.score-136 {background-color: #FFFF11;}\n",
       ".cython.score-137 {background-color: #FFFF11;}\n",
       ".cython.score-138 {background-color: #FFFF11;}\n",
       ".cython.score-139 {background-color: #FFFF11;}\n",
       ".cython.score-140 {background-color: #FFFF11;}\n",
       ".cython.score-141 {background-color: #FFFF10;}\n",
       ".cython.score-142 {background-color: #FFFF10;}\n",
       ".cython.score-143 {background-color: #FFFF10;}\n",
       ".cython.score-144 {background-color: #FFFF10;}\n",
       ".cython.score-145 {background-color: #FFFF10;}\n",
       ".cython.score-146 {background-color: #FFFF10;}\n",
       ".cython.score-147 {background-color: #FFFF10;}\n",
       ".cython.score-148 {background-color: #FFFF10;}\n",
       ".cython.score-149 {background-color: #FFFF10;}\n",
       ".cython.score-150 {background-color: #FFFF0f;}\n",
       ".cython.score-151 {background-color: #FFFF0f;}\n",
       ".cython.score-152 {background-color: #FFFF0f;}\n",
       ".cython.score-153 {background-color: #FFFF0f;}\n",
       ".cython.score-154 {background-color: #FFFF0f;}\n",
       ".cython.score-155 {background-color: #FFFF0f;}\n",
       ".cython.score-156 {background-color: #FFFF0f;}\n",
       ".cython.score-157 {background-color: #FFFF0f;}\n",
       ".cython.score-158 {background-color: #FFFF0f;}\n",
       ".cython.score-159 {background-color: #FFFF0f;}\n",
       ".cython.score-160 {background-color: #FFFF0f;}\n",
       ".cython.score-161 {background-color: #FFFF0e;}\n",
       ".cython.score-162 {background-color: #FFFF0e;}\n",
       ".cython.score-163 {background-color: #FFFF0e;}\n",
       ".cython.score-164 {background-color: #FFFF0e;}\n",
       ".cython.score-165 {background-color: #FFFF0e;}\n",
       ".cython.score-166 {background-color: #FFFF0e;}\n",
       ".cython.score-167 {background-color: #FFFF0e;}\n",
       ".cython.score-168 {background-color: #FFFF0e;}\n",
       ".cython.score-169 {background-color: #FFFF0e;}\n",
       ".cython.score-170 {background-color: #FFFF0e;}\n",
       ".cython.score-171 {background-color: #FFFF0e;}\n",
       ".cython.score-172 {background-color: #FFFF0e;}\n",
       ".cython.score-173 {background-color: #FFFF0d;}\n",
       ".cython.score-174 {background-color: #FFFF0d;}\n",
       ".cython.score-175 {background-color: #FFFF0d;}\n",
       ".cython.score-176 {background-color: #FFFF0d;}\n",
       ".cython.score-177 {background-color: #FFFF0d;}\n",
       ".cython.score-178 {background-color: #FFFF0d;}\n",
       ".cython.score-179 {background-color: #FFFF0d;}\n",
       ".cython.score-180 {background-color: #FFFF0d;}\n",
       ".cython.score-181 {background-color: #FFFF0d;}\n",
       ".cython.score-182 {background-color: #FFFF0d;}\n",
       ".cython.score-183 {background-color: #FFFF0d;}\n",
       ".cython.score-184 {background-color: #FFFF0d;}\n",
       ".cython.score-185 {background-color: #FFFF0d;}\n",
       ".cython.score-186 {background-color: #FFFF0d;}\n",
       ".cython.score-187 {background-color: #FFFF0c;}\n",
       ".cython.score-188 {background-color: #FFFF0c;}\n",
       ".cython.score-189 {background-color: #FFFF0c;}\n",
       ".cython.score-190 {background-color: #FFFF0c;}\n",
       ".cython.score-191 {background-color: #FFFF0c;}\n",
       ".cython.score-192 {background-color: #FFFF0c;}\n",
       ".cython.score-193 {background-color: #FFFF0c;}\n",
       ".cython.score-194 {background-color: #FFFF0c;}\n",
       ".cython.score-195 {background-color: #FFFF0c;}\n",
       ".cython.score-196 {background-color: #FFFF0c;}\n",
       ".cython.score-197 {background-color: #FFFF0c;}\n",
       ".cython.score-198 {background-color: #FFFF0c;}\n",
       ".cython.score-199 {background-color: #FFFF0c;}\n",
       ".cython.score-200 {background-color: #FFFF0c;}\n",
       ".cython.score-201 {background-color: #FFFF0c;}\n",
       ".cython.score-202 {background-color: #FFFF0c;}\n",
       ".cython.score-203 {background-color: #FFFF0b;}\n",
       ".cython.score-204 {background-color: #FFFF0b;}\n",
       ".cython.score-205 {background-color: #FFFF0b;}\n",
       ".cython.score-206 {background-color: #FFFF0b;}\n",
       ".cython.score-207 {background-color: #FFFF0b;}\n",
       ".cython.score-208 {background-color: #FFFF0b;}\n",
       ".cython.score-209 {background-color: #FFFF0b;}\n",
       ".cython.score-210 {background-color: #FFFF0b;}\n",
       ".cython.score-211 {background-color: #FFFF0b;}\n",
       ".cython.score-212 {background-color: #FFFF0b;}\n",
       ".cython.score-213 {background-color: #FFFF0b;}\n",
       ".cython.score-214 {background-color: #FFFF0b;}\n",
       ".cython.score-215 {background-color: #FFFF0b;}\n",
       ".cython.score-216 {background-color: #FFFF0b;}\n",
       ".cython.score-217 {background-color: #FFFF0b;}\n",
       ".cython.score-218 {background-color: #FFFF0b;}\n",
       ".cython.score-219 {background-color: #FFFF0b;}\n",
       ".cython.score-220 {background-color: #FFFF0b;}\n",
       ".cython.score-221 {background-color: #FFFF0b;}\n",
       ".cython.score-222 {background-color: #FFFF0a;}\n",
       ".cython.score-223 {background-color: #FFFF0a;}\n",
       ".cython.score-224 {background-color: #FFFF0a;}\n",
       ".cython.score-225 {background-color: #FFFF0a;}\n",
       ".cython.score-226 {background-color: #FFFF0a;}\n",
       ".cython.score-227 {background-color: #FFFF0a;}\n",
       ".cython.score-228 {background-color: #FFFF0a;}\n",
       ".cython.score-229 {background-color: #FFFF0a;}\n",
       ".cython.score-230 {background-color: #FFFF0a;}\n",
       ".cython.score-231 {background-color: #FFFF0a;}\n",
       ".cython.score-232 {background-color: #FFFF0a;}\n",
       ".cython.score-233 {background-color: #FFFF0a;}\n",
       ".cython.score-234 {background-color: #FFFF0a;}\n",
       ".cython.score-235 {background-color: #FFFF0a;}\n",
       ".cython.score-236 {background-color: #FFFF0a;}\n",
       ".cython.score-237 {background-color: #FFFF0a;}\n",
       ".cython.score-238 {background-color: #FFFF0a;}\n",
       ".cython.score-239 {background-color: #FFFF0a;}\n",
       ".cython.score-240 {background-color: #FFFF0a;}\n",
       ".cython.score-241 {background-color: #FFFF0a;}\n",
       ".cython.score-242 {background-color: #FFFF0a;}\n",
       ".cython.score-243 {background-color: #FFFF0a;}\n",
       ".cython.score-244 {background-color: #FFFF0a;}\n",
       ".cython.score-245 {background-color: #FFFF0a;}\n",
       ".cython.score-246 {background-color: #FFFF09;}\n",
       ".cython.score-247 {background-color: #FFFF09;}\n",
       ".cython.score-248 {background-color: #FFFF09;}\n",
       ".cython.score-249 {background-color: #FFFF09;}\n",
       ".cython.score-250 {background-color: #FFFF09;}\n",
       ".cython.score-251 {background-color: #FFFF09;}\n",
       ".cython.score-252 {background-color: #FFFF09;}\n",
       ".cython.score-253 {background-color: #FFFF09;}\n",
       ".cython.score-254 {background-color: #FFFF09;}\n",
       ".cython .hll { background-color: #ffffcc }\n",
       ".cython  { background: #f8f8f8; }\n",
       ".cython .c { color: #408080; font-style: italic } /* Comment */\n",
       ".cython .err { border: 1px solid #FF0000 } /* Error */\n",
       ".cython .k { color: #008000; font-weight: bold } /* Keyword */\n",
       ".cython .o { color: #666666 } /* Operator */\n",
       ".cython .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       ".cython .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       ".cython .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       ".cython .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       ".cython .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       ".cython .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       ".cython .gd { color: #A00000 } /* Generic.Deleted */\n",
       ".cython .ge { font-style: italic } /* Generic.Emph */\n",
       ".cython .gr { color: #FF0000 } /* Generic.Error */\n",
       ".cython .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       ".cython .gi { color: #00A000 } /* Generic.Inserted */\n",
       ".cython .go { color: #888888 } /* Generic.Output */\n",
       ".cython .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       ".cython .gs { font-weight: bold } /* Generic.Strong */\n",
       ".cython .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       ".cython .gt { color: #0044DD } /* Generic.Traceback */\n",
       ".cython .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       ".cython .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       ".cython .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       ".cython .kp { color: #008000 } /* Keyword.Pseudo */\n",
       ".cython .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       ".cython .kt { color: #B00040 } /* Keyword.Type */\n",
       ".cython .m { color: #666666 } /* Literal.Number */\n",
       ".cython .s { color: #BA2121 } /* Literal.String */\n",
       ".cython .na { color: #7D9029 } /* Name.Attribute */\n",
       ".cython .nb { color: #008000 } /* Name.Builtin */\n",
       ".cython .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       ".cython .no { color: #880000 } /* Name.Constant */\n",
       ".cython .nd { color: #AA22FF } /* Name.Decorator */\n",
       ".cython .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       ".cython .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       ".cython .nf { color: #0000FF } /* Name.Function */\n",
       ".cython .nl { color: #A0A000 } /* Name.Label */\n",
       ".cython .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       ".cython .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       ".cython .nv { color: #19177C } /* Name.Variable */\n",
       ".cython .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       ".cython .w { color: #bbbbbb } /* Text.Whitespace */\n",
       ".cython .mb { color: #666666 } /* Literal.Number.Bin */\n",
       ".cython .mf { color: #666666 } /* Literal.Number.Float */\n",
       ".cython .mh { color: #666666 } /* Literal.Number.Hex */\n",
       ".cython .mi { color: #666666 } /* Literal.Number.Integer */\n",
       ".cython .mo { color: #666666 } /* Literal.Number.Oct */\n",
       ".cython .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       ".cython .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       ".cython .sc { color: #BA2121 } /* Literal.String.Char */\n",
       ".cython .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       ".cython .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       ".cython .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       ".cython .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       ".cython .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       ".cython .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       ".cython .sx { color: #008000 } /* Literal.String.Other */\n",
       ".cython .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       ".cython .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       ".cython .ss { color: #19177C } /* Literal.String.Symbol */\n",
       ".cython .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       ".cython .fm { color: #0000FF } /* Name.Function.Magic */\n",
       ".cython .vc { color: #19177C } /* Name.Variable.Class */\n",
       ".cython .vg { color: #19177C } /* Name.Variable.Global */\n",
       ".cython .vi { color: #19177C } /* Name.Variable.Instance */\n",
       ".cython .vm { color: #19177C } /* Name.Variable.Magic */\n",
       ".cython .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "    </style>\n",
       "</head>\n",
       "<body class=\"cython\">\n",
       "<p><span style=\"border-bottom: solid 1px grey;\">Generated by Cython 0.29.17</span></p>\n",
       "<p>\n",
       "    <span style=\"background-color: #FFFF00\">Yellow lines</span> hint at Python interaction.<br />\n",
       "    Click on a line that starts with a \"<code>+</code>\" to see the C code that Cython generated for it.\n",
       "</p>\n",
       "<div class=\"cython\"><pre class=\"cython line score-8\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">01</span>: <span class=\"c\"># cython: language_level=3</span></pre>\n",
       "<pre class='cython code score-8 '>  __pyx_t_1 = <span class='pyx_c_api'>__Pyx_PyDict_NewPresized</span>(0);<span class='error_goto'> if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 1, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  if (<span class='py_c_api'>PyDict_SetItem</span>(__pyx_d, __pyx_n_s_test, __pyx_t_1) &lt; 0) <span class='error_goto'>__PYX_ERR(0, 1, __pyx_L1_error)</span>\n",
       "  <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_1); __pyx_t_1 = 0;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">02</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">03</span>: <span class=\"k\">cimport</span> <span class=\"nn\">cython</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">04</span>: </pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">05</span>: <span class=\"nd\">@cython</span><span class=\"o\">.</span><span class=\"n\">wraparound</span><span class=\"p\">(</span><span class=\"bp\">False</span><span class=\"p\">)</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">06</span>: <span class=\"nd\">@cython</span><span class=\"o\">.</span><span class=\"n\">boundscheck</span><span class=\"p\">(</span><span class=\"bp\">False</span><span class=\"p\">)</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">07</span>: <span class=\"nd\">@cython</span><span class=\"o\">.</span><span class=\"n\">cdivision</span><span class=\"p\">(</span><span class=\"bp\">True</span><span class=\"p\">)</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">08</span>: <span class=\"nd\">@cython</span><span class=\"o\">.</span><span class=\"n\">nonecheck</span><span class=\"p\">(</span><span class=\"bp\">False</span><span class=\"p\">)</span></pre>\n",
       "<pre class=\"cython line score-44\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">09</span>: <span class=\"k\">cpdef</span> <span class=\"kt\">Py_ssize_t</span> <span class=\"nf\">binarySearch_v3</span><span class=\"p\">(</span><span class=\"nb\">int</span><span class=\"p\">[::</span><span class=\"mf\">1</span><span class=\"p\">]</span> <span class=\"n\">arr</span><span class=\"p\">,</span><span class=\"nb\">int</span> <span class=\"n\">x</span><span class=\"p\">):</span></pre>\n",
       "<pre class='cython code score-44 '>static PyObject *__pyx_pw_46_cython_magic_0f6259adb0185f4ee53abc0f79ce9417_1binarySearch_v3(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/\n",
       "static Py_ssize_t __pyx_f_46_cython_magic_0f6259adb0185f4ee53abc0f79ce9417_binarySearch_v3(__Pyx_memviewslice __pyx_v_arr, int __pyx_v_x, CYTHON_UNUSED int __pyx_skip_dispatch) {\n",
       "  Py_ssize_t __pyx_v_lo;\n",
       "  Py_ssize_t __pyx_v_hi;\n",
       "  Py_ssize_t __pyx_v_mid;\n",
       "  Py_ssize_t __pyx_r;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"binarySearch_v3\", 0);\n",
       "/* … */\n",
       "  /* function exit code */\n",
       "  __pyx_L0:;\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "/* Python wrapper */\n",
       "static PyObject *__pyx_pw_46_cython_magic_0f6259adb0185f4ee53abc0f79ce9417_1binarySearch_v3(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/\n",
       "static PyObject *__pyx_pw_46_cython_magic_0f6259adb0185f4ee53abc0f79ce9417_1binarySearch_v3(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {\n",
       "  __Pyx_memviewslice __pyx_v_arr = { 0, 0, { 0 }, { 0 }, { 0 } };\n",
       "  int __pyx_v_x;\n",
       "  PyObject *__pyx_r = 0;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"binarySearch_v3 (wrapper)\", 0);\n",
       "  {\n",
       "    static PyObject **__pyx_pyargnames[] = {&amp;__pyx_n_s_arr,&amp;__pyx_n_s_x,0};\n",
       "    PyObject* values[2] = {0,0};\n",
       "    if (unlikely(__pyx_kwds)) {\n",
       "      Py_ssize_t kw_args;\n",
       "      const Py_ssize_t pos_args = <span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args);\n",
       "      switch (pos_args) {\n",
       "        case  2: values[1] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 1);\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  1: values[0] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 0);\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  0: break;\n",
       "        default: goto __pyx_L5_argtuple_error;\n",
       "      }\n",
       "      kw_args = <span class='py_c_api'>PyDict_Size</span>(__pyx_kwds);\n",
       "      switch (pos_args) {\n",
       "        case  0:\n",
       "        if (likely((values[0] = <span class='pyx_c_api'>__Pyx_PyDict_GetItemStr</span>(__pyx_kwds, __pyx_n_s_arr)) != 0)) kw_args--;\n",
       "        else goto __pyx_L5_argtuple_error;\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  1:\n",
       "        if (likely((values[1] = <span class='pyx_c_api'>__Pyx_PyDict_GetItemStr</span>(__pyx_kwds, __pyx_n_s_x)) != 0)) kw_args--;\n",
       "        else {\n",
       "          <span class='pyx_c_api'>__Pyx_RaiseArgtupleInvalid</span>(\"binarySearch_v3\", 1, 2, 2, 1); <span class='error_goto'>__PYX_ERR(0, 9, __pyx_L3_error)</span>\n",
       "        }\n",
       "      }\n",
       "      if (unlikely(kw_args &gt; 0)) {\n",
       "        if (unlikely(<span class='pyx_c_api'>__Pyx_ParseOptionalKeywords</span>(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, \"binarySearch_v3\") &lt; 0)) <span class='error_goto'>__PYX_ERR(0, 9, __pyx_L3_error)</span>\n",
       "      }\n",
       "    } else if (<span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args) != 2) {\n",
       "      goto __pyx_L5_argtuple_error;\n",
       "    } else {\n",
       "      values[0] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 0);\n",
       "      values[1] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 1);\n",
       "    }\n",
       "    __pyx_v_arr = <span class='pyx_c_api'>__Pyx_PyObject_to_MemoryviewSlice_dc_int</span>(values[0], PyBUF_WRITABLE);<span class='error_goto'> if (unlikely(!__pyx_v_arr.memview)) __PYX_ERR(0, 9, __pyx_L3_error)</span>\n",
       "    __pyx_v_x = <span class='pyx_c_api'>__Pyx_PyInt_As_int</span>(values[1]); if (unlikely((__pyx_v_x == (int)-1) &amp;&amp; <span class='py_c_api'>PyErr_Occurred</span>())) <span class='error_goto'>__PYX_ERR(0, 9, __pyx_L3_error)</span>\n",
       "  }\n",
       "  goto __pyx_L4_argument_unpacking_done;\n",
       "  __pyx_L5_argtuple_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_RaiseArgtupleInvalid</span>(\"binarySearch_v3\", 1, 2, 2, <span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args)); <span class='error_goto'>__PYX_ERR(0, 9, __pyx_L3_error)</span>\n",
       "  __pyx_L3_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_0f6259adb0185f4ee53abc0f79ce9417.binarySearch_v3\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return NULL;\n",
       "  __pyx_L4_argument_unpacking_done:;\n",
       "  __pyx_r = __pyx_pf_46_cython_magic_0f6259adb0185f4ee53abc0f79ce9417_binarySearch_v3(__pyx_self, __pyx_v_arr, __pyx_v_x);\n",
       "\n",
       "  /* function exit code */\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "static PyObject *__pyx_pf_46_cython_magic_0f6259adb0185f4ee53abc0f79ce9417_binarySearch_v3(CYTHON_UNUSED PyObject *__pyx_self, __Pyx_memviewslice __pyx_v_arr, int __pyx_v_x) {\n",
       "  PyObject *__pyx_r = NULL;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"binarySearch_v3\", 0);\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_r);\n",
       "  if (unlikely(!__pyx_v_arr.memview)) { <span class='pyx_c_api'>__Pyx_RaiseUnboundLocalError</span>(\"arr\"); <span class='error_goto'>__PYX_ERR(0, 9, __pyx_L1_error)</span> }\n",
       "  __pyx_t_1 = <span class='py_c_api'>PyInt_FromSsize_t</span>(__pyx_f_46_cython_magic_0f6259adb0185f4ee53abc0f79ce9417_binarySearch_v3(__pyx_v_arr, __pyx_v_x, 0));<span class='error_goto'> if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 9, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  __pyx_r = __pyx_t_1;\n",
       "  __pyx_t_1 = 0;\n",
       "  goto __pyx_L0;\n",
       "\n",
       "  /* function exit code */\n",
       "  __pyx_L1_error:;\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_t_1);\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_0f6259adb0185f4ee53abc0f79ce9417.binarySearch_v3\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  __pyx_r = NULL;\n",
       "  __pyx_L0:;\n",
       "  __PYX_XDEC_MEMVIEW(&amp;__pyx_v_arr, 1);\n",
       "  <span class='refnanny'>__Pyx_XGIVEREF</span>(__pyx_r);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">10</span>:     <span class=\"k\">cdef</span><span class=\"p\">:</span></pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">11</span>:         <span class=\"n\">Py_ssize_t</span> <span class=\"n\">lo</span> <span class=\"o\">=</span> <span class=\"mf\">0</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_v_lo = 0;\n",
       "</pre><pre class=\"cython line score-2\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">12</span>:         <span class=\"n\">Py_ssize_t</span> <span class=\"n\">hi</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">arr</span><span class=\"p\">)</span></pre>\n",
       "<pre class='cython code score-2 '>  __pyx_t_1 = <span class='pyx_c_api'>__Pyx_MemoryView_Len</span>(__pyx_v_arr); \n",
       "  __pyx_v_hi = __pyx_t_1;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">13</span>:         <span class=\"n\">Py_ssize_t</span> <span class=\"n\">mid</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">14</span>: </pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">15</span>:     <span class=\"k\">while</span> <span class=\"n\">lo</span> <span class=\"o\">&lt;</span> <span class=\"n\">hi</span><span class=\"p\">:</span></pre>\n",
       "<pre class='cython code score-0 '>  while (1) {\n",
       "    __pyx_t_2 = ((__pyx_v_lo &lt; __pyx_v_hi) != 0);\n",
       "    if (!__pyx_t_2) break;\n",
       "</pre><pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">16</span>:         <span class=\"n\">mid</span> <span class=\"o\">=</span> <span class=\"p\">(</span><span class=\"n\">lo</span><span class=\"o\">+</span><span class=\"n\">hi</span><span class=\"p\">)</span><span class=\"o\">//</span><span class=\"mf\">2</span></pre>\n",
       "<pre class='cython code score-0 '>    __pyx_v_mid = ((__pyx_v_lo + __pyx_v_hi) / 2);\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">17</span>: </pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">18</span>:         <span class=\"k\">if</span> <span class=\"n\">arr</span><span class=\"p\">[</span><span class=\"n\">mid</span><span class=\"p\">]</span> <span class=\"o\">&lt;</span> <span class=\"n\">x</span><span class=\"p\">:</span></pre>\n",
       "<pre class='cython code score-0 '>    __pyx_t_3 = __pyx_v_mid;\n",
       "    __pyx_t_2 = (((*((int *) ( /* dim=0 */ ((char *) (((int *) __pyx_v_arr.data) + __pyx_t_3)) ))) &lt; __pyx_v_x) != 0);\n",
       "    if (__pyx_t_2) {\n",
       "/* … */\n",
       "      goto __pyx_L5;\n",
       "    }\n",
       "</pre><pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">19</span>:             <span class=\"n\">lo</span> <span class=\"o\">=</span> <span class=\"n\">mid</span><span class=\"o\">+</span><span class=\"mf\">1</span></pre>\n",
       "<pre class='cython code score-0 '>      __pyx_v_lo = (__pyx_v_mid + 1);\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">20</span>:         <span class=\"k\">else</span><span class=\"p\">:</span></pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">21</span>:             <span class=\"n\">hi</span> <span class=\"o\">=</span> <span class=\"n\">mid</span></pre>\n",
       "<pre class='cython code score-0 '>    /*else*/ {\n",
       "      __pyx_v_hi = __pyx_v_mid;\n",
       "    }\n",
       "    __pyx_L5:;\n",
       "  }\n",
       "</pre><pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">22</span>:     <span class=\"k\">return</span> <span class=\"n\">lo</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_r = __pyx_v_lo;\n",
       "  goto __pyx_L0;\n",
       "</pre></div></body></html>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%cython -a\n",
    "# cython: language_level=3\n",
    "\n",
    "cimport cython\n",
    "\n",
    "@cython.wraparound(False)\n",
    "@cython.boundscheck(False)\n",
    "@cython.cdivision(True)\n",
    "@cython.nonecheck(False)\n",
    "cpdef Py_ssize_t binarySearch_v3(int[::1] arr,int x):\n",
    "    cdef:\n",
    "        Py_ssize_t lo = 0\n",
    "        Py_ssize_t hi = len(arr)\n",
    "        Py_ssize_t mid\n",
    "\n",
    "    while lo < hi:\n",
    "        mid = (lo+hi)//2\n",
    "        \n",
    "        if arr[mid] < x:\n",
    "            lo = mid+1\n",
    "        else:\n",
    "            hi = mid\n",
    "    return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "630 ns ± 0.0393 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit binarySearch_v3(arr,4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как видим, это позволяет добиться небольшого прироста производительности даже в случае очень простых алгоритмов. Также директивы компилятора можно задавать на уровне модуля (или ячейки в Jupyter), чтобы не декорировать каждую функцию отдельно:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html>\n",
       "<!-- Generated by Cython 0.29.17 -->\n",
       "<html>\n",
       "<head>\n",
       "    <meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\" />\n",
       "    <title>Cython: _cython_magic_6172a75514763b92fb920daf6370d90e.pyx</title>\n",
       "    <style type=\"text/css\">\n",
       "    \n",
       "body.cython { font-family: courier; font-size: 12; }\n",
       "\n",
       ".cython.tag  {  }\n",
       ".cython.line { margin: 0em }\n",
       ".cython.code { font-size: 9; color: #444444; display: none; margin: 0px 0px 0px 8px; border-left: 8px none; }\n",
       "\n",
       ".cython.line .run { background-color: #B0FFB0; }\n",
       ".cython.line .mis { background-color: #FFB0B0; }\n",
       ".cython.code.run  { border-left: 8px solid #B0FFB0; }\n",
       ".cython.code.mis  { border-left: 8px solid #FFB0B0; }\n",
       "\n",
       ".cython.code .py_c_api  { color: red; }\n",
       ".cython.code .py_macro_api  { color: #FF7000; }\n",
       ".cython.code .pyx_c_api  { color: #FF3000; }\n",
       ".cython.code .pyx_macro_api  { color: #FF7000; }\n",
       ".cython.code .refnanny  { color: #FFA000; }\n",
       ".cython.code .trace  { color: #FFA000; }\n",
       ".cython.code .error_goto  { color: #FFA000; }\n",
       "\n",
       ".cython.code .coerce  { color: #008000; border: 1px dotted #008000 }\n",
       ".cython.code .py_attr { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_attr  { color: #0000FF; }\n",
       ".cython.code .py_call { color: #FF0000; font-weight: bold; }\n",
       ".cython.code .c_call  { color: #0000FF; }\n",
       "\n",
       ".cython.score-0 {background-color: #FFFFff;}\n",
       ".cython.score-1 {background-color: #FFFFe7;}\n",
       ".cython.score-2 {background-color: #FFFFd4;}\n",
       ".cython.score-3 {background-color: #FFFFc4;}\n",
       ".cython.score-4 {background-color: #FFFFb6;}\n",
       ".cython.score-5 {background-color: #FFFFaa;}\n",
       ".cython.score-6 {background-color: #FFFF9f;}\n",
       ".cython.score-7 {background-color: #FFFF96;}\n",
       ".cython.score-8 {background-color: #FFFF8d;}\n",
       ".cython.score-9 {background-color: #FFFF86;}\n",
       ".cython.score-10 {background-color: #FFFF7f;}\n",
       ".cython.score-11 {background-color: #FFFF79;}\n",
       ".cython.score-12 {background-color: #FFFF73;}\n",
       ".cython.score-13 {background-color: #FFFF6e;}\n",
       ".cython.score-14 {background-color: #FFFF6a;}\n",
       ".cython.score-15 {background-color: #FFFF66;}\n",
       ".cython.score-16 {background-color: #FFFF62;}\n",
       ".cython.score-17 {background-color: #FFFF5e;}\n",
       ".cython.score-18 {background-color: #FFFF5b;}\n",
       ".cython.score-19 {background-color: #FFFF57;}\n",
       ".cython.score-20 {background-color: #FFFF55;}\n",
       ".cython.score-21 {background-color: #FFFF52;}\n",
       ".cython.score-22 {background-color: #FFFF4f;}\n",
       ".cython.score-23 {background-color: #FFFF4d;}\n",
       ".cython.score-24 {background-color: #FFFF4b;}\n",
       ".cython.score-25 {background-color: #FFFF48;}\n",
       ".cython.score-26 {background-color: #FFFF46;}\n",
       ".cython.score-27 {background-color: #FFFF44;}\n",
       ".cython.score-28 {background-color: #FFFF43;}\n",
       ".cython.score-29 {background-color: #FFFF41;}\n",
       ".cython.score-30 {background-color: #FFFF3f;}\n",
       ".cython.score-31 {background-color: #FFFF3e;}\n",
       ".cython.score-32 {background-color: #FFFF3c;}\n",
       ".cython.score-33 {background-color: #FFFF3b;}\n",
       ".cython.score-34 {background-color: #FFFF39;}\n",
       ".cython.score-35 {background-color: #FFFF38;}\n",
       ".cython.score-36 {background-color: #FFFF37;}\n",
       ".cython.score-37 {background-color: #FFFF36;}\n",
       ".cython.score-38 {background-color: #FFFF35;}\n",
       ".cython.score-39 {background-color: #FFFF34;}\n",
       ".cython.score-40 {background-color: #FFFF33;}\n",
       ".cython.score-41 {background-color: #FFFF32;}\n",
       ".cython.score-42 {background-color: #FFFF31;}\n",
       ".cython.score-43 {background-color: #FFFF30;}\n",
       ".cython.score-44 {background-color: #FFFF2f;}\n",
       ".cython.score-45 {background-color: #FFFF2e;}\n",
       ".cython.score-46 {background-color: #FFFF2d;}\n",
       ".cython.score-47 {background-color: #FFFF2c;}\n",
       ".cython.score-48 {background-color: #FFFF2b;}\n",
       ".cython.score-49 {background-color: #FFFF2b;}\n",
       ".cython.score-50 {background-color: #FFFF2a;}\n",
       ".cython.score-51 {background-color: #FFFF29;}\n",
       ".cython.score-52 {background-color: #FFFF29;}\n",
       ".cython.score-53 {background-color: #FFFF28;}\n",
       ".cython.score-54 {background-color: #FFFF27;}\n",
       ".cython.score-55 {background-color: #FFFF27;}\n",
       ".cython.score-56 {background-color: #FFFF26;}\n",
       ".cython.score-57 {background-color: #FFFF26;}\n",
       ".cython.score-58 {background-color: #FFFF25;}\n",
       ".cython.score-59 {background-color: #FFFF24;}\n",
       ".cython.score-60 {background-color: #FFFF24;}\n",
       ".cython.score-61 {background-color: #FFFF23;}\n",
       ".cython.score-62 {background-color: #FFFF23;}\n",
       ".cython.score-63 {background-color: #FFFF22;}\n",
       ".cython.score-64 {background-color: #FFFF22;}\n",
       ".cython.score-65 {background-color: #FFFF22;}\n",
       ".cython.score-66 {background-color: #FFFF21;}\n",
       ".cython.score-67 {background-color: #FFFF21;}\n",
       ".cython.score-68 {background-color: #FFFF20;}\n",
       ".cython.score-69 {background-color: #FFFF20;}\n",
       ".cython.score-70 {background-color: #FFFF1f;}\n",
       ".cython.score-71 {background-color: #FFFF1f;}\n",
       ".cython.score-72 {background-color: #FFFF1f;}\n",
       ".cython.score-73 {background-color: #FFFF1e;}\n",
       ".cython.score-74 {background-color: #FFFF1e;}\n",
       ".cython.score-75 {background-color: #FFFF1e;}\n",
       ".cython.score-76 {background-color: #FFFF1d;}\n",
       ".cython.score-77 {background-color: #FFFF1d;}\n",
       ".cython.score-78 {background-color: #FFFF1c;}\n",
       ".cython.score-79 {background-color: #FFFF1c;}\n",
       ".cython.score-80 {background-color: #FFFF1c;}\n",
       ".cython.score-81 {background-color: #FFFF1c;}\n",
       ".cython.score-82 {background-color: #FFFF1b;}\n",
       ".cython.score-83 {background-color: #FFFF1b;}\n",
       ".cython.score-84 {background-color: #FFFF1b;}\n",
       ".cython.score-85 {background-color: #FFFF1a;}\n",
       ".cython.score-86 {background-color: #FFFF1a;}\n",
       ".cython.score-87 {background-color: #FFFF1a;}\n",
       ".cython.score-88 {background-color: #FFFF1a;}\n",
       ".cython.score-89 {background-color: #FFFF19;}\n",
       ".cython.score-90 {background-color: #FFFF19;}\n",
       ".cython.score-91 {background-color: #FFFF19;}\n",
       ".cython.score-92 {background-color: #FFFF19;}\n",
       ".cython.score-93 {background-color: #FFFF18;}\n",
       ".cython.score-94 {background-color: #FFFF18;}\n",
       ".cython.score-95 {background-color: #FFFF18;}\n",
       ".cython.score-96 {background-color: #FFFF18;}\n",
       ".cython.score-97 {background-color: #FFFF17;}\n",
       ".cython.score-98 {background-color: #FFFF17;}\n",
       ".cython.score-99 {background-color: #FFFF17;}\n",
       ".cython.score-100 {background-color: #FFFF17;}\n",
       ".cython.score-101 {background-color: #FFFF16;}\n",
       ".cython.score-102 {background-color: #FFFF16;}\n",
       ".cython.score-103 {background-color: #FFFF16;}\n",
       ".cython.score-104 {background-color: #FFFF16;}\n",
       ".cython.score-105 {background-color: #FFFF16;}\n",
       ".cython.score-106 {background-color: #FFFF15;}\n",
       ".cython.score-107 {background-color: #FFFF15;}\n",
       ".cython.score-108 {background-color: #FFFF15;}\n",
       ".cython.score-109 {background-color: #FFFF15;}\n",
       ".cython.score-110 {background-color: #FFFF15;}\n",
       ".cython.score-111 {background-color: #FFFF15;}\n",
       ".cython.score-112 {background-color: #FFFF14;}\n",
       ".cython.score-113 {background-color: #FFFF14;}\n",
       ".cython.score-114 {background-color: #FFFF14;}\n",
       ".cython.score-115 {background-color: #FFFF14;}\n",
       ".cython.score-116 {background-color: #FFFF14;}\n",
       ".cython.score-117 {background-color: #FFFF14;}\n",
       ".cython.score-118 {background-color: #FFFF13;}\n",
       ".cython.score-119 {background-color: #FFFF13;}\n",
       ".cython.score-120 {background-color: #FFFF13;}\n",
       ".cython.score-121 {background-color: #FFFF13;}\n",
       ".cython.score-122 {background-color: #FFFF13;}\n",
       ".cython.score-123 {background-color: #FFFF13;}\n",
       ".cython.score-124 {background-color: #FFFF13;}\n",
       ".cython.score-125 {background-color: #FFFF12;}\n",
       ".cython.score-126 {background-color: #FFFF12;}\n",
       ".cython.score-127 {background-color: #FFFF12;}\n",
       ".cython.score-128 {background-color: #FFFF12;}\n",
       ".cython.score-129 {background-color: #FFFF12;}\n",
       ".cython.score-130 {background-color: #FFFF12;}\n",
       ".cython.score-131 {background-color: #FFFF12;}\n",
       ".cython.score-132 {background-color: #FFFF11;}\n",
       ".cython.score-133 {background-color: #FFFF11;}\n",
       ".cython.score-134 {background-color: #FFFF11;}\n",
       ".cython.score-135 {background-color: #FFFF11;}\n",
       ".cython.score-136 {background-color: #FFFF11;}\n",
       ".cython.score-137 {background-color: #FFFF11;}\n",
       ".cython.score-138 {background-color: #FFFF11;}\n",
       ".cython.score-139 {background-color: #FFFF11;}\n",
       ".cython.score-140 {background-color: #FFFF11;}\n",
       ".cython.score-141 {background-color: #FFFF10;}\n",
       ".cython.score-142 {background-color: #FFFF10;}\n",
       ".cython.score-143 {background-color: #FFFF10;}\n",
       ".cython.score-144 {background-color: #FFFF10;}\n",
       ".cython.score-145 {background-color: #FFFF10;}\n",
       ".cython.score-146 {background-color: #FFFF10;}\n",
       ".cython.score-147 {background-color: #FFFF10;}\n",
       ".cython.score-148 {background-color: #FFFF10;}\n",
       ".cython.score-149 {background-color: #FFFF10;}\n",
       ".cython.score-150 {background-color: #FFFF0f;}\n",
       ".cython.score-151 {background-color: #FFFF0f;}\n",
       ".cython.score-152 {background-color: #FFFF0f;}\n",
       ".cython.score-153 {background-color: #FFFF0f;}\n",
       ".cython.score-154 {background-color: #FFFF0f;}\n",
       ".cython.score-155 {background-color: #FFFF0f;}\n",
       ".cython.score-156 {background-color: #FFFF0f;}\n",
       ".cython.score-157 {background-color: #FFFF0f;}\n",
       ".cython.score-158 {background-color: #FFFF0f;}\n",
       ".cython.score-159 {background-color: #FFFF0f;}\n",
       ".cython.score-160 {background-color: #FFFF0f;}\n",
       ".cython.score-161 {background-color: #FFFF0e;}\n",
       ".cython.score-162 {background-color: #FFFF0e;}\n",
       ".cython.score-163 {background-color: #FFFF0e;}\n",
       ".cython.score-164 {background-color: #FFFF0e;}\n",
       ".cython.score-165 {background-color: #FFFF0e;}\n",
       ".cython.score-166 {background-color: #FFFF0e;}\n",
       ".cython.score-167 {background-color: #FFFF0e;}\n",
       ".cython.score-168 {background-color: #FFFF0e;}\n",
       ".cython.score-169 {background-color: #FFFF0e;}\n",
       ".cython.score-170 {background-color: #FFFF0e;}\n",
       ".cython.score-171 {background-color: #FFFF0e;}\n",
       ".cython.score-172 {background-color: #FFFF0e;}\n",
       ".cython.score-173 {background-color: #FFFF0d;}\n",
       ".cython.score-174 {background-color: #FFFF0d;}\n",
       ".cython.score-175 {background-color: #FFFF0d;}\n",
       ".cython.score-176 {background-color: #FFFF0d;}\n",
       ".cython.score-177 {background-color: #FFFF0d;}\n",
       ".cython.score-178 {background-color: #FFFF0d;}\n",
       ".cython.score-179 {background-color: #FFFF0d;}\n",
       ".cython.score-180 {background-color: #FFFF0d;}\n",
       ".cython.score-181 {background-color: #FFFF0d;}\n",
       ".cython.score-182 {background-color: #FFFF0d;}\n",
       ".cython.score-183 {background-color: #FFFF0d;}\n",
       ".cython.score-184 {background-color: #FFFF0d;}\n",
       ".cython.score-185 {background-color: #FFFF0d;}\n",
       ".cython.score-186 {background-color: #FFFF0d;}\n",
       ".cython.score-187 {background-color: #FFFF0c;}\n",
       ".cython.score-188 {background-color: #FFFF0c;}\n",
       ".cython.score-189 {background-color: #FFFF0c;}\n",
       ".cython.score-190 {background-color: #FFFF0c;}\n",
       ".cython.score-191 {background-color: #FFFF0c;}\n",
       ".cython.score-192 {background-color: #FFFF0c;}\n",
       ".cython.score-193 {background-color: #FFFF0c;}\n",
       ".cython.score-194 {background-color: #FFFF0c;}\n",
       ".cython.score-195 {background-color: #FFFF0c;}\n",
       ".cython.score-196 {background-color: #FFFF0c;}\n",
       ".cython.score-197 {background-color: #FFFF0c;}\n",
       ".cython.score-198 {background-color: #FFFF0c;}\n",
       ".cython.score-199 {background-color: #FFFF0c;}\n",
       ".cython.score-200 {background-color: #FFFF0c;}\n",
       ".cython.score-201 {background-color: #FFFF0c;}\n",
       ".cython.score-202 {background-color: #FFFF0c;}\n",
       ".cython.score-203 {background-color: #FFFF0b;}\n",
       ".cython.score-204 {background-color: #FFFF0b;}\n",
       ".cython.score-205 {background-color: #FFFF0b;}\n",
       ".cython.score-206 {background-color: #FFFF0b;}\n",
       ".cython.score-207 {background-color: #FFFF0b;}\n",
       ".cython.score-208 {background-color: #FFFF0b;}\n",
       ".cython.score-209 {background-color: #FFFF0b;}\n",
       ".cython.score-210 {background-color: #FFFF0b;}\n",
       ".cython.score-211 {background-color: #FFFF0b;}\n",
       ".cython.score-212 {background-color: #FFFF0b;}\n",
       ".cython.score-213 {background-color: #FFFF0b;}\n",
       ".cython.score-214 {background-color: #FFFF0b;}\n",
       ".cython.score-215 {background-color: #FFFF0b;}\n",
       ".cython.score-216 {background-color: #FFFF0b;}\n",
       ".cython.score-217 {background-color: #FFFF0b;}\n",
       ".cython.score-218 {background-color: #FFFF0b;}\n",
       ".cython.score-219 {background-color: #FFFF0b;}\n",
       ".cython.score-220 {background-color: #FFFF0b;}\n",
       ".cython.score-221 {background-color: #FFFF0b;}\n",
       ".cython.score-222 {background-color: #FFFF0a;}\n",
       ".cython.score-223 {background-color: #FFFF0a;}\n",
       ".cython.score-224 {background-color: #FFFF0a;}\n",
       ".cython.score-225 {background-color: #FFFF0a;}\n",
       ".cython.score-226 {background-color: #FFFF0a;}\n",
       ".cython.score-227 {background-color: #FFFF0a;}\n",
       ".cython.score-228 {background-color: #FFFF0a;}\n",
       ".cython.score-229 {background-color: #FFFF0a;}\n",
       ".cython.score-230 {background-color: #FFFF0a;}\n",
       ".cython.score-231 {background-color: #FFFF0a;}\n",
       ".cython.score-232 {background-color: #FFFF0a;}\n",
       ".cython.score-233 {background-color: #FFFF0a;}\n",
       ".cython.score-234 {background-color: #FFFF0a;}\n",
       ".cython.score-235 {background-color: #FFFF0a;}\n",
       ".cython.score-236 {background-color: #FFFF0a;}\n",
       ".cython.score-237 {background-color: #FFFF0a;}\n",
       ".cython.score-238 {background-color: #FFFF0a;}\n",
       ".cython.score-239 {background-color: #FFFF0a;}\n",
       ".cython.score-240 {background-color: #FFFF0a;}\n",
       ".cython.score-241 {background-color: #FFFF0a;}\n",
       ".cython.score-242 {background-color: #FFFF0a;}\n",
       ".cython.score-243 {background-color: #FFFF0a;}\n",
       ".cython.score-244 {background-color: #FFFF0a;}\n",
       ".cython.score-245 {background-color: #FFFF0a;}\n",
       ".cython.score-246 {background-color: #FFFF09;}\n",
       ".cython.score-247 {background-color: #FFFF09;}\n",
       ".cython.score-248 {background-color: #FFFF09;}\n",
       ".cython.score-249 {background-color: #FFFF09;}\n",
       ".cython.score-250 {background-color: #FFFF09;}\n",
       ".cython.score-251 {background-color: #FFFF09;}\n",
       ".cython.score-252 {background-color: #FFFF09;}\n",
       ".cython.score-253 {background-color: #FFFF09;}\n",
       ".cython.score-254 {background-color: #FFFF09;}\n",
       ".cython .hll { background-color: #ffffcc }\n",
       ".cython  { background: #f8f8f8; }\n",
       ".cython .c { color: #408080; font-style: italic } /* Comment */\n",
       ".cython .err { border: 1px solid #FF0000 } /* Error */\n",
       ".cython .k { color: #008000; font-weight: bold } /* Keyword */\n",
       ".cython .o { color: #666666 } /* Operator */\n",
       ".cython .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       ".cython .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       ".cython .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       ".cython .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       ".cython .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       ".cython .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       ".cython .gd { color: #A00000 } /* Generic.Deleted */\n",
       ".cython .ge { font-style: italic } /* Generic.Emph */\n",
       ".cython .gr { color: #FF0000 } /* Generic.Error */\n",
       ".cython .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       ".cython .gi { color: #00A000 } /* Generic.Inserted */\n",
       ".cython .go { color: #888888 } /* Generic.Output */\n",
       ".cython .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       ".cython .gs { font-weight: bold } /* Generic.Strong */\n",
       ".cython .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       ".cython .gt { color: #0044DD } /* Generic.Traceback */\n",
       ".cython .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       ".cython .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       ".cython .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       ".cython .kp { color: #008000 } /* Keyword.Pseudo */\n",
       ".cython .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       ".cython .kt { color: #B00040 } /* Keyword.Type */\n",
       ".cython .m { color: #666666 } /* Literal.Number */\n",
       ".cython .s { color: #BA2121 } /* Literal.String */\n",
       ".cython .na { color: #7D9029 } /* Name.Attribute */\n",
       ".cython .nb { color: #008000 } /* Name.Builtin */\n",
       ".cython .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       ".cython .no { color: #880000 } /* Name.Constant */\n",
       ".cython .nd { color: #AA22FF } /* Name.Decorator */\n",
       ".cython .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       ".cython .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       ".cython .nf { color: #0000FF } /* Name.Function */\n",
       ".cython .nl { color: #A0A000 } /* Name.Label */\n",
       ".cython .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       ".cython .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       ".cython .nv { color: #19177C } /* Name.Variable */\n",
       ".cython .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       ".cython .w { color: #bbbbbb } /* Text.Whitespace */\n",
       ".cython .mb { color: #666666 } /* Literal.Number.Bin */\n",
       ".cython .mf { color: #666666 } /* Literal.Number.Float */\n",
       ".cython .mh { color: #666666 } /* Literal.Number.Hex */\n",
       ".cython .mi { color: #666666 } /* Literal.Number.Integer */\n",
       ".cython .mo { color: #666666 } /* Literal.Number.Oct */\n",
       ".cython .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       ".cython .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       ".cython .sc { color: #BA2121 } /* Literal.String.Char */\n",
       ".cython .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       ".cython .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       ".cython .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       ".cython .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       ".cython .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       ".cython .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       ".cython .sx { color: #008000 } /* Literal.String.Other */\n",
       ".cython .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       ".cython .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       ".cython .ss { color: #19177C } /* Literal.String.Symbol */\n",
       ".cython .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       ".cython .fm { color: #0000FF } /* Name.Function.Magic */\n",
       ".cython .vc { color: #19177C } /* Name.Variable.Class */\n",
       ".cython .vg { color: #19177C } /* Name.Variable.Global */\n",
       ".cython .vi { color: #19177C } /* Name.Variable.Instance */\n",
       ".cython .vm { color: #19177C } /* Name.Variable.Magic */\n",
       ".cython .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "    </style>\n",
       "</head>\n",
       "<body class=\"cython\">\n",
       "<p><span style=\"border-bottom: solid 1px grey;\">Generated by Cython 0.29.17</span></p>\n",
       "<p>\n",
       "    <span style=\"background-color: #FFFF00\">Yellow lines</span> hint at Python interaction.<br />\n",
       "    Click on a line that starts with a \"<code>+</code>\" to see the C code that Cython generated for it.\n",
       "</p>\n",
       "<div class=\"cython\"><pre class=\"cython line score-8\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">01</span>: <span class=\"c\"># cython: language_level=3</span></pre>\n",
       "<pre class='cython code score-8 '>  __pyx_t_1 = <span class='pyx_c_api'>__Pyx_PyDict_NewPresized</span>(0);<span class='error_goto'> if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 1, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  if (<span class='py_c_api'>PyDict_SetItem</span>(__pyx_d, __pyx_n_s_test, __pyx_t_1) &lt; 0) <span class='error_goto'>__PYX_ERR(0, 1, __pyx_L1_error)</span>\n",
       "  <span class='pyx_macro_api'>__Pyx_DECREF</span>(__pyx_t_1); __pyx_t_1 = 0;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">02</span>: <span class=\"c\"># cython: infer_types=True</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">03</span>: <span class=\"c\"># cython: boundscheck=False</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">04</span>: <span class=\"c\"># cython: wraparound=False</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">05</span>: <span class=\"c\"># cython: nonecheck=False</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">06</span>: <span class=\"c\"># cython: cdivision=True</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">07</span>: </pre>\n",
       "<pre class=\"cython line score-44\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">08</span>: <span class=\"k\">cpdef</span> <span class=\"kt\">Py_ssize_t</span> <span class=\"nf\">binarySearch_v3</span><span class=\"p\">(</span><span class=\"nb\">int</span><span class=\"p\">[::</span><span class=\"mf\">1</span><span class=\"p\">]</span> <span class=\"n\">arr</span><span class=\"p\">,</span><span class=\"nb\">int</span> <span class=\"n\">x</span><span class=\"p\">):</span></pre>\n",
       "<pre class='cython code score-44 '>static PyObject *__pyx_pw_46_cython_magic_6172a75514763b92fb920daf6370d90e_1binarySearch_v3(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/\n",
       "static Py_ssize_t __pyx_f_46_cython_magic_6172a75514763b92fb920daf6370d90e_binarySearch_v3(__Pyx_memviewslice __pyx_v_arr, int __pyx_v_x, CYTHON_UNUSED int __pyx_skip_dispatch) {\n",
       "  Py_ssize_t __pyx_v_lo;\n",
       "  Py_ssize_t __pyx_v_hi;\n",
       "  Py_ssize_t __pyx_v_mid;\n",
       "  Py_ssize_t __pyx_r;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"binarySearch_v3\", 0);\n",
       "/* … */\n",
       "  /* function exit code */\n",
       "  __pyx_L0:;\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "/* Python wrapper */\n",
       "static PyObject *__pyx_pw_46_cython_magic_6172a75514763b92fb920daf6370d90e_1binarySearch_v3(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/\n",
       "static PyObject *__pyx_pw_46_cython_magic_6172a75514763b92fb920daf6370d90e_1binarySearch_v3(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {\n",
       "  __Pyx_memviewslice __pyx_v_arr = { 0, 0, { 0 }, { 0 }, { 0 } };\n",
       "  int __pyx_v_x;\n",
       "  PyObject *__pyx_r = 0;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"binarySearch_v3 (wrapper)\", 0);\n",
       "  {\n",
       "    static PyObject **__pyx_pyargnames[] = {&amp;__pyx_n_s_arr,&amp;__pyx_n_s_x,0};\n",
       "    PyObject* values[2] = {0,0};\n",
       "    if (unlikely(__pyx_kwds)) {\n",
       "      Py_ssize_t kw_args;\n",
       "      const Py_ssize_t pos_args = <span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args);\n",
       "      switch (pos_args) {\n",
       "        case  2: values[1] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 1);\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  1: values[0] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 0);\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  0: break;\n",
       "        default: goto __pyx_L5_argtuple_error;\n",
       "      }\n",
       "      kw_args = <span class='py_c_api'>PyDict_Size</span>(__pyx_kwds);\n",
       "      switch (pos_args) {\n",
       "        case  0:\n",
       "        if (likely((values[0] = <span class='pyx_c_api'>__Pyx_PyDict_GetItemStr</span>(__pyx_kwds, __pyx_n_s_arr)) != 0)) kw_args--;\n",
       "        else goto __pyx_L5_argtuple_error;\n",
       "        CYTHON_FALLTHROUGH;\n",
       "        case  1:\n",
       "        if (likely((values[1] = <span class='pyx_c_api'>__Pyx_PyDict_GetItemStr</span>(__pyx_kwds, __pyx_n_s_x)) != 0)) kw_args--;\n",
       "        else {\n",
       "          <span class='pyx_c_api'>__Pyx_RaiseArgtupleInvalid</span>(\"binarySearch_v3\", 1, 2, 2, 1); <span class='error_goto'>__PYX_ERR(0, 8, __pyx_L3_error)</span>\n",
       "        }\n",
       "      }\n",
       "      if (unlikely(kw_args &gt; 0)) {\n",
       "        if (unlikely(<span class='pyx_c_api'>__Pyx_ParseOptionalKeywords</span>(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, \"binarySearch_v3\") &lt; 0)) <span class='error_goto'>__PYX_ERR(0, 8, __pyx_L3_error)</span>\n",
       "      }\n",
       "    } else if (<span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args) != 2) {\n",
       "      goto __pyx_L5_argtuple_error;\n",
       "    } else {\n",
       "      values[0] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 0);\n",
       "      values[1] = <span class='py_macro_api'>PyTuple_GET_ITEM</span>(__pyx_args, 1);\n",
       "    }\n",
       "    __pyx_v_arr = <span class='pyx_c_api'>__Pyx_PyObject_to_MemoryviewSlice_dc_int</span>(values[0], PyBUF_WRITABLE);<span class='error_goto'> if (unlikely(!__pyx_v_arr.memview)) __PYX_ERR(0, 8, __pyx_L3_error)</span>\n",
       "    __pyx_v_x = <span class='pyx_c_api'>__Pyx_PyInt_As_int</span>(values[1]); if (unlikely((__pyx_v_x == (int)-1) &amp;&amp; <span class='py_c_api'>PyErr_Occurred</span>())) <span class='error_goto'>__PYX_ERR(0, 8, __pyx_L3_error)</span>\n",
       "  }\n",
       "  goto __pyx_L4_argument_unpacking_done;\n",
       "  __pyx_L5_argtuple_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_RaiseArgtupleInvalid</span>(\"binarySearch_v3\", 1, 2, 2, <span class='py_macro_api'>PyTuple_GET_SIZE</span>(__pyx_args)); <span class='error_goto'>__PYX_ERR(0, 8, __pyx_L3_error)</span>\n",
       "  __pyx_L3_error:;\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_6172a75514763b92fb920daf6370d90e.binarySearch_v3\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return NULL;\n",
       "  __pyx_L4_argument_unpacking_done:;\n",
       "  __pyx_r = __pyx_pf_46_cython_magic_6172a75514763b92fb920daf6370d90e_binarySearch_v3(__pyx_self, __pyx_v_arr, __pyx_v_x);\n",
       "\n",
       "  /* function exit code */\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "\n",
       "static PyObject *__pyx_pf_46_cython_magic_6172a75514763b92fb920daf6370d90e_binarySearch_v3(CYTHON_UNUSED PyObject *__pyx_self, __Pyx_memviewslice __pyx_v_arr, int __pyx_v_x) {\n",
       "  PyObject *__pyx_r = NULL;\n",
       "  <span class='refnanny'>__Pyx_RefNannyDeclarations</span>\n",
       "  <span class='refnanny'>__Pyx_RefNannySetupContext</span>(\"binarySearch_v3\", 0);\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_r);\n",
       "  if (unlikely(!__pyx_v_arr.memview)) { <span class='pyx_c_api'>__Pyx_RaiseUnboundLocalError</span>(\"arr\"); <span class='error_goto'>__PYX_ERR(0, 8, __pyx_L1_error)</span> }\n",
       "  __pyx_t_1 = <span class='py_c_api'>PyInt_FromSsize_t</span>(__pyx_f_46_cython_magic_6172a75514763b92fb920daf6370d90e_binarySearch_v3(__pyx_v_arr, __pyx_v_x, 0));<span class='error_goto'> if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 8, __pyx_L1_error)</span>\n",
       "  <span class='refnanny'>__Pyx_GOTREF</span>(__pyx_t_1);\n",
       "  __pyx_r = __pyx_t_1;\n",
       "  __pyx_t_1 = 0;\n",
       "  goto __pyx_L0;\n",
       "\n",
       "  /* function exit code */\n",
       "  __pyx_L1_error:;\n",
       "  <span class='pyx_macro_api'>__Pyx_XDECREF</span>(__pyx_t_1);\n",
       "  <span class='pyx_c_api'>__Pyx_AddTraceback</span>(\"_cython_magic_6172a75514763b92fb920daf6370d90e.binarySearch_v3\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n",
       "  __pyx_r = NULL;\n",
       "  __pyx_L0:;\n",
       "  __PYX_XDEC_MEMVIEW(&amp;__pyx_v_arr, 1);\n",
       "  <span class='refnanny'>__Pyx_XGIVEREF</span>(__pyx_r);\n",
       "  <span class='refnanny'>__Pyx_RefNannyFinishContext</span>();\n",
       "  return __pyx_r;\n",
       "}\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">09</span>:     <span class=\"k\">cdef</span><span class=\"p\">:</span></pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">10</span>:         <span class=\"n\">Py_ssize_t</span> <span class=\"n\">lo</span> <span class=\"o\">=</span> <span class=\"mf\">0</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_v_lo = 0;\n",
       "</pre><pre class=\"cython line score-2\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">11</span>:         <span class=\"n\">Py_ssize_t</span> <span class=\"n\">hi</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">arr</span><span class=\"p\">)</span></pre>\n",
       "<pre class='cython code score-2 '>  __pyx_t_1 = <span class='pyx_c_api'>__Pyx_MemoryView_Len</span>(__pyx_v_arr); \n",
       "  __pyx_v_hi = __pyx_t_1;\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">12</span>:         <span class=\"n\">Py_ssize_t</span> <span class=\"n\">mid</span></pre>\n",
       "<pre class=\"cython line score-0\">&#xA0;<span class=\"\">13</span>: </pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">14</span>:     <span class=\"k\">while</span> <span class=\"n\">lo</span> <span class=\"o\">&lt;</span> <span class=\"n\">hi</span><span class=\"p\">:</span></pre>\n",
       "<pre class='cython code score-0 '>  while (1) {\n",
       "    __pyx_t_2 = ((__pyx_v_lo &lt; __pyx_v_hi) != 0);\n",
       "    if (!__pyx_t_2) break;\n",
       "</pre><pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">15</span>:         <span class=\"n\">mid</span> <span class=\"o\">=</span> <span class=\"p\">(</span><span class=\"n\">lo</span><span class=\"o\">+</span><span class=\"n\">hi</span><span class=\"p\">)</span><span class=\"o\">//</span><span class=\"mf\">2</span></pre>\n",
       "<pre class='cython code score-0 '>    __pyx_v_mid = ((__pyx_v_lo + __pyx_v_hi) / 2);\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">16</span>: </pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">17</span>:         <span class=\"k\">if</span> <span class=\"n\">arr</span><span class=\"p\">[</span><span class=\"n\">mid</span><span class=\"p\">]</span> <span class=\"o\">&lt;</span> <span class=\"n\">x</span><span class=\"p\">:</span></pre>\n",
       "<pre class='cython code score-0 '>    __pyx_t_3 = __pyx_v_mid;\n",
       "    __pyx_t_2 = (((*((int *) ( /* dim=0 */ ((char *) (((int *) __pyx_v_arr.data) + __pyx_t_3)) ))) &lt; __pyx_v_x) != 0);\n",
       "    if (__pyx_t_2) {\n",
       "/* … */\n",
       "      goto __pyx_L5;\n",
       "    }\n",
       "</pre><pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">18</span>:             <span class=\"n\">lo</span> <span class=\"o\">=</span> <span class=\"n\">mid</span><span class=\"o\">+</span><span class=\"mf\">1</span></pre>\n",
       "<pre class='cython code score-0 '>      __pyx_v_lo = (__pyx_v_mid + 1);\n",
       "</pre><pre class=\"cython line score-0\">&#xA0;<span class=\"\">19</span>:         <span class=\"k\">else</span><span class=\"p\">:</span></pre>\n",
       "<pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">20</span>:             <span class=\"n\">hi</span> <span class=\"o\">=</span> <span class=\"n\">mid</span></pre>\n",
       "<pre class='cython code score-0 '>    /*else*/ {\n",
       "      __pyx_v_hi = __pyx_v_mid;\n",
       "    }\n",
       "    __pyx_L5:;\n",
       "  }\n",
       "</pre><pre class=\"cython line score-0\" onclick=\"(function(s){s.display=s.display==='block'?'none':'block'})(this.nextElementSibling.style)\">+<span class=\"\">21</span>:     <span class=\"k\">return</span> <span class=\"n\">lo</span></pre>\n",
       "<pre class='cython code score-0 '>  __pyx_r = __pyx_v_lo;\n",
       "  goto __pyx_L0;\n",
       "</pre></div></body></html>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%cython -a\n",
    "# cython: language_level=3\n",
    "# cython: infer_types=True\n",
    "# cython: boundscheck=False\n",
    "# cython: wraparound=False\n",
    "# cython: nonecheck=False\n",
    "# cython: cdivision=True\n",
    "\n",
    "cpdef Py_ssize_t binarySearch_v3(int[::1] arr,int x):\n",
    "    cdef:\n",
    "        Py_ssize_t lo = 0\n",
    "        Py_ssize_t hi = len(arr)\n",
    "        Py_ssize_t mid\n",
    "\n",
    "    while lo < hi:\n",
    "        mid = (lo+hi)//2\n",
    "        \n",
    "        if arr[mid] < x:\n",
    "            lo = mid+1\n",
    "        else:\n",
    "            hi = mid\n",
    "    return lo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "У Cython есть и другое применение: можно забыть все, чему нас учили, и писать невекторизованный код, который работает быстрее векторизованного. Разумеется, это не получится всегда, но в случае, когда несколько операций над одними и теми же данными можно скомбинировать, есть возможность получить прирост в скорости. Пример такого приведён ниже:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def process_arr(x):\n",
    "    return np.sin(x)*5*np.square(x)-np.cumsum(x)/len(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример ниже также показывает, что в Cython можно писать шаблонные функции с помощью [fused types](https://cython.readthedocs.io/en/latest/src/userguide/fusedtypes.html) и импортировать функции напрямую из C или даже C++ (об этом чуть позже):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "from libc.math cimport pow, sin\n",
    "# cython: language_level=3\n",
    "# cython: infer_types=True\n",
    "# cython: boundscheck=False\n",
    "# cython: wraparound=False\n",
    "# cython: nonecheck=False\n",
    "# cython: cdivision=True\n",
    "import numpy as np\n",
    "\n",
    "ctypedef fused any_float:\n",
    "    float\n",
    "    double\n",
    "\n",
    "cpdef any_float[::1] process_arr_v1(any_float[::1] x):\n",
    "    cdef:\n",
    "        any_float cumsum = 0\n",
    "        any_float[::1] buf = np.empty_like(x)\n",
    "        Py_ssize_t i, size = x.shape[0]\n",
    "    for i in range(size):\n",
    "        cumsum += x[i]\n",
    "        buf[i] = sin(x[i])*5*pow(x[i], 2)-cumsum/size\n",
    "    return buf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr=np.random.randn(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11.8 µs ± 29.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit process_arr(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6.86 µs ± 17.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit process_arr_v1(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr=np.random.randn(100000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.83 ms ± 286 ns per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit process_arr(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.56 ms ± 832 ns per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit process_arr_v1(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert np.allclose(process_arr(arr), process_arr_v1(arr))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как видим, невекторизованный код минимальными усилиями получилось ускорить до векторизованного. В завершение покажем, как пользоваться конструкциями из языка [C++](https://cython.readthedocs.io/en/latest/src/userguide/wrapping_CPlusPlus.html). Вообще говоря, в руководстве по ссылке демонстрируется возможность написания интерфейса для произвольного C++-класса, но мы ограничимся использованием [портированных](https://github.com/cython/cython/tree/master/Cython/Includes/libcpp) в Cython классов и функций из стандартной библиотеки. \n",
    "\n",
    "Чтобы компилировать Cython с поддержкой C++, нужно передать флаг `--cplus` и при сборке в командной строке, и при использовании Jupyter. Также для определения нетривиальных контейнеров нужно пользоваться командой `ctypedef`. Пример также показывает, как можно определять в Cython [классы](https://cython.readthedocs.io/en/latest/src/tutorial/cdef_classes.html), которые могут пользоваться C++-объектами."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0\n",
      "1 0\n",
      "2 0\n",
      "3 0\n",
      "4 0\n",
      "5 0\n",
      "6 0\n",
      "7 0\n",
      "8 0\n",
      "9 0\n",
      "True\n",
      "5\n",
      "5\n"
     ]
    },
    {
     "ename": "KeyError",
     "evalue": "20",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[0;31mKeyError\u001b[0m: 20"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Exception ignored in: '_cython_magic_d9b0fec9e9d67eace73935ed3c2d8086.MapInterface.get_top_by_key'\n",
      "Traceback (most recent call last):\n",
      "  File \"<frozen importlib._bootstrap>\", line 219, in _call_with_frames_removed\n",
      "KeyError: 20\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "%%cython --cplus -c=-std=c++14\n",
    "# cython: language_level=3\n",
    "# cython: infer_types=True\n",
    "# cython: boundscheck=False\n",
    "# cython: wraparound=False\n",
    "# cython: nonecheck=False\n",
    "# cython: cdivision=True\n",
    "\n",
    "from libcpp.unordered_map cimport unordered_map\n",
    "from libcpp.stack cimport stack\n",
    "from libcpp.queue cimport queue\n",
    "\n",
    "from cython.operator import dereference\n",
    "\n",
    "ctypedef stack[int] int_stack\n",
    "ctypedef unordered_map[int, int_stack] stack_map\n",
    "\n",
    "cdef:\n",
    "    unordered_map[int, int_stack].iterator it # we can even use iterators\n",
    "\n",
    "cdef class MapInterface:\n",
    "    cdef stack_map smap # attributes need to be declared outside of init\n",
    "    \n",
    "    def __init__(self):\n",
    "        cdef:\n",
    "            int i=0\n",
    "            queue[int] cur_queue\n",
    "            int_stack cur_stack\n",
    "            Py_ssize_t j, k\n",
    "        self.smap = stack_map()\n",
    "        \n",
    "        for j in range(10):\n",
    "            cur_stack = int_stack()\n",
    "            cur_queue = queue[int]()\n",
    "            for k in range(j+1):\n",
    "                cur_stack.push(k)\n",
    "                cur_queue.push(k)\n",
    "            print(cur_stack.top(),cur_queue.front())\n",
    "            self.smap[<int>j] = cur_stack # type casting is supported as well\n",
    "\n",
    "        \n",
    "    cpdef int get_top_by_key(self, int key):\n",
    "        cdef unordered_map[int, int_stack].iterator it = self.smap.find(key)\n",
    "        if it == self.smap.end():\n",
    "            raise KeyError(key) # exceptions are thrown the same way\n",
    "        cdef int_stack found_stack = dereference(it).second\n",
    "        return found_stack.top()\n",
    "    \n",
    "cdef MapInterface map_interface = MapInterface()\n",
    "    \n",
    "it = map_interface.smap.find(10)\n",
    "print(it == map_interface.smap.end())\n",
    "# you can cast the pointer, cast it back and dereference with square bracket notation\n",
    "print(dereference(<int*>(<void*>&map_interface.smap[5].top())))\n",
    "print(map_interface.get_top_by_key(5))\n",
    "print(map_interface.get_top_by_key(20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Часть 1. Locality-Sensitive Hashing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В этом задании мы будем работать с датасетом [FashionMnist](https://github.com/zalandoresearch/fashion-mnist) изображений предметов одежды и обуви. В файле уже находится массив со 100 найденными соседями каждого тестового объекта по евклидовой метрике, однако мы для начала (чтобы реализовать метод случайных проекций) попробуем найти 100 ближайших соседей для каждого объекта по косинусной близости.\n",
    "\n",
    "Ниже вы можете увидеть, как загружается этот датасет, и посмотреть на примеры нескольких изображений из обучающей выборки."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "!wget -nc -q http://ann-benchmarks.com/fashion-mnist-784-euclidean.hdf5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(60000, 784)\n",
      "(10000, 784)\n",
      "(10000, 100)\n"
     ]
    }
   ],
   "source": [
    "import h5py\n",
    "\n",
    "with h5py.File('fashion-mnist-784-euclidean.hdf5', 'r') as f:\n",
    "    train = f['train'][()]\n",
    "    test = f['test'][()]\n",
    "    true_neighbors_eucl = f['neighbors'][()]\n",
    "\n",
    "print(train.shape)\n",
    "print(test.shape)\n",
    "print(true_neighbors_eucl.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.image.AxesImage at 0x7f972de09460>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA54AAADiCAYAAAAmhxjAAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3debhkdX3n8e+vlrv2Xfr2vtFNA82qLLaI4CgqRmCIaNyXiIkJxomZmHEyOpoZyfKYxASdPHEbEgmQMWoM+qCGKIpBFlm6aVpoaIGm6X1fbt+1bm2/+YNL0oH6fLu7bp2q07ffr+fph+76cur8qup8z6lf1b2/T4gxGgAAAAAAScm0egAAAAAAgOmNiScAAAAAIFFMPAEAAAAAiWLiCQAAAABIFBNPAAAAAECimHgCAAAAABI1pYlnCOHyEMKTIYQNIYRPNGpQABqDHgXSjR4F0o0eBRon1JvjGULImtlTZvYGM9tmZqvM7N0xxifUNm2hPXZYd137A6aLgo1aMU6EpPdDjzZQd6cs5ZYUZW18sENvN1b73BuqzjnZKZW79OeIoa+styvmZK1jx4QeSlnf5/GOHm2d0Kl7ptiblbVcb0nWShVnuwO6b7IjhZq3V7va5TbFflmygRmjslaq6jGODurzT36Xvs/pjB5Np9CWl7VSX5usdcyq3WtmZkWnf0sFsT9vapPVxf6uMVkbHOuStY6tevyxWnUGM32pHtXvOI7sQjPbEGPcaGYWQviGmV1tZrIZO6zbXhFeP4VdAse/B+OdzdrV8d2jwXlPUecHZnU75yWyNPPz22Vt3ffOkLW5a2pPWLMTFblNKOoL2L5z9UUxe9V+Wdu/aaasnfHHz8paZfceWTve0aOtkzlV98yONwzI2swrdsjazoO9sjb3G3pS13PPhpq3Fy44WW7z7K/oiex7L7pf1nZP6DHe/+1zZW3Rn/9M1qYzevQwKbpW5hYukbWdVy6WtRXve1LWtg7rT3N2Pj2n5u0Z5zOJSp++xl59wSOydtva82TtjI/q8VeHh2Wtbil6zRXVo1P5UdtFZrb1sH9vm7wNQDrQo0C60aNAutGjQANN5RvPWtPtF02zQwjXmtm1ZmYdpj+RB9Bw9CiQbvQokG70KNBAU/nGc5uZHf6d+mIze9HPusQYb4gxrowxrsyb/r0IAA1HjwLpRo8C6UaPAg00lYnnKjM7LYRwcgihzczeZWbfbcywADQAPQqkGz0KpBs9CjRQ3T9qG2MshxA+YmY/NLOsmd0YY3y8YSMDMCWp6dF6fwm+zl+Qr1x6gaw98059yvvD135b1gpRL6SzLL9X1uZ+6F9k7bz25n0q/tVD82WttFyvGPibb9kqa/dN6M8tP/zIe2Vt0ef0qofhvrWyNh2lpkcTMPSei2Rt0YdrL9pjZnZwQq8quTQ/qPc3oVfDPX/xNln7net/LGuXdNQ+xm8d0QsBjVb1yp33HDpd1raMOIt8XfWUrL3m/Qdl7fOrLpO10z7wsKzh36WmRxNYTCa3WP+q6vr/oRcCetMl+tiZmXtG1nYX9bWyJ6dXhf3TxXqef/JLZ8iaMlLV+7p9bJ6slV+qr5Vz7tULCK0f0dff1Q+skLXT/0Iv7lfetVvW0m4qv+NpMcbbzez2Bo0FQIPRo0C60aNAutGjQONM5UdtAQAAAAA4IiaeAAAAAIBEMfEEAAAAACSKiScAAAAAIFFMPAEAAAAAiQqxzmWY69EbBuIrwuubtj8gjR6Md9pQPOCsjd46aerR7OxZsjb+db2E+oeX3iVrbaEia5uKs2VtT1HHJ4xUdCxKOerl1zszxZq3n9apl0nfVhyQtZKzr2ps/OE2Oz8ia/Pyh2StP6vjMj79+C/L2vw3rz+6gTUAPXp0MueeKWvb/1BvN7xH92+mqyxrIaPfr8SqfrliWX/GftLC/bKmlKv6/ipOrx0Y6tbbVfR9Vp3xhwM6viW3QPda8ZA+b624dpWspcUJ16N1xql4PXrV1++VtQcPnSxrg8UuWRsv67isUkVfo0aL+jg+MKj7pqt7oubtXj8VizrQI5/X7xFOGtDRRe05fd6akas9RjOznryOdtlb0OfJLTefKmuzvnq/rDWT6lG+8QQAAAAAJIqJJwAAAAAgUUw8AQAAAACJYuIJAAAAAEgUE08AAAAAQKKYeAIAAAAAEqXXFEb61bm8tpKdpaMaDr5xhaz1/sMDx7wvM3PHH3J6Se5Yqh1DkRjvefY0MapoOuq9TT9/75p1n6w9OHyKrHmRI53ZkqyNV/TxmAl6nG1BL7Gutnt0dIncJufEwXjydW7n2VPskbV9Jb0MvBft8sdn3yZrX7zwrXowDz2ma0jMU7/fIWvVfbrXPF5kSnu77tFyWe+v5MSRbN6iY5QyQ7XfIlU7qnKb4MW6tOntXM59Wk4/X5WtOvZizpk6RubQ+y6Stb7/V+f1HlNT5/uJg3+qe+b+QX2tfHZIvx/scKJDvPP7hBOnEpzrqIpMMTObmKjdo2UnMiXnRKb0dOl4Ey8qZqKi9zc0oc+T2Yy+jnbn9XvdU3/9Sb2/b8+UtcpBHQnTLHzjCQAAAABIFBNPAAAAAECimHgCAAAAABLFxBMAAAAAkCgmngAAAACARDHxBAAAAAAkijiV41jI6qWpY7n2cteZ886S26z/kI5AyIzrceRHL5S13LhePj5/x2pZqzsyxYtocZ4vC/ozmHrHEnKivfRK5Cec8uteJmtXztLRGmtGl8laV0a/Xu3Okz+3bUjW3tC9XtYWZvUy8HnnuBqu1h5LV0YfpxNR95P3KWJPpk3Wxqp6uf2NZX2J+Jfhl+r7rOj9mZMMUYh6ufqnfkMvSb/iIX2fSM7SW/Sxeuh3dD8d3K8jBOIe/TqPzXDesjiRKZ5QdOJPZtc+l7gBW0P6GA6Fxn/Wn3HGX+nVsRF7t/fL2goiU44rueXLZO0ls3bK2tZRfQx05fV1YcK5Lgx0jMnanE59/c0FfW0rR903RRFjUqzqc1N/m35Du6DjkKxNVHVve5FrE1X9fO0e1+dCL4ZlXsewrD35nnNlbe4XfyZrzcI3ngAAAACARDHxBAAAAAAkioknAAAAACBRTDwBAAAAAIli4gkAAAAASBQTTwAAAABAoqYUpxJC2GRmw2ZWMbNyjHFlIwaFoyPjOkzHqWx9o14++72vvEfW7tu7XNY2t8/X4+iUJctd9kpZW/Gl7bJW3rRF32nU0RbqOTmS7MyZuljRy9VXhkScgB5iw6W9R7e9TsduzMqNyNrMnF6yvRT1MuodGb1E/L6SXtb8XV/6mKx179DLwPdsnpC1kSXtNW+fsV1vEzM6OiFT1OOotOvnpNSra3vO1+eYP3r312Tt4dGTZc2LuylFvb/Pv/brsvZlO1XW0i7tPerxIrHGLrpY1i584y9k7aFHTpO1kNMnz0yXPq6qB2r3mpkfRxL31T4/ZSecCJNO5xrkjD83rL8HKM3S166q8/1Bpktvd/pH9XVUX9VOTGnv0fLcXlm7pE/HZ/ykeoas9eb0dWhh+6CsjVX1NX0gNypr3nU740St5EPto7XqRLC0O+8Dsqb35V2fvDF6MSymXzpbO7xYb5bTkTCFS3XUin1Rl5qlETmer40x7mvA/QBIBj0KpBs9CqQbPQo0AD9qCwAAAABI1FQnntHM7gghPBxCuLYRAwLQUPQokG70KJBu9CjQIFP9UdtLYow7QghzzexHIYRfxBjvPvx/mGzSa83MOqxrirsDcIzoUSDd6FEg3ehRoEGm9I1njHHH5H/3mNl3zOzCGv/PDTHGlTHGlXnTv+APoPHoUSDd6FEg3ehRoHHqnniGELpDCD3P/93MfsnM1jVqYACmhh4F0o0eBdKNHgUaayo/ajvPzL4TQnj+fv4hxviDhowKR6VaKBzzNsXzdUTF2/r00vheDMVPM3oZ6e0/WSJrlZfqsWz+nI62qD6il+mftU4vBN/7yE5Z2/fqRbK292V6Cfx5D8iSzfzxMzVvDwcasZj0UUl9j151xYOyNlrVnxp7x+NEWT+/s3N6mfGnx+fJ2sLP6iXph995kaztvlDnCS24vvZ9bv+EPr5nP6Yfd2m2XrI9ZnX8Q9cuHUOx9NMPyVrhnXp/XmTK7Lx+DXaUdNzTh/sfl7WvvOxqWYsP6+1SIPU9Wq+T/kj3zJvfu1nWfj5Pn4sL+3U/VcZ0HENuTH/GnhvRvaG4sSijel9OGoNV805UzIh+bNVeHZky544OWavs268Hg8Olvkf3nt8tax1BXzMu7qv9HsVMx5Q8V9PH3L6yzge598ApsvbzLTo6JLtFH8e50dr9m9VpMJYfdXpNP11WadfnisGz9XPyu6+5Q9b2FPXztaJ7j6yd1KYXWL6nSz/PaVD3O+AY40YzO7eBYwHQQPQokG70KJBu9CjQWMSpAAAAAAASxcQTAAAAAJAoJp4AAAAAgEQx8QQAAAAAJIqJJwAAAAAgUU3LdUCdgrPUe9RLQo+8o3bEw/vPuktu80xpjqwtbjsga29f+LCs2ft07QtPvkbWRjf2yVqmWz/uXRfpz1K2X60fXyzppbBnrtFtkrlmt6wNFZfXvL1yJ+HSz/ufc++Rte+Pnixr7c6a5zPzOt7Hs7xzr6yts1myds/nviRr2ytjsvaaFb9X8/Znf1nf36sfe4us/ejsb8paV6ZN1j6992xZe+BcHZky5sTdeOeLQtT3WarqXrttVMds7PxP+nwx3zk9YWpCXh9XsaQjdf7+Cn3utz+vbyxZJzLFSYawSqe+nmTHa19/o043ce8vM6Gv57HerwGc7fpvub/OO8XxZM6X9et8y49fK2sbfk1HiLWfeUjWFn1GN0Bc9Zismelr7KlOLdurI0dCz4za4+jW0UvVXieWqVNfn3LDOqNl7hefkLV/MR0T9rJH9PuVV3U/JWvbyzNl7bKFT8rawyn4vrH1IwAAAAAATGtMPAEAAAAAiWLiCQAAAABIFBNPAAAAAECimHgCAAAAABLFxBMAAAAAkCjiVJrFi0VJwEUff6jm7a+doZd89iwyvUT8aNRL6g9WumXt02f9s6ztXdEja6WoD9u/ffpiWRtxIlqyZf36XPTrj8jaWwdWydpnb31JzdszcVRuMx3FS86TtQcnfiFro05cR97JR+gIOmplfl4vEf/I2FJZ81z51g/IWmZcj+WkJbWPuSv/9y/JbXqCjmd528QbZc0y+vgevGyF3p89IGt3H9TbXTqgl3MvOVkUXm1vWZ8TCq8ckTX7P7qEqfEiUzzljZt07dlXylrbUn3uLBe6ZC074lx/nfSlrEpPcPop55zeC7OcqBUn8sX7iqB9m45/wInhqa9cqIv6kLMFP9XFsFZHmBRn6vi5d63fI2tZp9meKcyVtSeGdPzJ9uHacSoTZSfyJepxhFCQtXk9+jrzwcWbZe2f9rxM1tb8ho60WXvoFFmLO3SUX3VMv09IA77xBAAAAAAkioknAAAAACBRTDwBAAAAAIli4gkAAAAASBQTTwAAAABAoph4AgAAAAASRZxKs0RnTesEPD1Se2nq/b21l542M9tV7pe1WVm9jHRPZlzWluX3ydreio5HyOb1ctdFJ3LhD8/+nqwVztTLznvxHBd37JC1tz/xflnrto2ydiLZ/fsqk8BsfnZI1jbZHFmbqOrXcp4TmbKnrJeIH6voWKDy6y+QtfE5eizjA/qzPfUQRufrJdQzOp3FcgV9jqm06fiHiX5dK/yWjra4eMZPZW1PST/PKzp2ylrWWfu/L6tzKq4580FZ+6nppfiRPjHjHAMz9LVmf1XHqVTa9X3mh/Xxr3o0o09plqkvYcacS5Crc09zo9qQPot+rI+BHa/V2+27WvfTZ1feKmsf++f3ydotf/DLsjbRp6+HQ/qyZ+Vu5/2zKMWc3ibmnRiZon4uR6s6ku8v/vFdstY2rPd38ONORFRJvyevDur4mU+8Tr8Pvu11L9X727lL1hqJbzwBAAAAAIli4gkAAAAASBQTTwAAAABAoph4AgAAAAASxcQTAAAAAJAoJp4AAAAAgEQdMU4lhHCjmV1lZntijOdM3jZgZt80s2VmtsnM3hFjPJjcMHGs5rTXjj/pCDqPoS2UZW1HaaasPT1+uqw9NaSXfL583uOyVnIiU7zIBS8WZWFeH6KFqCMxnAQLu2SejkxZ62zXSGnv0fJD+tj589lXyNo7566StdPa9sjakqyO4vm7Q+fI2kRVnw5vv+UrslaK+pgrRT2Wgqh1BP15YFdGH6cZ53PEiaiP4nzQvbaxpLe78cAlsraoXR9q3jko75yDfjp4hqzd90O9RPxS+5msNUvaezQRGX1cWVX3TNdOfRxnz9b95H2Mnp1wIkecpIZqW+1itqDvr9Kh7y/nbOdFtBQH9OOesb2+HJaQ1/FRsVRnJsxx7Hju0Vd/6n5ZG6m0y9rD+5bI2o07XiVr73/t3bL26Xc8IWuekWpB1g5U9XWhEGv3VEXcbmY2FvW1vsN5D9mX0bXFOR1V+HhRx9Z8avObZe3pfbNlreNRfaL5wkZ9nwt2tv56eDTfeN5kZpe/4LZPmNmdMcbTzOzOyX8DaI2bjB4F0uwmo0eBNLvJ6FEgcUeceMYY7zazAy+4+Wozu3ny7zebmZ5eA0gUPQqkGz0KpBs9CjRHvb/jOS/GuNPMbPK/8ucpQwjXhhBWhxBWl8z5WRIAjUSPAulGjwLpRo8CDZb44kIxxhtijCtjjCvzpn/WHEBr0KNAutGjQLrRo8DRqXfiuTuEsMDMbPK/eqUPAK1AjwLpRo8C6UaPAg1W78Tzu2Z2zeTfrzGz2xozHAANQo8C6UaPAulGjwINdjRxKl83s0vNbHYIYZuZfdrM/szM/jGE8EEz22Jmb09ykNNC0Es7h6xedj6W9TLS2Zk6puI1/Y/VvH1vpVduM1jpkrX+7JisDZf1ss4HxvV9ntG+U9bWjC2TtTltejVzb5ybinpp6tPad8naZ3e/XtaWdLxwLYJ/V379q2veHh/US5/XI+09uvgzevnuQ5/R2904/5WyNv5SvQz8rmv1suzXvfR7svb4yEJZu36/jmF5ekxHBnVndSxBe8YL6mmsTKgvgmh/qVvWTu3SH/7fvOEiWZt79S9kzVc7IsosHZEpnrT3aJr0bnLiQZzjuNqmI0eK/fouu7fqz98z5drX7YkBPY62Qedary/n5pwqLGb0/pp4GpnWjuce/dYdOtrqZa96UtZ+/5Q7ZO2/P6Qf6jM/WC5rt8yp/b7HzKx7m+41J0HPnKQzq3TW7g3v/jxB9LyZWU6norh9WNJJK1ZYoht/wxU3yNqvLbxU1m5ZquNuLnv412Ute9caWWukI048Y4zvFiX9bhxA09CjQLrRo0C60aNAcyS+uBAAAAAA4MTGxBMAAAAAkCgmngAAAACARDHxBAAAAAAkioknAAAAACBRR1zVFg0S9XLoIadfBi9OZesHz5S113XVjo34WWGR3GZObljWSs7a1AvaD8lazzwdbeHFtwzkdHTCcKVT1royE7LmPb4L2vbJ2u/9+AJZ6zlnv6z15sXnOnq1bhymvGu3rOWd2qLx82Wt40a95nnVeWH6cjqmxzv+2zO6f72eUrJBR0ZkTJ9jvH3Nzuu+GCrrXvP6aeKhAVkDPPlRfYwXYp0nT32XFp2P3yvttW932tDaD+o+LMzW43eSi1yVdi4oJ7rO0wdl7WBBv8+6Z2iFrHWv0uf+8VeMytp/Pu0JWas6zVZvvJi6tnn7ynjXUSeyybuel6t6f2sO6Pi3oX/SMW5/8nId4/bQ1qWy9pJd75G1JWs2yJoTZNVQfOMJAAAAAEgUE08AAAAAQKKYeAIAAAAAEsXEEwAAAACQKCaeAAAAAIBEMfEEAAAAACSKOJUmCfk2WasWdOSIZ/ZjRVnbV8nXvL0/o2Mh2oJeTLnoxDFcPPCsrO11ok/WjJ8saz3ZcVmbk9ExDkvyOt7ksYJe0vr20VNl7YNX/VjWvn7DG2St7Qc/q3l7iPo1OOEEHQWQaRdZBnaEnnGiizYW58paW53RJ5U6P79T0SgVL9+hyepd4t5JmHG50VIVZ7F35zVHi1TrW5w/U9JRB3v29+rtirpv2gbr66l2kVJRKunzlpNAZJ179HE6PkffZ27Ei15ysl1wQnj1oo2y1pnV7xMv73tU1u7fdaGsDY3Xfn9pZjZe0e91t4/1yVouo4/jibK+LuSztc8zXrxJdGKZghOnMrtDx8iMlfVzcnb/LllbNabjVE5u3yNrZ83X93nKDB0PuG7Z6bJmjw7pWgOl5x0OAAAAAGBaYuIJAAAAAEgUE08AAAAAQKKYeAIAAAAAEsXEEwAAAACQqONjVVtn5cuQ0ytJhawzr87oWrUwoberc6W+WNIri9Xrr/7vF2Rta7m/5u27SrVvNzPrz+rVViumX4MHxvVKZR3OqphzcnoFraGqszSgY7jaIWveyqTeOD8+62lZ+/ahy45uYKjNWY20OuH0oSO/Tq+yvGFsnqx1ZvUxcLDcXddYqk7fZKz2Y6/vDKNXyTXzj33vsc3I1fcatA3Vucps1lm9s6xXHUYKZZzX0rmOTvTrtyX9fQdl7cCY3m5iQF9/vSM87Ku9Qme1S/datlfvq1r0Vqd1ZHQ/DZ+kr3neWSuJ9yRojVxG99OBoj4KClG/f24b0veZ79TXyrKzKnubM862rD6/q2ulmX7s5aB7LeNcK8vOtTLvjH9GXt+ntzp81976rmtn9OzW9+msZDx2kl4ZvEMvctxQfOMJAAAAAEgUE08AAAAAQKKYeAIAAAAAEsXEEwAAAACQKCaeAAAAAIBEMfEEAAAAACTqiHEqIYQbzewqM9sTYzxn8rbrzOw3zWzv5P/2yRjj7VMZSMjpoURnGX1vSfCoVzBuuvGrL5S1rW/WSzS/9/yHZG1XuUfWHhlbVvP2vuy43KY7oxeW95bd3lGcKWteTMlAbkTW5jpRKxVnue7tJT0Wjxcls62sxzn8pmF9n7fUNZRj1qwebbbgRGt454TKkH69hpzokP687o2xSu1YBTN/6XJvGXgVteLFonj3lw/6PFIJumcOlrtkbUHbIWcsepyhUmecyjQ1XXvUVWf0WNcufR3avX6WrPVu19FF5S59/coV9FjG59Y+jjNOLErbFt1PWSe7paQv59a5S/fT2EJ6rRGO5x71zv2ZoI+PUtTvu9v36cbo6NTX31JV94YX+1KNun89ajs/ykwbL+tzRSmvH5sXx5bL6Gtlxzb9HnJfWUefTFSd1y6jX59ir370OpipsY7mG8+bzOzyGrd/PsZ43uSf1DUicAK5yehRIM1uMnoUSLObjB4FEnfEiWeM8W4zO9CEsQCoAz0KpBs9CqQbPQo0x1R+x/MjIYRHQwg3hhDq+/lGAEmiR4F0o0eBdKNHgQaqd+L5ZTM7xczOM7OdZna9+h9DCNeGEFaHEFaXzPkFBwCNRI8C6UaPAulGjwINVtfEM8a4O8ZYiTFWzexvzEyunBNjvCHGuDLGuDJv7fWOE8AxoEeBdKNHgXSjR4HGq2viGUJYcNg/32Jm6xozHACNQI8C6UaPAulGjwKNdzRxKl83s0vNbHYIYZuZfdrMLg0hnGdm0cw2mdmHpjoQLx6hXrkF82WtdPI8WTtwpl4OfWy+XqL5vCvXy9oH5v2drO2t6CWT80E/L1tLemn587s21bz9J4fOktvsy82QNS+G5eLup2VtsKqfy4W5g7L28Q1vk7V5XXr56b9dqhedK0W9pPWTJf0J5SFnefD/eta/ytp3bI6sNVKzerTZYrXOmAAnxqHoLEFedWJ6vKXevaXsPaVq7WXbvQgiT8aJYfHG6D22UnRiI5z7dIbiq/c1T7np2qNJ2P4afc2YsUlv17fJiTMY18dqblD/WGS5v/Z1oTCgIxfyo/rgz07ocYws0pFNnoNz9f5yS5fIWnnzVn2nGd339cbkpN107VE3WsM5v+e27JG1ng4dS1YvL/al7FybO0RES86cnnfiTbw4s6LzXtB7nj2hoM8/3jXdewxe1Eo1W19sTSMdceIZY3x3jZu/msBYANSBHgXSjR4F0o0eBZpjKqvaAgAAAABwREw8AQAAAACJYuIJAAAAAEgUE08AAAAAQKKYeAIAAAAAEnXEVW2bZeKKl8va3E9tlLXzerfJ2lmd98paQUQZmPlxBk+ML5K1sapeDv3poo52OVTWy8d7SzvvKfbI2vXPXlbz9jsv/Irc5g92XC5rmU691PX+io5heeuMIVkz06/Bh066W9aWt+llvr8/ukDWdpRmytq8/CFZW5bfK2u/0vOUrDUrTgVH79KZT8raE2MLZc1bKr3iLPXuxZh4vd1M3hiHKx2y5i317qzSj+mkztiN7Omnytr4GQVZq2zSsVfFfn09mRjQ4+zZqI/xskiNGF2qH1v+kH5bVerxPuuvL0ooO6Lvc+Ov6TiVk65z4lSmaWTKdOVFYnmyzjFX3rVb1jpyJ9U1lrITR+JdTyYquqdyYruq6XFUK/V951ao6HOMGoeZWdaca2W3Pv88NabnDf25MVnzOJf0puEbTwAAAABAoph4AgAAAAASxcQTAAAAAJAoJp4AAAAAgEQx8QQAAAAAJIqJJwAAAAAgUc2NUwlmIVd7l6/4zCq52et7Hpe1saiXV/ciU7xoDU+fs4TxREk/nXtKvXXtb0X7Lll7S+9aWbv7C6+oefurCr8jt3nmdX8na3eO62Ww95b1Y3vXs6+TtTVb9FLvFy17VtZe0rNd1rxomp6sXqY/H3RcxmhVH2MPFHSUDKYoNj5upBD1OcHTlxvX9+mcZ7zIlEysvZR9xlni3lsi3lsaf8zJN5mRm5C1gyXdT1UnRqaSr295/yRecySoztiNrW+aK2udv9DbVTr0Md7mJHeNnaSPq57tunbgDHFNdw7Tru362B88R4+/Y49+/zAxoJ/ntkHdh+ML9XUtnH+2rMVH9HsuoK9NXw/LznXBi0zJZZw4kjqix9yIGafkxaNVnevTSFm/T8xndP9WunUM412bdezUe1aslrVD5U5ZqzN5p6H4xhMAAAAAkCgmngAAAACARDHxBAAAAAAkioknAAAAACBRTDwBAAAAAIli4gkAAAAASFRT41RKc7ttx69eWHh3S2MAABNrSURBVLN2Xd9fy+3+4cBFsrak44CsLW3bJ2vndm6WNU9PRkdynN6rly7//uhiWbtr8AxZW5AflLV7xk6RtW9c9xc1b//A731MbvPK239L1oaW6c8oyt16ifjec/fL2h+c/8+y1hb08tODFR3xMNA+Kmv9WR2F4/Eie3oyelnx7Om1l8IOm+6taxyYun2lHllrz+j+HavqJc/bnSiekhNjoqJROjIluc2hil4mveKsEd+V1ZEpXizKrmp9MVDF/hSs2Y7UGj1bH4/dj+vzbczo46qiNzNr8+IY9PHvtK8Uqvp6GKp6/Bn9lFjnohFZKw/rHs0N6QcwfKqOApvxiB4L0mfruI4HnN+hc4a8GDnPrHb9XmrYiRXxrjXlOpO01HU0E3QfepFlXvSJF9EyXtaxat7+vHPaxDbdo11nFGXtYNTvkes5pzUa33gCAAAAABLFxBMAAAAAkCgmngAAAACARDHxBAAAAAAkioknAAAAACBRTDwBAAAAAIk6YpxKCGGJmd1iZvPNrGpmN8QY/yqEMGBm3zSzZWa2yczeEWM86N1XpmTWtbv2msnfHzpPbre8c6+sefEIPxx5iawt7tRD7cvqiIxT23fJ2tpCv6z9YO/ZsrawUy93vbvUJ2v7S92yNlatvaT1Vz//ObnN9bsvk7W3DKyRtXPbdGTKYFV/tvFEcb6sDVc7ZK0Q9bLVh5yolR7ndS1F3QrZqNf57s/oZcWHXjKr5u2V3Y1NMWpkj053XrxJvbJBHx/VOvaXd6KEvGXZPd4y9hl3/Hq7UXGOMTMr6/Z1RSeK4nh2IvZo5hwdE5bdpeOJvFiUvE7Lsqp3Wi3ryIJy57F//h6c+3PayaIb66LPFYVx/XxV5+hIjPZd+kkZm6P3p0Mcpq+092imQ59UvZgP73qyYUK/B/N053T2z2hZH6se71rTldPRIUXR+F6ciqcjq+PM1L7MzCrOe10V+WJmFvN6u+4tujYjq6MdJ6r6PXI13/qos6M545bN7GMxxjPN7CIz++0Qwllm9gkzuzPGeJqZ3Tn5bwDNR48C6UaPAulGjwJNcMSJZ4xxZ4xxzeTfh81svZktMrOrzezmyf/tZjN7c1KDBKDRo0C60aNAutGjQHMc08+YhBCWmdn5Zvagmc2LMe40e65hzWxuowcH4NjQo0C60aNAutGjQHKOeuIZQphhZrea2UdjjPqXEl+83bUhhNUhhNXlCecXNABMSSN6tGT6dzcATA09CqQbPQok66gmniGEvD3XiF+LMX578ubdIYQFk/UFZran1rYxxhtijCtjjCtz7XoxHAD1a1SP5s1Z2QNA3ehRIN3oUSB5R5x4hhCCmX3VzNbHGA9fEvW7ZnbN5N+vMbPbGj88AEdCjwLpRo8C6UaPAs1xNLkOl5jZr5rZYyGEtZO3fdLM/szM/jGE8EEz22Jmbz/SHWWLVevZWvtHELzloH+yTy/LPq9jWNbO69kqa0+O6WWkHxtfKGtrcifJWqezDHNfm1762FuaenZeP76T22t+8GZmZm1iCe1VBT3+D8+5S9a2lGfK2vdGV8jaE2P6uZyZ01Ekjw3p7cac5bonKvqQLpR1vE5fu359Xj6wWdaetAWytvfc2p/rlO+Tm9SrYT063XlLyzsrnrsqzjLw9cgHHY/gRbd4vDF6z4l3XlaRTWZm5a7pGYsyBSdcj46e0itrXtKBk2xlFSepwYthsao+jt0YFrVNv+7RTFlHGVhOP3AveSm3WUdpxOX6Ohr36gdX1Eltllug3x+Vd+pIueNcqns0Rn3seOdp733p3ftPc/a4W1baM/r496JDynVeKzPOfarYFC96zBtH2XkPmct40WN6jAUn3qTYp/c38KR+7bozet7gxre0Pk3lyBPPGOO9pt+Svb6xwwFwrOhRIN3oUSDd6FGgORr7UT0AAAAAAC/AxBMAAAAAkCgmngAAAACARDHxBAAAAAAkioknAAAAACBRdSwkPgUj45b56SM1S9+64xK52f+6+luy9tNBHbXy/V06PmOoqNden9M1Kmu9TrzJQF5v1+dEh3Q48QkHy92yNpHRSzRXxOJsuyb0Gur3VfXS2qWqXut9wql5S3kfKM6WtYWdh2RtuKyXlt80PCBr+w7NkLVCl26FeyunyNrl8x+Xtc49tV8DZyVyHM5ZPj4JHRl9rNbLizHxlntX2usco7e8esaJaMlldNRKwcm98KIhcGKo5upb0j87rmuVTmd/ed1Poah36CYUibts6y7KTdw4laI+H4wv1BeGWWt0Q826aL+sbditnzDnsm3VuTo+zaZvnMpxq1pnXNYvds+VtaVOnEq9EVxdOd03OacR27O6N7z3pop3zfOey6KzLxXrciSFPqe31w7Kmhe75r63SEGcCt94AgAAAAASxcQTAAAAAJAoJp4AAAAAgEQx8QQAAAAAJIqJJwAAAAAgUUw8AQAAAACJam6cimP5x++XtS89+ja93X95UtaumL9O1tYMnSRrW5xIjp+PL5S1fEYv0dyV18tIdziRI21ZvWy1t2Syik/ozupxdOcmZG2gXUfF9GQLsuYtW+3JOo/toUPLZG1el467ObV3n6yVnSW0X9n3jKzd+OzFeix//bOat2+K+rnEYYKz7nedUStDThRPV5vujXqVnFwRFd9SiDqOwVvG3tuXx1s+PussET9R1eN07tIX6ztfIH3GZ+mDoNqmj6vOvfo+D57lXPM6dC03rMdSadP7U9FXfTN05kulTUegZQp6HEvO0jEl8XYde7FzuEfWqm26n2K/PpfEPHlIxxMvLsu9ZmzTx6pnsNQlaxsO6Ji84REn3qdSX85HrIieyjjxSl70iTMM7y1Jvk3Hm/S36TjF0gznTjdskSXvPXLJuQBXUzDr4xtPAAAAAECimHgCAAAAABLFxBMAAAAAkCgmngAAAACARDHxBAAAAAAkioknAAAAACBRzV9YNyOW6a7qJZ/7vvaArO3/mt7VP731jbL2ik+ukrWrlv1c1s5o2y1redNLl3c4sSLdGb2ccsGJjfA+Nbh3fEnN2yvOVj85eKasDZb0Mti7x3plLe/EwXiqUT8n42Ud43BoXMdlZJ3ltQt36SXAn33iDFnru10fRzi+5FV2gvnRIV6skbeUvap5y6RXnLXeve083n16j81TZ7ILppHCbCcmwDkXd+7XPbOv1zkec06cyi59QFacaJf2g7Vrw2NOLFMCH+e3DevItZFBHW0Rqvo1iGP6ORldomM2ulbLEhIUnCyPes/T+ZH6Ikz68zoepKtNH6vFDj3lWNw/KGsTFb1dsVL7OK7vkZllnKiVrBOZuG9E98yCjiFZe3C+ExE1qqP3+rO61ulENDpvZZqGbzwBAAAAAIli4gkAAAAASBQTTwAAAABAoph4AgAAAAASxcQTAAAAAJCoI048QwhLQgj/GkJYH0J4PITwu5O3XxdC2B5CWDv558rkhwvghehRIN3oUSDd6FGgOY4mTqVsZh+LMa4JIfSY2cMhhB9N1j4fY/zLY9qjE5vSaN23Pihr627V262zk2UtvPxNsjY+X0eOtO+fkLXhpXq73mf0ksmZCR3/UP35elnTRurYxsxMLxWtF3WuX5tTm1P3vT5V95Yp0NgeTQsnSqheD++rHTNkZrZk8QFZG6voo67kZId4tRnZ2ueEeu+vEvXniBNVfarvytaXfeLtL2brfO0SeM1TYnr2qKPc7cQSjDsRYjO941Ff87IdupYp6f6t5pyxiJStwn59zW7rdoIcZhdk6ayZu2TtodMWyFqsOldZJ7bGi1op9uje1uEtx71092he52CMlvXxPVbVNSe1zvXNH7xK1sq9+j1++z7d289mdSyfk0omeZFe7uN2ak4qooWy3vBbQxfI2uKH65sTjVbbZa3oXO+dy3bTHHHiGWPcaWY7J/8+HEJYb2aLkh4YgKNDjwLpRo8C6UaPAs1xTHPfEMIyMzvfzJ7/KvEjIYRHQwg3hhBmNnhsAI4RPQqkGz0KpBs9CiTnqCeeIYQZZnarmX00xjhkZl82s1PM7Dx77lOi68V214YQVocQVpdM/7gpgKmhR4F0o0eBdKNHgWQd1cQzhJC35xrxazHGb5uZxRh3xxgrMcaqmf2NmV1Ya9sY4w0xxpUxxpV50z+TDKB+9CiQbvQokG70KJC8o1nVNpjZV81sfYzxc4fdfvhvu7/FzNY1fngAjoQeBdKNHgXSjR4FmuNoVrW9xMx+1cweCyGsnbztk2b27hDCeWYWzWyTmX0okRECOBJ6FEg3ehRIN3oUaIKjWdX2Xqu9wPDtjR9O+sVVj8laR5332fuz+rZzVnbGCYQePXpLegZ1La/jVLoyRVl7eedGWWtzujQv1mbvyzQ+cmrMWT++I+jIhe+NnClri/IHZa3rZB2x5Mo4a+A3MYqr0U7EHo3Lx3Rtsw7lKNd5Ic04x3FFp59YViec2ML7av+u3sZ3635ykgxs5l36wd2ROUPW+pyfTevqG5e18bEZsta9WffarO/pOLbjtwt9ae/RzIxuWcs6OR95J4uk1Fffu8jln7i/ru3QOFXnB1Yzps+Fpb7WR5alINEFAAAAADCdMfEEAAAAACSKiScAAAAAIFFMPAEAAAAAiWLiCQAAAABIFBNPAAAAAECijibHEwCaL+jIAov1LQn+4LpTZO2h9pP1hofyeij5OoONxMd+2RHn80AnFsWcOIlQ1ts5m1mmpGtFZ1n2OaudcXqO48gU/EfL368jOWJJxxN5kTpznOMjc66O/olP6LGE05fLWnXdL2revuJOuUndZv1tnRve0NBhmNn0jUw5npV37pK1p555uaxt2DlX1uasqvO7J+/a7Knzuo0X+28/fK+szVyqo85mr239a8A3ngAAAACARDHxBAAAAAAkioknAAAAACBRTDwBAAAAAIli4gkAAAAASBQTTwAAAABAokJs4vLGIYS9ZrZ58p+zzWxf03buYywvlpZxmE2/sSyNMc5pxGAajR49KmkZS1rGYTb9xkKPHjvG8mJpGYfZ9BsLPXrs0jKWtIzDjLHU0qhx1OzRpk48/8OOQ1gdY1zZkp2/AGNJ7zjMGEurpOmxMpb0jsOMsbRKmh4rY0nvOMwYS6uk6bGmZSxpGYcZY2nFOPhRWwAAAABAoph4AgAAAAAS1cqJ5w0t3PcLMZYXS8s4zBhLq6TpsTKWF0vLOMwYS6uk6bEylhdLyzjMGEurpOmxpmUsaRmHGWOpJdFxtOx3PAEAAAAAJwZ+1BYAAAAAkKiWTDxDCJeHEJ4MIWwIIXyiFWM4bCybQgiPhRDWhhBWN3nfN4YQ9oQQ1h1220AI4UchhKcn/zuzReO4LoSwffJ5WRtCuLIJ41gSQvjXEML6EMLjIYTfnby9Fc+JGkvTn5dWoEfT05/OWOhRepQepUdfOA56NCXS0qOt6s/JfdOjLx7HCd2jTf9R2xBC1syeMrM3mNk2M1tlZu+OMT7R1IH8+3g2mdnKGGPTs3NCCK82sxEzuyXGeM7kbZ81swMxxj+bPFHNjDF+vAXjuM7MRmKMf5nkvl8wjgVmtiDGuCaE0GNmD5vZm83sA9b850SN5R3W5Oel2ejRf9tvKvrTGct1Ro/So/QoPfofx0GPpkCaepT3ue5YrjN6tKk92opvPC80sw0xxo0xxqKZfcPMrm7BOFouxni3mR14wc1Xm9nNk3+/2Z47AFoxjqaLMe6MMa6Z/Puwma03s0XWmudEjeVEQI9aevrTGUvT0aOpQY8aPSrGQY+mAz1q9KgYxwndo62YeC4ys62H/XubtfZEFM3sjhDCwyGEa1s4jufNizHuNHvugDCzuS0cy0dCCI9O/nhCU34U4nkhhGVmdr6ZPWgtfk5eMBazFj4vTUKPamnqTzN6tNZYzOjRZqNHNXr0xWMxo0ebKU39aUaP/psTsUdbMfEMNW5r5dK6l8QYLzCzK8zstye/iofZl83sFDM7z8x2mtn1zdpxCGGGmd1qZh+NMQ41a79HOZaWPS9NRI8eH+jR2mOhR5uPHq2NHq09Fnq0uehPjR6tPZbEnpdWTDy3mdmSw/692Mx2tGAcZmYWY9wx+d89ZvYde+7HI1pp9+TPXD//s9d7WjGIGOPuGGMlxlg1s7+xJj0vIYS8PXfwfy3G+O3Jm1vynNQaS6uelyajR7VU9KcZParGQo82Hz1aGz1Kjx7275b1aMr604wePaF7tBUTz1VmdloI4eQQQpuZvcvMvtuCcVgIoXvyl2kthNBtZr9kZuv8rRL3XTO7ZvLv15jZba0YxPMH/6S3WBOelxBCMLOvmtn6GOPnDis1/TlRY2nF89IC9KiWiv40o0fpUXpUoEfp0TRIRY+msD/N6NETu0djjE3/Y2ZX2nOrfT1jZp9qxRgmx7HczH4++efxZo/FzL5uz32FXbLnPh37oJnNMrM7zezpyf8OtGgcf29mj5nZo/ZcMyxowjheZc/9KMqjZrZ28s+VLXpO1Fia/ry04g89mp7+dMZCj9Kj9Cg9+sJx0KMp+ZOGHm1lf07unx598ThO6B5tepwKAAAAAODE0ooftQUAAAAAnECYeAIAAAAAEsXEEwAAAACQKCaeAAAAAIBEMfEEAAAAACSKiScAAAAAIFFMPAEAAAAAiWLiCQAAAABI1P8H2kLTi8wZDhcAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 1152x288 with 4 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "plt.figure(figsize=(16, 4))\n",
    "plt.subplot(141)\n",
    "plt.imshow(train[0].reshape(28, 28))\n",
    "plt.subplot(142)\n",
    "plt.imshow(train[1].reshape(28, 28))\n",
    "plt.subplot(143)\n",
    "plt.imshow(train[3].reshape(28, 28))\n",
    "plt.subplot(144)\n",
    "plt.imshow(train[5].reshape(28, 28))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В библиотеке `scikit-learn` есть [модуль](https://scikit-learn.org/stable/modules/classes.html#module-sklearn.neighbors) с алгоритмами поиска ближайших соседей, помогающий решать задачи классификации и регрессии. В этом задании, однако, нас будет интересовать не классификация, а качество и скорость решения непосредственно задачи поиска. Определим для этого две метрики:\n",
    "* Recall: доля «настоящих соседей», которых нашёл алгоритм поиска. Пример: если вам необходимо найти 100 ближайших соседей, и из 100 возвращённых алгоритмом объектов 93 действительно находятся в множестве ближайших, то полнота равна 0.93.\n",
    "* Queries per second (QPS), также requests per second (RPS): число запросов, на которое алгоритм успевает ответить за одну секунду. Часто эту характеристику вычисляют как $num\\_queries/total\\_time$, где $num\\_queries$ — общее число запросов, а $total\\_time$ — суммарное время их выполнения; однако, так как некоторые реализации в задании умеют группировать запросы и выполнять несколько параллельно, мы будем осуществлять их по отдельности и усреднять величину $1/request\\_time$.\n",
    "\n",
    "Хотя в классе `NearestNeighbors` нет методов приближённого поиска ближайших соседей, мы воспользуемся им, чтобы найти 100 ближайших объектов по косинусной близости, сформировав таким образом правильные ответы для приближённых методов. Алгоритмы `kd_tree` и `ball_tree` в этом классе не поддерживают `metric=cosine`, поэтому распараллелим полный перебор: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.neighbors import NearestNeighbors\n",
    "\n",
    "sklearn_index = NearestNeighbors(n_neighbors=100,\n",
    "                                 algorithm='brute',\n",
    "                                 metric='cosine',\n",
    "                                 n_jobs=-1)\n",
    "sklearn_index.fit(train)\n",
    "\n",
    "true_neighbors_cosine = sklearn_index.kneighbors(test,\n",
    "                                                 n_neighbors=100,\n",
    "                                                 return_distance=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В ячейке ниже определяются гиперпараметры алгоритма LSH: размерность хэша (так как для каждой гиперплоскости мы храним только знак скалярного произведения, каждую координату можно представить одним битом) и число хэш-таблиц, а также создаётся массив гиперплоскостей для каждого бита в хэше и каждой таблицы."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(0xDEADF00D)\n",
    "\n",
    "NUM_TABLES = 20\n",
    "NUM_BITS = 8\n",
    "\n",
    "random_hyperplanes = np.random.randn(NUM_TABLES, NUM_BITS, train.shape[1]).astype(np.float32)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 1. (3 балла)**\n",
    "\n",
    "Реализуйте на Cython все методы класса `LSHIndex`, а затем постройте индекс по датасету FashionMNIST и подсчитайте recall вашего решения. Чтобы для удобства вместо косинусной близости считать скалярное произведение, и обучающую, и тестовую части датасета можно нормировать заранее.\n",
    "\n",
    "Здесь и в последующих заданиях на использование Cython при оценивании будут применяться следующие штрафы для неэффективного кода (компилируйте свой класс с `cython -a` для удобства проверяющих):\n",
    "* Использование функций из numpy (-10% от максимального балла). Вы можете отказаться от numpy-массивов как аргументов функций в предложенном шаблоне и перейти на использование memoryviews, если это окажется удобнее.\n",
    "* Взаимодействие с Python-объектами (коллекции, классы) в критических частях циклов (-20% от максимального балла)\n",
    "* Не указаны типы используемых переменных либо не продемонстрировано, что типизация не ускоряет код (до -20% от максимального балла)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython -a --cplus -c=-std=c++14\n",
    "# cython: embedsignature=True\n",
    "# cython: initializedcheck=False\n",
    "# cython: boundscheck=False\n",
    "# cython: wraparound=False\n",
    "# cython: nonecheck=False\n",
    "# cython: cdivision=True\n",
    "\n",
    "import numpy as np\n",
    "cimport numpy as cnp\n",
    "cimport scipy.linalg.cython_blas as blas\n",
    "cimport cython\n",
    "\n",
    "ctypedef vector[Py_ssize_t] s_vec\n",
    "\n",
    "cdef cnp.ndarray[cnp.uint32_t] compute_hashes(cnp.ndarray[cnp.float32_t, ndim=3] matrices,\n",
    "                                                    cnp.ndarray[cnp.float32_t] query):\n",
    "    \"\"\"\n",
    "    Compute hash values for each hash table and a given vector.\n",
    "    Args:\n",
    "        matrices: np.array of shape (NUM_TABLES, NUM_BITS, dim), last axis represents\n",
    "            random hyperplanes for each hash bit of each table\n",
    "        query: vector to be hashed\n",
    "    Returns:\n",
    "        hashes: np.array of shape (NUM_TABLES, ), contains hash values for each table as unsigned integers\n",
    "    \"\"\"\n",
    "    pass\n",
    "\n",
    "cdef class LSHIndex:\n",
    "    def __init__(self, cnp.ndarray[cnp.float32_t, ndim=2] vectors,\n",
    "                  cnp.ndarray[cnp.float32_t, ndim=3] projection_matrices):\n",
    "        \"\"\"\n",
    "        Build the index and store vectors for efficient neighbors search.\n",
    "        Args:\n",
    "            vectors: Training data, np.array (num_vectors, dim). Each k-NN query looks for neighbors in this set\n",
    "            projection_matrices: np.array of shape (NUM_TABLES, NUM_BITS, dim), last axis represents\n",
    "                random hyperplanes for each hash bit of each table\n",
    "        \"\"\"\n",
    "        pass\n",
    "        \n",
    "    cpdef query(self, cnp.ndarray[cnp.float32_t] query, unsigned k_neighbors):\n",
    "        \"\"\"\n",
    "        A helper function to perform a k-NN query. Computes hashes and allocates memory outside the cdef function\n",
    "            to avoid numpy calls in search_neighbors.\n",
    "        Args:\n",
    "            query: a normalized query vector the neighbors of which we need to find\n",
    "            k_neighbors: the number of neighbors to return\n",
    "        Returns:\n",
    "            neighbors: a list (or a C++ vector, they're interchangeable) of indices in the dataset\n",
    "                used to build the index. Vectors at these positions represent approximate k nearest neighbors of\n",
    "                the query, indices do not need to be sorted by any property\n",
    "        \"\"\"\n",
    "        cdef unsigned[:] hashes = compute_hashes(np.asarray(self.matrices), query)\n",
    "        return self._search_neighbors(query, k_neighbors, hashes)\n",
    "    \n",
    "    cdef s_vec _search_neighbors(self, float[::1] query, unsigned k_neighbors, unsigned[:] hashes) nogil:\n",
    "        \"\"\"\n",
    "        All the fun happens here. Given a sample, its hashes and the number  of neighbors, locate nearest neighbors\n",
    "            wrt cosine similarity using the hash tables built during index construction.\n",
    "        Args:\n",
    "            query: a normalized query vector the neighbors of which we need to find\n",
    "            k_neighbors: the number of neighbors to return\n",
    "            hashes: an array containing hash values of query for each hash table\n",
    "        Returns:\n",
    "            neighbors: a list (or a C++ vector, they're interchangeable) of indices in the dataset\n",
    "                used to build the index. Vectors at these positions represent approximate k nearest neighbors of\n",
    "                the query, indices do not need to be sorted by any property\n",
    "        \"\"\"\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ପ(⚈᷉ʙ⚈᷉)੭̸୫炎炎炎炎炎炎炎"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ниже приведена реализация функции для подсчёта всех интересующих нас метрик."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tqdm.auto import tqdm\n",
    "from time import perf_counter\n",
    "\n",
    "\n",
    "def compute_recall_qps(query_func: callable, testset: np.ndarray, true_neighbors: np.ndarray, **kwargs):\n",
    "    \"\"\"\n",
    "    Given a function that returns a list of nearest neighbors, estimate its recall and speed.\n",
    "    Args:\n",
    "        query_func: function with signature (query, k_neighbors, **kwargs).\n",
    "            Returns a list of k_neighbors approximate nearest neighbors for a query\n",
    "        testset: array with shape (num_objects, dim). Contains query vectors for recall evaluation\n",
    "        true_neighbors: array of indices with shape (num_objects, num_neighbors). Contains ground truth data for\n",
    "            recall evaluation. k_neighbors from query_func is inferred from its shape\n",
    "        **kwargs: passed to query_func\n",
    "    Returns:\n",
    "        avg_recall: average recall of query_func over the test set\n",
    "        qps: number of queries per second handled by query_func \n",
    "    \"\"\"\n",
    "    recalls = []\n",
    "    query_times = []\n",
    "\n",
    "    for sample, neighbors_for_sample in zip(testset, tqdm(true_neighbors)):\n",
    "        start = perf_counter()\n",
    "        approx_neighbors = query_func(\n",
    "            sample, k_neighbors=neighbors_for_sample.shape[0], **kwargs)\n",
    "        query_times.append(1 / (perf_counter() - start))\n",
    "        set_true = set(neighbors_for_sample.tolist())\n",
    "        hits = sum(1 for neighbor in approx_neighbors if neighbor in set_true)\n",
    "        recalls.append(hits / len(set_true))\n",
    "\n",
    "    return np.mean(recalls), np.mean(query_times)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# recall, qps = ...\n",
    "print(recall, qps)\n",
    "assert recall>=0.98"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Визуализируйте пример работы алгоритма: найдите 5 ближайших соседей для нескольких объектов тестовой выборки и покажите, каким изображениям они соответствуют (вместе с самим запросом)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#╰( ´・ω・)つ──☆✿✿✿✿✿✿"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 2. (1 балл)**\n",
    "\n",
    "Исследуйте и покажите на графиках зависимость recall и QPS от размера хэша и числа хэш-таблиц. Сравните вашу реализацию с классом sklearn.neighbors.NearestNeighbors: так как для косинусной близости в этом классе поддерживается только algorithm='brute', вы получите время работы точного поиска ближайших соседей. Для честности сравнения укажите в конструкторе метода n_jobs равным 1 и при замерах времени проводите поиск соседей для каждого объекта отдельно.\n",
    "\n",
    "Отметьте соответствующую ему точку на графике recall-QPS, а затем с помощью перебора гиперпараметров LSH постройте кривую в этих координатах для вашей реализации (нужно протестировать хотя бы 5 различных комбинаций размера хэша и числа таблиц). При построении можете вдохновляться графиками с сайта [ann-benchmarks](http://ann-benchmarks.com/):\n",
    "\n",
    "![](http://ann-benchmarks.com/fashion-mnist-784-euclidean_100_euclidean.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# (@・∀・)✎"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 3. (2 балла)**\n",
    "\n",
    "Как вы знаете из лекций, семейство хэш-функций, порождаемое случайными гиперплоскостями, подходит только для косинусного расстояния. Воспользуйтесь подходом, предложенным в статье с RecSys 2014 [«Speeding Up the Xbox Recommender System Using a Euclidean Transformation for Inner-Product Spaces»](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/XboxInnerProduct.pdf), и сведите задачу поиска ближайших соседей по евклидовой метрике к задаче поиска ближайших соседей по косинусной близости (важно заметить, что нормы векторов могут быть произвольными и поэтому метрики сами по себе не эквивалентны). \n",
    "\n",
    "Преобразуйте данные и проведите аналогичные эксперименты с реализацией из scikit-learn для metric='euclidean' и algorithm='ball_tree'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# (。・ω・)＝《《≠≠≠≠≠≠≠≠〇"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Часть 2. Navigable Small World"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 4. (3 балла)**\n",
    "\n",
    "Ниже расположен шаблон класса `NSWIndex`, который реализует алгоритм [Navigable Small World](https://publications.hse.ru/mirror/pubs/share/folder/x5p6h7thif/direct/128296059). Реализуйте все его методы, а затем постройте индекс по датасету FashionMNIST и подсчитайте recall вашего решения."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "%%cython --cplus -c=-std=c++14\n",
    "# cython: language_level=3\n",
    "# cython: embedsignature=True\n",
    "# cython: infer_types=True\n",
    "# cython: boundscheck=False\n",
    "# cython: wraparound=False\n",
    "# cython: nonecheck=False\n",
    "# cython: cdivision=True\n",
    "\n",
    "ctypedef vector[Py_ssize_t] s_vec\n",
    "\n",
    "\n",
    "cdef class NSWIndex:\n",
    "    def __init__(self, float[:,::1] vectors, unsigned num_neighbors, unsigned num_construction_runs):\n",
    "        \"\"\"\n",
    "        Build the index and store vectors for efficient neighbors search.\n",
    "        Args:\n",
    "            vectors: Training data, np.array (num_vectors, dim). Each k-NN query looks for neighbors in this set\n",
    "            num_neighbors: how many neighbors to look for during sequential insertion\n",
    "            num_construction_runs: number of search attempts in k-NN search during construction\n",
    "        \"\"\"\n",
    "        pass\n",
    "\n",
    "    cpdef s_vec query(self, float[::1] query, unsigned k_neighbors, unsigned num_search_runs):\n",
    "        \"\"\"\n",
    "        A helper function to perform a k-NN query. Used to ensure that _knn_search can be called with GIL lifted.\n",
    "        Args:\n",
    "            query: a normalized query vector the neighbors of which we need to find\n",
    "            k_neighbors: the number of neighbors to return\n",
    "            num_search_runs: number of search attempts (parameter m in the NSW paper)\n",
    "        Returns:\n",
    "            neighbors: a list of indices in the dataset used to build the index. Vectors at these positions\n",
    "            represent approximate k nearest neighbors of the query, indices do not need to be sorted\n",
    "        \"\"\"\n",
    "        return self._knn_search(sample,k_neighbors,num_search_runs)\n",
    "                \n",
    "    cdef s_vec _knn_search(self, float[::1] query, unsigned k_neighbors, unsigned num_search_runs) nogil:\n",
    "        \"\"\"\n",
    "        Run the NSW search algorithm in a constructed graph.\n",
    "        Args:\n",
    "            query: a normalized query vector the neighbors of which we need to find\n",
    "            k_neighbors: the number of neighbors to return\n",
    "            num_search_runs: number of search attempts (parameter m in the NSW paper)\n",
    "        Returns:\n",
    "            neighbors: a list of indices in the dataset used to build the index. Vectors at these positions\n",
    "            represent approximate k nearest neighbors of the query, indices do not need to be sorted\n",
    "        \"\"\"\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nsw_index = NSWIndex(train_normalized, 5, 5)\n",
    "recall, qps = compute_recall_qps(nsw_index.query, test_normalized, true_neighbors_cosine, num_search_runs=2)\n",
    "print(recall, qps)\n",
    "assert recall >= 0.98"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 5. (1 балл)**\n",
    "\n",
    "Исследуйте и покажите на графиках зависимость recall и QPS от размера хэша и числа хэш-таблиц. Сравните вашу реализацию с классом sklearn.neighbors.NearestNeighbors и LSHIndex, построив recall-QPS-кривые в зависимости от параметров `num_construction_runs` и `num_search_runs`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ੭•̀ω•́)੭̸*✩⁺˚"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 6. (1 балл)**\n",
    "\n",
    "Воспользуйтесь библиотекой nmslib, в которой есть эффективная реализация алгоритма HNSW. Постройте индекс для датасета и постройте аналогичную прошлым заданиям кривую recall-qps, варьируя параметры `efConstruction`, `M` и `efSearch`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nmslib\n",
    "# -_-)_／☆･ ･ ･ ‥……━━●~*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 7. (2 баллов)**\n",
    "\n",
    "Реализуйте параллельную версию поиска ближайших соседей методом NSW, пользуясь [cython.parallel](https://cython.readthedocs.io/en/latest/src/userguide/parallelism.html). Для этого можно заметить, что и отдельные запуски поиска для одного объекта, и поиск соседей для разных объектов можно реализовать как независимые процедуры.\n",
    "\n",
    "Оцените качество и скорость работы вашего метода на датасете [glove-100-angular](http://ann-benchmarks.com/glove-100-angular.hdf5), в обучающей выборке которого содержится 1183514 объектов, сравнив его с реализацией HNSW библиотеки nmslib. Для сравнения, как и обычно, используйте recall-QPS-кривую."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!wget -nc http://ann-benchmarks.com/glove-100-angular.hdf5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "with h5py.File('glove-100-angular.hdf5','r') as f:\n",
    "    print(f.keys())\n",
    "    glove_train=f['train'][()]\n",
    "    glove_test=f['test'][()]\n",
    "    glove_neighbors=f['neighbors'][()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# (❀∩´◔‿ゝ◔`⑅)⊃―☆　*’“*:.｡. .｡.:*･゜ﾟ･♡♪+*."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}