{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Les dictionnaires\n",
    "\n",
    "> Cours NSI Terminale - Thème 1.\n",
    "\n",
    "- toc: true \n",
    "- badges: true\n",
    "- comments: false\n",
    "- categories: [python, NSI, Terminale, Structure_donnees, TP]\n",
    "- image: images/nsi1.png"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "375435ca66c73c8d792cb68ab5e1afcc",
     "grade": false,
     "grade_id": "cell-61c1637a1efa9a1a",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Rappels sur les dictionnaires\n",
    "\n",
    "Dans cette partie, nous allons fabriquer un carnet d'adresse pour stocker des contacts. \n",
    "\n",
    "### Fabrication d'un contact \n",
    "\n",
    "Chaque contact sera un dictionnaire dont les clés seront :\n",
    "- `nom` : Nom et prénom du contact\n",
    "- `tel` : N° de téléphone\n",
    "- `rue` : adresse complète\n",
    "- `code` : code postal\n",
    "- `ville` : ville\n",
    "- `naissance` : date de naissance\n",
    "\n",
    "Créez un dictionnaire nommé `contact` correspondant au contact suivant :\n",
    "> Margaret Costa-Royer<br/>\n",
    "> 08 06 18 37 28<br/>\n",
    "> 93, avenue Bruneau<br/>\n",
    "> 13749 Perrot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "e967c7409fcfffebb53b0a985d42646b",
     "grade": false,
     "grade_id": "cell-2fd9bc81593ae294",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "6263e63d2630e42a828206daa115968a",
     "grade": true,
     "grade_id": "cell-6f79e90fabb23d67",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Vérification\n",
    "assert contact[\"nom\"] == \"Margaret Costa-Royer\"\n",
    "assert contact[\"tel\"] == \"08 06 18 37 28\"\n",
    "assert contact[\"ville\"] == \"Perrot\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ab76baa96b292bd0e12fa5791cb4549c",
     "grade": false,
     "grade_id": "cell-4da91c69c4155bef",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Ajouter une nouvelle entrée \"passwd\" dans le contact ayant pour valeur 's75JWikE&o'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "f3cec15cf971a73036827996d693396b",
     "grade": false,
     "grade_id": "cell-788061858e153019",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "f0f0f716174549b7fbbe7756e78ecf87",
     "grade": true,
     "grade_id": "cell-9f918fabbdab4271",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Vérification\n",
    "assert contact[\"passwd\"] == 's75JWikE&o'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "977ab0d9706d8578f5569ab0689c3bce",
     "grade": false,
     "grade_id": "cell-19e7e9eae67b19d1",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Génération automatique d'un contact\n",
    "\n",
    "Ecrire une fonction `genere_contact()`\n",
    "- qui ne prend aucun paramètre\n",
    "- qui renvoie un dictionnaire possédant les mêmes clés que le contact ci-dessus, y compris \"passwd\"\n",
    "\n",
    "On pourra utiliser le module `faker` de python dont un exemple d'utilisation est donné dans la cellile ci-dessous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "4a6712e527fd4acf73da131f1bbe1fbb",
     "grade": false,
     "grade_id": "cell-d30407a51d0d68aa",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "from faker import Faker\n",
    "\n",
    "fake = Faker(\"fr_FR\") # Générateur de données personnelles pour un français\n",
    "\n",
    "print(fake.name())\n",
    "print(fake.phone_number())\n",
    "print(fake.street_address())\n",
    "print(fake.postcode(), fake.city())\n",
    "print(fake.password())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "4fb8b568cd8a4f82303bda56df78627a",
     "grade": false,
     "grade_id": "cell-16e333cf71d7c879",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "***Remarque*** :  Si la cellule ci-dessus provoque une erreur disant que le module `faker` n'est pas disponible, vous pouvez l'installer dans l'environnement jupyter via la commande\n",
    "\n",
    "```!pip install faker```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "887bd34b97f35f3a1721029695f99e92",
     "grade": false,
     "grade_id": "cell-4a7bb8470b471432",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def genere_contact():\n",
    "    \"\"\"Fabrique un contact factice et renvoie le contact sous forme d'un dictionnaire\"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "be6bb38374afdfef8101c3fc9ccb60f3",
     "grade": true,
     "grade_id": "cell-93d3004c755a1e03",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "contact1 = genere_contact()\n",
    "assert type(contact1[\"nom\"]) == str\n",
    "assert \"city\" in contact1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "82537f41486685b385c1312c3aa0da2e",
     "grade": false,
     "grade_id": "cell-63a5650a68b92eb8",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Mise en pratique\n",
    "\n",
    "### Fabrication du carnet d'adresse\n",
    "\n",
    "Tout est à présent en place pour que nous puissions fabriquer notre carnet d'adresse.\n",
    "\n",
    "#### Première implémentation\n",
    "\n",
    "Dans une première approche, nous allons considérer que le carnet d'adresse sera une liste de contacts, chaque contact étant un dictionnaire dont la structure a été définie à la section précédente.\n",
    "\n",
    "Fabriquez une fonction `genere_carnet1`\n",
    "- prenant en paramètre le nombre `n` de contacts à générer\n",
    "- renvoyant une **liste** de `n` contacts générés aléatoirement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "ddffdc3b6f414982b1ff3077c3283350",
     "grade": false,
     "grade_id": "cell-5d540b645515b45a",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def genere_carnet1(n):\n",
    "    \"\"\"Renvoie une liste de n contacts aléatoires\"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9b01be0c292b8ee439c2ef9387c66df4",
     "grade": true,
     "grade_id": "cell-b9ef7ac2f3b6b1b5",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# vérification\n",
    "\n",
    "carnet1 = genere_carnet1(10)\n",
    "assert type(carnet1) == list\n",
    "assert \"nom\" in carnet1[3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "df549f696d103d06a5a7dd136c364541",
     "grade": false,
     "grade_id": "cell-6a8b930aec69eca5",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Ecrire à présent une fonction `est_present`\n",
    "- prenant 2 paramètres : un nom et un carnet d'adresse\n",
    "- renvoyant `True` si le nom figure dans le carnet d'adresse, `False` sinon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "f32c79ff8d52a2ab8acedd246fb2186f",
     "grade": false,
     "grade_id": "cell-b9733eec3aeef3ed",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def est_present(nom, carnet):\n",
    "    \"\"\"Teste si nom est présent dans le carnet d'adresse\"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "365af12b91dc244abd75975ad28c8fc4",
     "grade": true,
     "grade_id": "cell-68e271be070a4245",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Vérification\n",
    "\n",
    "carnet1 = genere_carnet1(10)\n",
    "nom = carnet1[-1][\"nom\"]\n",
    "assert est_present(nom, carnet1)\n",
    "assert not est_present(\"Lecluse Olivier\", carnet1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "76df47d18bc361e17b21092848a7534c",
     "grade": false,
     "grade_id": "cell-d2970465e41dbb2f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "#### Mesure de performance de la recherche\n",
    "\n",
    "Nous allons regarder ici comment évolue la vitesse de recherche en fonciton de la taille du carnet d'adresse. On utilisera pour ncela la fonction magique de *jupyter* : `%%timeit`.\n",
    "Etudiez la cellule suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ba597fb0cf106319e8ae6290ebd9db73",
     "grade": false,
     "grade_id": "cell-2e8632dbb543a74e",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Fabrication d'un carnet de 100 contacts\n",
    "carnet1 = genere_carnet1(100)\n",
    "nom = carnet1[-1][\"nom\"]  # On récupère un nom du carnet\n",
    "nom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "bc32f86741b295d6bfcfe5c4d790d123",
     "grade": false,
     "grade_id": "cell-907e36aac6add99d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%%timeit\n",
    "\n",
    "# On mesure le temps d'une recherche\n",
    "est_present(nom, carnet1) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "0dfc0f05f673aa7d31c4cb600c48be33",
     "grade": false,
     "grade_id": "cell-d90d845208dcbc60",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Vous lisez sous la cellule le temps de recherche.\n",
    "\n",
    "A présent, on refait l'expérience pour 1000 contacts dans le carnet d'adresse."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "carnet1 = genere_carnet1(1000)\n",
    "nom = carnet1[-1][\"nom\"]  # On récupère un nom du carnet\n",
    "nom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "\n",
    "# On mesure le temps d'une recherche dans ce carnet\n",
    "est_present(nom, carnet1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "0f8748021b03f476720903e2c1d6cab1",
     "grade": false,
     "grade_id": "cell-fa379101620f6c66",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "#### Seconde implémentation\n",
    "\n",
    "Vous devez avoir constaté ci-dessus que le temps de recherche est proportionnel à la taille du carnet d'adresse : si celui-ci contient 10 fois plus de contact, la recherche peut être jusqu'à 10 fois plus longue.\n",
    "\n",
    "Nous allons changer d'approche et fabriquer un carnet d'adresse sous forme d'un dictionnaire dont les clés seront les **noms** et les valeurs seront les fiches contacts. Ainsi notre carnet d'adresse sera un dictionnaire dont les valeurs seront des dictionnaires !\n",
    "\n",
    "Fabriquez une fonction `genere_carnet2`\n",
    "- prenant en paramètre le nombre n de contacts à générer\n",
    "- renvoyant un **dictionnaire** de `n` contacts générés aléatoirement"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "2b7279b4eff634e786fe05e9442fdf73",
     "grade": false,
     "grade_id": "cell-dd15db6baca83d33",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def genere_carnet2(n):\n",
    "    \"\"\"Renvoie un dictionnaire de n contacts aléatoires\"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "e503968c7a0ce7e813d30a9028824d9a",
     "grade": true,
     "grade_id": "cell-4c06f806b0e977b1",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Vérification\n",
    "\n",
    "carnet2 = genere_carnet2(10)\n",
    "assert type(carnet2) == dict\n",
    "nom = list(carnet2.keys())[-1]\n",
    "assert type(carnet2[nom]) == dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "07ab11e991968472755703a38c6779a9",
     "grade": false,
     "grade_id": "cell-98631c6fabfa075a",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "#### Mesure de performance de la recherche\n",
    "\n",
    "Nous allons regarder pour cette nouvelle implémentation comment évolue la vitesse de recherche en fonction de la taille du carnet d'adresse. Validez les 2 cellules suivantes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9c0099667b5f39052f7ac2acef7a7513",
     "grade": false,
     "grade_id": "cell-c99dbdcd9cbba6d6",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Fabrication d'un carnet de 100 contacts\n",
    "carnet2 = genere_carnet2(100)\n",
    "nom = list(carnet2.keys())[-1] # On récupère un nom du carnet\n",
    "nom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "73a549f43082b78b6b2750386de52c6b",
     "grade": false,
     "grade_id": "cell-688db45f21122b08",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "%%timeit\n",
    "\n",
    "nom in carnet2                 # On le recherche"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "fd983fe3c8769888963ddfa3aa4076c9",
     "grade": false,
     "grade_id": "cell-72cfb9b178aca662",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "On constate déjà que la recherche est plus rapide que pour la première implémentation du carnet à l'aide d'un tableau.\n",
    "\n",
    "Refaisons l'expérience avec 100 fois plus de contacts dans le carnet !!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Fabrication d'un carnet de 10000 contacts\n",
    "carnet2 = genere_carnet2(10000)\n",
    "nom = list(carnet2.keys())[-1] # On récupère un nom du carnet\n",
    "nom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%timeit\n",
    "\n",
    "nom in carnet2           # On le recherche"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9b867beca148c9ccee142ee230c3185d",
     "grade": false,
     "grade_id": "cell-5ae07b00d2bdb9e3",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Conclusion\n",
    "\n",
    "Vous le constatez d'après les expériences ci-dessus : le temps de recherche dans le dictionnaire est pratiquement indépendant du nombre d'entrées dans ce dictionnaires, car en multipliant le nombre de contacts par 100, le temps est resté pratiquement identique alors que dans le cas de la recherche dans un tableau, celui-ci est proportionnel à la longueur du tableau.\n",
    "\n",
    "Le dictionnaire est donc une structure de données optimisée pour la recherche sur les clés."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Aucun(e)",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}