.. _question_2014:
Questions TD 2014
=================
.. _question_1A_2014_1:
Question à propos de trie
+++++++++++++++++++++++++
**question**
Il s'agit de reproduire à l'aide de dictionnaires un trie.
Voici le code que vous avez donné et qui effectivement fonctionne à merveille ::
def build_trie(mots) :
trie = { }
for m in mots :
r = trie
for c in m :
if c not in r : r[c] = { }
r = r[c]
return trie
Cependant, je ne comprends pas très bien comment il fait pour tourner !
A quel moment est ce que l'on modifie le dictionnaire ``trie`` défini
initialement comme ``{}`` ? Pour moi, pour chaque ``m`` dans ``mots``,
on ne fait que créer une copie nommée ``r`` de trie,
c'est à dire au début ``{}``, puis on réalise des opérations
sur ce ``r`` que l'on modifie en cours de route, et à la fin de ces opérations,
on passe au mot suivant en créant une nouvelle copie ``r`` de ``trie``,
à savoir toujours ``{}`` !
**réponse**
Il existe un bon moyen de visualiser l'exécution, c'est le site
`Python Tutor `_. En recopiant, l'exemple suivant,
on peut suivre pas à pas l'exécution ::
def build_trie(mots) :
trie = { }
for m in mots :
r = trie
for c in m :
if c not in r : r[c] = { }
r = r[c]
return trie
mots = [ "aaa", "aba", "aab", "baa", "bbb", "bba", "bab" ]
trie = build_trie(mots)
print(trie)
A chaque nouveau mot, les premiers caractères vont probablement faire déjà partie du
trie, les derniers vont être ajoutés au bout d'une branche existante. La question
est comment trouver cette branche. Cette branche peut avoir une longueur
variable.
.. image:: wiki_trie2.png
Pour trouver cette branche, le mécanisme qu'on utilise est très proche
de celui qu'on uilise pour se déplacer dans une
`liste chaînée `_.
Dans une liste chaînée, il n'y a pas d'indice pour un élément. Chaque élément
pointe sur le suivant (il est conseillé d'utiliser
`Python Tutor `_ pour visualiser l'exécution) ::
class liste_chainee :
def __init__ (self, value):
self.value = value
self.next = None
def attache(self, element):
self.next = element
def atteindre_la_fin(self):
position_courante = self
if position_courante.next is not None:
position_courante = position_courante.next
return position_courante
e0 = liste_chainee (0)
e1 = liste_chainee (1)
e2 = liste_chainee (2)
e0.attache(e1)
e1.attache(e2)
fin = e0.atteindre_la_fin()
print(fin.value)
Cet exemple est plus simple car pour se déplacer du début à la fin, il n'y
qu'une seule *direction* : soit on est à la fin, soit il faut continuer
car il y a un élément suivant (``next`` n'est pas ``None``).
Toutefois, le programme précédent montre qu'il faut utiliser une
variable ``position_courante`` qui mémorise la position
à laquelle on se trouve lorsqu'on parcours la liste.
Pour avancer, on exécute simplement ::
position_courante = position_courante.next
La position courante devient la suivante. Dans le cas du trie, cette
instruction change car l'élément suivant dépend du caractère ``c`` ::
r = r[c]
Le premier code comprend deux éléments :
* le fait de se promener le long d'un chemin ::
r = trie # initialisation
r = r[c] # on avance d'un cran
* le fait d'ajouter un caractère au trie ::
r[c] = { }
Le caractère ``c`` a été ajouté au trie en tant que clé d'un dictionnaire,
lui-même valeur d'un dictionnaire associé à une clé égale
au caractère précédent dans le mot qu'on est en train d'ajouter.
**suite**
Lorsque l'on crée un dictionnaire, appelons le "a", puis que l'on en crée
une autre copie, que l'on appelle "b", et que l'on modifie b,
alors a se retrouve modifié ! Le dictionnaire ``b`` est en fait plus qu'une copie,
mais une deuxième entité qui code le même objet,
et je crois que c'est ca que je n'avais pas compris.
Par ailleurs, ce qui est surprenant, c'est que ceci ne fonctionne
qu'avec les dictionnaires ! Lorsque l'on execute ceci ::
a=[]
b=a
b = b+[2]
print(a)
Alors la sortie est ``[]``. Quand on execute ceci ::
a={}
b=a
b[1]=1
print(a)
La réponse est ``{1 : 1}``.
**réponse**
Ceci est une propriété des listes et des dictionnaires qui sont des objets **mutable** en Python.
Je renvoie à la page `Qu’est-ce qu’un type immuable ou immutable ? `_
pour comprendre ce que sont ces deux propriétés en particulier.
Les listes sont **mutable**. Donc si on écrit ``b = a``, on crée un second identifiant pour accéder
à la même liste. Voici pourquoi écrire ``a[0]=1`` a le même effet que ``b[0]=1``.
Toutefois, dans le cas où ``b`` désigne une copie de la liste ``a``, ces deux instructions
n'auront pas les mêmes conséquences. Pour comprendre le résultat, il faut se demander
dans quel cas, on ne fait de copie, dans quel autre une copie a été créée.
L'instruction ``b=a`` ne crée pas de copie. L'instuction ``b=b+[2]`` construit
la concaténation de deux listes, c'est donc une nouvelle liste qu'on affecte à ``b``.
Dans l'exemple suivant, ce n'est plus le cas même si le code paraît équivalent ::
a=[]
b=a
b += [2] # --> il n'y a plus de copie implicite
print(a) # --> affiche [2]
Le même exemple pour être écrit avec des dictionnaires car ils sont aussi **mutable**.