tadeu/Test KDTree Performance.ipynb

## Test KDTree Performance.ipynb
{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from scipy.spatial import KDTree\n",
    "import numpy as np\n",
    "import numpy.random as npr\n",
    "\n",
    "ns = [100, 1000, 10000, 100000, 1000000]\n",
    "datas = [None] * len(ns)\n",
    "trees = [None] * len(ns)\n",
    "\n",
    "datas[0] = npr.rand(ns[0], 2)\n",
    "trees[0] = KDTree(datas[0])\n",
    "\n",
    "\n",
    "for i in xrange(1, len(ns)):\n",
    "    datas[i] = np.vstack((datas[i-1], npr.rand(ns[i] - ns[i-1], 2)))\n",
    "    trees[i] = KDTree(datas[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "p = npr.rand(1000, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 109 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "trees[0].query(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 138 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "trees[1].query(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 loops, best of 3: 169 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "trees[2].query(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loops, best of 3: 192 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "trees[3].query(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loops, best of 3: 222 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "trees[4].query(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEFCAYAAADgylzDAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XucVXW9//HXJ295q9EsCeGc0aPc1ONUgBceHMYbCT8N\nHuUlO6RDqRknzUsRqI+wkyCYF0wfXkhxMIXCTEJ/ogI6CmGAyiAwEKBOORjkDZMUuX3OH9+N7MaZ\nPXv2rL3X2nu/n48HD/Za+8LXj5sPa97ru77L3B0RESl9n4p7ACIiUhhq+CIiZUINX0SkTKjhi4iU\nCTV8EZEyoYYvIlImMjZ8M+tqZs+Y2QozW25mlzZ7/koz22FmB6btG21ma8xslZkNzNfARUSkfXZv\n4/mtwOXuXm9m+wEvmtlsd19pZl2BU4G/7HyxmfUCzgF6AYcAc8ysm7vvyNP4RUQkSxmP8N19vbvX\npx5vAlYCnVNP3wyMbPaWIcA0d9/q7o3AWqBvpCMWEZGcZJ3hm1kl8CVgoZkNAZrc/eVmL+sMNKVt\nNxGO9EVEJGZtRToApOKc3wE/BHYAVxHinI9fkuHtWrtBRCQB2mz4ZrYH8DDwgLvPMLOjgUpgqZkB\ndCFk+8cC64CuaW/vktrX/DP1j4CISA7cPdMBdkZtzdIx4F6gwd0npv6wZe5+sLsf6u6HEmKbL7v7\nBmAm8E0z29PMDgWOABa1Mui8/hozZkze39vW6zI939pzzfe39LpsXpOUerbnfVHXM5faJbmWhapn\ne/aXSz0L8Xc9m/p1VFtH+P2AYcDLZrYkte8qd5+V3rvTmniDmU0HGoBtwAiPYpQ5qK6uzvt723pd\npudbe675/pZe13xfY2NjxnFEIdd6tud9Udczm33FVMv2vjfXerZnf7nUsxB/11va15H/tpZYHP3Y\nzOL6d6Ak1dTUUFtbG/cwSoJqGS3VM1pmhucr0pHiUFNTE/cQSoZqGS3VM1l0hC8iUiR0hC/U1dXF\nPYSSoVpGS/VMFjV8EZEyoUhHRKRIKNIREZGsqOGXAOWk0VEto6V6JosavohImVCGLyJSJJThi4hI\nVtTwS4By0uioltFSPZNFDV9EpEwowxcRKRLK8EVEJCtq+CVAOWl0VMtoqZ7JooYvIlImlOGLiBQJ\nZfgiIpIVNfwSoJw0OqpltFTPZFHDFxEpE8rwRUSKhDJ8ERHJihp+CVBOGh3VMlqqZ7JkbPhm1tXM\nnjGzFWa23MwuTe3/hZmtNLOlZvZ7M/ts2ntGm9kaM1tlZgPz/R8gIlIOzj+/45+RMcM3s05AJ3ev\nN7P9gBeBoUAXYK677zCz8QDuPsrMegFTgT7AIcAcoJu772j2ucrwRUSy8MEHcNNN8L//C9u25THD\nd/f17l6ferwJWAl0dvfZaU18IeEfAIAhwDR33+rujcBaoG+ugxMRKVfuMG0a9OwJy5ZBv34d/8ys\nM3wzqwS+RGjw6b4DPJ563BloSnuuiXCkL3mknDQ6qmW0VM/cLFoUGvyNN8IDD8D06TBjRsc/N6uG\nn4pzfgf8MHWkv3P/1cAWd5+a4e3KbkREsrBuHZx3HgwdChdeCIsXQ//+4bmKio5//u5tvcDM9gAe\nBh5w9xlp+2uAwcDJ6eMFuqZtd0nt+4SamhoqKysBqKiooKqqiurqamDXUYG2s9veuS8p4ynm7erq\n6kSNp9i3Vc/stjdvhsWLq5k4EQYNquOee2Dw4FC72tpagI/7ZUe0ddLWgCnA2+5+edr+04CbgAHu\n/lba/p0nbfuy66Tt4c3P0OqkrYhIyOl/8xsYNQqOPRYmTIBDD2399fm+8KofMAw40cyWpH4NAm4D\n9gNmp/bdEQbvDcB0oAGYBYxQZ8+/nUcM0nGqZbRUz9a1lNNnavZRyBjpuPt8Wv5H4YgM7xkHjOvg\nuEREStK6dTB6NMyZA2PHhvn1nyrQJbBaS0dEpAB2zqefOBEuvjjEOPvv377P6Gik0+ZJWxERyV3z\nnP6FF/If3bRGa+mUAOWk0VEto1Xu9Ywjp89EDV9EJGKZ5tPHSRm+iEhEosjpM1GGLyISsyTl9Jko\n0ikB5Z6TRkm1jFY51DNpOX0mavgiIjlIak6fiTJ8EZF2yHdOn4kyfBGRAiiWnD4TRToloBxy0kJR\nLaNVKvUsppw+EzV8EZFWFGNOn4kyfBGRZuLM6TNRhi8iEpFSyOkzUaRTAkolJ00C1TJaxVTPUsnp\nM1HDF5GyVmo5fSbK8EWkLCU1p89EGb6ISDuUek6fiSKdElBMOWnSqZbRSlo9yyGnz0QNX0RKXjnl\n9JkowxeRklWMOX0myvBFRJop55w+E0U6JSBpOWkxUy2jFUc9yz2nzyRjwzezrmb2jJmtMLPlZnZp\nav+BZjbbzFab2VNmVpH2ntFmtsbMVpnZwHz/B4iIgHL6bGTM8M2sE9DJ3evNbD/gRWAoMBx4y91v\nMLOfAAe4+ygz6wVMBfoAhwBzgG7uvqPZ5yrDF5FIlFpOn0lHM/yMR/juvt7d61OPNwErCY38a8CU\n1MumEP4RABgCTHP3re7eCKwF+uY6OBGR1rjDtGnQsycsWxZy+rFjS7fZRyHrDN/MKoEvAQuBg919\nQ+qpDcDBqcedgaa0tzUR/oGQPFLuHB3VMlr5qqdy+txk1fBTcc7DwA/d/f3051LZTKZ8RtmNiERC\nOX3HtDkt08z2IDT7X7v7jNTuDWbWyd3Xm9kXgb+n9q8Duqa9vUtq3yfU1NRQWVkJQEVFBVVVVVRX\nVwO7jgq0nd32zn1JGU8xb1dXVydqPMW+HVU9N2+GxYurmTgRBg2q4557YPDg+P/78r1dV1dHbW0t\nwMf9siPaOmlrhIz+bXe/PG3/Dal9E8xsFFDR7KRtX3adtD28+RlanbQVkWw0n08/YUJ5Rzd5PWkL\n9AOGASea2ZLUr9OA8cCpZrYaOCm1jbs3ANOBBmAWMEKdPf92HhFIx6mW0epIPZXTRy9jpOPu82n9\nH4VTWnnPOGBcB8clImVq3ToYPRrmzAmzbs4/Hz6lS0QjobV0RCQRymk+fa60lo6IFDWte1M4+kGp\nBCh3jo5qGa226qmcvrDU8EWk4DSfPh7K8EWkYJTTd4wyfBFJPOX0yaBIpwQod46Oahmturo65fQJ\noiN8EcmLb30LZs0KMc7NN8P3v6/59HFThi8ikVq0KGT006fD9u1h31lnhW3pmHwvrSAi0qZt20JD\nP+EEOPts6N0bTjwxPNe7N0yaFO/4JFDDLwHKnaOjWrbPu+/CDTfAYYfB7bfDj34Ea9fCFVfAQw/B\ngAF1zJ4NFRVtf5bknzJ8EWm3P/8ZfvlLmDoVzjgDHnkEvvKVf31NRQVce62afZIowxeRrLiHBc0m\nTgwXSn3vezBiBHzxi3GPrHxoHr6I5NWHH4bplLfeCmZw2WXwu9/B3nvHPTJpL2X4JUC5c3RUy13e\neAOuuQb+/d9h5szQ8F9+Gb773eybveqZLGr4IvIvXngBhg2DI4+EjRth/nx49FE4+eRwhC/FSxm+\niLBtG/zhD3DLLfD663DJJeFI/oAD4h6ZpFOGLyI527gR7r0XbrsNunQJ+fzQobC7OkNJUqRTApST\nRqdcarlmTTiKP+wweOmlcNHU/Plw5pnRNvtyqWexUMMXKRPu8PTTYd78CSfAZz4Dy5bBgw9C375x\nj04KQRm+SInbvDlcIDVxYljb5rLL4L//G/bZJ+6RSXspwxeRFv3tb3DnnXD33eEq2BtvhFNP1Uyb\ncqZIpwQoJ41OKdTypZfC7QN79YK33oJnn4XHH4eBAwvf7EuhnqWkzYZvZpPNbIOZLUvb19fMFpnZ\nEjNbbGZ90p4bbWZrzGyVmQ3M18BFZJft28N6NgMGwJAhcNRR8MorcMcd0KNH3KOTpGgzwzez/sAm\n4H53Pzq1rw643t2fNLNBwEh3P9HMegFTgT7AIcAcoJu772j2mcrwRSLw3nsweXJYyKxTp5DPf/3r\nsMcecY9M8iHv6+G7+zzg3Wa7/wZ8NvW4AliXejwEmObuW929EVgL6Py/SMReeSU090MPDTccmTYN\nnn8ezjlHzV5al2uGPwq4ycz+CvwCGJ3a3xloSntdE+FIX/JIOWl0klxLd6irCxdGHXssfPrTsHRp\naPbHHRf36FqW5HqWo1xn6dwLXOruj5jZWcBk4NRWXttidlNTU0NlZSUAFRUVVFVVUV1dDez6kmg7\nu+36+vpEjUfb0W4/9VQdTz8NTzxRzebNMHhwHd/7HgwalIzxaTt/23V1ddTW1gJ83C87Iqt5+GZW\nCTyaluH/w90/k3pswEZ3/6yZjQJw9/Gp554Axrj7wmafpwxfpA0bNsBdd4WplVVVIcIZOFA3Ai9n\ncd3Tdq2ZDUg9PglYnXo8E/imme1pZocCRwCLch2cSDmqr4fhw8PsmjfeIHV0D6edpmYvHZPNtMxp\nwAKgu5m9bmbDgYuAG8ysHrgutY27NwDTgQZgFjBCh/L5t/NHQOm4uGq5fXtYrfLEE+H006Fbt3Bv\n2LvvDvPpi5W+m8nSZobv7ue28tSxrbx+HDCuI4MSKRfvv79rWuXnPgeXXx4WMNNMG8kHraUjEoPX\nXgtLEk+ZEm4scvnlYaaNlj2QTOLK8EWkndzhuefChVF9+oRliHcuTXz88Wr2kn9q+CVAOWl08lHL\njz6C++8PC5hdeCGccgo0NsINN4T7xZYyfTeTRatliuTJ3/8eTrrecUdY2+bnP4dBgzTTRuKjDF8k\nYi+/DLfeCr//fTgB+8MfhoYv0lFaD18kAXbsCEsQ33ILrFwJ//M/sHo1fP7zcY9MZBf9cFkClJNG\np7213LQJbr8duneHMWPCBVONjXD11Wr2oO9m0ugIXyQHjY2h0d93X7hY6r77oF8/zbSRZFOGL5Il\nd1iwIMQ2zzwTjuZ/8AOIYE0rkawowxfJsy1b4KGHwk3A3303nIS97z7Yf/+4RybSPsrwS4By0uik\n1/Ktt2Ds2HCTkcmT4ac/hT//GS65RM0+W/puJosavkgzK1bARRfBEUfAq6/CrFkwdy6ccQbstlvc\noxPJnTJ8kZShQ+HZZ+GDD+CKK8L6Nl/4QtyjEtlFa+mIdNCGDeEE7OOPw8aNIbN/5RU1eyk9avgl\nQDlpbrZuDSdijzoKDjoIBgwAqKN3b5g0Ke7RlQZ9N5NFs3SkLD39dDj52qULzJsX7i61cWOIdWbM\ngIqKuEcoEj1l+FJW/vpXuPJKeOGFMJ9+yBBdLCXFQxm+SBY2b4brroMvfzlEOA0N4WhezV7KiRp+\nCVBO2jp3mDkTjjwSliwJR/ZjxsDee7f8etUyWqpnsijDl5K1enW4KraxEe66C049Ne4RicRLGb6U\nnPffD/HN5MkwenQ4OaubgkspUIYvkuIODz4IPXvC+vWwbFm4gErNXiRQwy8Byklh6dIwj/7mm8NN\nwadMgU6d2v85qmW0VM9kabPhm9lkM9tgZsua7b/EzFaa2XIzm5C2f7SZrTGzVWY2MB+DFtnpnXfC\n3aUGDoRhw2DRIjjhhLhHJZJMbWb4ZtYf2ATc7+5Hp/adCFwFDHb3rWb2eXd/08x6AVOBPsAhwByg\nm7vvaPaZyvClQ7Zvh3vuCStYnnlmuEH4gQfGPSqR/Mr7evjuPs/MKpvt/j5wvbtvTb3mzdT+IcC0\n1P5GM1sL9AX+lOsARZp7/vlw45F99oGnnoJjjol7RCLFIdcM/wjgv8zsT2ZWZ2a9U/s7A01pr2si\nHOlLHpVLTrp+PZx/Ppx1Vrha9rnnom/25VLLQlE9kyXXefi7Awe4+3Fm1geYDhzWymtbzG5qamqo\nTN0brqKigqqqKqqrq4FdXxJtZ7ddX1+fqPFEvT1nTh0PPwwPPVTNBRfApEl17LMPmCVjfNrWdr62\n6+rqqK2tBfi4X3ZEVvPwU5HOo2kZ/ixgvLs/m9peCxwHXADg7uNT+58Axrj7wmafpwxfsjJ7Nlx6\nabhv7MSJ0L173CMSiU9c8/BnACelBtAN2NPd3wJmAt80sz3N7FBC9LMo18FJ+WpshG98Ay6+GCZM\nCGvVq9mLdEw20zKnAQuAbmb2upkNByYDh6Wmak4DzgNw9wZCvNMAzAJG6FA+/3b+CFgKPvwQfvYz\n6N0bvvSlcLvBr32tcIuclVItk0D1TJZsZumc28pT327l9eOAcR0ZlJQf97AO/RVXQJ8+8NJL8G//\nFveoREqL1tKR2K1aFRY5a2qC226Dk06Ke0QiyaS1dKRo/eMf8OMfQ//+MGgQ1Ner2Yvkkxp+CSi2\nnNQdfv3rsMjZ22/D8uVw2WXJWOSs2GqZdKpnsmg9fCmol14KyxVv2QIPPwzHHRf3iETKhzJ8KYi3\n34arrw4nZq+7Dr7zHfiUfr4UaRdl+JJo27fDnXdCr16w556wciVccIGavUgc9NeuBCQ1J50/P8yn\n/+1vYc4c+OUv4YAD4h5VZkmtZbFSPZNFGb5E7o03YORIePZZuPFGOPvswl04JSKtU4YvkdmyBW69\nNSyFcNFFcNVVsN9+cY9KpHTkfT18kWw8+WS4eOrww+FPfwq/i0iyKMMvAXHmpK++CkOHhtsM3ngj\nPPZYcTd7Zc7RUj2TRQ1fcvLBB+H2gn37hl/Ll8Ppp8c9KhHJRBm+tIt7uGDqyivh+OPhF7+Arl3j\nHpVIeVCGLwXT0BBuRrJhA0yZAqkb9IhIkVCkUwLynZO+915YtnjAgLA2/ZIlpdvslTlHS/VMFjV8\nadWOHeFIvmfPsLLlihXhCH93/VwoUpSU4UuLXnwRfvCD0PRvvz3clERE4qW1dCRSb70VLpo6/fTw\n+/PPq9mLlAo1/BIQRU66bVs4ku/VC/bdNyxyNnx4+S1ypsw5WqpnsiiNFZ57LqxR/7nPwdNPw1FH\nxT0iEckHZfhlbN26cIvB+fPhppvgzDO1yJlIkinDl3b76CMYPx6OOQYOOyzEN2edpWYvUurU8EtA\ne3LSxx+Ho4+GBQtg4cJw96l9983f2IqNMudoqZ7J0mbDN7PJZrbBzJa18NyVZrbDzA5M2zfazNaY\n2SozGxj1gCU3r7wCZ5wRbhZ+660wcyb8x3/EPSoRKaQ2M3wz6w9sAu5396PT9ncFfgV0B77i7u+Y\nWS9gKtAHOASYA3Rz9x3NPlMZfoH8859w/fVw110hr7/sMthrr7hHJSK5yHuG7+7zgHdbeOpmYGSz\nfUOAae6+1d0bgbVA31wHJ7lzh+nTw1Wyr70GS5fCT36iZi9SznLK8M1sCNDk7i83e6oz0JS23UQ4\n0pc8ap6TLl8OJ58MY8fCAw/Agw/CIfq/kBVlztFSPZOl3fPwzWwf4Crg1PTdGd7SYnZTU1NDZWUl\nABUVFVRVVVGdWpFr55dE29lt19fXA1BVVc2110JtbR3nnw833VTN7rvHPz5ta1vbuW3X1dVRW1sL\n8HG/7Iis5uGbWSXwqLsfbWZHE7L5D1JPdwHWAccCwwHcfXzqfU8AY9x9YbPPU4YfoR07oLYWrr46\nrGY5diwcdFDcoxKRqBV8PXx3XwYcnDaA19h10nYmMNXMbiZEOUcAi3IdnLRt6FCYOxd22w1mzCjd\nZYtFpOOymZY5DVgAdDOz181seLOXfHyo7u4NwHSgAZgFjNChfH785S8wbFiYV79pUx3vvQd33BH3\nqIrfzh+nJRqqZ7JkM0vnXHfv7O57uXtXd7+v2fOHufs7advj3P1wd+/h7k/mY9DlbOPGMNvmy18O\n8+h3HtH37g2TJsU6NBFJOK2lUyS2bIE774Rx40JO/7OfQefO4R+Aiy4Kzb6iIu5Rikg+dTTDV8NP\nuJ03DR81Crp1gxtu0GqWIuVKi6eVsAULoF+/MOvmrrtCXt9Ss1dOGh3VMlqqZ7JoPfwEWrs2HNEv\nXBia/bBh5XcjEhGJniKdBHn7bfj5z8PVsVdeGda92XvvuEclIkmhSKcEbN4csvkePcKtBhsaYPRo\nNXsRiZYafox27Ajr3PToEW4WPn9+uK/sF77Qvs9RThod1TJaqmeyKMOPyTPPhOWKd9sNfv1r6N8/\n7hGJSKlThl9gK1fCyJGwYkVYp/7ss3VrQRHJjjL8IrF+PVx8MQwYACeeGBr/Oeeo2YtI4ajh59k/\n/xlm3hx5ZLh37KpVcMUV0d6IRDlpdFTLaKmeyaKGnyfbt8O990L37iG+WbwYbroJDjyw7feKiOSD\nMvw8ePLJcEK2ogJuvBH66iaPIhKBgq+HL61bujQ0+r/8BSZMgCFDlNGLSHIo0olAUxMMHw5f/Wq4\nIcny5eH3QjV75aTRUS2jpXomixp+B/zjH3DNNXDMMWGp4tWrYcQI2GOPuEcmIvJJyvBzsHUr/OpX\nYfbNV78afu/aNe5RiUipU4ZfQO4wc2a441TXrjBrFlRVxT0qEZHsKNLJ0uLF4XaC11wDEyfCU08l\np9krJ42Oahkt1TNZ1PDb8NprcO654STseedBfT2cdppm34hI8VGG34p33w03H6mthUsvDevT77tv\n3KMSkXKmtXQi9tFHcMst4QrZ998PUyx/+lM1exEpfmr4Ke4wfTr06gVz54bli+++Gzp1intkbVNO\nGh3VMlqqZ7K02fDNbLKZbTCzZWn7fmFmK81sqZn93sw+m/bcaDNbY2arzGxgvgYepfnz4fjjYfz4\nMN3yscfCYmciIqWkzQzfzPoDm4D73f3o1L5TgbnuvsPMxgO4+ygz6wVMBfoAhwBzgG7uvqPZZyYi\nw1+9Otws/MUXQ17/rW/pZuEiklx5z/DdfR7wbrN9s9Oa+EKgS+rxEGCau29190ZgLZC4pcPefBMu\nuQROOAGOPTYsWTxsmJq9iJS2KFrcd4DHU487A01pzzURjvQT4cMPw12mevYM0ypXrQoXURX7zcKV\nk0ZHtYyW6pksHbrS1syuBra4+9QML2sxu6mpqaGyshKAiooKqqqqqK6uBnZ9SaLafvrpOmbPhgcf\nrKZvX5g4sY4uXeCgg/Lz5xV6u76+PlHj0ba2tR3Ndl1dHbW1tQAf98uOyGoevplVAo/uzPBT+2qA\nC4GT3X1zat8oAHcfn9p+Ahjj7gubfV7BMvy5c8OSxXvtFdam79evIH+siEjkYllLx8xOA34MDNjZ\n7FNmAlPN7GZClHMEsCjXwXXEihXhZuGrVoW16b/xDV0dKyLlLZtpmdOABUB3M3vdzL4D3AbsB8w2\nsyVmdgeAuzcA04EGYBYwotDTcf72N7joonCj8IEDw83CzzyztJv9zh8BpeNUy2ipnsnS5hG+u5/b\nwu7JGV4/DhjXkUHlYtOmENncdht897thymVFRaFHISKSXEW/ls62bXDffXDttWE1y7FjIYJzGyIi\niVO26+G7h/XoR46Egw6CP/wBeveOe1QiIslVlJcaLVkCp5wSVrC8/vqw7k05N3vlpNFRLaOleiZL\nUTX8v/41rEk/eDCcdRYsWwZnnFHaJ2RFRKJSFBn+e++Fhc0mTQo3CR85EvbfP48DFBFJoJJeD3/r\nVrj9dujWDTZsgJdfDjcMV7MXEWm/RDZ8d3jkkbBE8WOPwezZMHkyHJKYVXmSRTlpdFTLaKmeyZK4\nWToLF4aTse+/H47uBxbFivoiIsmXmAz/1Vdh9Gj44x/huuvg29+G3XYr+NBERBKr6DP8d96BK66A\nvn3hP/8zXCFbU6NmLyIStdga/ubNYSmE7t3D4xUr4OqrYZ994hpR8VJOGh3VMlqqZ7LEluH37BmO\n6OfNgx494hqFiEj5iC3D79vXefJJLXAmIpKtos3wFy0KyxiLiEhhxNbwe/cOV85KxyknjY5qGS3V\nM1lia/izZyvOEREppMTMwxcRkcyKNsMXEZHCUsMvAcpJo6NaRkv1TBY1fBGRMqEMX0SkSCjDFxGR\nrLTZ8M1sspltMLNlafsONLPZZrbazJ4ys4q050ab2RozW2VmWty4AJSTRke1jJbqmSzZHOHfB5zW\nbN8oYLa7dwPmprYxs17AOUCv1HvuMDP9FJFn9fX1cQ+hZKiW0VI9k6XNZuzu84B3m+3+GjAl9XgK\nMDT1eAgwzd23unsjsBboG81QpTUbN26MewglQ7WMluqZLLkefR/s7htSjzcAB6cedwaa0l7XBMRy\nY8KO/CiZ7Xvbel2m51t7rvn+ll4Xx4/Juf6Z7Xlf1PXMZl8x1bK97821nu3ZXy71LMTf9Zb2RV3P\nDsctqek2mabcxDIdp1S+BNl8KRobGzOOIwrl0vCTXMv2vjcJDb9U6lkqDT+raZlmVgk86u5Hp7ZX\nAdXuvt7Mvgg84+49zGwUgLuPT73uCWCMuy9s9nmakykikoOOTMvM9QYoM4HzgQmp32ek7Z9qZjcT\nopwjgEXN39yRAYuISG7abPhmNg0YABxkZq8DPwXGA9PN7LtAI3A2gLs3mNl0oAHYBozQFVYiIskQ\ny5W2IiJSeJojLyJSJtTwRUTKRCIavpkNMbNJZvYbMzs17vEUMzPrYWZ3mtnOcyzSQWa2r5ktNrP/\nF/dYip2ZVZvZvNR3dEDc4ylmFow1s1+a2XnZvCcRDd/d/+DuFwEXE5ZmkBy5+yp3/z7wTeCrcY+n\nRIwEfhv3IErEDuB9YC/+9SJNab+hhNmQW8iylnlr+C0tupbaf1pqYbU1ZvaTZm+7Brg9X2MqVu2t\npZmdAfx/4DeFHmsxaE89Uz9xNgBvxjHWYtDO7+c8dx9MWH/rZwUfbMK1s5bdgD+6+4+A72fz+fk8\nwv/EomtmthuhoZ9GWGDtXDPrmfrRZAIwy9212tInZV1LAHd/1N0HEa6RkE9qTz0HAMcB3wIuNDNd\nQ/JJWdczbZr2RsJRvvyr9nw3mwh1hPCTU5tyvfCqTe4+L3WFbrq+wNrUwmqY2W8IC66dApwMfMbM\nDnf3u/M1rmLUnlqa2ReArwOfBp4p4DCLRnvq6e7XpLbPB97UdSWf1M7vZw9C1FgB3FbAYRaFdvbN\nW4HbzKw/UJfN5+et4bfiEOD1tO0m4Fh3vwT9z2+v1mr5LPBsPEMqai3Wc+eGu0/5xDskk9a+n+OB\nR+IZUtFqrZYfAhe054MKfdJWR0fRUS2jpXpGS/WMTmS1LHTDXwd0Tdvuis7U50q1jJbqGS3VMzqR\n1bLQDf9pEt7HAAAAiUlEQVQF4AgzqzSzPQlTMGcWeAylQrWMluoZLdUzOpHVMp/TMqcBC4BuZva6\nmQ13923AD4AnCVPdfuvuK/M1hlKhWkZL9YyW6hmdfNdSi6eJiJSJRFxpKyIi+aeGLyJSJtTwRUTK\nhBq+iEiZUMMXESkTavgiImVCDV9EpEyo4YuIlAk1fBGRMvF/VmlFVQ7pinMAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1fbdcb38>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "times = [109, 138, 169, 192, 222]\n",
    "\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "plt.semilogx(ns, times, '.-')\n",
    "plt.grid(True)"
   ]
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
	{
	"cells": [
	{
	"cell_type": "code",
	"execution_count": 1,
	"metadata": {
	"collapsed": false
	},
	"outputs": [],
	"source": [
	"from scipy.spatial import KDTree\n",
	"import numpy as np\n",
	"import numpy.random as npr\n",
	"\n",
	"ns = [100, 1000, 10000, 100000, 1000000]\n",
	"datas = [None] * len(ns)\n",
	"trees = [None] * len(ns)\n",
	"\n",
	"datas[0] = npr.rand(ns[0], 2)\n",
	"trees[0] = KDTree(datas[0])\n",
	"\n",
	"\n",
	"for i in xrange(1, len(ns)):\n",
	" datas[i] = np.vstack((datas[i-1], npr.rand(ns[i] - ns[i-1], 2)))\n",
	" trees[i] = KDTree(datas[i])"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 11,
	"metadata": {
	"collapsed": false
	},
	"outputs": [],
	"source": [
	"p = npr.rand(1000, 2)"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 12,
	"metadata": {
	"collapsed": false
	},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"10 loops, best of 3: 109 ms per loop\n"
	]
	}
	],
	"source": [
	"%%timeit\n",
	"trees[0].query(p)"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 13,
	"metadata": {
	"collapsed": false
	},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"10 loops, best of 3: 138 ms per loop\n"
	]
	}
	],
	"source": [
	"%%timeit\n",
	"trees[1].query(p)"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 14,
	"metadata": {
	"collapsed": false
	},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"10 loops, best of 3: 169 ms per loop\n"
	]
	}
	],
	"source": [
	"%%timeit\n",
	"trees[2].query(p)"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 15,
	"metadata": {
	"collapsed": false
	},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"1 loops, best of 3: 192 ms per loop\n"
	]
	}
	],
	"source": [
	"%%timeit\n",
	"trees[3].query(p)"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 16,
	"metadata": {
	"collapsed": false
	},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"1 loops, best of 3: 222 ms per loop\n"
	]
	}
	],
	"source": [
	"%%timeit\n",
	"trees[4].query(p)"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 20,
	"metadata": {
	"collapsed": false
	},
	"outputs": [
	{
	"data": {
	"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEFCAYAAADgylzDAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XucVXW9//HXJ295q9EsCeGc0aPc1ONUgBceHMYbCT8N\nHuUlO6RDqRknzUsRqI+wkyCYF0wfXkhxMIXCTEJ/ogI6CmGAyiAwEKBOORjkDZMUuX3OH9+N7MaZ\nPXv2rL3X2nu/n48HD/Za+8LXj5sPa97ru77L3B0RESl9n4p7ACIiUhhq+CIiZUINX0SkTKjhi4iU\nCTV8EZEyoYYvIlImMjZ8M+tqZs+Y2QozW25mlzZ7/koz22FmB6btG21ma8xslZkNzNfARUSkfXZv\n4/mtwOXuXm9m+wEvmtlsd19pZl2BU4G/7HyxmfUCzgF6AYcAc8ysm7vvyNP4RUQkSxmP8N19vbvX\npx5vAlYCnVNP3wyMbPaWIcA0d9/q7o3AWqBvpCMWEZGcZJ3hm1kl8CVgoZkNAZrc/eVmL+sMNKVt\nNxGO9EVEJGZtRToApOKc3wE/BHYAVxHinI9fkuHtWrtBRCQB2mz4ZrYH8DDwgLvPMLOjgUpgqZkB\ndCFk+8cC64CuaW/vktrX/DP1j4CISA7cPdMBdkZtzdIx4F6gwd0npv6wZe5+sLsf6u6HEmKbL7v7\nBmAm8E0z29PMDgWOABa1Mui8/hozZkze39vW6zI939pzzfe39LpsXpOUerbnfVHXM5faJbmWhapn\ne/aXSz0L8Xc9m/p1VFtH+P2AYcDLZrYkte8qd5+V3rvTmniDmU0HGoBtwAiPYpQ5qK6uzvt723pd\npudbe675/pZe13xfY2NjxnFEIdd6tud9Udczm33FVMv2vjfXerZnf7nUsxB/11va15H/tpZYHP3Y\nzOL6d6Ak1dTUUFtbG/cwSoJqGS3VM1pmhucr0pHiUFNTE/cQSoZqGS3VM1l0hC8iUiR0hC/U1dXF\nPYSSoVpGS/VMFjV8EZEyoUhHRKRIKNIREZGsqOGXAOWk0VEto6V6JosavohImVCGLyJSJJThi4hI\nVtTwS4By0uioltFSPZNFDV9EpEwowxcRKRLK8EVEJCtq+CVAOWl0VMtoqZ7JooYvIlImlOGLiBQJ\nZfgiIpIVNfwSoJw0OqpltFTPZFHDFxEpE8rwRUSKhDJ8ERHJihp+CVBOGh3VMlqqZ7JkbPhm1tXM\nnjGzFWa23MwuTe3/hZmtNLOlZvZ7M/ts2ntGm9kaM1tlZgPz/R8gIlIOzj+/45+RMcM3s05AJ3ev\nN7P9gBeBoUAXYK677zCz8QDuPsrMegFTgT7AIcAcoJu772j2ucrwRUSy8MEHcNNN8L//C9u25THD\nd/f17l6ferwJWAl0dvfZaU18IeEfAIAhwDR33+rujcBaoG+ugxMRKVfuMG0a9OwJy5ZBv34d/8ys\nM3wzqwS+RGjw6b4DPJ563BloSnuuiXCkL3mknDQ6qmW0VM/cLFoUGvyNN8IDD8D06TBjRsc/N6uG\nn4pzfgf8MHWkv3P/1cAWd5+a4e3KbkREsrBuHZx3HgwdChdeCIsXQ//+4bmKio5//u5tvcDM9gAe\nBh5w9xlp+2uAwcDJ6eMFuqZtd0nt+4SamhoqKysBqKiooKqqiurqamDXUYG2s9veuS8p4ynm7erq\n6kSNp9i3Vc/stjdvhsWLq5k4EQYNquOee2Dw4FC72tpagI/7ZUe0ddLWgCnA2+5+edr+04CbgAHu\n/lba/p0nbfuy66Tt4c3P0OqkrYhIyOl/8xsYNQqOPRYmTIBDD2399fm+8KofMAw40cyWpH4NAm4D\n9gNmp/bdEQbvDcB0oAGYBYxQZ8+/nUcM0nGqZbRUz9a1lNNnavZRyBjpuPt8Wv5H4YgM7xkHjOvg\nuEREStK6dTB6NMyZA2PHhvn1nyrQJbBaS0dEpAB2zqefOBEuvjjEOPvv377P6Gik0+ZJWxERyV3z\nnP6FF/If3bRGa+mUAOWk0VEto1Xu9Ywjp89EDV9EJGKZ5tPHSRm+iEhEosjpM1GGLyISsyTl9Jko\n0ikB5Z6TRkm1jFY51DNpOX0mavgiIjlIak6fiTJ8EZF2yHdOn4kyfBGRAiiWnD4TRToloBxy0kJR\nLaNVKvUsppw+EzV8EZFWFGNOn4kyfBGRZuLM6TNRhi8iEpFSyOkzUaRTAkolJ00C1TJaxVTPUsnp\nM1HDF5GyVmo5fSbK8EWkLCU1p89EGb6ISDuUek6fiSKdElBMOWnSqZbRSlo9yyGnz0QNX0RKXjnl\n9JkowxeRklWMOX0myvBFRJop55w+E0U6JSBpOWkxUy2jFUc9yz2nzyRjwzezrmb2jJmtMLPlZnZp\nav+BZjbbzFab2VNmVpH2ntFmtsbMVpnZwHz/B4iIgHL6bGTM8M2sE9DJ3evNbD/gRWAoMBx4y91v\nMLOfAAe4+ygz6wVMBfoAhwBzgG7uvqPZ5yrDF5FIlFpOn0lHM/yMR/juvt7d61OPNwErCY38a8CU\n1MumEP4RABgCTHP3re7eCKwF+uY6OBGR1rjDtGnQsycsWxZy+rFjS7fZRyHrDN/MKoEvAQuBg919\nQ+qpDcDBqcedgaa0tzUR/oGQPFLuHB3VMlr5qqdy+txk1fBTcc7DwA/d/f3051LZTKZ8RtmNiERC\nOX3HtDkt08z2IDT7X7v7jNTuDWbWyd3Xm9kXgb+n9q8Duqa9vUtq3yfU1NRQWVkJQEVFBVVVVVRX\nVwO7jgq0nd32zn1JGU8xb1dXVydqPMW+HVU9N2+GxYurmTgRBg2q4557YPDg+P/78r1dV1dHbW0t\nwMf9siPaOmlrhIz+bXe/PG3/Dal9E8xsFFDR7KRtX3adtD28+RlanbQVkWw0n08/YUJ5Rzd5PWkL\n9AOGASea2ZLUr9OA8cCpZrYaOCm1jbs3ANOBBmAWMEKdPf92HhFIx6mW0epIPZXTRy9jpOPu82n9\nH4VTWnnPOGBcB8clImVq3ToYPRrmzAmzbs4/Hz6lS0QjobV0RCQRymk+fa60lo6IFDWte1M4+kGp\nBCh3jo5qGa226qmcvrDU8EWk4DSfPh7K8EWkYJTTd4wyfBFJPOX0yaBIpwQod46Oahmturo65fQJ\noiN8EcmLb30LZs0KMc7NN8P3v6/59HFThi8ikVq0KGT006fD9u1h31lnhW3pmHwvrSAi0qZt20JD\nP+EEOPts6N0bTjwxPNe7N0yaFO/4JFDDLwHKnaOjWrbPu+/CDTfAYYfB7bfDj34Ea9fCFVfAQw/B\ngAF1zJ4NFRVtf5bknzJ8EWm3P/8ZfvlLmDoVzjgDHnkEvvKVf31NRQVce62afZIowxeRrLiHBc0m\nTgwXSn3vezBiBHzxi3GPrHxoHr6I5NWHH4bplLfeCmZw2WXwu9/B3nvHPTJpL2X4JUC5c3RUy13e\neAOuuQb+/d9h5szQ8F9+Gb773eybveqZLGr4IvIvXngBhg2DI4+EjRth/nx49FE4+eRwhC/FSxm+\niLBtG/zhD3DLLfD663DJJeFI/oAD4h6ZpFOGLyI527gR7r0XbrsNunQJ+fzQobC7OkNJUqRTApST\nRqdcarlmTTiKP+wweOmlcNHU/Plw5pnRNvtyqWexUMMXKRPu8PTTYd78CSfAZz4Dy5bBgw9C375x\nj04KQRm+SInbvDlcIDVxYljb5rLL4L//G/bZJ+6RSXspwxeRFv3tb3DnnXD33eEq2BtvhFNP1Uyb\ncqZIpwQoJ41OKdTypZfC7QN79YK33oJnn4XHH4eBAwvf7EuhnqWkzYZvZpPNbIOZLUvb19fMFpnZ\nEjNbbGZ90p4bbWZrzGyVmQ3M18BFZJft28N6NgMGwJAhcNRR8MorcMcd0KNH3KOTpGgzwzez/sAm\n4H53Pzq1rw643t2fNLNBwEh3P9HMegFTgT7AIcAcoJu772j2mcrwRSLw3nsweXJYyKxTp5DPf/3r\nsMcecY9M8iHv6+G7+zzg3Wa7/wZ8NvW4AliXejwEmObuW929EVgL6Py/SMReeSU090MPDTccmTYN\nnn8ezjlHzV5al2uGPwq4ycz+CvwCGJ3a3xloSntdE+FIX/JIOWl0klxLd6irCxdGHXssfPrTsHRp\naPbHHRf36FqW5HqWo1xn6dwLXOruj5jZWcBk4NRWXttidlNTU0NlZSUAFRUVVFVVUV1dDez6kmg7\nu+36+vpEjUfb0W4/9VQdTz8NTzxRzebNMHhwHd/7HgwalIzxaTt/23V1ddTW1gJ83C87Iqt5+GZW\nCTyaluH/w90/k3pswEZ3/6yZjQJw9/Gp554Axrj7wmafpwxfpA0bNsBdd4WplVVVIcIZOFA3Ai9n\ncd3Tdq2ZDUg9PglYnXo8E/imme1pZocCRwCLch2cSDmqr4fhw8PsmjfeIHV0D6edpmYvHZPNtMxp\nwAKgu5m9bmbDgYuAG8ysHrgutY27NwDTgQZgFjBCh/L5t/NHQOm4uGq5fXtYrfLEE+H006Fbt3Bv\n2LvvDvPpi5W+m8nSZobv7ue28tSxrbx+HDCuI4MSKRfvv79rWuXnPgeXXx4WMNNMG8kHraUjEoPX\nXgtLEk+ZEm4scvnlYaaNlj2QTOLK8EWkndzhuefChVF9+oRliHcuTXz88Wr2kn9q+CVAOWl08lHL\njz6C++8PC5hdeCGccgo0NsINN4T7xZYyfTeTRatliuTJ3/8eTrrecUdY2+bnP4dBgzTTRuKjDF8k\nYi+/DLfeCr//fTgB+8MfhoYv0lFaD18kAXbsCEsQ33ILrFwJ//M/sHo1fP7zcY9MZBf9cFkClJNG\np7213LQJbr8duneHMWPCBVONjXD11Wr2oO9m0ugIXyQHjY2h0d93X7hY6r77oF8/zbSRZFOGL5Il\nd1iwIMQ2zzwTjuZ/8AOIYE0rkawowxfJsy1b4KGHwk3A3303nIS97z7Yf/+4RybSPsrwS4By0uik\n1/Ktt2Ds2HCTkcmT4ac/hT//GS65RM0+W/puJosavkgzK1bARRfBEUfAq6/CrFkwdy6ccQbstlvc\noxPJnTJ8kZShQ+HZZ+GDD+CKK8L6Nl/4QtyjEtlFa+mIdNCGDeEE7OOPw8aNIbN/5RU1eyk9avgl\nQDlpbrZuDSdijzoKDjoIBgwAqKN3b5g0Ke7RlQZ9N5NFs3SkLD39dDj52qULzJsX7i61cWOIdWbM\ngIqKuEcoEj1l+FJW/vpXuPJKeOGFMJ9+yBBdLCXFQxm+SBY2b4brroMvfzlEOA0N4WhezV7KiRp+\nCVBO2jp3mDkTjjwSliwJR/ZjxsDee7f8etUyWqpnsijDl5K1enW4KraxEe66C049Ne4RicRLGb6U\nnPffD/HN5MkwenQ4OaubgkspUIYvkuIODz4IPXvC+vWwbFm4gErNXiRQwy8Byklh6dIwj/7mm8NN\nwadMgU6d2v85qmW0VM9kabPhm9lkM9tgZsua7b/EzFaa2XIzm5C2f7SZrTGzVWY2MB+DFtnpnXfC\n3aUGDoRhw2DRIjjhhLhHJZJMbWb4ZtYf2ATc7+5Hp/adCFwFDHb3rWb2eXd/08x6AVOBPsAhwByg\nm7vvaPaZyvClQ7Zvh3vuCStYnnlmuEH4gQfGPSqR/Mr7evjuPs/MKpvt/j5wvbtvTb3mzdT+IcC0\n1P5GM1sL9AX+lOsARZp7/vlw45F99oGnnoJjjol7RCLFIdcM/wjgv8zsT2ZWZ2a9U/s7A01pr2si\nHOlLHpVLTrp+PZx/Ppx1Vrha9rnnom/25VLLQlE9kyXXefi7Awe4+3Fm1geYDhzWymtbzG5qamqo\nTN0brqKigqqqKqqrq4FdXxJtZ7ddX1+fqPFEvT1nTh0PPwwPPVTNBRfApEl17LMPmCVjfNrWdr62\n6+rqqK2tBfi4X3ZEVvPwU5HOo2kZ/ixgvLs/m9peCxwHXADg7uNT+58Axrj7wmafpwxfsjJ7Nlx6\nabhv7MSJ0L173CMSiU9c8/BnACelBtAN2NPd3wJmAt80sz3N7FBC9LMo18FJ+WpshG98Ay6+GCZM\nCGvVq9mLdEw20zKnAQuAbmb2upkNByYDh6Wmak4DzgNw9wZCvNMAzAJG6FA+/3b+CFgKPvwQfvYz\n6N0bvvSlcLvBr32tcIuclVItk0D1TJZsZumc28pT327l9eOAcR0ZlJQf97AO/RVXQJ8+8NJL8G//\nFveoREqL1tKR2K1aFRY5a2qC226Dk06Ke0QiyaS1dKRo/eMf8OMfQ//+MGgQ1Ner2Yvkkxp+CSi2\nnNQdfv3rsMjZ22/D8uVw2WXJWOSs2GqZdKpnsmg9fCmol14KyxVv2QIPPwzHHRf3iETKhzJ8KYi3\n34arrw4nZq+7Dr7zHfiUfr4UaRdl+JJo27fDnXdCr16w556wciVccIGavUgc9NeuBCQ1J50/P8yn\n/+1vYc4c+OUv4YAD4h5VZkmtZbFSPZNFGb5E7o03YORIePZZuPFGOPvswl04JSKtU4YvkdmyBW69\nNSyFcNFFcNVVsN9+cY9KpHTkfT18kWw8+WS4eOrww+FPfwq/i0iyKMMvAXHmpK++CkOHhtsM3ngj\nPPZYcTd7Zc7RUj2TRQ1fcvLBB+H2gn37hl/Ll8Ppp8c9KhHJRBm+tIt7uGDqyivh+OPhF7+Arl3j\nHpVIeVCGLwXT0BBuRrJhA0yZAqkb9IhIkVCkUwLynZO+915YtnjAgLA2/ZIlpdvslTlHS/VMFjV8\nadWOHeFIvmfPsLLlihXhCH93/VwoUpSU4UuLXnwRfvCD0PRvvz3clERE4qW1dCRSb70VLpo6/fTw\n+/PPq9mLlAo1/BIQRU66bVs4ku/VC/bdNyxyNnx4+S1ypsw5WqpnsiiNFZ57LqxR/7nPwdNPw1FH\nxT0iEckHZfhlbN26cIvB+fPhppvgzDO1yJlIkinDl3b76CMYPx6OOQYOOyzEN2edpWYvUurU8EtA\ne3LSxx+Ho4+GBQtg4cJw96l9983f2IqNMudoqZ7J0mbDN7PJZrbBzJa18NyVZrbDzA5M2zfazNaY\n2SozGxj1gCU3r7wCZ5wRbhZ+660wcyb8x3/EPSoRKaQ2M3wz6w9sAu5396PT9ncFfgV0B77i7u+Y\nWS9gKtAHOASYA3Rz9x3NPlMZfoH8859w/fVw110hr7/sMthrr7hHJSK5yHuG7+7zgHdbeOpmYGSz\nfUOAae6+1d0bgbVA31wHJ7lzh+nTw1Wyr70GS5fCT36iZi9SznLK8M1sCNDk7i83e6oz0JS23UQ4\n0pc8ap6TLl8OJ58MY8fCAw/Agw/CIfq/kBVlztFSPZOl3fPwzWwf4Crg1PTdGd7SYnZTU1NDZWUl\nABUVFVRVVVGdWpFr55dE29lt19fXA1BVVc2110JtbR3nnw833VTN7rvHPz5ta1vbuW3X1dVRW1sL\n8HG/7Iis5uGbWSXwqLsfbWZHE7L5D1JPdwHWAccCwwHcfXzqfU8AY9x9YbPPU4YfoR07oLYWrr46\nrGY5diwcdFDcoxKRqBV8PXx3XwYcnDaA19h10nYmMNXMbiZEOUcAi3IdnLRt6FCYOxd22w1mzCjd\nZYtFpOOymZY5DVgAdDOz181seLOXfHyo7u4NwHSgAZgFjNChfH785S8wbFiYV79pUx3vvQd33BH3\nqIrfzh+nJRqqZ7JkM0vnXHfv7O57uXtXd7+v2fOHufs7advj3P1wd+/h7k/mY9DlbOPGMNvmy18O\n8+h3HtH37g2TJsU6NBFJOK2lUyS2bIE774Rx40JO/7OfQefO4R+Aiy4Kzb6iIu5Rikg+dTTDV8NP\nuJ03DR81Crp1gxtu0GqWIuVKi6eVsAULoF+/MOvmrrtCXt9Ss1dOGh3VMlqqZ7JoPfwEWrs2HNEv\nXBia/bBh5XcjEhGJniKdBHn7bfj5z8PVsVdeGda92XvvuEclIkmhSKcEbN4csvkePcKtBhsaYPRo\nNXsRiZYafox27Ajr3PToEW4WPn9+uK/sF77Qvs9RThod1TJaqmeyKMOPyTPPhOWKd9sNfv1r6N8/\n7hGJSKlThl9gK1fCyJGwYkVYp/7ss3VrQRHJjjL8IrF+PVx8MQwYACeeGBr/Oeeo2YtI4ajh59k/\n/xlm3hx5ZLh37KpVcMUV0d6IRDlpdFTLaKmeyaKGnyfbt8O990L37iG+WbwYbroJDjyw7feKiOSD\nMvw8ePLJcEK2ogJuvBH66iaPIhKBgq+HL61bujQ0+r/8BSZMgCFDlNGLSHIo0olAUxMMHw5f/Wq4\nIcny5eH3QjV75aTRUS2jpXomixp+B/zjH3DNNXDMMWGp4tWrYcQI2GOPuEcmIvJJyvBzsHUr/OpX\nYfbNV78afu/aNe5RiUipU4ZfQO4wc2a441TXrjBrFlRVxT0qEZHsKNLJ0uLF4XaC11wDEyfCU08l\np9krJ42Oahkt1TNZ1PDb8NprcO654STseedBfT2cdppm34hI8VGG34p33w03H6mthUsvDevT77tv\n3KMSkXKmtXQi9tFHcMst4QrZ998PUyx/+lM1exEpfmr4Ke4wfTr06gVz54bli+++Gzp1intkbVNO\nGh3VMlqqZ7K02fDNbLKZbTCzZWn7fmFmK81sqZn93sw+m/bcaDNbY2arzGxgvgYepfnz4fjjYfz4\nMN3yscfCYmciIqWkzQzfzPoDm4D73f3o1L5TgbnuvsPMxgO4+ygz6wVMBfoAhwBzgG7uvqPZZyYi\nw1+9Otws/MUXQ17/rW/pZuEiklx5z/DdfR7wbrN9s9Oa+EKgS+rxEGCau29190ZgLZC4pcPefBMu\nuQROOAGOPTYsWTxsmJq9iJS2KFrcd4DHU487A01pzzURjvQT4cMPw12mevYM0ypXrQoXURX7zcKV\nk0ZHtYyW6pksHbrS1syuBra4+9QML2sxu6mpqaGyshKAiooKqqqqqK6uBnZ9SaLafvrpOmbPhgcf\nrKZvX5g4sY4uXeCgg/Lz5xV6u76+PlHj0ba2tR3Ndl1dHbW1tQAf98uOyGoevplVAo/uzPBT+2qA\nC4GT3X1zat8oAHcfn9p+Ahjj7gubfV7BMvy5c8OSxXvtFdam79evIH+siEjkYllLx8xOA34MDNjZ\n7FNmAlPN7GZClHMEsCjXwXXEihXhZuGrVoW16b/xDV0dKyLlLZtpmdOABUB3M3vdzL4D3AbsB8w2\nsyVmdgeAuzcA04EGYBYwotDTcf72N7joonCj8IEDw83CzzyztJv9zh8BpeNUy2ipnsnS5hG+u5/b\nwu7JGV4/DhjXkUHlYtOmENncdht897thymVFRaFHISKSXEW/ls62bXDffXDttWE1y7FjIYJzGyIi\niVO26+G7h/XoR46Egw6CP/wBeveOe1QiIslVlJcaLVkCp5wSVrC8/vqw7k05N3vlpNFRLaOleiZL\nUTX8v/41rEk/eDCcdRYsWwZnnFHaJ2RFRKJSFBn+e++Fhc0mTQo3CR85EvbfP48DFBFJoJJeD3/r\nVrj9dujWDTZsgJdfDjcMV7MXEWm/RDZ8d3jkkbBE8WOPwezZMHkyHJKYVXmSRTlpdFTLaKmeyZK4\nWToLF4aTse+/H47uBxbFivoiIsmXmAz/1Vdh9Gj44x/huuvg29+G3XYr+NBERBKr6DP8d96BK66A\nvn3hP/8zXCFbU6NmLyIStdga/ubNYSmE7t3D4xUr4OqrYZ994hpR8VJOGh3VMlqqZ7LEluH37BmO\n6OfNgx494hqFiEj5iC3D79vXefJJLXAmIpKtos3wFy0KyxiLiEhhxNbwe/cOV85KxyknjY5qGS3V\nM1lia/izZyvOEREppMTMwxcRkcyKNsMXEZHCUsMvAcpJo6NaRkv1TBY1fBGRMqEMX0SkSCjDFxGR\nrLTZ8M1sspltMLNlafsONLPZZrbazJ4ys4q050ab2RozW2VmWty4AJSTRke1jJbqmSzZHOHfB5zW\nbN8oYLa7dwPmprYxs17AOUCv1HvuMDP9FJFn9fX1cQ+hZKiW0VI9k6XNZuzu84B3m+3+GjAl9XgK\nMDT1eAgwzd23unsjsBboG81QpTUbN26MewglQ7WMluqZLLkefR/s7htSjzcAB6cedwaa0l7XBMRy\nY8KO/CiZ7Xvbel2m51t7rvn+ll4Xx4/Juf6Z7Xlf1PXMZl8x1bK97821nu3ZXy71LMTf9Zb2RV3P\nDsctqek2mabcxDIdp1S+BNl8KRobGzOOIwrl0vCTXMv2vjcJDb9U6lkqDT+raZlmVgk86u5Hp7ZX\nAdXuvt7Mvgg84+49zGwUgLuPT73uCWCMuy9s9nmakykikoOOTMvM9QYoM4HzgQmp32ek7Z9qZjcT\nopwjgEXN39yRAYuISG7abPhmNg0YABxkZq8DPwXGA9PN7LtAI3A2gLs3mNl0oAHYBozQFVYiIskQ\ny5W2IiJSeJojLyJSJtTwRUTKRCIavpkNMbNJZvYbMzs17vEUMzPrYWZ3mtnOcyzSQWa2r5ktNrP/\nF/dYip2ZVZvZvNR3dEDc4ylmFow1s1+a2XnZvCcRDd/d/+DuFwEXE5ZmkBy5+yp3/z7wTeCrcY+n\nRIwEfhv3IErEDuB9YC/+9SJNab+hhNmQW8iylnlr+C0tupbaf1pqYbU1ZvaTZm+7Brg9X2MqVu2t\npZmdAfx/4DeFHmsxaE89Uz9xNgBvxjHWYtDO7+c8dx9MWH/rZwUfbMK1s5bdgD+6+4+A72fz+fk8\nwv/EomtmthuhoZ9GWGDtXDPrmfrRZAIwy9212tInZV1LAHd/1N0HEa6RkE9qTz0HAMcB3wIuNDNd\nQ/JJWdczbZr2RsJRvvyr9nw3mwh1hPCTU5tyvfCqTe4+L3WFbrq+wNrUwmqY2W8IC66dApwMfMbM\nDnf3u/M1rmLUnlqa2ReArwOfBp4p4DCLRnvq6e7XpLbPB97UdSWf1M7vZw9C1FgB3FbAYRaFdvbN\nW4HbzKw/UJfN5+et4bfiEOD1tO0m4Fh3vwT9z2+v1mr5LPBsPEMqai3Wc+eGu0/5xDskk9a+n+OB\nR+IZUtFqrZYfAhe054MKfdJWR0fRUS2jpXpGS/WMTmS1LHTDXwd0Tdvuis7U50q1jJbqGS3VMzqR\n1bLQDf9pEt7HAAAAiUlEQVQF4AgzqzSzPQlTMGcWeAylQrWMluoZLdUzOpHVMp/TMqcBC4BuZva6\nmQ13923AD4AnCVPdfuvuK/M1hlKhWkZL9YyW6hmdfNdSi6eJiJSJRFxpKyIi+aeGLyJSJtTwRUTK\nhBq+iEiZUMMXESkTavgiImVCDV9EpEyo4YuIlAk1fBGRMvF/VmlFVQ7pinMAAAAASUVORK5CYII=\n",
	"text/plain": [
	"<matplotlib.figure.Figure at 0x1fbdcb38>"
	]
	},
	"metadata": {},
	"output_type": "display_data"
	}
	],
	"source": [
	"times = [109, 138, 169, 192, 222]\n",
	"\n",
	"%matplotlib inline\n",
	"import matplotlib.pyplot as plt\n",
	"plt.semilogx(ns, times, '.-')\n",
	"plt.grid(True)"
	]
	}
	],
	"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.10"
	}
	},
	"nbformat": 4,
	"nbformat_minor": 0
	}
No results found