{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# langages de script – Python\n",
    "\n",
    "## Cours 2 – structures de données\n",
    "\n",
    "### M1 Ingénierie Multilingue – INaLCO\n",
    "\n",
    "clement.plancq@ens.fr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Avant de commencer\n",
    "\n",
    "Les structures de données sont un point essentiel de tout langage de programmation\n",
    "\n",
    "Les diapos qui suivent n'offrent qu'une couverture partielle du sujet\n",
    "\n",
    "Vous *devez* lire attentivement et vous référer à la documentation officelle de Python :\n",
    "- [le chapitre 5 du tutoriel](https://docs.python.org/3.6/tutorial/datastructures.html)\n",
    "- la [doc](https://docs.python.org/3.6/library/stdtypes.html) sur les types built-in\n",
    "- la [doc](https://docs.python.org/3/library/collections.html) du module collections"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Les listes\n",
    "\n",
    "- Les listes sont des *sequences* (`str`, `tuple`, `list`)\n",
    "- Les *sequences* sont des structures de données indicées qui peuvent contenir des éléments de différents types\n",
    "- Les *sequences* sont des *iterables*, les listes aussi donc\n",
    "- Les éléments d'une liste peuvent être modifiés (*mutable*)\n",
    "\n",
    "- Une liste vide peut se déclarer de deux façons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stack = list()\n",
    "stack = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stack = [\"le\", \"guépard\", \"le\", \"poursuit\"]\n",
    "stack = list('Perl')\n",
    "stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Les listes : fonctions\n",
    "\n",
    "- Les listes héritent des fonctions des *sequences*, elles ont également des [fonctions propres](https://docs.python.org/3.6/tutorial/datastructures.html#more-on-lists)\n",
    "- Parmi ces fonctions nous utiliserons principalement :\n",
    "  - `append(x)` : ajoute un élément x à la fin de la liste (haut de la pile*)\n",
    "  - `extend([x, y, z])` : ajoute tous les éléments de la liste arg à la fin de la liste\n",
    "  - `pop([index])` : supprime et renvoie le dernier élément de la liste ou les index de la liste argument si arg\n",
    "  - `index(x)` : renvoie l'index du premier élément de valeur x\n",
    "  - `count(x)` : renvoie le nombre de fois où x apparaît\n",
    "  - `sort()` : trie et modifie la liste, lire la [doc](https://docs.python.org/3.6/howto/sorting.html#sortinghowto) pour en savoir plus sur les ordres de tri"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "stack = [12, 15, 12, 7, 18]\n",
    "stack.index(12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "stack.count(12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "stack.sort()\n",
    "stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stack.append(23)\n",
    "stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "stack.append([35, 46])\n",
    "stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stack.extend([51, 52])\n",
    "stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Les listes en compréhension\n",
    "\n",
    "- Elles permettent de définir des listes par filtrage ou opération sur les éléments d'une autre liste\n",
    "- Elles viennent de la programmation fonctionnelle\n",
    "- La [PEP 202](http://www.python.org/dev/peps/pep-0202/) conseille de préférer les listes en compréhension aux fonctions `map()` et `filter()`\n",
    "- Pas évident-évident de prime abord mais très expressif, élégant et *so pythonic*. Un dév python **doit** maîtriser les listes en compréhension\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[i ** 2 for i in range(10)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[i ** 2 for i in range(10) if i % 2 == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[(i, j) for i in range(2) for j in ['a', 'b']]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Attention !\n",
    "## Copie de liste\n",
    "\n",
    "Dans `y = x`, `y` n'est pas un copie de x, les deux pointent vers le même objet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [1, 2, 3]\n",
    "y = x\n",
    "y[0] = 4\n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour copier une liste il faut utiliser :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [1, 2, 3]\n",
    "y = x[:]\n",
    "# ou\n",
    "y = list(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Les tuples\n",
    "\n",
    "- Les tuples (`tuple`) sont des *sequences* similaires aux listes sauf qu'elles ne peuvent pas être modifiées (*immutable*)\n",
    "- Les tuples sont souvent utilisées comme valeur de retour d'une fonction\n",
    "- Les tuples peuvent être utilisées comme clé de dictionnaire"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "voyelles = ('a', 'e', 'i', 'o', 'u', 'y')\n",
    "var = tuple('Perl')\n",
    "var"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Déballage de séquences\n",
    "\n",
    "- Le *sequence unpacking* permet d'effectuer plusieurs affectations simultanées\n",
    "- L'*unpacking* s'applique souvent sur des tuples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x, y, z = (1, 2, 3)\n",
    "y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lexique = [(\"maison\", \"mEz§\"), (\"serpent\", \"sERp@\")]\n",
    "for ortho, phon in lexique:\n",
    "    print(phon)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Attention !\n",
    "\n",
    "## Tuple à 1 élément\n",
    "Pour créer un tuple à un élément il faut utiliser la notation `(elem, )`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "var = (1)\n",
    "type(var)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "var = (1, )\n",
    "type(var)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Parcours de liste\n",
    "\n",
    "La boucle `for` est particulièrement adaptée pour parcourir les *iterables* et donc les listes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for item in voyelles:\n",
    "    print(item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `enumerate` peut être utile dans certains cas, elle renvoie un `tuple` contenant l'indice et la valeur de l'item à l'indice concerné"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i, item in enumerate(voyelles):\n",
    "    print(i, item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Les ensembles\n",
    "\n",
    "Les ensembles (`set`) sont des collections non ordonnées d'élements sans doublons\n",
    "Les ensembles supportent les fonctions mathématiques d'union, d'intersection, de différence ([doc](https://docs.python.org/3.6/library/stdtypes.html#set))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ens1 = {'le', 'guépard', 'le', 'poursuit'}\n",
    "ens1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ens2 = {\"avec\", \"le\", \"chandelier\", \"dans\", \"la\", \"cuisine\"}\n",
    "ens1.intersection(ens2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Les dictionnaires\n",
    "\n",
    "- Les dictionnaires (`dict`) sont des structures de données associatives de type clé: valeur\n",
    "- Les clés d'un dictionnaire sont uniques, seuls les types *immutable* peuvent être des clés ([doc](https://docs.python.org/3.6/library/stdtypes.html#mapping-types-dict))\n",
    "\n",
    "  - `key in d` retourne True si `key` est une clé de `d`\n",
    "  - `keys()` retourne la liste des clés\n",
    "  - `values()` retourne la liste des valeurs\n",
    "  - `items()` retourne la liste des couples clé:valeur (tuple)\n",
    "  - `setdefault(key, default)` retourne la valeur associée à la clé. Si la clé n'existe pas, ajoute la clé associée à default"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {'Perl':'Larry Wall', 'Python':'Guido Van Rossum', 'C++':'Bjarne Stroustrup'}\n",
    "d['Perl']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "d['Ruby']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d.get('Ruby')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Module collections\n",
    "\n",
    "- Le module *collections* propose des implémentations de structures de données supplémentaires\n",
    "- Dans la liste (voir [doc](https://docs.python.org/3.6/library/collections.html)), deux pourront nous intéresser :\n",
    "\n",
    "  - `defaultdict`\n",
    "\n",
    "     `defauldict` est similaire à un `dict` mais il permet l'autovivification\n",
    "\n",
    "      Son implémentation le rend plus rapide qu'un dictionnaire utilisé avec la fonction `setdefault`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "lexique = [(\"couvent\", \"kuv\"), (\"couvent\", \"kuv@\")]\n",
    "dico = collections.defaultdict(list)\n",
    "for ortho, phon in lexique:\n",
    "    dico[ortho].append(phon)\n",
    "dico"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Module collections\n",
    "\n",
    "  - Counter\n",
    "  \n",
    "`Counter` est un dictionnaire où les valeurs attendues sont les nombres d'occurences des clés"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "cnt = Counter()\n",
    "list = ['le', 'guépard', 'le', 'poursuit']\n",
    "for item in list:\n",
    "    cnt[item] += 1\n",
    "cnt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Help !\n",
    "\n",
    "## Fonction `repr`\n",
    "\n",
    "Dans la console Python les structures de données s'affichent de façon lisible\n",
    "\n",
    "`print(obj)` ne donnera pas toujours le résultat escompté\n",
    "\n",
    "La fonction `repr(obj)` est à préférer, elle donne une \"représentation textuelle\" d'un objet\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Exos\n",
    "\n",
    "Vous rendrez des scripts Python3. Avec des commentaires c'est mieux.\n",
    "\n",
    "1. À partir du fichier tsv `sem_Ef9POe.conll`\n",
    "  1. pour chaque POS listez les types classés par ordre d'occurrence décroissante,\n",
    "  2. pour chaque type de chunk indiquez les longueurs min et max (en nb de mots).\n",
    "2. Résoudre [Mime types](https://www.codingame.com/training/easy/mime-type) sur CodinGame"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.7.0"
  },
  "livereveal": {
   "autolaunch": true,
   "scroll": true,
   "transition": "none"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}