D’une structure de données à l’autre

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.

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.

ens = ["a", "b", "gh", "er", "b", "gh"]
hist = {}
for e in ens:
    hist[e] = hist.get(e, 0) + 1
hist

{'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 :

ens = ["a", "b", "gh", "er", "b", "gh"]
hist = {}
for e in ens:
    if e in hist:
        hist[e] += 1
    else:
        hist[e] = 1
hist

{'a': 1, 'b': 2, 'gh': 2, 'er': 1}

Il existe également la fonction Counter qui fait cela.

from collections import Counter

ens = ["a", "b", "gh", "er", "b", "gh"]
hist = Counter(ens)
hist

Counter({'b': 2, 'gh': 2, 'a': 1, '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.

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

['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.

hist.items()

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 :

import sys

vue = hist.items()
sys.getsizeof(ens), sys.getsizeof(hist), sys.getsizeof(vue)

(120, 232, 40)

Et pour un dictionnaire plus grand, la taille du dictionnaire.

d = {i: i for i in range(1000)}
sys.getsizeof(d), sys.getsizeof(d.items())

(36960, 40)

On peut ne pas utiliser la méthode items :

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

['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.

hist = {"a": 1, "b": 2, "er": 1, "gh": 2}
cles = [k for k in hist]
vals = [hist[k] for k in hist]
cles, vals

(['a', 'b', 'er', 'gh'], [1, 2, 1, 2])

On peut écrire aussi ce programme

hist = {"a": 1, "b": 2, "er": 1, "gh": 2}
cles = list(hist.keys())
vals = list(hist.values())
cles, vals

(['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.

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

(['a', 'b', 'er', 'gh'], [1, 2, 1, 2])

deux listes et dictionnaires

On effectue l’opération inverse.

cles, vals = ["a", "gh", "er", "b"], [1, 2, 1, 2]
hist = {a: b for a, b in zip(cles, vals)}
hist

{'a': 1, 'gh': 2, 'er': 1, 'b': 2}

Et si on ne veut pas utiliser la fonction zip :

cles, vals = ["a", "gh", "er", "b"], [1, 2, 1, 2]
hist = {}
for i in range(len(cles)):
    hist[cles[i]] = vals[i]
hist

{'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 :

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

(['a', 'b', 'er', 'gh'], [1, 2, 1, 2])

Cela devient :

hist = {"a": 1, "b": 2, "er": 1, "gh": 2}
cles, vals = zip(*hist.items())
cles, vals

(('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.

mat = [[1, 2], [3, 4]]
dv = {}
for i, row in enumerate(mat):
    for j, x in enumerate(row):
        dv[i, j] = x
dv

{(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.

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

[[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.

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

{(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.

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

[[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.

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

[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 :

import sys

sys.getsizeof(mat), sys.getsizeof(arr)

(80, 184)

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.

from teachpyx.tools import total_size

total_size(mat), total_size(arr)

(480, 320)

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++.

from numpy import array

amat = array(mat)
aarr = array(arr)
total_size(amat), total_size(aarr)

(200, 184)

Et si on augmente le nombre de réels pour faire disparaître les coûts fixes :

n = 100000
li = list(float(x) for x in range(n))
ar = array(li)
total_size(li) / n, total_size(ar) / n

(32.00984, 8.00112)

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.

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

[[1, 0, 0], [0, 4, 0], [1, 2, 3]]

On peut aussi faire comme ceci :

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

[[1, 0, 0], [0, 4, 0], [1, 2, 3]]

---

Notebook on github