Structures de données

by Christian Nguyen, Joseph Razik, on 2019-10-18
structures_de_donnees

Les tuples

In [1]:
tup = (1, 2, 3)
In [2]:
# informations sur un tuple
print('TUPLE tup = ', tup)
print("nombre d'éléments : ", len(tup))
print("2ème élément : ", tup[1])
print("id(tup): ", id(tup))
TUPLE tup =  (1, 2, 3)
nombre d'éléments :  3
2ème élément :  2
id(tup):  140110630613496
In [3]:
# tentative de modification d'une valeur du tupple
tup[1] = 4
# c'est un non mutable
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-3-d50014dc00e3> in <module>()
      1 # tentative de modification d'une valeur du tupple
----> 2 tup[1] = 4
      3 # c'est un non mutable

TypeError: 'tuple' object does not support item assignment
In [4]:
# nouveau tuple -> nouvelle référence
print('id(tup): ', id(tup))
tup = (4, 5)
print('id(tup): ', id(tup))
print('tup = ', tup)
id(tup):  140110630613496
id(tup):  140110673332232
tup =  (4, 5)

Les chaînes de caractères

In [5]:
ch = 'bonkour le monde'
In [6]:
print('id(ch) = ', id(ch))
print('ch[3] = ', ch[3])
id(ch) =  140110630542264
ch[3] =  k
In [7]:
try:
    ch[3] = 'j'
except TypeError as e:
    print("error: ", e)
ch = 'bonjour le monde'
print('id(ch) = ', id(ch))
print(ch)
error:  'str' object does not support item assignment
id(ch) =  140110630410616
bonjour le monde

Les listes

In [8]:
liste1 = [1, 2, 3]
print('LISTE liste1 = ', liste1)
print("nombre d'éléments : ", len(liste1))
print("2ème élément : ", liste1[1])
print("ref liste1: ", id(liste1))
liste1[1] = 4
print('liste1 = ', liste1, ' ; id(liste1) = ', id(liste1))
liste1 = [5, 6]
print('liste1 = ', liste1, ' ; id(liste1) = ', id(liste1))
LISTE liste1 =  [1, 2, 3]
nombre d'éléments :  3
2ème élément :  2
ref liste1:  140110630066120
liste1 =  [1, 4, 3]  ; id(liste1) =  140110630066120
liste1 =  [5, 6]  ; id(liste1) =  140110630066248
In [9]:
# attention encore aux références
liste2 = liste1
liste2[0] = 7
print('liste1 = ', liste1, ' ; liste2 = ', liste2)
print('id(liste1)= ', id(liste1), ' ; id(liste2) = ', id(liste2))
liste2 = liste1[:]
liste2[0] = 9
print('liste1 = ', liste1, ' ; liste2 = ', liste2)
print('id(liste1) = ', id(liste1), ' ; id(liste2) = ', id(liste2))
liste1 =  [7, 6]  ; liste2 =  [7, 6]
id(liste1)=  140110630066248  ; id(liste2) =  140110630066248
liste1 =  [7, 6]  ; liste2 =  [9, 6]
id(liste1) =  140110630066248  ; id(liste2) =  140110630066184
In [10]:
%load_ext tutormagic
In [11]:
%%tutor
liste1 =  [5, 6]
# attention encore aux références
liste2 = liste1
liste2[0] = 7
print('liste = ', liste, ' ; liste2 = ', liste2)
print('id(liste1)= ', id(liste1), ' ; id(liste2) = ', id(liste2))
liste2 = liste1[:]
liste2[0] = 9
print('liste1 = ', liste1, ' ; liste2 = ', liste2)
print('id(liste1) = ', id(liste1), ' ; id(liste2) = ', id(liste2))
In [12]:
# attention encore encore aux références
liste3 = [[0] * 3] * 4
print('liste3 = ', liste3)
print('id(liste3): ', id(liste3))
liste3[0][0] = 2
print('liste3 = ', liste3)
print('id(liste3[0]): ', id(liste3[0]), ' ; id(liste3[1]): ', id(liste3[1]),
      ' ; id(liste3[2]): ', id(liste3[2]), ' ; id(liste3[3]): ', id(liste3[3]))
