Projet-info-samuel.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Elements logiciels pour le traitement des données en grande dimension"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Installation de pyspark"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import findspark\n",
    "sparkHome = \"C:\\Dev\\Spark\\spark-2.2.0-bin-hadoop2.7\"\n",
    "findspark.init(sparkHome)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Petit essai pour calculer PI"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def printSpendTime (startTime) :\n",
    "    spendTime = time.time() - startTime\n",
    "    m, s = divmod(spendTime, 60)\n",
    "    h, m = divmod(m, 60)\n",
    "    print(\"--------------------------------------------------\")\n",
    "    print (\"-----   Temps écoulé : %dh%02dm%02ds\" % (h, m, s))\n",
    "    print(\"--------------------------------------------------\")\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nimport pyspark\\nimport random\\nimport time\\n\\nstartTime = time.time()\\n\\nsc = pyspark.SparkContext(appName=\"Pi\")\\nnum_samples = 100000000\\n\\ndef inside(p):     \\n  x, y = random.random(), random.random()\\n  return x*x + y*y < 1\\n\\ncount = sc.parallelize(range(0, num_samples)).filter(inside).count()\\n\\npi = 4 * count / num_samples\\nprint(pi)\\n\\nsc.stop()\\n\\nprintSpendTime(startTime)\\n'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "import pyspark\n",
    "import random\n",
    "import time\n",
    "\n",
    "startTime = time.time()\n",
    "\n",
    "sc = pyspark.SparkContext(appName=\"Pi\")\n",
    "num_samples = 100000000\n",
    "\n",
    "def inside(p):     \n",
    "  x, y = random.random(), random.random()\n",
    "  return x*x + y*y < 1\n",
    "\n",
    "count = sc.parallelize(range(0, num_samples)).filter(inside).count()\n",
    "\n",
    "pi = 4 * count / num_samples\n",
    "print(pi)\n",
    "\n",
    "sc.stop()\n",
    "\n",
    "printSpendTime(startTime)\n",
    "'''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Arbre k-d classique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Création d'un jeu de données"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>X</th>\n",
       "      <th>Y</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>30.674486</td>\n",
       "      <td>74.483784</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>45.611507</td>\n",
       "      <td>33.289203</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>66.720810</td>\n",
       "      <td>85.330904</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3.334040</td>\n",
       "      <td>70.346150</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>64.522692</td>\n",
       "      <td>20.628539</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>74.540500</td>\n",
       "      <td>88.996181</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>0.491450</td>\n",
       "      <td>61.015777</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>49.378190</td>\n",
       "      <td>26.759434</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>39.273316</td>\n",
       "      <td>78.196802</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>85.380725</td>\n",
       "      <td>90.455667</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "           X          Y\n",
       "0  30.674486  74.483784\n",
       "1  45.611507  33.289203\n",
       "2  66.720810  85.330904\n",
       "3   3.334040  70.346150\n",
       "4  64.522692  20.628539\n",
       "5  74.540500  88.996181\n",
       "6   0.491450  61.015777\n",
       "7  49.378190  26.759434\n",
       "8  39.273316  78.196802\n",
       "9  85.380725  90.455667"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import pandas\n",
    "\n",
    "n = 10\n",
    "data = pandas.DataFrame(np.random.rand(n,2)*100,  columns = ['X', 'Y'])\n",
    "data.iloc[0:10, ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAEaRJREFUeJzt3V+MHWd5x/HvU/8Rm7Ro82cT2WtS\nJ5JlQFiJ6SoKpEVtjGr+RGRrJTSIVhZy6xtUArSGmIsipCITGTVwUSFZSZErURJjjB1xETcyoWov\n6rJmoU4wloMJjtcmXsBLKazANk8vzixxwq7PHPucPWff8/1I1jnz7ozn0Wj82/E7884bmYkkaeH7\nnW4XIElqDwNdkgphoEtSIQx0SSqEgS5JhTDQJakQBrokFcJAl6RCGOiSVIjF87mz66+/PleuXDmf\nu5SkBe/QoUM/ysyhZuvNa6CvXLmSsbGx+dylJC14EfGDOuvZ5SJJhTDQJakQBrokFcJAl6RCGOiS\nVIh5fcpFkvrJ3vEJtu8/yqmpaZYPDrBl/WpG1w53bH+1rtAj4oGIeCYino2ID1Zt10bEUxFxrPq8\npmNVStICs3d8gq17DjMxNU0CE1PTbN1zmL3jEx3bZ9NAj4g3AH8N3A7cCtwdEauAB4EDmbkKOFAt\nS5KA7fuPMn3uwsvaps9dYPv+ox3bZ50r9NcB/5WZv8jM88C/A38G3APsrNbZCYx2pkRJWnhOTU23\n1N4OdfrQnwE+GRHXAdPAO4Ax4MbMPA2Qmacj4oaOVSlJlzDffdV1LB8cYGKW8F4+ONCxfTa9Qs/M\nI8BDwFPAk8C3gfN1dxARmyNiLCLGJicnL7tQSZpNN/qq69iyfjUDSxa9rG1gySK2rF/dsX3Wuima\nmY9m5hsz8y3AT4BjwIsRsQyg+jwzx7Y7MnMkM0eGhpq+W0aSWtKNvuo6RtcOs23DGoYHBwhgeHCA\nbRvWdPR/DrUeW4yIGzLzTETcBGwA3gTcDGwEPlV97utYlZI0h270Vdc1unZ4Xrt+6j6H/uWqD/0c\n8P7MPBsRnwJ2RcQm4ARwX6eKlKS5dKOvulfVCvTM/KNZ2n4MrGt7RZLUgi3rV7N1z+GXdbt0uq+6\nVzlSVNKCNtOl0WtPuXSDgS5pwZvvvupe5cu5JKkQBrokFcJAl6RC2Icuqe16cSh+PzDQJbXVzFD8\nmccIZ4biA4Z6h9nlIqmtenUofj8w0CW1VS8PxS+dgS6preYact+PQ/Hnm4Euqa268dpYNXhTVFJb\nORS/ewx0SW3nUPzusMtFkgphoEtSIQx0SSqEgS5JhTDQJakQBrokFaJWoEfEhyLi2Yh4JiK+GBGv\nioibI+JgRByLiMcjYmmni5Ukza1poEfEMPABYCQz3wAsAu4HHgIezsxVwFlgUycLlSRdWt0ul8XA\nQEQsBq4CTgN3Aburn+8ERttfniSprqaBnpkTwKeBEzSC/KfAIWAqM89Xq50EHBYmSV1Up8vlGuAe\n4GZgOXA18PZZVs05tt8cEWMRMTY5OXkltUqSLqFOl8tbge9n5mRmngP2AG8GBqsuGIAVwKnZNs7M\nHZk5kpkjQ0NDbSlakvTb6ryc6wRwR0RcBUwD64Ax4GngXuAxYCOwr1NFSnU4j6X6XZ0+9IM0bn5+\nEzhcbbMD+Cjw4Yh4DrgOeLSDdUqXNDOP5cTUNMlL81juHZ/odmnSvKn1+tzM/Djw8Vc0Hwdub3tF\n0mW41DyWXqWrXzhSVEVwHkvJQFchnMdSMtBVCOexlJyCToVwHkvJQFdBnMdS/c4uF0kqhIEuSYWw\ny0Vt5WhNqXsMdLXNzGjNmQE+M6M1AUNdmgd2uahtLjVaU1LnGehqG0drSt1loKttHK0pdZeBrrZx\ntKbUXd4UVds4WlPqLgNdbeVoTal77HKRpEIY6JJUCANdkgphoEtSIZreFI2I1cDjFzXdAvw98C9V\n+0rgeeDdmXm2/SXW4ztEJPW7plfomXk0M2/LzNuAPwB+AXwFeBA4kJmrgAPVclc447sktd7lsg74\nXmb+ALgH2Fm17wRG21lYK3yHiCS1Huj3A1+svt+YmacBqs8b2llYK3yHiCS1EOgRsRR4F/ClVnYQ\nEZsjYiwixiYnJ1utrxbfISJJrV2hvx34Zma+WC2/GBHLAKrPM7NtlJk7MnMkM0eGhoaurNo5+A4R\nSWot0N/DS90tAE8AG6vvG4F97SqqVaNrh9m2YQ3DgwMEMDw4wLYNa3zKRVJficxsvlLEVcALwC2Z\n+dOq7TpgF3ATcAK4LzN/cqm/Z2RkJMfGxq64aEnqJxFxKDNHmq1X6+VcmfkL4LpXtP2YxlMvkqQe\n4EhRSSqEgS5JhTDQJakQBrokFcJAl6RCGOiSVAgDXZIKYaBLUiEMdEkqhIEuSYUw0CWpEAa6JBXC\nQJekQhjoklQIA12SCmGgS1IhDHRJKoSBLkmFqDUFXTftHZ9g+/6jnJqaZvngAFvWr3byZ0maRU8H\n+t7xCbbuOcz0uQsATExNs3XPYQBDXZJeoVaXS0QMRsTuiPhuRByJiDdFxLUR8VREHKs+r2l3cdv3\nH/1NmM+YPneB7fuPtntXkrTg1e1D/yzwZGa+FrgVOAI8CBzIzFXAgWq5rU5NTbfULkn9rGmgR8Sr\ngbcAjwJk5q8ycwq4B9hZrbYTGG13ccsHB1pql6R+VucK/RZgEvh8RIxHxCMRcTVwY2aeBqg+b5ht\n44jYHBFjETE2OTnZUnFb1q9mYMmil7UNLFnElvWrW/p7JKkf1An0xcAbgc9l5lrg57TQvZKZOzJz\nJDNHhoaGWipudO0w2zasYXhwgACGBwfYtmGNN0QlaRZ1nnI5CZzMzIPV8m4agf5iRCzLzNMRsQw4\n04kCR9cOG+CSVEPTK/TM/CHwQkTM9HOsA74DPAFsrNo2Avs6UqEkqZa6z6H/DfCFiFgKHAfeR+OX\nwa6I2AScAO7rTImSpDpqBXpmfgsYmeVH69pbjiTpcvkuF0kqhIEuSYUw0CWpEAa6JBXCQJekQhjo\nklQIA12SCmGgS1IhDHRJKoSBLkmFMNAlqRAGuiQVwkCXpEIY6JJUCANdkgphoEtSIQx0SSqEgS5J\nhTDQJakQteYUjYjngZ8BF4DzmTkSEdcCjwMrgeeBd2fm2c6UKUlqppUr9D/JzNsyc2ay6AeBA5m5\nCjhQLUuSuuRKulzuAXZW33cCo1dejiTpctUN9AT+LSIORcTmqu3GzDwNUH3e0IkCJUn11OpDB+7M\nzFMRcQPwVER8t+4Oql8AmwFuuummyyhRklRHrSv0zDxVfZ4BvgLcDrwYEcsAqs8zc2y7IzNHMnNk\naGioPVVLkn5L00CPiKsj4vdmvgN/CjwDPAFsrFbbCOzrVJGSpObqdLncCHwlImbW/9fMfDIivgHs\niohNwAngvs6VKUlqpmmgZ+Zx4NZZ2n8MrOtEUZKk1jlSVJIKYaBLUiEMdEkqhIEuSYUw0CWpEAa6\nJBXCQJekQhjoklQIA12SCmGgS1IhDHRJKoSBLkmFMNAlqRAGuiQVwkCXpEIY6JJUCANdkgphoEtS\nIQx0SSpE7UCPiEURMR4RX62Wb46IgxFxLCIej4ilnStTktRMK1foDwBHLlp+CHg4M1cBZ4FN7SxM\nktSaWoEeESuAdwKPVMsB3AXsrlbZCYx2okBJUj11r9A/A3wE+HW1fB0wlZnnq+WTwHCba5MktaBp\noEfE3cCZzDx0cfMsq+Yc22+OiLGIGJucnLzMMiVJzdS5Qr8TeFdEPA88RqOr5TPAYEQsrtZZAZya\nbePM3JGZI5k5MjQ01IaSJUmzaRrombk1M1dk5krgfuBrmfle4Gng3mq1jcC+jlUpSWrqSp5D/yjw\n4Yh4jkaf+qPtKUmSdDkWN1/lJZn5deDr1ffjwO3tL0mSdDkcKSpJhTDQJakQBrokFcJAl6RCGOiS\nVAgDXZIKYaBLUiEMdEkqhIEuSYUw0CWpEAa6JBWipXe5SP1q7/gE2/cf5dTUNMsHB9iyfjWja53T\nRb3FQJea2Ds+wdY9h5k+dwGAialptu45DGCoq6fY5SI1sX3/0d+E+YzpcxfYvv9olyqSZmegS02c\nmppuqV3qFgNdamL54EBL7VK3GOhSE1vWr2ZgyaKXtQ0sWcSW9au7VJE0O2+KSk3M3Pj0KRf1OgNd\nqmF07bABrp5nl4skFaJpoEfEqyLivyPi2xHxbER8omq/OSIORsSxiHg8IpZ2vlxJ0lzqXKH/Ergr\nM28FbgPeFhF3AA8BD2fmKuAssKlzZUqSmmka6Nnwf9XikupPAncBu6v2ncBoRyqUJNVSqw89IhZF\nxLeAM8BTwPeAqcw8X61yEpj1jlFEbI6IsYgYm5ycbEfNkqRZ1Ar0zLyQmbcBK4DbgdfNttoc2+7I\nzJHMHBkaGrr8SiVJl9TSUy6ZOQV8HbgDGIyImcceVwCn2luaJKkVdZ5yGYqIwer7APBW4AjwNHBv\ntdpGYF+nipQkNVdnYNEyYGdELKLxC2BXZn41Ir4DPBYR/wCMA492sE5JUhNNAz0z/wdYO0v7cRr9\n6ZKkHuBIUUkqhO9ykTrEaes03wx0qQOctk7dYJeL1AFOW6duMNClDnDaOnWDgS51gNPWqRsMdKkD\nnLZO3eBNUakDnLZO3WCgSx3itHWab3a5SFIhDHRJKoSBLkmFMNAlqRAGuiQVwkCXpEIY6JJUCANd\nkgphoEtSIRwpKqllTt7Rm5peoUfEayLi6Yg4EhHPRsQDVfu1EfFURByrPq/pfLmSum1m8o6JqWmS\nlybv2Ds+0e3S+l6dLpfzwN9m5uuAO4D3R8TrgQeBA5m5CjhQLUsqnJN39K6mgZ6ZpzPzm9X3nwFH\ngGHgHmBntdpOYLRTRUrqHU7e0btauikaESuBtcBB4MbMPA2N0AduaHdxknqPk3f0rtqBHhG/C3wZ\n+GBm/m8L222OiLGIGJucnLycGiX1ECfv6F21Aj0iltAI8y9k5p6q+cWIWFb9fBlwZrZtM3NHZo5k\n5sjQ0FA7apbURaNrh9m2YQ3DgwMEMDw4wLYNa3zKpQc0fWwxIgJ4FDiSmf940Y+eADYCn6o+93Wk\nQkk9x8k7elOd59DvBP4SOBwR36raPkYjyHdFxCbgBHBfZ0qUJNXRNNAz8z+BmOPH69pbjiTpcjn0\nX5IKYaBLUiEMdEkqRGTm/O0sYhL4QYubXQ/8qAPllMLjc2ken7l5bC6tl47P72dm0+e+5zXQL0dE\njGXmSLfr6FUen0vz+MzNY3NpC/H42OUiSYUw0CWpEAsh0Hd0u4Ae5/G5NI/P3Dw2l7bgjk/P96FL\nkupZCFfokqQaejrQI+JtEXE0Ip6LiL6eEcmpAOuJiEURMR4RX62Wb46Ig9XxeTwilna7xm6JiMGI\n2B0R363Oozd5/jRExIeqf1fPRMQXI+JVC/Hc6dlAj4hFwD8BbwdeD7ynmvquXzkVYD0P0JhVa8ZD\nwMPV8TkLbOpKVb3hs8CTmfla4FYax6nvz5+IGAY+AIxk5huARcD9LMBzp2cDHbgdeC4zj2fmr4DH\naEx715ecCrC5iFgBvBN4pFoO4C5gd7VK3x6fiHg18BYar8ImM3+VmVN4/sxYDAxExGLgKuA0C/Dc\n6eVAHwZeuGj5ZNXW95wKcE6fAT4C/Lpavg6Yyszz1XI/n0O3AJPA56suqUci4mo8f8jMCeDTNF4D\nfhr4KXCIBXju9HKgz/bK3r5/JOdypwIsXUTcDZzJzEMXN8+yar+eQ4uBNwKfy8y1wM/pw+6V2VT3\nDe4BbgaWA1fT6Op9pZ4/d3o50E8Cr7loeQVwqku19IQrmQqwD9wJvCsinqfRPXcXjSv2weq/0dDf\n59BJ4GRmHqyWd9MIeM8feCvw/cyczMxzwB7gzSzAc6eXA/0bwKrqTvNSGjcpnuhyTV1TYypA6OOp\nADNza2auyMyVNM6Vr2Xme4GngXur1fr5+PwQeCEiZmZyXgd8B88faHS13BERV1X/zmaOzYI7d3p6\nYFFEvIPGVdYi4J8z85NdLqlrIuIPgf8ADvNSH/HHaPSj7wJuopoKMDN/0pUie0RE/DHwd5l5d0Tc\nQuOK/VpgHPiLzPxlN+vrloi4jcYN46XAceB9NC7q+v78iYhPAH9O42myceCvaPSZL6hzp6cDXZJU\nXy93uUiSWmCgS1IhDHRJKoSBLkmFMNAlqRAGuiQVwkCXpEIY6JJUiP8Htzv2BLfFnqsAAAAASUVO\nRK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1cb57a50fd0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.plot(data[['X']], data[['Y']], 'o')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Définition d'une structure de données pour les arbres binaires"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### Classe permettant de definir un arbre binaire simple\n",
    "### Il se constitue d'un noeud racine, de deux sous-arbres\n",
    "### et des donnees correspondant au noeud racine\n",
    "class Tree(object) :\n",
    "    \n",
    "    ## Constructeur simple\n",
    "    def __init__(self) :\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.key = None\n",
    "        self.data = None\n",
    "    \n",
    "    ## Reprensation de l'arbre sous forme de chaine\n",
    "    ## de caracteres\n",
    "    def __str__(self) :\n",
    "        return self.strRec(0)\n",
    "    \n",
    "    ## Represente l'arbre sous forme de chaine de caracteres\n",
    "    ## de facon recursive\n",
    "    def strRec(self, depth) :\n",
    "        line = \"-\" * 3 * depth\n",
    "        res = line + str(self.data)\n",
    "        if self.left :\n",
    "            res += \"\\n\" + self.left.strRec(depth+1)\n",
    "        if self.right :\n",
    "            res += \"\\n\" + self.right.strRec(depth+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.lines as lines\n",
    "\n",
    "### Trace un arbre k-d (classe 'Tree') de facon recursive\n",
    "def pltTreeRec(ax, tree, keyX, keyY, xLim, yLim) :\n",
    "    if tree :\n",
    "        x, y = tree.data[keyX], tree.data[keyY]\n",
    "        if tree.key == keyX :\n",
    "            pltTreeRec(ax, tree.left, keyX, keyY, (xLim[0], x), yLim)\n",
    "            pltTreeRec(ax, tree.right, keyX, keyY, (x, xLim[1]), yLim)\n",
    "            ax.add_line(lines.Line2D((x, x), yLim, linewidth=0.5, color='red'))\n",
    "        elif tree.key == keyY :\n",
    "            pltTreeRec(ax, tree.left, keyX, keyY, xLim, (yLim[0], y))\n",
    "            pltTreeRec(ax, tree.right, keyX, keyY, xLim, (y, yLim[1]))\n",
    "            ax.add_line(lines.Line2D(xLim, (y, y), linewidth=0.5, color='red'))\n",
    "        plt.plot(x, y, 'o', color='#1f77b4')\n",
    "\n",
    "### Trace un jeu de donnees et l'arbre k-d associe.\n",
    "### Le parametre 'tree' doit etre une instance de la \n",
    "### classe 'Tree'\n",
    "def plotDataTree(data, tree) :\n",
    "    colList = data.columns.values.tolist()\n",
    "    keyX, keyY = colList[0], colList[1]\n",
    "    ax = plt.axes()\n",
    "    plt.plot(data[['X']], data[['Y']], 'o', color='#1f77b4')\n",
    "    xLim, yLim = ax.get_xlim(), ax.get_ylim()\n",
    "    pltTreeRec(ax, tree, keyX, keyY, xLim, yLim)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algorithme \"naïf\" pour constituer un arbre k-d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>\n",
    "On propose une première implémentation, \"naïve\", pour la constitution d'un arbre k-d. Le principe : on découpe de façon cyclique selon les différentes dimension ; à chaque étape on recherche la médiane du tableau (donc une opération de tri) selon la dimension courante ; on lui attache deux sous-arbres correspondants aux valeurs inférieures (resp. supérieures) à la médiane.\n",
    "</p>\n",
    "<p>\n",
    "D'après Bentley, si on est en mesure de trouver la médiane en $O(n)$, la complexité de l'algorithme est en $O(n\\log(n))$.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### Fonction recursive pour constituer un arbre k-d\n",
    "def arbreKDnaifRec (data, colList, curCol) :\n",
    "    nCol = len(colList)\n",
    "    nRow = data.shape[0]\n",
    "    sortCol = colList[curCol]\n",
    "    if nRow == 0 :\n",
    "        return None\n",
    "    elif nRow == 1 :\n",
    "        dataNode = data.iloc[0,]\n",
    "        rootNode = Tree()\n",
    "        rootNode.key = sortCol\n",
    "        rootNode.data = dict()\n",
    "        for col in colList :\n",
    "            rootNode.data[col] = dataNode[col].item()\n",
    "        return rootNode\n",
    "    median = int(nRow / 2)\n",
    "    if nRow % 2 == 1 :\n",
    "        median = int((nRow-1) / 2)\n",
    "    nextCol = (curCol + 1) % nCol\n",
    "    #if nextCol > nCol :\n",
    "    #    nextCol = 0\n",
    "    dataSort = data.sort_values(by=sortCol)\n",
    "    dataNode = dataSort.iloc[median,]\n",
    "    rootNode = Tree()\n",
    "    rootNode.key = sortCol\n",
    "    rootNode.data = dict()\n",
    "    for col in colList :\n",
    "        rootNode.data[col] = dataNode[col].item()\n",
    "    rootNode.left = arbreKDnaifRec(dataSort.iloc[0:median,], colList, nextCol)\n",
    "    rootNode.right = arbreKDnaifRec(dataSort.iloc[(median+1):nRow,], colList, nextCol)\n",
    "    return rootNode\n",
    "\n",
    "### Fonction englobante permettant la construction d'un arbre k-d\n",
    "def arbreKDnaif (data) :\n",
    "    colList = data.columns.values.tolist()\n",
    "    curCol = 0\n",
    "    return(arbreKDnaifRec(data, colList, curCol))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'X': 49.37819040066077, 'Y': 26.759433858493452}\n",
      "---{'X': 3.3340403954696174, 'Y': 70.34615028413086}\n",
      "------{'X': 45.61150668319305, 'Y': 33.28920293806107}\n",
      "---------{'X': 0.4914501615307709, 'Y': 61.01577697077555}\n",
      "------{'X': 39.273315526831844, 'Y': 78.19680246760275}\n",
      "---------{'X': 30.674486173893424, 'Y': 74.48378354038319}\n",
      "---{'X': 74.54049982644099, 'Y': 88.99618079028801}\n",
      "------{'X': 66.72081020386534, 'Y': 85.33090379515743}\n",
      "---------{'X': 64.52269220061821, 'Y': 20.62853942009507}\n",
      "------{'X': 85.38072486303344, 'Y': 90.45566670187175}\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAEyBJREFUeJzt3W+MXNd93vHvw5VVW0oD/fFKYESy\nlF3CsWHCtLuQ6Lg1XMkt4sSw2EJKTYQBFbBlXxiNnKSIRYNoFYABJCCInRdFAMJqxEAuLUG2KcEQ\njAqMVLQvxGRpbUrJdCBHoSlGjLhxpMSNDdtc/vpiLiXSWnJnqJ2d3TPfD0DM3DN3OL+5e/fh5bn3\n3JOqQpK08q0adQGSpMVhoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIacdlSftjb\n3/72Wr9+/VJ+pCSteIcPH/6bqppcaL0lDfT169czPT29lB8pSSteku/0s55dLpLUCANdkhphoEtS\nIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOhq0wMPjLqC5VGDFt8y/rka6GrTsWOjrmB51KDFt4x/\nrga6JDXCQJekRhjoktQIA12SGmGgS1Ifdh84wjt3Pc76H0zxzl2Ps/vAkVGX9AZ9BXqSu5I8m+S5\nJJ/u2q5J8kSS57vHq4dbqiSNxu4DR3jw6ePMVUHCXBUPPn182YX6goGe5L3AfwBuAt4HfDzJBuBu\n4GBVbQAOdsuS1Jz9h14cqH1U+jlCfzfwdFV9v6pOA/8L+DfAbcC+bp19wJbhlChJozVXNVD7qPQz\nBd2zwO8kuRb4AfALwDRwfVWdBKiqk0mum+/NSXYCOwHWrVu3KEVLat/uA0fYf+hF5qqYSNh681r2\nbNk4klomum6W+dqXkwWP0KvqKHAf8ATwdeDPgNP9fkBV7a2qqaqampxccI5TSTq/zxpG3me99ea1\nA7WPSl8nRavq/qr6QFV9GPhb4Hng5SSrAbrHU8MrU9I4WW591nu2bGTb5nW9I/LufwzbNq8b2f8Y\nLqSfLheSXFdVp5KsA/4t8EHgRmA7cG/3+OjQqpRWopkZuOeeUVcxXDMzsGnTov+1c2emYJ7ujLkz\nZ0a2TfcAe/4Rr3/nmT+BmS/39+b16+HOO4dXXKevQAe+3PWh/xj4VFW9kuRe4OEkO4DjwB3DKlJa\nkTZtaj/Q77lnKN9xYtfj8/dZr1rV/jZ9E/oK9Kr6F/O0fRe4ddErkjT2tt68lgefPj5vuy6s3yN0\nSVoyZ/uml8tVLiuFgS5pWdqzZaMBPiDv5SJJjTDQJQ1sJdyoahzZ5SJpIGcH/QDn3agKsItkxDxC\nlzSQ5TboR68z0CUNZKXcqGocGeiSBnKhG1IttxtVjSMDXdJAVsqNqsaRJ0UlDeS8QT9nzjCxapWD\nfpYJA13SwF4b9DOke7no0tjlIkmNMNAlqREGuiQ1wkCXpEYY6JLUiL4CPcmvJ3kuybNJ9id5a5Ib\nkxxK8nySh5JcPuxiJUkXtmCgJ7kB+DVgqqreC0wAnwTuAz5XVRuAV4AdwyxUknRx/Xa5XAa8Lcll\nwBXASeAW4JHu9X3AlsUvT5LUrwUDvar+CvhdehNBnwT+DjgMvFpVp7vVTgA3DKtISdLC+ulyuRq4\nDbgR+BngSuBj86w6763WkuxMMp1kenZ29s3UKkm6iH66XD4K/GVVzVbVj4GvAD8HXNV1wQCsAV6a\n781VtbeqpqpqanJyclGKliS9UT+BfhzYnOSKJAFuBb4JPAnc3q2zHXh0OCVK/XNqNI2zfvrQD9E7\n+fkN4Ej3nr3AZ4DfSPJt4Frg/iHWKS3o7NRoc1XnTY1mqGtc9HWVS1X916r62ap6b1X9SlX9sKpe\nqKqbquqfVtUdVfXDYRcrXYxTo2ncOVJUzXBqNI07A13NcGo0jTsDXc1wajSNO2csUjOcGk3jzkBX\nU5waTePMLhdJaoRH6Bqq3QeO9LpAqphI7AKRhshA19CcHehz1tmBPoChLg2BXS4aGgf6SEtr5Ryh\nP/AAHDs26io0gLkzUzDPNeBzZ84M/4TlzMxw/35pGVo5gX7nnaOuQAOa2PX4vKM0J1atGn6ge4WL\nxpBdLhoaB/pIS2vlHKFrxTlvoI9XuUhDZ6BrqF4b6CNp6OxykaRGGOiS1AgDXZIasWAfepJ3AQ+d\n0/QO4L8Af9S1rweOAb9UVa8sfonD47B0SS3pZ07RP6+qTVW1CfhnwPeBrwJ3AweragNwsFteMc6b\nfxKcf1LSijdol8utwF9U1XeA24B9Xfs+YMtiFjZsDkuX1JpBL1v8JLC/e359VZ0EqKqTSa5b1Mp+\n0iIP/R/psHQN38zM4v8cZ2Zg06bB1peWUN+BnuRy4BPArkE+IMlOYCfAunXrBiruPIs89H+kw9K1\nMg06aYb7kZbYIF0uHwO+UVUvd8svJ1kN0D2emu9NVbW3qqaqampycvLNVbuIHJYuqTWDBPpWXu9u\nAXgM2N493w48ulhFLYU9WzaybfO612aEn0jYtnmdV7lIWrH66nJJcgXwr4D/eE7zvcDDSXYAx4E7\nFr+84XJYuqSW9BXoVfV94NqfaPsuvateJEnLgCNFJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMM\ndElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJasSgk0SvGLsPHGH/oReZq2Ii\nYevNa53MQlLTmgz03QeO8ODTx19bnqt6bdlQl9SqvrpcklyV5JEk30pyNMkHk1yT5Ikkz3ePVw+7\n2H7tP/TiQO2S1IJ+j9B/H/h6Vd2e5HLgCuCzwMGqujfJ3cDdwGeGVCc88AAcO9bXqnNnpqCb/Pn8\n9jNwzz2LWpbGyMzMqCuQLmrBQE/y08CHgTsBqupHwI+S3AZ8pFttH/AUwwz0O+/se9WJXY8zV/XG\n9lWrDHRdOvcdLXP9dLm8A5gF/jDJM0m+kORK4PqqOgnQPV43xDoHsvXmtQO1S1IL+gn0y4APAH9Q\nVe8H/oFe90pfkuxMMp1kenZ29hLLHMyeLRvZtnkdE123y0TCts3rPCEqqWn99KGfAE5U1aFu+RF6\ngf5yktVVdTLJauDUfG+uqr3AXoCpqak39oMMyZ4tGw1wSWNlwSP0qvpr4MUk7+qabgW+CTwGbO/a\ntgOPDqVCSVJf+r3K5T8BX+yucHkB+FV6/xg8nGQHcBy4YzglSpL60VegV9UMMDXPS7cubjmSpEvl\nvVwkqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgD\nXZIaYaBLUiMMdElqhIEuSY0w0CWpEX3NWJTkGPA9YA44XVVTSa4BHgLWA8eAX6qqV4ZTpiRpIYMc\nof/LqtpUVWenorsbOFhVG4CD3bIkaUTeTJfLbcC+7vk+YMubL0eSdKn6DfQC/meSw0l2dm3XV9VJ\ngO7xuvnemGRnkukk07Ozs2++YknSvPrqQwc+VFUvJbkOeCLJt/r9gKraC+wFmJqaqkuoUZLUh76O\n0Kvqpe7xFPBV4Cbg5SSrAbrHU8MqUpK0sAUDPcmVSf7x2efAvwaeBR4DtnerbQceHVaRkqSF9dPl\ncj3w1SRn1/8fVfX1JH8KPJxkB3AcuGN4ZUqSFrJgoFfVC8D75mn/LnDrMIqSJA3OkaKS1AgDXZIa\nYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREG\nuiQ1wkCXpEb0HehJJpI8k+Rr3fKNSQ4leT7JQ0kuH16ZkqSFDHKEfhdw9Jzl+4DPVdUG4BVgx2IW\nJkkaTF+BnmQN8IvAF7rlALcAj3Sr7AO2DKNASVJ/+j1C/zzwW8CZbvla4NWqOt0tnwBuWOTaJEkD\nWDDQk3wcOFVVh89tnmfVusD7dyaZTjI9Ozt7iWVKkhbSzxH6h4BPJDkGfIleV8vngauSXNatswZ4\nab43V9XeqpqqqqnJyclFKFmSNJ8FA72qdlXVmqpaD3wS+OOq+mXgSeD2brXtwKNDq1KStKA3cx36\nZ4DfSPJten3q9y9OSZKkS3HZwqu8rqqeAp7qnr8A3LT4JUmSLoUjRSWpEQa6JDXCQJekRhjoktQI\nA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGurSA3QeO8M5dj7P+B1O8c9fj7D5wZNQlSfMaaOi/NG52\nHzjCg08f7y0kzFW9trxny8YRVia9kUfo0kXsP/TiQO3SKBno0kXM1bzztlywXRolA126iInMNznX\nhdulUTLQpYvYevPagdqlUfKkqHQRZ0987j/0InNnzjCxahVbb17rCVEtSwa6tIA9Wzb2Avyee3p/\npGVqwS6XJG9N8idJ/izJc0l+u2u/McmhJM8neSjJ5cMvV5J0If30of8QuKWq3gdsAn4+yWbgPuBz\nVbUBeAXYMbwyJUkLWTDQq+f/dYtv6f4UcAvwSNe+D9gylAolSX3p6yqXJBNJZoBTwBPAXwCvVtXp\nbpUTwA3DKVGS1I++Ar2q5qpqE7AGuAl493yrzffeJDuTTCeZnp2dvfRKJUkXNdB16FX1KvAUsBm4\nKsnZq2TWAC9d4D17q2qqqqYmJyffTK2SpIvo5yqXySRXdc/fBnwUOAo8CdzerbYdeHRYRUqSFtbP\ndeirgX1JJuj9A/BwVX0tyTeBLyXZAzwD3D/EOiVJC1gw0Kvq/wLvn6f9BXr96ZKkZcB7uUiLzAkx\nNCoO/ZcWkRNiaJQ8QpcWkRNiaJQMdGkROSGGRslAlxaRE2JolAx0aRE5IYZGyZOi0iJyQgyNkoEu\nLTInxNCo2OUiSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoQDiyTNa/eBI70Rr1VM\nJI54XQH6mVN0bZInkxxN8lySu7r2a5I8keT57vHq4ZcraSmcva/72btEnr2vu5N1LG/9dLmcBn6z\nqt4NbAY+leQ9wN3AwaraABzsliU1wPu6r0z9zCl6EjjZPf9ekqPADcBtwEe61fYBTwGfGUqV0ko0\nM7Ni7+Uyd2YK5rnl79yZM+d/p5mZpStKCxqoDz3JenoTRh8Cru/Cnqo6meS6Ra9OWsk2bVqxgT6x\n6/F5J+WYWLXq/O+0Qr9fq/q+yiXJTwFfBj5dVX8/wPt2JplOMj07O3spNUpaYt7XfWXqK9CTvIVe\nmH+xqr7SNb+cZHX3+mrg1Hzvraq9VTVVVVOTk5OLUbOkIduzZSPbNq97baaliYRtm9d5lcsyt2CX\nS5IA9wNHq+r3znnpMWA7cG/3+OhQKpQ0Eq/d110rRj996B8CfgU4kuTsGZDP0gvyh5PsAI4Ddwyn\nRElSP/q5yuX/ABea4fbWxS1HknSpHPovSY0w0CWpEQa61K/164e7/ko0Dt9xBUnNM3hgWKampmp6\nenrJPk+SWpDkcFVNLbSeR+iS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRizpwKIk\ns8B3lujj3g78zRJ91nLlNuhxO7gNYGVvg39SVQtOKLGkgb6Ukkz3M7KqZW6DHreD2wDGYxvY5SJJ\njTDQJakRLQf63lEXsAy4DXrcDm4DGINt0GwfuiSNm5aP0CVprDQZ6El+PsmfJ/l2krtHXc9SSLI2\nyZNJjiZ5LsldXfs1SZ5I8nz3ePWoax22JBNJnknytW75xiSHum3wUJLLR13jMCW5KskjSb7V7Q8f\nHLf9IMmvd78HzybZn+St47AfNBfoSSaA/wZ8DHgPsDXJe0Zb1ZI4DfxmVb0b2Ax8qvvedwMHq2oD\ncLBbbt1dwNFzlu8DPtdtg1eAHSOpaun8PvD1qvpZ4H30tsXY7AdJbgB+DZiqqvcCE8AnGYP9oLlA\nB24Cvl1VL1TVj4AvAbeNuKahq6qTVfWN7vn36P0S30Dvu+/rVtsHbBlNhUsjyRrgF4EvdMsBbgEe\n6VZpehsk+Wngw8D9AFX1o6p6lTHbD4DLgLcluQy4AjjJGOwHLQb6DcCL5yyf6NrGRpL1wPuBQ8D1\nVXUSeqEPXDe6ypbE54HfAs50y9cCr1bV6W659f3hHcAs8Iddt9MXklzJGO0HVfVXwO8Cx+kF+d8B\nhxmD/aDFQM88bWNzKU+SnwK+DHy6qv5+1PUspSQfB05V1eFzm+dZteX94TLgA8AfVNX7gX+g4e6V\n+XTnB24DbgR+BriSXhfsT2puP2gx0E8Aa89ZXgO8NKJallSSt9AL8y9W1Ve65peTrO5eXw2cGlV9\nS+BDwCeSHKPX1XYLvSP2q7r/ekP7+8MJ4ERVHeqWH6EX8OO0H3wU+Muqmq2qHwNfAX6OMdgPWgz0\nPwU2dGe0L6d3MuSxEdc0dF1f8f3A0ar6vXNeegzY3j3fDjy61LUtlaraVVVrqmo9vZ/7H1fVLwNP\nArd3q7W+Df4aeDHJu7qmW4FvMkb7Ab2uls1Jruh+L85ug+b3gyYHFiX5BXpHZhPAf6+q3xlxSUOX\n5J8D/xs4wuv9x5+l14/+MLCO3o5+R1X97UiKXEJJPgL856r6eJJ30DtivwZ4BthWVT8cZX3DlGQT\nvZPClwMvAL9K7+BtbPaDJL8N/Dt6V389A/x7en3mTe8HTQa6JI2jFrtcJGksGeiS1AgDXZIaYaBL\nUiMMdElqhIEuSY0w0CWpEQa6JDXi/wPxzAxdyaRJmQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1cb58cc7c88>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "### Test de la fonction 'arbreKDnaif' sur le \n",
    "### jeu de donnees 'data'\n",
    "arbre = arbreKDnaif(data)\n",
    "print(arbre)\n",
    "plotDataTree(data, arbre)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Construction d'un arbre k-d avec pré-tri par dimension"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>\n",
    "On implémente, toujours de façon non distribuée, un algorithme de construction d'un arbre k-d où le tri selon les différentes dimension du jeu de données est fait en amont.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### Fonction recursive pour constituer un arbre k-d\n",
    "def arbreKDpretriRec (sortedData, colList, curCol) :\n",
    "    nCol = len(colList)\n",
    "    sortCol = colList[curCol]\n",
    "    curData = sortedData[sortCol]\n",
    "    nRow = curData.shape[0]\n",
    "    if nRow == 0 :\n",
    "        return None\n",
    "    elif nRow == 1 :\n",
    "        dataNode = curData.iloc[0,]\n",
    "        rootNode = Tree()\n",
    "        rootNode.key = sortCol\n",
    "        rootNode.data = dict()\n",
    "        for col in colList :\n",
    "            rootNode.data[col] = dataNode[col].item()\n",
    "        return rootNode\n",
    "    median = int(nRow / 2)\n",
    "    if nRow % 2 == 1 :\n",
    "        median = int((nRow-1) / 2)\n",
    "    nextCol = (curCol + 1) % nCol\n",
    "    dataNode = curData.iloc[median,]\n",
    "    rootNode = Tree()\n",
    "    rootNode.key = sortCol\n",
    "    rootNode.data = dict()\n",
    "    for col in colList :\n",
    "        rootNode.data[col] = dataNode[col].item()\n",
    "    leftSortedData = dict()\n",
    "    rightSortedData = dict()\n",
    "    for col in colList :\n",
    "        leftSortedData[col] = sortedData[col][sortedData[col][sortCol]<rootNode.data[sortCol]]\n",
    "        rightSortedData[col] = sortedData[col][sortedData[col][sortCol]>rootNode.data[sortCol]]\n",
    "    rootNode.left = arbreKDpretriRec(leftSortedData, colList, nextCol)\n",
    "    rootNode.right = arbreKDpretriRec(rightSortedData, colList, nextCol)\n",
    "    return rootNode\n",
    "\n",
    "### Fonction englobante permettant la construction d'un arbre k-d\n",
    "def arbreKDpretri (data) :\n",
    "    colList = data.columns.values.tolist()\n",
    "    sortedData = dict()\n",
    "    for col in colList :\n",
    "        sortedData[col] = data.sort_values(by = col)\n",
    "    curCol = 0\n",
    "    return(arbreKDpretriRec(sortedData, colList, curCol))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'X': 49.37819040066077, 'Y': 26.759433858493452}\n",
      "---{'X': 3.3340403954696174, 'Y': 70.34615028413086}\n",
      "------{'X': 45.61150668319305, 'Y': 33.28920293806107}\n",
      "---------{'X': 0.4914501615307709, 'Y': 61.01577697077555}\n",
      "------{'X': 39.273315526831844, 'Y': 78.19680246760275}\n",
      "---------{'X': 30.674486173893424, 'Y': 74.48378354038319}\n",
      "---{'X': 74.54049982644099, 'Y': 88.99618079028801}\n",
      "------{'X': 66.72081020386534, 'Y': 85.33090379515743}\n",
      "---------{'X': 64.52269220061821, 'Y': 20.62853942009507}\n",
      "------{'X': 85.38072486303344, 'Y': 90.45566670187175}\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAEyBJREFUeJzt3W+MXNd93vHvw5VVW0oD/fFKYESy\nlF3CsWHCtLuQ6Lg1XMkt4sSw2EJKTYQBFbBlXxiNnKSIRYNoFYABJCCInRdFAMJqxEAuLUG2KcEQ\njAqMVLQvxGRpbUrJdCBHoSlGjLhxpMSNDdtc/vpiLiXSWnJnqJ2d3TPfD0DM3DN3OL+5e/fh5bn3\n3JOqQpK08q0adQGSpMVhoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIacdlSftjb\n3/72Wr9+/VJ+pCSteIcPH/6bqppcaL0lDfT169czPT29lB8pSSteku/0s55dLpLUCANdkhphoEtS\nIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOhq0wMPjLqC5VGDFt8y/rka6GrTsWOjrmB51KDFt4x/\nrga6JDXCQJekRhjoktQIA12SGmGgS1Ifdh84wjt3Pc76H0zxzl2Ps/vAkVGX9AZ9BXqSu5I8m+S5\nJJ/u2q5J8kSS57vHq4dbqiSNxu4DR3jw6ePMVUHCXBUPPn182YX6goGe5L3AfwBuAt4HfDzJBuBu\n4GBVbQAOdsuS1Jz9h14cqH1U+jlCfzfwdFV9v6pOA/8L+DfAbcC+bp19wJbhlChJozVXNVD7qPQz\nBd2zwO8kuRb4AfALwDRwfVWdBKiqk0mum+/NSXYCOwHWrVu3KEVLat/uA0fYf+hF5qqYSNh681r2\nbNk4klomum6W+dqXkwWP0KvqKHAf8ATwdeDPgNP9fkBV7a2qqaqampxccI5TSTq/zxpG3me99ea1\nA7WPSl8nRavq/qr6QFV9GPhb4Hng5SSrAbrHU8MrU9I4WW591nu2bGTb5nW9I/LufwzbNq8b2f8Y\nLqSfLheSXFdVp5KsA/4t8EHgRmA7cG/3+OjQqpRWopkZuOeeUVcxXDMzsGnTov+1c2emYJ7ujLkz\nZ0a2TfcAe/4Rr3/nmT+BmS/39+b16+HOO4dXXKevQAe+3PWh/xj4VFW9kuRe4OEkO4DjwB3DKlJa\nkTZtaj/Q77lnKN9xYtfj8/dZr1rV/jZ9E/oK9Kr6F/O0fRe4ddErkjT2tt68lgefPj5vuy6s3yN0\nSVoyZ/uml8tVLiuFgS5pWdqzZaMBPiDv5SJJjTDQJQ1sJdyoahzZ5SJpIGcH/QDn3agKsItkxDxC\nlzSQ5TboR68z0CUNZKXcqGocGeiSBnKhG1IttxtVjSMDXdJAVsqNqsaRJ0UlDeS8QT9nzjCxapWD\nfpYJA13SwF4b9DOke7no0tjlIkmNMNAlqREGuiQ1wkCXpEYY6JLUiL4CPcmvJ3kuybNJ9id5a5Ib\nkxxK8nySh5JcPuxiJUkXtmCgJ7kB+DVgqqreC0wAnwTuAz5XVRuAV4AdwyxUknRx/Xa5XAa8Lcll\nwBXASeAW4JHu9X3AlsUvT5LUrwUDvar+CvhdehNBnwT+DjgMvFpVp7vVTgA3DKtISdLC+ulyuRq4\nDbgR+BngSuBj86w6763WkuxMMp1kenZ29s3UKkm6iH66XD4K/GVVzVbVj4GvAD8HXNV1wQCsAV6a\n781VtbeqpqpqanJyclGKliS9UT+BfhzYnOSKJAFuBb4JPAnc3q2zHXh0OCVK/XNqNI2zfvrQD9E7\n+fkN4Ej3nr3AZ4DfSPJt4Frg/iHWKS3o7NRoc1XnTY1mqGtc9HWVS1X916r62ap6b1X9SlX9sKpe\nqKqbquqfVtUdVfXDYRcrXYxTo2ncOVJUzXBqNI07A13NcGo0jTsDXc1wajSNO2csUjOcGk3jzkBX\nU5waTePMLhdJaoRH6Bqq3QeO9LpAqphI7AKRhshA19CcHehz1tmBPoChLg2BXS4aGgf6SEtr5Ryh\nP/AAHDs26io0gLkzUzDPNeBzZ84M/4TlzMxw/35pGVo5gX7nnaOuQAOa2PX4vKM0J1atGn6ge4WL\nxpBdLhoaB/pIS2vlHKFrxTlvoI9XuUhDZ6BrqF4b6CNp6OxykaRGGOiS1AgDXZIasWAfepJ3AQ+d\n0/QO4L8Af9S1rweOAb9UVa8sfonD47B0SS3pZ07RP6+qTVW1CfhnwPeBrwJ3AweragNwsFteMc6b\nfxKcf1LSijdol8utwF9U1XeA24B9Xfs+YMtiFjZsDkuX1JpBL1v8JLC/e359VZ0EqKqTSa5b1Mp+\n0iIP/R/psHQN38zM4v8cZ2Zg06bB1peWUN+BnuRy4BPArkE+IMlOYCfAunXrBiruPIs89H+kw9K1\nMg06aYb7kZbYIF0uHwO+UVUvd8svJ1kN0D2emu9NVbW3qqaqampycvLNVbuIHJYuqTWDBPpWXu9u\nAXgM2N493w48ulhFLYU9WzaybfO612aEn0jYtnmdV7lIWrH66nJJcgXwr4D/eE7zvcDDSXYAx4E7\nFr+84XJYuqSW9BXoVfV94NqfaPsuvateJEnLgCNFJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMM\ndElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJasSgk0SvGLsPHGH/oReZq2Ii\nYevNa53MQlLTmgz03QeO8ODTx19bnqt6bdlQl9SqvrpcklyV5JEk30pyNMkHk1yT5Ikkz3ePVw+7\n2H7tP/TiQO2S1IJ+j9B/H/h6Vd2e5HLgCuCzwMGqujfJ3cDdwGeGVCc88AAcO9bXqnNnpqCb/Pn8\n9jNwzz2LWpbGyMzMqCuQLmrBQE/y08CHgTsBqupHwI+S3AZ8pFttH/AUwwz0O+/se9WJXY8zV/XG\n9lWrDHRdOvcdLXP9dLm8A5gF/jDJM0m+kORK4PqqOgnQPV43xDoHsvXmtQO1S1IL+gn0y4APAH9Q\nVe8H/oFe90pfkuxMMp1kenZ29hLLHMyeLRvZtnkdE123y0TCts3rPCEqqWn99KGfAE5U1aFu+RF6\ngf5yktVVdTLJauDUfG+uqr3AXoCpqak39oMMyZ4tGw1wSWNlwSP0qvpr4MUk7+qabgW+CTwGbO/a\ntgOPDqVCSVJf+r3K5T8BX+yucHkB+FV6/xg8nGQHcBy4YzglSpL60VegV9UMMDXPS7cubjmSpEvl\nvVwkqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgD\nXZIaYaBLUiMMdElqhIEuSY0w0CWpEX3NWJTkGPA9YA44XVVTSa4BHgLWA8eAX6qqV4ZTpiRpIYMc\nof/LqtpUVWenorsbOFhVG4CD3bIkaUTeTJfLbcC+7vk+YMubL0eSdKn6DfQC/meSw0l2dm3XV9VJ\ngO7xuvnemGRnkukk07Ozs2++YknSvPrqQwc+VFUvJbkOeCLJt/r9gKraC+wFmJqaqkuoUZLUh76O\n0Kvqpe7xFPBV4Cbg5SSrAbrHU8MqUpK0sAUDPcmVSf7x2efAvwaeBR4DtnerbQceHVaRkqSF9dPl\ncj3w1SRn1/8fVfX1JH8KPJxkB3AcuGN4ZUqSFrJgoFfVC8D75mn/LnDrMIqSJA3OkaKS1AgDXZIa\nYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREG\nuiQ1wkCXpEb0HehJJpI8k+Rr3fKNSQ4leT7JQ0kuH16ZkqSFDHKEfhdw9Jzl+4DPVdUG4BVgx2IW\nJkkaTF+BnmQN8IvAF7rlALcAj3Sr7AO2DKNASVJ/+j1C/zzwW8CZbvla4NWqOt0tnwBuWOTaJEkD\nWDDQk3wcOFVVh89tnmfVusD7dyaZTjI9Ozt7iWVKkhbSzxH6h4BPJDkGfIleV8vngauSXNatswZ4\nab43V9XeqpqqqqnJyclFKFmSNJ8FA72qdlXVmqpaD3wS+OOq+mXgSeD2brXtwKNDq1KStKA3cx36\nZ4DfSPJten3q9y9OSZKkS3HZwqu8rqqeAp7qnr8A3LT4JUmSLoUjRSWpEQa6JDXCQJekRhjoktQI\nA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGurSA3QeO8M5dj7P+B1O8c9fj7D5wZNQlSfMaaOi/NG52\nHzjCg08f7y0kzFW9trxny8YRVia9kUfo0kXsP/TiQO3SKBno0kXM1bzztlywXRolA126iInMNznX\nhdulUTLQpYvYevPagdqlUfKkqHQRZ0987j/0InNnzjCxahVbb17rCVEtSwa6tIA9Wzb2Avyee3p/\npGVqwS6XJG9N8idJ/izJc0l+u2u/McmhJM8neSjJ5cMvV5J0If30of8QuKWq3gdsAn4+yWbgPuBz\nVbUBeAXYMbwyJUkLWTDQq+f/dYtv6f4UcAvwSNe+D9gylAolSX3p6yqXJBNJZoBTwBPAXwCvVtXp\nbpUTwA3DKVGS1I++Ar2q5qpqE7AGuAl493yrzffeJDuTTCeZnp2dvfRKJUkXNdB16FX1KvAUsBm4\nKsnZq2TWAC9d4D17q2qqqqYmJyffTK2SpIvo5yqXySRXdc/fBnwUOAo8CdzerbYdeHRYRUqSFtbP\ndeirgX1JJuj9A/BwVX0tyTeBLyXZAzwD3D/EOiVJC1gw0Kvq/wLvn6f9BXr96ZKkZcB7uUiLzAkx\nNCoO/ZcWkRNiaJQ8QpcWkRNiaJQMdGkROSGGRslAlxaRE2JolAx0aRE5IYZGyZOi0iJyQgyNkoEu\nLTInxNCo2OUiSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoQDiyTNa/eBI70Rr1VM\nJI54XQH6mVN0bZInkxxN8lySu7r2a5I8keT57vHq4ZcraSmcva/72btEnr2vu5N1LG/9dLmcBn6z\nqt4NbAY+leQ9wN3AwaraABzsliU1wPu6r0z9zCl6EjjZPf9ekqPADcBtwEe61fYBTwGfGUqV0ko0\nM7Ni7+Uyd2YK5rnl79yZM+d/p5mZpStKCxqoDz3JenoTRh8Cru/Cnqo6meS6Ra9OWsk2bVqxgT6x\n6/F5J+WYWLXq/O+0Qr9fq/q+yiXJTwFfBj5dVX8/wPt2JplOMj07O3spNUpaYt7XfWXqK9CTvIVe\nmH+xqr7SNb+cZHX3+mrg1Hzvraq9VTVVVVOTk5OLUbOkIduzZSPbNq97baaliYRtm9d5lcsyt2CX\nS5IA9wNHq+r3znnpMWA7cG/3+OhQKpQ0Eq/d110rRj996B8CfgU4kuTsGZDP0gvyh5PsAI4Ddwyn\nRElSP/q5yuX/ABea4fbWxS1HknSpHPovSY0w0CWpEQa61K/164e7/ko0Dt9xBUnNM3hgWKampmp6\nenrJPk+SWpDkcFVNLbSeR+iS1AgDXZIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRizpwKIk\ns8B3lujj3g78zRJ91nLlNuhxO7gNYGVvg39SVQtOKLGkgb6Ukkz3M7KqZW6DHreD2wDGYxvY5SJJ\njTDQJakRLQf63lEXsAy4DXrcDm4DGINt0GwfuiSNm5aP0CVprDQZ6El+PsmfJ/l2krtHXc9SSLI2\nyZNJjiZ5LsldXfs1SZ5I8nz3ePWoax22JBNJnknytW75xiSHum3wUJLLR13jMCW5KskjSb7V7Q8f\nHLf9IMmvd78HzybZn+St47AfNBfoSSaA/wZ8DHgPsDXJe0Zb1ZI4DfxmVb0b2Ax8qvvedwMHq2oD\ncLBbbt1dwNFzlu8DPtdtg1eAHSOpaun8PvD1qvpZ4H30tsXY7AdJbgB+DZiqqvcCE8AnGYP9oLlA\nB24Cvl1VL1TVj4AvAbeNuKahq6qTVfWN7vn36P0S30Dvu+/rVtsHbBlNhUsjyRrgF4EvdMsBbgEe\n6VZpehsk+Wngw8D9AFX1o6p6lTHbD4DLgLcluQy4AjjJGOwHLQb6DcCL5yyf6NrGRpL1wPuBQ8D1\nVXUSeqEPXDe6ypbE54HfAs50y9cCr1bV6W659f3hHcAs8Iddt9MXklzJGO0HVfVXwO8Cx+kF+d8B\nhxmD/aDFQM88bWNzKU+SnwK+DHy6qv5+1PUspSQfB05V1eFzm+dZteX94TLgA8AfVNX7gX+g4e6V\n+XTnB24DbgR+BriSXhfsT2puP2gx0E8Aa89ZXgO8NKJallSSt9AL8y9W1Ve65peTrO5eXw2cGlV9\nS+BDwCeSHKPX1XYLvSP2q7r/ekP7+8MJ4ERVHeqWH6EX8OO0H3wU+Muqmq2qHwNfAX6OMdgPWgz0\nPwU2dGe0L6d3MuSxEdc0dF1f8f3A0ar6vXNeegzY3j3fDjy61LUtlaraVVVrqmo9vZ/7H1fVLwNP\nArd3q7W+Df4aeDHJu7qmW4FvMkb7Ab2uls1Jruh+L85ug+b3gyYHFiX5BXpHZhPAf6+q3xlxSUOX\n5J8D/xs4wuv9x5+l14/+MLCO3o5+R1X97UiKXEJJPgL856r6eJJ30DtivwZ4BthWVT8cZX3DlGQT\nvZPClwMvAL9K7+BtbPaDJL8N/Dt6V389A/x7en3mTe8HTQa6JI2jFrtcJGksGeiS1AgDXZIaYaBL\nUiMMdElqhIEuSY0w0CWpEQa6JDXi/wPxzAxdyaRJmQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1cb58d10cf8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "### Test de la fonction 'arbreKDpretri' sur le \n",
    "### jeu de donnees 'data'\n",
    "### --> on doit retrouver le même arbre qu'avec 'arbreKDpretri'\n",
    "arbre = arbreKDpretri(data)\n",
    "print(arbre)\n",
    "plotDataTree(data, arbre)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Arbre k-d distribué avec Spark"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>On reprend l'algorithme de constitution d'un arbre k-d avec tri initial selon toutes les dimensions. L'idée est de ne plus charger en mémoire l'intégralité des données, ainsi que l'arbre construit. On utilise pour cela la solution Spark, basée sur les RDD.</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### Export du jeu de données au format CSV, pour permettre un traitement général\n",
    "data.to_csv(\"data.csv\", index=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nimport pyspark\\nimport time\\n\\ndef loadRecord(line, header, col) :\\n    values = line.split(\",\")\\n    res = dict()\\n    for i in range(0, len(header)) :\\n        res[header[i]] = float(values[i])\\n    return (res[col], res)\\n\\ndef createRddDict(sc, file) :\\n    rddFile = sc.textFile(file)\\n    rawHeader = rddFile.first()\\n    header = rawHeader.split(\",\")\\n    rawRows = rddFile.filter(lambda l : l != rawHeader)\\n    res = dict()\\n    for col in header :\\n        res[col] = rawRows.map(lambda l : loadRecord(l, header, col)).sortByKey()\\n    return res\\n\\ndef getMedianUgly (rdd, n) :\\n    iterator = iter(range(0, n))\\n    median = int(n / 2)\\n    if n % 2 == 1 :\\n        median = int((n-1) / 2)\\n    print(\"--------------------------------------------------\")\\n    print(\"Nb lignes : \"+str(n))\\n    print(\"Median index : \"+str(median))\\n    print(iterator)\\n    print(rdd.collect())\\n    # return rdd.filter(lambda l : next(iterator) == median).first()[1]\\n    return rdd.filter(lambda l : avirer(next(iterator), median, l)).first()[1]\\n\\ndef avirer(it, median, l) :\\n    print(\"Iter. : \"+str(it)+\" - Mediane : \"+str(median))\\n    print(l)\\n    return it == median\\n\\ndef arbreKDsparkRec (rddDict, colList, curCol, keyIter, outputFile) :\\n    nCol = len(colList)\\n    sortCol = colList[curCol]\\n    curRdd = rddDict[sortCol]\\n    nRow = curRdd.count()\\n    if nRow == 0 :\\n        return (None, (None, None, None))\\n    elif nRow == 1 :\\n        res = (next(keyIter), (curRdd.first()[1], None, None))\\n        with open(outputFile, \"a\") as fw:\\n            fw.write(str(res) + \"\\n\")\\n        return res\\n    median = getMedianUgly(curRdd, nRow)\\n    index = next(keyIter)\\n    nextCol = (curCol + 1) % nCol\\n    leftRddDict = dict()\\n    rightRddDict = dict()\\n    for col in colList :\\n        leftRddDict[col] = rddDict[col].filter(lambda l : l[1][sortCol]<median[sortCol])\\n        rightRddDict[col] = rddDict[col].filter(lambda l : l[1][sortCol]>median[sortCol])\\n    left = arbreKDsparkRec(leftRddDict, colList, nextCol, keyIter, outputFile)\\n    right = arbreKDsparkRec(rightRddDict, colList, nextCol, keyIter, outputFile)\\n    res = (index, (median, left[0], right[0]))\\n    with open(outputFile, \"a\") as fw:\\n            fw.write(str(res) + \"\\n\")\\n    return res\\n\\ndef arbreKDspark (sc, inputFile, outputFile) :\\n    print(\"--------------------------------------------------\")\\n    print(\"Constitution d\\'un arbre KD avec Spark\")\\n    print(\"Entrée : \" + inputFile + \" - Sortie : \" + outputFile)\\n    startTime = time.time()\\n    \\n    rddDict = createRddDict(sc, inputFile)\\n    colList = list(rddDict.keys())\\n    nRow = rddDict[colList[0]].count()\\n    keyIter = iter(range(0,nRow))\\n    res = arbreKDsparkRec(rddDict, colList, 0, keyIter, outputFile)\\n    \\n    printSpendTime(startTime)\\n    #return res\\n    return \"\"\\n\\nsc = pyspark.SparkContext(appName=\"arbreKD\")\\narbre = arbreKDspark(sc, \"data.csv\", \"arbre.txt\")\\nsc.stop()\\n'"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "import pyspark\n",
    "import time\n",
    "\n",
    "def loadRecord(line, header, col) :\n",
    "    values = line.split(\",\")\n",
    "    res = dict()\n",
    "    for i in range(0, len(header)) :\n",
    "        res[header[i]] = float(values[i])\n",
    "    return (res[col], res)\n",
    "\n",
    "def createRddDict(sc, file) :\n",
    "    rddFile = sc.textFile(file)\n",
    "    rawHeader = rddFile.first()\n",
    "    header = rawHeader.split(\",\")\n",
    "    rawRows = rddFile.filter(lambda l : l != rawHeader)\n",
    "    res = dict()\n",
    "    for col in header :\n",
    "        res[col] = rawRows.map(lambda l : loadRecord(l, header, col)).sortByKey()\n",
    "    return res\n",
    "\n",
    "def getMedianUgly (rdd, n) :\n",
    "    iterator = iter(range(0, n))\n",
    "    median = int(n / 2)\n",
    "    if n % 2 == 1 :\n",
    "        median = int((n-1) / 2)\n",
    "    print(\"--------------------------------------------------\")\n",
    "    print(\"Nb lignes : \"+str(n))\n",
    "    print(\"Median index : \"+str(median))\n",
    "    print(iterator)\n",
    "    print(rdd.collect())\n",
    "    # return rdd.filter(lambda l : next(iterator) == median).first()[1]\n",
    "    return rdd.filter(lambda l : avirer(next(iterator), median, l)).first()[1]\n",
    "\n",
    "def avirer(it, median, l) :\n",
    "    print(\"Iter. : \"+str(it)+\" - Mediane : \"+str(median))\n",
    "    print(l)\n",
    "    return it == median\n",
    "\n",
    "def arbreKDsparkRec (rddDict, colList, curCol, keyIter, outputFile) :\n",
    "    nCol = len(colList)\n",
    "    sortCol = colList[curCol]\n",
    "    curRdd = rddDict[sortCol]\n",
    "    nRow = curRdd.count()\n",
    "    if nRow == 0 :\n",
    "        return (None, (None, None, None))\n",
    "    elif nRow == 1 :\n",
    "        res = (next(keyIter), (curRdd.first()[1], None, None))\n",
    "        with open(outputFile, \"a\") as fw:\n",
    "            fw.write(str(res) + \"\\n\")\n",
    "        return res\n",
    "    median = getMedianUgly(curRdd, nRow)\n",
    "    index = next(keyIter)\n",
    "    nextCol = (curCol + 1) % nCol\n",
    "    leftRddDict = dict()\n",
    "    rightRddDict = dict()\n",
    "    for col in colList :\n",
    "        leftRddDict[col] = rddDict[col].filter(lambda l : l[1][sortCol]<median[sortCol])\n",
    "        rightRddDict[col] = rddDict[col].filter(lambda l : l[1][sortCol]>median[sortCol])\n",
    "    left = arbreKDsparkRec(leftRddDict, colList, nextCol, keyIter, outputFile)\n",
    "    right = arbreKDsparkRec(rightRddDict, colList, nextCol, keyIter, outputFile)\n",
    "    res = (index, (median, left[0], right[0]))\n",
    "    with open(outputFile, \"a\") as fw:\n",
    "            fw.write(str(res) + \"\\n\")\n",
    "    return res\n",
    "\n",
    "def arbreKDspark (sc, inputFile, outputFile) :\n",
    "    print(\"--------------------------------------------------\")\n",
    "    print(\"Constitution d'un arbre KD avec Spark\")\n",
    "    print(\"Entrée : \" + inputFile + \" - Sortie : \" + outputFile)\n",
    "    startTime = time.time()\n",
    "    \n",
    "    rddDict = createRddDict(sc, inputFile)\n",
    "    colList = list(rddDict.keys())\n",
    "    nRow = rddDict[colList[0]].count()\n",
    "    keyIter = iter(range(0,nRow))\n",
    "    res = arbreKDsparkRec(rddDict, colList, 0, keyIter, outputFile)\n",
    "    \n",
    "    printSpendTime(startTime)\n",
    "    #return res\n",
    "    return \"\"\n",
    "\n",
    "sc = pyspark.SparkContext(appName=\"arbreKD\")\n",
    "arbre = arbreKDspark(sc, \"data.csv\", \"arbre.txt\")\n",
    "sc.stop()\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--------------------------------------------------\n",
      "Constitution d'un arbre KD avec Spark\n",
      "Entrée : data.csv - Sortie : arbre.txt\n",
      "Mediane : \n",
      "(49.37819040066077, 26.759433858493452)\n",
      "Mediane : \n",
      "(3.3340403954696174, 70.34615028413086)\n",
      "Mediane : \n",
      "(45.61150668319305, 33.28920293806107)\n",
      "Mediane : \n",
      "(39.273315526831844, 78.19680246760275)\n",
      "Mediane : \n",
      "(74.54049982644099, 88.99618079028801)\n",
      "Mediane : \n",
      "(66.72081020386534, 85.33090379515743)\n",
      "--------------------------------------------------\n",
      "-----   Temps écoulé : 0h02m01s\n",
      "--------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "import pyspark\n",
    "import time\n",
    "\n",
    "def loadRecord(line) :\n",
    "    values = line.split(\",\")\n",
    "    values = [float(v) for v in values]\n",
    "    return tuple(values)\n",
    "\n",
    "def createRddDict(sc, file) :\n",
    "    rddFile = sc.textFile(file)\n",
    "    rawHeader = rddFile.first()\n",
    "    header = rawHeader.split(\",\")\n",
    "    rawRows = rddFile.filter(lambda l : l != rawHeader)\n",
    "    res = dict()\n",
    "    for i in range(0, len(header)) :\n",
    "        res[header[i]] = rawRows.map(lambda l : loadRecord(l)) \\\n",
    "        .sortBy(lambda l : l[i]).zipWithIndex().map(lambda l : (l[1], l[0])) \\\n",
    "        .sortByKey()\n",
    "    return res\n",
    "\n",
    "def arbreKDsparkRec (rddDict, colList, curCol, keyIter, outputFile) :\n",
    "    nCol = len(colList)\n",
    "    sortCol = colList[curCol]\n",
    "    curRdd = rddDict[sortCol]\n",
    "    nRow = curRdd.count()\n",
    "    if nRow == 0 :\n",
    "        return (None, (None, None, None))\n",
    "    elif nRow == 1 :\n",
    "        res = (next(keyIter), (curRdd.first()[1], None, None))\n",
    "        with open(outputFile, \"a\") as fw:\n",
    "            fw.write(str(res) + \"\\n\")\n",
    "        return res\n",
    "    median = int(nRow / 2)\n",
    "    if nRow % 2 == 1 :\n",
    "        median = int((nRow-1) / 2)\n",
    "    median = curRdd.lookup(median)[0]\n",
    "    print(\"Mediane : \")\n",
    "    print(median)\n",
    "    index = next(keyIter)\n",
    "    nextCol = (curCol + 1) % nCol\n",
    "    leftRddDict = dict()\n",
    "    rightRddDict = dict()\n",
    "    for col in colList :\n",
    "        leftRddDict[col] = rddDict[col].filter(lambda l : l[1][curCol]<median[curCol]) \\\n",
    "        .zipWithIndex().map(lambda l : (l[1], l[0][1]))\n",
    "        rightRddDict[col] = rddDict[col].filter(lambda l : l[1][curCol]>median[curCol]) \\\n",
    "        .zipWithIndex().map(lambda l : (l[1], l[0][1]))\n",
    "    left = arbreKDsparkRec(leftRddDict, colList, nextCol, keyIter, outputFile)\n",
    "    right = arbreKDsparkRec(rightRddDict, colList, nextCol, keyIter, outputFile)\n",
    "    res = (index, (median, left[0], right[0]))\n",
    "    with open(outputFile, \"a\") as fw:\n",
    "            fw.write(str(res) + \"\\n\")\n",
    "    return res\n",
    "\n",
    "def arbreKDspark (sc, inputFile, outputFile) :\n",
    "    print(\"--------------------------------------------------\")\n",
    "    print(\"Constitution d'un arbre KD avec Spark\")\n",
    "    print(\"Entrée : \" + inputFile + \" - Sortie : \" + outputFile)\n",
    "    startTime = time.time()\n",
    "    \n",
    "    rddDict = createRddDict(sc, inputFile)\n",
    "    colList = list(rddDict.keys())\n",
    "    nRow = rddDict[colList[0]].count()\n",
    "    keyIter = iter(range(0,nRow))\n",
    "    res = arbreKDsparkRec(rddDict, colList, 0, keyIter, outputFile)\n",
    "    \n",
    "    printSpendTime(startTime)\n",
    "    #return res\n",
    "    return \"\"\n",
    "\n",
    "sc = pyspark.SparkContext(appName=\"arbreKD\")\n",
    "arbre = arbreKDspark(sc, \"data.csv\", \"arbre.txt\")\n",
    "sc.stop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### Si le programme précédent a planté, il est nécessaire d'arrêter\n",
    "### le contexte Spark (un seul contexte en même temps)\n",
    "sc.stop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[6, 4]\n"
     ]
    }
   ],
   "source": [
    "sc = pyspark.SparkContext(appName=\"testMedian\")\n",
    "rddDict = createRddDict(sc, \"data.csv\")\n",
    "rdd = rddDict['X']\n",
    "#print(rdd.zipWithIndex().collect())\n",
    "test = rdd.mapPartitions(lambda it: [sum(1 for _ in it)]).collect()\n",
    "#test = getMedian(rdd)\n",
    "print(test)\n",
    "#print(rdd.glom().collect())\n",
    "sc.stop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('a', 'b', 'c')\n",
      "a\n",
      "('a', 'b', 'c')\n",
      "('a', 'b', 'c')\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "import ast\n",
    "strTup = \"('a', 'b', 'c')\"\n",
    "test = ast.literal_eval(strTup)\n",
    "print(test)\n",
    "print(test[0])\n",
    "print(strTup)\n",
    "print(str(test))\n",
    "print(str(test)==strTup)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.lines as lines\n",
    "\n",
    "### Trace un arbre k-d (classe 'Tree') de facon recursive\n",
    "def pltTreeRec(ax, tree, keyX, keyY, xLim, yLim) :\n",
    "    if tree :\n",
    "        x, y = tree.data[keyX], tree.data[keyY]\n",
    "        if tree.key == keyX :\n",
    "            pltTreeRec(ax, tree.left, keyX, keyY, (xLim[0], x), yLim)\n",
    "            pltTreeRec(ax, tree.right, keyX, keyY, (x, xLim[1]), yLim)\n",
    "            ax.add_line(lines.Line2D((x, x), yLim, linewidth=0.5, color='red'))\n",
    "        elif tree.key == keyY :\n",
    "            pltTreeRec(ax, tree.left, keyX, keyY, xLim, (yLim[0], y))\n",
    "            pltTreeRec(ax, tree.right, keyX, keyY, xLim, (y, yLim[1]))\n",
    "            ax.add_line(lines.Line2D(xLim, (y, y), linewidth=0.5, color='red'))\n",
    "        plt.plot(x, y, 'o', color='#1f77b4')\n",
    "\n",
    "### Trace un jeu de donnees et l'arbre k-d associe.\n",
    "### Le parametre 'tree' doit etre une instance de la \n",
    "### classe 'Tree'\n",
    "def plotSparkTree(data, tree) :\n",
    "    colList = data.columns.values.tolist()\n",
    "    keyX, keyY = colList[0], colList[1]\n",
    "    ax = plt.axes()\n",
    "    plt.plot(data[['X']], data[['Y']], 'o', color='#1f77b4')\n",
    "    xLim, yLim = ax.get_xlim(), ax.get_ylim()\n",
    "    pltTreeRec(ax, tree, keyX, keyY, xLim, yLim)\n",
    "    plt.show()"
   ]
  }
 ],
 "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}