.. _structuresdonneesconversionrst: =========================================== 1A.1 - D’une structure de données à l’autre =========================================== .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/1a/structures_donnees_conversion.ipynb|*` Ce notebook s’amuse à passer d’une structure de données à une autre, d’une liste à un dictionnaire, d’une liste de liste à un dictionnaire, avec toujours les mêmes données : `list `__, `dict `__, `tuple `__. .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: histogramme et dictionnaire --------------------------- liste à dictionnaire ~~~~~~~~~~~~~~~~~~~~ Un histogramme est le moyen le plus simple de calculer la distribution d’une variable, de compter la fréquence des éléments d’une liste. .. code:: ipython3 ens = ["a", "b", "gh", "er", "b", "gh"] hist = {} for e in ens: hist[e] = hist.get(e, 0) + 1 hist .. parsed-literal:: {'a': 1, 'b': 2, 'gh': 2, 'er': 1} La méthode `get `__ comme beaucoup de fonctions implémente un besoin fréquent. Elle regarde si une clé appartient au dictionnaire, retourne la valeur associée ou une valeur par défault dans le cas contraire. Sans utiliser cette méthode, le code précédent devient : .. code:: ipython3 ens = ["a", "b", "gh", "er", "b", "gh"] hist = {} for e in ens: if e in hist: hist[e] += 1 else: hist[e] = 1 hist .. parsed-literal:: {'a': 1, 'b': 2, 'gh': 2, 'er': 1} Il existe également la fonction `Counter `__ qui fait cela. .. code:: ipython3 from collections import Counter ens = ["a", "b", "gh", "er", "b", "gh"] hist = Counter(ens) hist .. parsed-literal:: Counter({'a': 1, 'b': 2, 'gh': 2, 'er': 1}) dictionnaire à liste ~~~~~~~~~~~~~~~~~~~~ A priori l’histogramme représente la même information que la liste initiale ``ens``. Il doit exister un moyen de recontruire la liste initiale. .. code:: ipython3 hist = {'a': 1, 'b': 2, 'er': 1, 'gh': 2} ens = [] for k, v in hist.items(): for i in range(v): ens.append(k) ens .. parsed-literal:: ['a', 'b', 'b', 'er', 'gh', 'gh'] La liste initiale est retrouvée excepté l’ordre qui est différent. Les éléments identiques sont côte à côte. La méthode `items `__ retourne des couples ``(clé, valeur)`` ou plutôt une vue, c’est-à-dire une façon de parcourir un ensemble. .. code:: ipython3 hist.items() .. parsed-literal:: dict_items([('a', 1), ('b', 2), ('er', 1), ('gh', 2)]) Pour vérifier que la méthode `items `__ ne retourne pas un ensemble mais une façon de parcourir un ensemble, on regarde sa taille avec la fonction `getsizeof `__ : .. code:: ipython3 import sys vue = hist.items() sys.getsizeof(ens), sys.getsizeof(hist), sys.getsizeof(vue) .. parsed-literal:: (128, 240, 48) Et pour un dictionnaire plus grand, la taille du dictionnaire. .. code:: ipython3 d = {i:i for i in range(1000)} sys.getsizeof(d), sys.getsizeof(d.items()) .. parsed-literal:: (36968, 48) On peut ne pas utiliser la méthode `items `__ : .. code:: ipython3 hist = {'a': 1, 'b': 2, 'er': 1, 'gh': 2} ens = [] for k in hist: v = hist[k] for i in range(v): ens.append(k) ens .. parsed-literal:: ['a', 'b', 'b', 'er', 'gh', 'gh'] dictionnaire et deux listes ~~~~~~~~~~~~~~~~~~~~~~~~~~~ Cette fois-ci, on met les clés d’un côté et les valeurs de l’autre. .. code:: ipython3 hist = {'a': 1, 'b': 2, 'er': 1, 'gh': 2} cles = [k for k in hist] vals = [hist[k] for k in hist] cles, vals .. parsed-literal:: (['a', 'b', 'er', 'gh'], [1, 2, 1, 2]) On peut écrire aussi ce programme .. code:: ipython3 hist = {'a': 1, 'b': 2, 'er': 1, 'gh': 2} cles = list(hist.keys()) vals = list(hist.values()) cles, vals .. parsed-literal:: (['a', 'b', 'er', 'gh'], [1, 2, 1, 2]) Toutefois, cette écriture n’est pas recommandée car il est possible que l’expression ``for k in hist`` ou ``list(hist.keys())`` parcourent les clés d’un dictionnaire de deux façons différentes si le dictionnaire est modifié entre temps. Mais on ne s’en pas toujours compte car cela dépend de l’implémentation des méthodes associées à la classe `dict `__ (voir `cpython `__). C’est pourquoi on préfère ne parcourir qu’une seule fois le dictionnaire tout en créant les deux listes. .. code:: ipython3 hist = {'a': 1, 'b': 2, 'er': 1, 'gh': 2} cles = [] vals = [] for k, v in hist.items(): cles.append(k) vals.append(v) cles, vals .. parsed-literal:: (['a', 'b', 'er', 'gh'], [1, 2, 1, 2]) deux listes et dictionnaires ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ On effectue l’opération inverse. .. code:: ipython3 cles, vals = ['a', 'gh', 'er', 'b'], [1, 2, 1, 2] hist = {a:b for a, b in zip(cles, vals)} hist .. parsed-literal:: {'a': 1, 'gh': 2, 'er': 1, 'b': 2} Et si on ne veut pas utiliser la fonction `zip `__ : .. code:: ipython3 cles, vals = ['a', 'gh', 'er', 'b'], [1, 2, 1, 2] hist = {} for i in range(len(cles)): hist[cles[i]] = vals[i] hist .. parsed-literal:: {'a': 1, 'gh': 2, 'er': 1, 'b': 2} zip reverse ~~~~~~~~~~~ La fonction `zip `__ permet de parcourir deux listes en parallèles. Cela permet de raccourcir le code pour créer un dictionnaire à partir de clés et de valeurs séparés. Ca paraît bien plus long que de créer les listes des clés et des valeurs. Et pourtant le code suivant peut être considérablement raccourci : .. code:: ipython3 hist = {'a': 1, 'b': 2, 'er': 1, 'gh': 2} cles = [] vals = [] for k, v in hist.items(): cles.append(k) vals.append(v) cles, vals .. parsed-literal:: (['a', 'b', 'er', 'gh'], [1, 2, 1, 2]) Cela devient : .. code:: ipython3 hist = {'a': 1, 'b': 2, 'er': 1, 'gh': 2} cles, vals = zip(*hist.items()) cles, vals .. parsed-literal:: (('a', 'b', 'er', 'gh'), (1, 2, 1, 2)) Petite différence, ``cles``, ``vals`` sont sous forme de `tuple `__ mais cela reste très élégant. matrices et dictionnaires ------------------------- liste de listes et dictionnaires ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Une liste de listes est la représentation la plus naturelle. Essayons de la transformer sous forme de dictionnaire. On utilise la fonction `enumerate `__. .. code:: ipython3 mat = [[1, 2], [3, 4]] dv = {} for i, row in enumerate(mat): for j, x in enumerate(row): dv[i,j] = x dv .. parsed-literal:: {(0, 0): 1, (0, 1): 2, (1, 0): 3, (1, 1): 4} dictionnaires et liste de listes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ On effectue l’opération inverse. Nous n’avons pas perdu d’information, nous devrions retrouver la liste de listes originale. .. code:: ipython3 dx = {(0, 0): 1, (0, 1): 2, (1, 0): 3, (1, 1): 4} max_i = max(k[0] for k in dx) + 1 max_j = max(k[1] for k in dx) + 1 mat = [[0] * max_j for i in range(max_i)] for k, v in dv.items(): mat[k[0]][k[1]] = v mat .. parsed-literal:: [[1, 2], [3, 4]] La différence principale entre un dictionnaire ``d`` et une liste ``l`` est que l’instruction ``d[k]`` ajoute un élément d’indice ``k`` (quel que soit ``k``) alors que l’instruction ``l[k]``) suppose que l’élément d’indice ``k`` existe dans la liste. C’est pour cela qu’on commence à calculer les indices maximaux largeur, longueur. matrice sparse ~~~~~~~~~~~~~~ On utilise cette répresentation surtout lorsque pour des matrices sparses : la majorité des coefficients sont nuls. Dans ce cas, le dictionnaire final ne contient que les coefficients non nuls. .. code:: ipython3 mat = [[1, 0, 0], [0, 4, 0]] dv = {} for i, row in enumerate(mat): for j, x in enumerate(row): if x != 0: dv[i,j] = x dv .. parsed-literal:: {(0, 0): 1, (1, 1): 4} Si on ne conserve pas les dimensions de la matrice originale, on perd un peu d’information dans un cas précis : si la matrice se termine par une colonne ou une ligne de zéros. .. code:: ipython3 dx = {(0, 0): 1, (1, 1): 4} max_i = max(k[0] for k in dx) + 1 max_j = max(k[1] for k in dx) + 1 mat = [[0] * max_j for i in range(max_i)] for k, v in dv.items(): mat[k[0]][k[1]] = v mat .. parsed-literal:: [[1, 0], [0, 4]] matrices et tableaux -------------------- 2 dimensions logiques, 1 dimension en mémoire ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ On préfère représenter une matrice par un seul vecteur même si logiquement elle en contient car cela prend moins de place en mémoire. Dans ce cas, on met les lignes bout à bout. .. code:: ipython3 mat = [[1, 0, 0], [0, 4, 0], [1, 2, 3]] arr = [] for i, row in enumerate(mat): for j, x in enumerate(row): arr.append(x) arr .. parsed-literal:: [1, 0, 0, 0, 4, 0, 1, 2, 3] D’un côté, nous avons 4 listes avec ``mat`` et une seule avec ``arr``. Vérifions les tailles : .. code:: ipython3 import sys sys.getsizeof(mat), sys.getsizeof(arr) .. parsed-literal:: (88, 192) Etrange ! Mais pour comprendre, il faut lire la documentation de la fonction `getsizeof `__ qui ne compte pas la somme des objets référencés par celui dont on mesure la taille. Autrement dit, dans le cas d’une liste de listes, la fonction ne mesure que la taille de la première liste. Pour corriger le tir, on utilise la fonction suggérée par la documentation de Python. .. code:: ipython3 from ensae_teaching_cs.helpers.size_helper import total_size total_size(mat), total_size(arr) .. parsed-literal:: (488, 328) On peut aussi utiliser le module `pympler `__ et la fonction `asizeof `__. .. code:: ipython3 from pympler.asizeof import asizeof asizeof(mat), asizeof(arr) .. parsed-literal:: (504, 344) Cela prend énormément de place pour 9 *float* (soit 9x8 octets) mais Python stocke beaucoup plus d’informations qu’un langage compilé type C++. Cela explique pourquoi le module `numpy `__ fait la même chose avec moins d’espace mémoire car il est codé en C++. .. code:: ipython3 from numpy import array amat = array(mat) aarr = array(arr) asizeof(amat), asizeof(aarr) .. parsed-literal:: (152, 136) Et si on augmente le nombre de réels pour faire disparaître les coûts fixes : .. code:: ipython3 n = 100000 li = list(float(x) for x in range(n)) ar = array(li) asizeof(li) / n, asizeof(ar) / n .. parsed-literal:: (32.7984, 8.00096) Python prend 4 fois plus de place que numpy. du tableau à la liste de listes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ A moins que la matrice soit carrée, il faut conserver une des dimensions du tableau original, le nombre de lignes par exemple. .. code:: ipython3 arr = [1, 0, 0, 0, 4, 0, 1, 2, 3] nb_lin = 3 nb_col = len(arr) // nb_lin mat = [] pos = 0 for i in range(nb_lin): row = [] for j in range(nb_col): row.append(arr[pos]) pos += 1 mat.append(row) mat .. parsed-literal:: [[1, 0, 0], [0, 4, 0], [1, 2, 3]] On peut aussi faire comme ceci : .. code:: ipython3 arr = [1, 0, 0, 0, 4, 0, 1, 2, 3] nb_lin = 3 nb_col = len(arr) // nb_lin mat = [[0] * nb_col for i in range(nb_lin)] for pos, x in enumerate(arr): i = pos // nb_lin j = pos % nb_lin mat[i][j] = x mat .. parsed-literal:: [[1, 0, 0], [0, 4, 0], [1, 2, 3]]