liste3 = [[0] * 3 for i in range(4)]
liste3[0][0] = 2
print('liste3 = ', liste3)
print('id(liste3[0]): ', id(liste3[0]), ' ; id(liste3[1]): ', id(liste3[1]),
      ' ; id(liste3[2]): ', id(liste3[2]), ' ; id(liste3[3]): ', id(liste3[3]))
liste3 =  [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
id(liste3):  140110673338824
liste3 =  [[2, 0, 0], [2, 0, 0], [2, 0, 0], [2, 0, 0]]
id(liste3[0]):  140110673339144  ; id(liste3[1]):  140110673339144  ; id(liste3[2]):  140110673339144  ; id(liste3[3]):  140110673339144
liste3 =  [[2, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
id(liste3[0]):  140110630054600  ; id(liste3[1]):  140110673353480  ; id(liste3[2]):  140110673339080  ; id(liste3[3]):  140110673340936
In [13]:
%%tutor
# attention encore encore aux références
liste3 = [[0] * 3] * 4
print('liste3 = ', liste3)
print('id(liste3): ', id(liste3))
liste3[0][0] = 2
print('liste3 = ', liste3)
print('id(liste3[0]): ', id(liste3[0]), ' ; id(liste3[1]): ', id(liste3[1]),
      ' ; id(liste3[2]): ', id(liste3[2]), ' ; id(liste3[3]): ', id(liste3[3]))
liste3 = [[0] * 3 for i in range(4)]
liste3[0][0] = 2
print('liste3 = ', liste3)
print('id(liste3[0]): ', id(liste3[0]), ' ; id(liste3[1]): ', id(liste3[1]),
      ' ; id(liste3[2]): ', id(liste3[2]), ' ; id(liste3[3]): ', id(liste3[3]))

Les ensembles

In [14]:
tt1 = set((1, 2, 3))
tt2 = set([3, 4])
print('intersection : ', tt1 & tt2)
print('union : ', tt1 | tt2)
print('différence : ', tt1 - tt2)  # ens. vide == set()
tt3 = set([1, 2, 3, 2, 2])
print("set de [1, 2, 3, 2, 2]: ", tt3)
intersection :  {3}
union :  {1, 2, 3, 4}
différence :  {1, 2}
set de [1, 2, 3, 2, 2]:  {1, 2, 3}

Les dictionnaires

In [15]:
# on défini une fonction qui affiche une chaîne de caractères
def une_fonction():
    print("La fonction a été appelée.")
In [16]:
# on défini un dictionnaire. Celui-ci peut contenir en même temps des éléments de type différents
# un élément d'un dictionnaire est défini par un couple clé-valeur
# les dictionnaires ne sont pas ordonnés, chercher le ième élément n'a pas de sens
d = {'un': 1, 'deux': 'two', 3: 'trois'}
In [17]:
# modification de la valeur de l'élément de clé 3

d[3] = 'three'
print('d[3]: ', d[3])
print('d: ', d)
d[3]:  three
d:  {3: 'three', 'deux': 'two', 'un': 1}
In [18]:
# ajout d'un nouvel élément avec comme clé le caractère '4' et de valeur 4
d['4'] = 4
print("d['4']: ", d['4'])
print("d: ", d)
d['4']:  4
d:  {3: 'three', 'deux': 'two', '4': 4, 'un': 1}
In [19]:
# intérogation d'une clé qui n'existe pas dans le dictionnaire
d[5]
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-19-c4a3dbbac95b> in <module>()
      1 # interrogation d'une clé qui n'existe pas dans le dictionnaire
----> 2 d[5]

KeyError: 5
In [20]:
# il est possible et parfois très pratique de faire un dictionnaire de fonctions.
# ceci évite un succession de if/elsif en ne faisant qu'un appel à d[clé]()

une_fonction()  # appel de la fonction de manière classique
 
# on associe à la clé '4' la fonction précédente
d['4'] = une_fonction

# notez bien qu'il n'y a pas de parenthèses après le nom de la fonction
print('d: ', d)
print('d[4]: ', d['4'])

# appel de la fonction à travers le dictionnaire
d['4']()
La fonction a été appelée.
d:  {3: 'three', 'deux': 'two', '4': <function une_fonction at 0x7f6e0c5bb950>, 'un': 1}
d[4]:  <function une_fonction at 0x7f6e0c5bb950>
La fonction a été appelée.
In [21]:
# que se passe-t-il si on met les parenthèses après le nom de la fonction ?
d['4'] = une_fonction()
print('d: ', d)

# essayons de l'appeler comme précédemment
d['4']()
La fonction a été appelée.
d:  {3: 'three', 'deux': 'two', '4': None, 'un': 1}
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-21-e9bfe06efd16> in <module>()
      4 
      5 # essayons de l'appeler comme précédemment
----> 6 d['4']()

TypeError: 'NoneType' object is not callable

Application pratique des dictionnaires de fonctions

In [22]:
# Soit une grille de 3 cases sur 3 cases avec les valeurs suivantes:
M3x3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
BSUP = 2  # les bornes des positions sont entre 0 et BSUP
i, j = 0, 0  # les variables que nous utiliserons pour indiquer notre position

# on définit un dictionnaire de fonctions pour connaitre la valeur dans la grille à partir d'une position (i,j)
# dans une direction donnée: Nord, Sud, Est, Ouest
dmvt = {'N': max(j-1, 0), 'S': min(j+1, BSUP), 'E': min(i+1, BSUP),
        'O': max(i-1, 0)}

print('M3x3 = ', M3x3)
print('dmvt = ', dmvt)
M3x3 =  [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
dmvt =  {'N': 0, 'S': 1, 'E': 1, 'O': 0}
In [23]:
# nous nous plaçons en (0,0), quelle est la valeur de la case adjacente à l'est ?
print('a droite de M['+str(i)+']['+str(j)+']', ':', M3x3[j][dmvt['E']])

# plaçons nous en (0,1), quelle est maintenant la valeur de la case adjacente à l'est ?
i += 1
print('a droite de M['+str(i)+']['+str(j)+']', ':', M3x3[j][dmvt['E']])
# et vers le sud ?
print('en dessous de M['+str(i)+']['+str(j)+']', ':', M3x3[dmvt['S']][i])

# plaçons nous en (1,1), quelle est la valeur de la case adjacente au sud ?
j += 1
print('en dessous de M['+str(i)+']['+str(j)+']', ':', M3x3[dmvt['S']][i])
# ne fonctionne pas car évalué au moment de la lecture du code par l'interpréte
# d'où les valeurs déjà calculées de dmvt, qui ne dépendent plus de i ni de j
a droite de M[0][0] : 2
a droite de M[1][0] : 2
en dessous de M[1][0] : 5
en dessous de M[1][1] : 5
In [24]:
# nous devons utiliser des fonctions qui seront appelées à la demande
# comme ces fonctions sont simples, nous pouvons utiliser des fonctions anonymes: les fonctions lambda
i, j = 0, 0
dmvt = {'N': lambda: max(j-1, 0), 'S': lambda: min(j+1, BSUP),
        'E': lambda: min(i+1, BSUP), 'O': lambda: max(i-1, 0)}

print('dmvt = ', dmvt)
print('M3x3 = ', M3x3)
dmvt =  {'N': <function <lambda> at 0x7f6e0c5bbe18>, 'S': <function <lambda> at 0x7f6e0c5bb2f0>, 'E': <function <lambda> at 0x7f6e0c5bb9d8>, 'O': <function <lambda> at 0x7f6e0c5bba60>}
M3x3 =  [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
In [25]:
# on voit bien maintenant que le dictionnaire contient des fonctions et non plus des valeurs
# essayons de nouveau nos interrogations de valeurs
print('a droite de M['+str(i)+']['+str(j)+']', ':', M3x3[j][dmvt['E']()])
i += 1
print('a droite de M['+str(i)+']['+str(j)+']', ':', M3x3[j][dmvt['E']()])
print('en dessous de M['+str(i)+']['+str(j)+']', ':', M3x3[dmvt['S']()][i])
j += 1
print('en dessous de M['+str(i)+']['+str(j)+']', ':', M3x3[dmvt['S']()][i])
a droite de M[0][0] : 2
a droite de M[1][0] : 3
en dessous de M[1][0] : 5
en dessous de M[1][1] : 8