Tools vs Algorithm - A case study.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tool vs Algorithm - A case study\n",
    "\n",
    "> I stand tall on the shoulders of giants. I read biographies of people I respect, and I trust tools built by people much more into the problem-set to handle any dirty-work. This started when I programmed a TI-89 to do the quadratic equation over learning the rote a squared + b squared notation (ironically, writing the program foced me to understand the equation). Recently I came across an algorithm question posed as such:\n",
    "\n",
    "#### Request\n",
    "> You have a very large array of cordinates and want the top K closest. Write a fast method to do this.\n",
    "\n",
    "#### Response\n",
    "> My go-to was to import pandas and use it's built in `.sort()`. Done. Right? What's the BigO of this implementation? Probably close to nlog(n), but I couldn't be sure and didn't have access to the docs (it's [quicksort](https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.sort_values.html), timsort is python default). Some direction later I attempted to write a heap-sorted sub array implementation (denoted as `iterate_saver` below). Conclusion at the bottom."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd \n",
    "import heapq as hq\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "##\n",
    "# Use this method to generate N points on an X, Y coordinate plane.\n",
    "def generate_array(n):\n",
    "    return (np.random.rand(n, 2) * 100).astype(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAzwAAAHiCAYAAAAtXcmYAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3W+MnWWZP/Dv9B/YVrYMZYj13w6aX1+0QEqThqbbaFFr\n7MIaEmBqlja7vjBxKu66hoIQK3FRBM2y3WBHXcAtSJkWumox1hKNGjY1MJkiSWmEBCYooKVMGdvS\nImw5vxdMR1jGzsyZM3PO85zP5xXnTOf0Gu7nOWe+va/7vlsqlUolAAAAJTSl3gUAAABMFIEHAAAo\nLYEHAAAoLYEHAAAoLYEHAAAoLYEHAAAorVEFnieeeCIf+chHcvfddydJfv/73+cf//Efs2bNmnzy\nk59Mf39/kmTHjh259NJL09HRkfvuu2/iqgYAABiFEQPPsWPHcsMNN2Tp0qVDz23cuDGrV6/OXXfd\nlQ996EP57ne/m2PHjmXTpk3ZvHlz7rzzzmzevDmHDh2a0OIBAABOZsTAc8opp+S2225LW1vb0HPX\nX399Vq5cmSRpbW3NwMBAHn300Zx77rmZNWtWTjnllJx//vnZs2fPxFUOAAAwghEDz5QpUzJjxow3\nPXfqqaempaUlr732WrZs2ZKLLrooL7zwQlpbW4f+TGtraw4cOFD7igEAAEZpWrXf+Nprr+Wqq67K\n0qVLc8EFF+RHP/rRm75eqVRGfI3e3t5q/3oAAKCJLF68uKrvqzrwfOELX0h7e3s6OzuTJG1tbW+a\n0dm/f38WLVo04utUWzj119vba/wKzPgVl7ErNuNXXMau2IxfsY1noqSqbal37NiRGTNm5DOf+czQ\nc+edd1727t2bI0eO5KWXXsojjzziogIAAOpqxBmexx57LF/72tfy3HPPZdq0adm1a1cOHjyYGTNm\nZM2aNWlpacn73//+bNiwIZ///OfzyU9+MlOmTMmVV16Z2bNnT8bPAAAAMKwRA8+CBQty1113jerF\nVq5cObR7GwAAQL1V1dIGAABQBAIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIP\nAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQ\nWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIP\nAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQ\nWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIP\nAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQWgIPAABQ\nWqMKPE888UQ+8pGP5O67706S/OEPf8iaNWtyxRVX5HOf+1xeffXVJMmOHTty6aWXpqOjI/fdd9/E\nVQ0AADAKIwaeY8eO5YYbbsjSpUuHntu4cWPWrFmT733ve3nPe96T7du359ixY9m0aVM2b96cO++8\nM5s3b86hQ4cmtHgAAICTGTHwnHLKKbntttvS1tY29NzDDz+cFStWJElWrFiR3bt359FHH825556b\nWbNm5ZRTTsn555+fPXv2TFzlAAAAIxgx8EyZMiUzZsx403PHjh3L9OnTkyRnnHFGnn/++fT396e1\ntXXoz7S2tubAgQM1LhcAAGD0po33BSqVypie/796e3vHWwJ1ZPyKzfgVl7ErNuNXXMau2Ixfc6oq\n8MyaNSuvvPJKZsyYkf379+ess85KW1vbm2Z09u/fn0WLFo34WosXL66mBBpAb2/viOPX3z+Qzs6d\n6eubnfb2w+nqWpXW1jmTVCEnM5rxozEZu2IzfsX9bDB2xWb8im08YbWqbamXLl2aXbt2JUl27dqV\n5cuX59xzz83evXtz5MiRvPTSS3nkkUdcVKSzc2e2bVudnp6Ls23bJ/LpT++sd0kA1JnPBmAyjTjD\n89hjj+VrX/tannvuuUybNi27du3KN77xjVxzzTXZunVr5s2bl0suuSRTp07N5z//+Xzyk5/MlClT\ncuWVV2b27NmT8TPQwPr6ZidpGXzUMvgYgGbmswGYTCMGngULFuSuu+56y/N33HHHW55buXJlVq5c\nWZvKKIX29sPp6ank9Q+2Strbj9S7JADqzGcDMJnGvWkBnExX16ok3YN92kfS1fWxepfEBClqTz4U\nRaPfY8PVV6lk2Jp9NgCTSeBhQrW2zsnWrZ+odxlMghM9+UnL4L/cdht7qKFGv8eGqy/JsDX7bAAm\nk8AD1ISefJhYjX6P/eX6GrdmoDlUtUsbwP/V3n44yYnzt/TkQ601+j02XH2NXjPQHMzwADWhJx8m\nVqPfY3+5vsatGWgOAg9QE3ryYWI1+j32l+pr5JqB5qClDQCgifX3D6Sj454sWXJ/Ojq25ODBgXqX\nBDVlhgcAoIk1+g6AMF5meAAAmlij7wAI4yXwQI1pDQCgSOymR9lpaYMa0xoAQJE0+g6AMF4CD9SY\n1gAAiqTRdwCE8dLSBjWmNQAAoHGY4YEa0xoAANA4BB6oMa0BAACNQ0sbAABQWgIPAABQWgIPAABQ\nWgIPAABQWgIPMCb9/QPp6LgnS5bcn46OLTl4cKDeJQEA/EV2aQPGpLNzZ7ZtW52kJT09lSTddqUD\nABqWGR5gTPr6ZidpGXzUMvgYAKAxCTzAmLS3H05SGXxUSXv7kXqWAwBwUlragDHp6lqVpDt9fbPT\n3n4kXV0fq3dJAAB/kcADjElr6xxrdgCAwtDSBgAAlJbAAwAAlJbAAwAAlJbAAwANxgG/jJZrBUZm\n0wIAaDAO+GW0XCswMjM8ANBgHPDLaLlWYGQCDwDD0ipTPw74La7Jvm9cKzAyLW0ADEurTP044Le4\nJvu+ca3AyAQeAIalVaZ+HPBbXJN937hWYGRa2gAYllYZGDv3DTQeMzwADKtRWmX6+wfS2blzsI7D\n6epaldbWOXWpBUbSKPcN8GcCDwDDapRWGWuJKJJGuW+AP9PSBkBDs5YIgPEQeABoaNZEADAeWtoA\naGjWRAAwHgIPAA3NmggAxkNLGwAAUFoCDwAAUFoCDwAAUFoCD1AT/f0D6ei4J0uW3J+Oji05eHCg\n3iUxQYw1AEVi0wKgJhwO2TyMNQBFYoYHqAmHQzYPYw1AkQg8QE00wuGQWq0mRyOMNUymE+8ta9c+\n4b0FCkhLG1ATjXA4pFarydEIYw2T6Y3vLfv2eW+BohF4gJpohMMhtVpNjkYYa5hM3lug2LS0AaWh\n1QqYCN5boNjM8AClMZGtVv39A+ns3Dn42ofT1bUqra1zavb6MBLXYP2ceG/ZuzdZuDDaOKFgBB6g\nNCay1cr6IOrNNVg/J95bent7s3jx4nqXA4yRljaAUdDDT725BgGqI/AAjIIefurNNQhQnapb2o4e\nPZqrr746f/zjH/Pqq69m3bp1mTt3bq6//vpMmTIl8+fPz5e+9KVa1gpQN7Zipt5cgwDVqTrwfP/7\n38/ZZ5+dz33uczlw4EDWrl2btra2fPGLX8yCBQvy+c9/Pg8++GCWL19ey3oB6sJWzNSbaxCgOlW3\ntJ1++ul58cUXkyQDAwOZM2dOnnnmmSxYsCBJcuGFF2b37t21qRIAgFHr7x9IR8c9WbLk/nR0bMnB\ngwP1LgnqpuoZnlWrVuW///u/s3Llyhw6dChdXV3513/916Gvt7a25sCBAzUpEgCA0bOrH/xZ1YFn\nx44dmTdvXm677bY8/vjjWbduXU477bQxv05vb2+1JdAAjF+xGb/iMnbFZvyKqyhjt3dv8sZd/fbu\nLU7tE8n/g+ZUdeDZs2fP0Pqc+fPn5+WXX87x48eHvr5///60tbWN+Dr2sy8u5xEU04nDC18/QK/i\n8MICcu8Vm/ErriKN3cKFj2ffvkpeDz2VLFzod64ijR9vNZ6wWnXgee9735tf//rX+chHPpJnn302\ns2bNyrve9a6hi+mBBx7ImjVrqi4MmBhvbHN4/cNQmwNA2djVD/6s6sDT0dGRa6+9NmvWrMnx48fz\n5S9/OXPnzs2GDRtSqVRy3nnnZenSpbWsFagBhxcClJ9d/eDPqg48M2fOzL//+7+/5fm77757XAUB\nE6u9/fDgAtbX2xwcXghQXCfalF+fyTmsTRmGUXXgAYrpRJvD62t4os0BoMDsxgYjE3igyZxoc7B4\nE6D4tCnDyKo+eBQAgPpqbz+cpDL4SJsyDMcMDwBAQdmNDUYm8AAAFJTd2GBkWtoAAIDSEngAAIDS\nEngAAIDSEngAAIDSEngAgAnR3z+Qjo57smTJ/eno2JKDBwfqXRLQhOzSBgBMiM7Ondm2bXWSlvT0\nVJJ021EMmHRmeACACdHXNztJy+CjlsHHAJNL4AFgUmlzah7t7YeTVAYfVdLefqSe5VTtxDW7du0T\nrlkoIC1tAEwqbU7No6trVZLu9PXNTnv7kXR1fazeJVXljdfsvn2uWSgagQeASaXNqXm0ts4pRTBw\nzUKxaWkDYFKVpc2J5uGahWIzwwPApCpLmxPN48Q1u3dvsnBhXLNQMAIPAJOqLG1ONI8T12xvb28W\nL15c73KAMdLSBgAAlJbAAwAAlJbAAwAAlJbAAwAAlJbAAwAAlJbAAwAAlJbAAwAAlJbAA0y6/v6B\ndHTckyVL7k9Hx5YcPDhQ75KgsNxPACfn4FFg0nV27sy2bauTtKSnp5Kk20GUUCX3E8DJmeEBJl1f\n3+wkLYOPWgYfA9VwPwGcnMADTLr29sNJKoOPKmlvP1LPcqDQ3E8AJ6elDZh0XV2rknSnr2922tuP\npKvrY/UuCQrL/QRwcgIPMOlaW+dYYwA14n4CODktbQAAQGkJPAAAQGkJPAAAQGkJPAAAQGkJPAAA\nQGkJPAAAQGkJPAAAQGkJPABNrr9/IB0d92TJkvvT0bElBw8O1LskAKgZB48CNLnOzp3Ztm11kpb0\n9FSSdDvIEoDSMMMD0OT6+mYnaRl81DL4GADKQeABaCLDta+1tx9OUhn8E5W0tx+pZ4kAUFNa2gCa\nyHDta11dq5J0p69vdtrbj6Sr62N1rhIAakfgAWgiw7WvtbbOsWYHgNLS0gbQRLSvAdBszPAANBHt\nawA0G4EHoIloXwOg2WhpA2hyDh4FoMzM8AA0OQePAlBmZngAmpyDRwEoM4EHoMnZuQ2AMtPSBtDk\n7NwGQJkJPABNzs5tAJSZljYAAKC0BB4oENsHAzBZfOZQFuNqaduxY0duv/32TJs2LZ/97Gczf/78\nXHXVValUKjnzzDNz8803Z/r06bWqFZqe7YMBmCw+cyiLqmd4BgYG8s1vfjPd3d359re/nZ/97GfZ\nuHFj1qxZk+9973t5z3vek+3bt9eyVmh6tg8GYLL4zKEsqg48u3fvzrJly/K2t70tc+fOzZe//OU8\n/PDDWbFiRZJkxYoV2b17d80KBWwfDMDk8ZlDWVTd0vbss8/m2LFj+fSnP53Dhw9n3bp1efnll4da\n2M4444wcOHCgZoUCtg8GYPL4zKEsWiqVSmXkP/ZW3/nOd/LII4/km9/8Zp599tmsXbs2f/rTn4Zm\ndX7729/m6quvzj333PMXX6O3t7e6qgEAgKayePHiqr6v6hmeuXPnZtGiRZkyZUre/e53Z9asWZk2\nbVpeeeWVzJgxI/v3709bW9uIr1Nt4dRfb2+v8Ssw41dcxq7YjF9xGbtiM37FNp6JkqrX8CxbtiwP\nPfRQKpVKXnzxxRw9ejRLly7NT37ykyTJrl27snz58qoLAwAAGK+qZ3jOOuusfPSjH83ll1+elpaW\nbNiwIQsXLsz69euzbdu2zJs3L5dcckktawUAABiTcZ3Dc/nll+fyyy9/03N33HHHuAoCxqa/fyCd\nnTsHF5UeTlfXqrS2zql3WQClceJ9du/eZOHCx73PQsGMK/AA9edgOICJ9cb32X37vM9C0VS9hgdo\nDA6GA5hY3meh2AQeKDgHwwFMLO+zUGxa2qDgHAwHMLFOvM++voYn3mehYAQeKLjW1jl6yQEm0In3\nWee4QDFpaQMAAEpL4AEAAEpL4AEAAEpL4AEAAEpL4AEAAEpL4AEAAEpL4AEAAEpL4AEAAEpL4AEA\nAEpL4AEAAEpL4AEAKID+/oF0dNyTJUvuT0fHlhw8OFDvkqAQptW7AAAARtbZuTPbtq1O0pKenkqS\n7mzd+ol6lwUNzwwPAEAB9PXNTtIy+Khl8DEwEoEHRkEbAQD11t5+OEll8FEl7e1H6lkOFIaWNhgF\nbQQA1FtX16ok3enrm5329iPp6vpYvUuCQhB4YBS0EQBQb62tc/xjG1RBSxuMgjYCAJh8WsqpBTM8\nMAraCABg8mkppxYEHhgFbQQAMPm0lFMLWtoAAGhIWsqpBTM8AEAp9PcPpLNz52D78eF0da1Ka+uc\nepfFOGgppxYEHgCgFKz3KB8t5dSCljYAoBSs9wCGI/AAAKVQxPUetl2GiaelDQAohSKu99CGBxNP\n4AEASqGI6z204cHE09IGAFAnRWzDg6IxwwMAUCdFbMODohF4AADqpIhteFA0WtoAAIDSEngAAIDS\nEngAAIDSEngYsxOHpK1d+4RD0gAAaGg2LWDM3nhI2r59DkkDAKBxmeFhzBySBgBAUQg8jJlD0gAA\nKAotbYzZiUPS9u5NFi6MQ9KgQPr7B9LZuXPwkMPD6epaldbWOfUuCwAmjMDDmJ04JK23tzeLFy+u\ndznAGLxxDV5PjzV4AJSfljaAJmINHgDNRuABaCLW4AHQbLS0ATSRE2vwXl/Dc8QaPABKT+ABaCIn\n1uABQLPQ0gYAQN319w+ko+OeLFlyfzo6tuTgwYF6l0RJmOEBAKDu7CLJRDHDAwBA3dlFkoki8AAA\nb6G9iPEa6zVkF0kmipY2AOAttBcxXmO9huwiyUQReACAt9BexHiN9RqyiyQTRUsbAPAWjdJepLWu\nuBrlGoJxzfD86U9/ykUXXZR169blggsuyFVXXZVKpZIzzzwzN998c6ZPn16rOgGASdQo7UVa64qr\nUa4hGFfg2bRpU+bMmZMk2bhxY9asWZOVK1fmlltuyfbt27N69eqaFAkATK5GaS/SWldcjXINQdUt\nbU899VSeeuqpfOADH0ilUklPT09WrFiRJFmxYkV2795dsyIBgOakLQoYr6pneG666aZs2LAh3//+\n95Mkx44dG2phO+OMM3LgwIHaVAgANC1tUcB4VRV4fvCDH2TRokV55zvfOezXK5XKsM8Pp7e3t5oS\naBDGr9iMX3EZu2IzfmOzfv3/G/rvvr4n09dXv1qMXbEZv+ZUVeD55S9/mWeeeSY///nPs3///kyf\nPj0zZ87MK6+8khkzZmT//v1pa2sb1WstXry4mhJoAL29vcavwIxfcRm7YjN+xWXsis34Fdt4wmpV\ngeeWW24Z+u9bb70173rXu7Jnz5785Cc/yd/93d9l165dWb58edVFwWTo7x9IZ+fOwTaJw+nqWpXW\n1jn1LgsAgBqq2cGjn/3sZ7N+/fps27Yt8+bNyyWXXFKrl4YJYatTAIDyG3fg+cxnPjP033fcccd4\nXw4mja1OAQDKr+ptqaHobHUKAFB+NWtpg6Kx1SkAQPkJPDQtJ0ADAJSfljaAKvX3D6Sj454sWXJ/\nOjq25ODBgXqXVJWy/BwAMBwzPABVKstOf2X5OQBgOGZ4AKpUlp3+yvJzAMBwBB6AKpVlp78i/hza\n8AAYLS1tAFUqy05/Rfw5tOEBMFoCD0CVyrLTXxF/Dm14AIyWljYACqeIbXgA1IcZHgAKp4hteADU\nh8ADQOEUsQ0PgPrQ0gYAAJSWwAMAUAC2Y4fqaGkDACgA27FDdczwAAAUgO3YoToCDwBAAdiOHaqj\npQ0AoABsxw7VEXgAAArAduxQHS1tMAp2xgEAKCYzPDAKdsYBACgmMzwwCnbGAQAoJoEHRsHOOAAA\nxaSlDUbBzjgAAMUk8MAo2BkHAKCYtLQBQJOw4yTQjMzwAECTsOMk0IzM8ABAk7DjJNCMBB4AaBJ2\nnASakZY2AMatv38gnZ07B3cyPJyurlVpbZ1T77L4P+w4CTQjgQeAcbM2pBjsOAk0Iy1tAIybtSEA\nNCqBB4BxszaE8bJlNjBRtLQBMG7WhjBe2iKBiSLwADBu1oYwXtoigYmipQ0AqDttkcBEMcMDANSd\ntkhgogg8AEDdaYsEJoqWNpqC3X8AAJqTGR6agt1/AACakxkemoLdfwAAmpPAQ1Ow+w8AQHPS0kZT\nsPsPAEBzEnhoCnb/AQBoTlraAACA0hJ4AACA0hJ4AACA0hJ4AACA0hJ4AACA0hJ4AACA0hJ4AACA\n0hJ4AACA0hJ4AACA0hJ4AACA0hJ4AOqov38gHR33ZMmS+9PRsSUHDw7UuyQAKJVp4/nmm2++OXv2\n7Mnx48fzqU99Kuecc06uuuqqVCqVnHnmmbn55pszffr0WtUKUDqdnTuzbdvqJC3p6akk6c7WrZ+o\nd1kAUBpVB56HHnooTz75ZLq7uzMwMJBLLrkkF1xwQa644op89KMfzS233JLt27dn9erVtawXoFT6\n+mYnaRl81DL4GAColapb2pYsWZKNGzcmSU477bQcPXo0PT09ufDCC5MkK1asyO7du2tTJVAzJ1qo\n1q59QgtVA2hvP5ykMviokvb2I/UsBwBKp+oZnpaWlpx66qlJkvvuuy8f/OAH8z//8z9DLWxnnHFG\nDhw4UJsqgZp5YwvVvn1aqOqtq2tVku709c1Oe/uRdHV9rN4lAUCpjGsNT5L89Kc/zfbt23P77bdn\n5cqVQ89XKpWTfNef9fb2jrcE6sj4Fc/evckbW6j27jWO9bZ+/f8b+u++vifT1zfy9xizYjN+xWXs\nis34NadxBZ4HH3ww3/nOd3L77bdn9uzZmTVrVl555ZXMmDEj+/fvT1tb24ivsXjx4vGUQB319vYa\nvwJauPDxwZmdliSVLFzoPiwa916xlXX8+vsH0tm5c3C28nC6ulaltXVOvcuqqbKOXbMwfsU2nrBa\ndeA5cuRIvv71r+e//uu/8va3vz1JsnTp0uzatSsXX3xxdu3aleXLl1ddGDAxTrRQ7d2bLFwYLVRA\nTdhxEGhUVQeeH//4xxkYGMg///M/p1KppKWlJTfddFOuu+66bN26NfPmzcsll1xSy1qBGmhtnZOt\nWz/hX7qAmrLjINCoqg48l19+eS6//PK3PH/HHXeMqyAAoHja2w8Pzuy83i5rx0GgUYx70wKAidQM\n6wKgDOw4CDQqgQdoaNYFQDGcaJcFaDRVHzwKMBmsCwAAxkPgARpae/vhJCfO9bIuAAAYGy1tQEOz\nLgAAGA+BB2ho1gUAAOOhpQ2AYfX3D6Sj454sWXJ/Ojq25ODBgXqXBABjZoYHgGHZIQ+AMjDDA8Cw\n7JAHQBkIPAAMyw55AJSBljYAhmWHPADKQOABYFh2yAOgDLS0AQAApSXwAAAApSXwAAAApSXwAAAA\npSXwAFBq/f0D6ei4J0uW3J+Oji05eHCg3iVBYbmfKCK7tAFQap2dO7Nt2+okLenpqSTptvscVMn9\nRBGZ4QGg1Pr6ZidpGXzUMvgYqIb7iSISeAAotfb2w0kqg48qaW8/Us9yoDCGa19zP1FEWtoAKLWu\nrlVJutPXNzvt7UfS1fWxepcEhTBc+5r7iSISeAAotdbWOdYYQBWGa19zP1FEWtoAAHgL7WuUhRke\nAADeQvsaZSHwAADwFtrXKAstbQAAQGkJPAAAQGkJPAAAQGkJPAAAJ3HiAM61a58YOoATKA6bFgAA\nnMQbD+Dct+/1Azgt5ofiMMMDAHASwx3ACRSHwAMAcBIO4IRi09IGQEPr7x9IZ+fOwcMPD6era1Va\nW+fUuyyayIkDOPfuTRYujAM4oWAEHgAa2hvXT/T0WD/B5DtxAGdvb28WL15c73KAMdLSBkBDs34C\ngPEQeABoaNZPADAeWtoAaGgn1k+8vobniPUTAIyJwANAQzuxfgIAqqGlDQAAKC2BBwAAKC2BBwAA\nKC2BBxpQf/9AOjruyZIl96ejY0sOHhyod0mMgfEDgMZh0wJoQA5aLDbjBwCNwwwPNCAHLRab8QOA\nxiHwQANy0GKxGT8AaBxa2qABOWix2IwfADQOgQcakIMWi834AUDj0NIGAACUlsADAACUlsADAACU\nlsADAACUlsADAFAj/f0D6ei4J0uW3J+Oji05eHCg3iVB07NLGwBAjXR27sy2bauTtKSnp5Kk266N\nUGdmeAAAaqSvb3aSlsFHLYOPgXoSeAAAaqS9/XCSyuCjStrbj9SzHCAT0NJ244035tFHH01LS0uu\nvfbanHPOObX+KwAAGlJX16ok3enrm5329iPp6vpYvUuCplfTwNPT05Onn3463d3defLJJ3Pdddel\nu7u7ln8FAEDDam2dY80ONJiatrT96le/yoc//OEkyfve974cOnQoL730Ui3/CgAACsCOdTSKms7w\nvPDCC1m4cOHQ49NPPz0vvPBCZs2aVcu/BgCABmfHOhrFhG5LXalURvwzvb29E1kCE8z4FZvxKy5j\nV2zGr7iM3ejt3Zu8cce6vXvr//+v3n8/9VHTwNPW1pYXXnhh6PHzzz+fM88886Tfs3jx4lqWwCTq\n7e01fgVm/IrL2BWb8SsuYzc2Cxc+nn37Knk99FSycGF9f+8zfsU2nrBa08CzbNmy3Hrrrbn88svz\n2GOP5ayzzsrMmTNr+VcAAFAAdqyjUdQ08CxatCgLFizI6tWrM3Xq1GzYsKGWLw8AQEHYsY5GUfM1\nPP/yL/9S65cEAACoSk23pQYAAGgkAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBa\nAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8A\nAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBa\nAg8AAFAasDLxAAAJ6klEQVRaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8A\nAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBa\nAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8AAFBaAg8A\nAFBaAg8AAFBaAg8AAFBa06r5puPHj+e6667Lb3/727z22mtZv359zj///PzmN7/J9ddfnylTpmT+\n/Pn50pe+VOt6AQAARq2qGZ4f/vCHmTlzZrZs2ZIbbrghN954Y5Lkq1/9ar74xS9my5YtOXToUB58\n8MGaFgsAADAWVQWej3/847nmmmuSJK2trfnjH/+YV199Nc8880wWLFiQJLnwwguze/fu2lUKAAAw\nRlW1tE2dOjVTp05NkmzevDkXX3xxXnzxxcyZM2foz7S2tubAgQO1qRIAAKAKIwaee++9N/fdd19a\nWlpSqVTS0tKSK6+8MsuWLcvdd9+dffv25Vvf+lb6+/urKqC3t7eq76MxGL9iM37FZeyKzfgVl7Er\nNuPXnEYMPJdddlkuu+yytzx/77335he/+EU2bdqUqVOnprW1NS+++OLQ1/fv35+2traTvvbixYur\nKBkAAGB0qlrD87vf/S5bt27NrbfemunTpydJpk2blrPPPjt79uxJkjzwwANZvnx57SoFAAAYo5ZK\npVIZ6zfdcsst+fGPf5x3vOMdQ21ud9xxR55++uls2LAhlUol5513Xq6++uqJqBkAAGBUqgo8AAAA\nRVBVSxsAAEARCDwAAEBpCTwAAEBpVXXw6HgcP3481113XX7729/mtddey/r163P++efnN7/5Ta6/\n/vpMmTIl8+fPz5e+9KXJLo1RuvHGG/Poo4+mpaUl1157bc4555x6l8QIbr755uzZsyfHjx/Ppz71\nqZxzzjm56qqrUqlUcuaZZ+bmm28e2nGRxvSnP/0pF110UdatW5cLLrjA+BXIjh07cvvtt2fatGn5\n7Gc/m/nz5xu/Ajh69Giuvvrq/PGPf8yrr76adevWZe7cuX5XaXBPPPFE1q1bl3/4h3/I3//93+cP\nf/jDsPfbjh07cuedd2bq1Km57LLLcumll9a7dPLW8fv973+fa6+9Nv/7v/+b6dOn5+tf/3rOOOOM\nMY/fpM/w/PCHP8zMmTOzZcuW3HDDDbnxxhuTJF/96lfzxS9+MVu2bMmhQ4fy4IMPTnZpjEJPT0+e\nfvrpdHd354YbbshXvvKVepfECB566KE8+eST6e7uzn/+53/mq1/9ajZu3Jgrrrgi3/ve9/Ke97wn\n27dvr3eZjGDTpk2ZM2dOkmTjxo1Zs2aN8SuAgYGBfPOb30x3d3e+/e1v52c/+5nxK4jvf//7Ofvs\ns3PnnXfmP/7jP/KVr3wlN954o99VGtixY8dyww03ZOnSpUPPDXe/HTt2LJs2bcrmzZtz5513ZvPm\nzTl06FAdKyf5y+O3evXq3HXXXfnQhz6U7373u1WN36QHno9//OO55pprkiStra1D/3LyzDPPZMGC\nBUmSCy+8MLt3757s0hiFX/3qV/nwhz+cJHnf+96XQ4cO5aWXXqpzVZzMkiVLsnHjxiTJaaedlqNH\nj6anpycXXnhhkmTFihXutwb31FNP5amnnsoHPvCBVCqV9PT0ZMWKFUmMX6PbvXt3li1blre97W2Z\nO3duvvzlL+fhhx82fgVw+umnDx2oPjAwkDlz5vhdpcGdcsopue2229508P1w99ujjz6ac889N7Nm\nzcopp5yS888/f+gcSepnuPG7/vrrs3LlyiSv54aBgYGqxm/SA8/UqVMzY8aMJMnmzZtz8cUX58UX\nXxz6l8vk9R/owIEDk10ao/DCCy+ktbV16PHpp5+eF154oY4VMZKWlpaceuqpSZL77rsvH/zgB3Ps\n2LGhFpozzjjD/dbgbrrppqF/KEpi/Ark2WefzbFjx/LpT386V1xxRX71q1/l5ZdfNn4FsGrVqjz3\n3HNZuXJl1qxZk/Xr1+ev/uqvhr7ud5XGM2XKlKHfMU/4v++Xzz//fPr7+9/0u4yxbAzDjd+pp56a\nlpaWvPbaa9myZUsuuuiit/wuOprxm9A1PPfee2/uu+++tLS0DB1QeuWVV2bZsmW5++67s2/fvnzr\nW99Kf3//RJbBBHKMU3H89Kc/zfbt23P77bcP/WtJYgwb3Q9+8IMsWrQo73znO4f9uvFrbJVKZait\n7dlnn83atWvfNGbGr3Ht2LEj8+bNy2233ZbHH38869aty2mnnVbvshiHv3S/uQ8b22uvvZarrroq\nS5cuzQUXXJAf/ehHb/r6aMZvQgPPZZddlssuu+wtz9977735xS9+kU2bNmXq1KlpbW0dmjZOkv37\n979pOovG0dbW9qYZneeffz5nnnlmHStiNB588MF85zvfye23357Zs2dn1qxZeeWVVzJjxgz3W4P7\n5S9/mWeeeSY///nPs3///kyfPj0zZ840fgUxd+7cLFq0KFOmTMm73/3uzJo1K9OmTTN+BbBnz54s\nX748STJ//vy8/PLLOX78+NDXjV0x/N/Pu7POOittbW1vmhHYv39/Fi1aVMcqOZkvfOELaW9vT2dn\nZ5JUNX6T3tL2u9/9Llu3bs2tt946NMU4bdq0nH322UP9dw888MDQmwyNZdmyZdm1a1eS5LHHHstZ\nZ52VmTNn1rkqTubIkSP5+te/nm9961t5+9vfniRZunTp0Dju2rXL/dbAbrnlltx7773ZunVrLr30\n0qxbty5Lly7NT37ykyTGr9EtW7YsDz30UCqVSl588cUcPXrU+BXEe9/73vz6179O8npr4qxZs3L2\n2Went7c3id9VimK4z7tzzz03e/fuzZEjR/LSSy/lkUceyeLFi+tcKcPZsWNHZsyYkc985jNDz513\n3nljHr+WyiTP491yyy358Y9/nHe84x1DbW533HFHnn766WzYsCGVSiXnnXderr766sksizH4t3/7\ntzz88MOZOnVqNmzYkPnz59e7JE5i27ZtufXWW/PXf/3XQ/fcTTfdlOuuuy6vvPJK5s2blxtvvDFT\np06td6mM4NZbb8273vWu/M3f/E3Wr19v/Api27Ztuffee9PS0pLOzs4sXLjQ+BXA0aNHc+2116a/\nvz/Hjx/PP/3TP2Xu3Ll+V2lgjz32WL72ta/lueeey7Rp03LWWWflG9/4Rq655pq33G8PPPBAbrvt\ntkyZMiVr1qzJ3/7t39a7/KY33PgdPHgwM2bMyKxZs9LS0pL3v//92bBhw5jHb9IDDwAAwGSZ9JY2\nAACAySLwAAAApSXwAAAApSXwAAAApSXwAAAApSXwAAAApSXwAAAApfX/Ad6sD0s7chmnAAAAAElF\nTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7feb0c848f90>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "##\n",
    "# Show example of a generated array\n",
    "plt.scatter(*zip(*generate_array(70)))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "## This is the an implementation where we keep a heap-stack array and only loop over `arry` once.\n",
    "# - we keep N for looping over the array \n",
    "# - then keep a max-heap of k-length\n",
    "\n",
    "def iterate_saver(arry, k):\n",
    "    k_arry = []\n",
    "    for x in arry:\n",
    "        dist = -1.0 * (x[0]**2 + x[1]**2) # -1 * for max-heap\n",
    "        if(len(k_arry) < k):\n",
    "            hq.heappush(k_arry, dist)\n",
    "        else:\n",
    "            if(dist > k_arry[0]):\n",
    "                hq.heapreplace(k_arry, dist)\n",
    "    return (-1 * np.array(k_arry)) ** (0.5) # -1 * to min-heap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "## This is using the tools... pandas\n",
    "# just do what 'comes to mind'\n",
    "# - with pandas do the math\n",
    "# - sort\n",
    "# - take 0-k\n",
    "\n",
    "def pandas_df(arry, k, sort_kind='quicksort'):\n",
    "    frame = pd.DataFrame(arry)\n",
    "    return np.sort(((frame[0] ** 2 + frame[1] ** 2)), kind=sort_kind)[0:k] ** (0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iterate Saver\n",
      "[ 11.18033989   6.           8.06225775]\n",
      "Pandas\n",
      "[  6.           8.06225775  11.18033989]\n",
      "Note that iterate-saver is not ordered, which was not technically a requirement if we just wanted smallest k\n"
     ]
    }
   ],
   "source": [
    "## Test\n",
    "# - confirming they are both returning the same thing on a smaller sample\n",
    "\n",
    "arry = generate_array(100)\n",
    "k = 3\n",
    "\n",
    "print('Iterate Saver')\n",
    "print(iterate_saver(arry, k))\n",
    "print('Pandas')\n",
    "print(pandas_df(arry, k))\n",
    "print(\"Note that iterate-saver is not ordered, which was not technically a requirement if we just wanted smallest k\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Setup of Timing\n",
    "\n",
    "# don't have %%timeit in this env.. so using poor-mans\n",
    "import time\n",
    " \n",
    "loops = 10 # 10x for sanity\n",
    "N = 10000000 # 10 Million points\n",
    "k = 5\n",
    "data_saver = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "78.967302084\n"
     ]
    }
   ],
   "source": [
    "##\n",
    "# Test of iterate_saver which is 'algorithmically' preferred\n",
    "start = time.time()\n",
    "\n",
    "for x in range(loops):\n",
    "    iterate_saver(generate_array(N), k)\n",
    "\n",
    "data_saver['iterate_saver'] = time.time() - start\n",
    "print(data_saver['iterate_saver'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10.7560799122\n"
     ]
    }
   ],
   "source": [
    "##\n",
    "# Test of pandas_df which is 'read-ability/tool' preferred\n",
    "start = time.time()\n",
    "\n",
    "for x in range(loops):\n",
    "    pandas_df(generate_array(N), k, sort_kind='quicksort')\n",
    "\n",
    "data_saver['pd_quicksort'] = time.time() - start\n",
    "print(data_saver['pd_quicksort'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "23.4478480816\n"
     ]
    }
   ],
   "source": [
    "##\n",
    "# Test of pandas_df which is 'read-ability/tool' preferred, with default sort modified to be heapsort\n",
    "start = time.time()\n",
    "\n",
    "for x in range(loops):\n",
    "    pandas_df(generate_array(N), k, sort_kind='heapsort')\n",
    "\n",
    "data_saver['pd_heapsort'] = time.time() - start\n",
    "print(data_saver['pd_heapsort'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Outcomes\n",
      "                       0\n",
      "pd_quicksort   10.756080\n",
      "pd_heapsort    23.447848\n",
      "iterate_saver  78.967302\n"
     ]
    }
   ],
   "source": [
    "print(\"Outcomes\")\n",
    "print(pd.DataFrame.from_dict(data_saver, orient=\"index\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conclusion\n",
    "\n",
    "> Pretty cut and dry. Not only is pandas 8x faster (!), it is significantly cleaner, it easier to read and took me significantly less time to write than the heap-sort native implementation. I will note it is important to have some understanding of the choices being made here. IE, while quicksort is a great default for the pandas implementation there are orderings of `generate_array` that would be faster with mergesort. At the same time, that requires an understanding of the state of the given array which would require inspection or assumption. \n",
    "\n",
    "> Thanks for reading! "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}