Sous-sections
5. Structures de Données
Ce chapitre décrit avec plus de détail quelques éléments que vous
avez déjà étudié, et ajoute aussi quelques nouveautés.
5.1 Plus de Détails sur les Listes
Le type de données liste possède d'autres méthodes. Voici toutes les
méthodes des objets listes:
append(x)
- Equivalent à
a.insert(len(a), x) .
extend(L)
- Rallonge la liste en ajoutant à la fin tous les éléments de la liste
donnée; équivalent à
a[len(a):] = L .
insert(i, x)
- Insère un élément à une position donnée. Le premier argument est
l'indice de l'élément avant lequel il faut insérer, donc
a.insert(0, x) insère au début de la liste, et
a.insert(len(a), x) est équivalent à a.append(x) .
remove(x)
- Enlève le premier élément de la liste dont la valeur est
x .
Il y a erreur si cet élément n'existe pas.
pop([i])
- Enlève l'élément présent à la position donnée dans la liste, et le
renvoie. Si aucun indice n'est spécifié,
a.pop() renvoie le
dernier élément de la liste. L'élément est aussi supprimé de la
liste.
index(x)
- Retourne l'indice dans la liste du premier élément dont la valeur
est
x . Il y a erreur si cet élément n'existe pas.
count(x)
- Renvoie le nombre de fois que
x apparaît dans la liste.
sort()
- Trie les éléments à l'intérieur de la liste.
reverse()
- Renverse l'ordre des éléments à l'intérieur de la liste.
Un exemple qui utilise toutes les méthodes des listes:
>>> a = [66.6, 333, 333, 1, 1234.5]
>>> print a.count(333), a.count(66.6), a.count('x')
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.6, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.remove(333)
>>> a
[66.6, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.6]
>>> a.sort()
>>> a
[-1, 1, 66.6, 333, 333, 1234.5]
5.1.1 Utiliser les Listes comme des Piles
Les méthodes des listes rendent très facile l'utilisation d'une liste
comme une pile, où le dernier élément ajouté est le premier élément
récupéré (LIFO, ``last-in, first-out''). Pour ajouter un élément au
sommet de la pile, utilisez la méthode append(). Pour
récupérer un élément du sommet de la pile, utilisez pop()
sans indice explicite. Par exemple:
>>> pile = [3, 4, 5]
>>> pile.append(6)
>>> pile.append(7)
>>> pile
[3, 4, 5, 6, 7]
>>> pile.pop()
7
>>> pile
[3, 4, 5, 6]
>>> pile.pop()
6
>>> pile.pop()
5
>>> pile
[3, 4]
5.1.2 Utiliser les Listes comme des files
Vous pouvez aussi utiliser facilement une liste comme une file, où le
premier élément ajouté est le premier élément retiré (FIFO,
``first-in, first-out''). Pour ajouter un élément à la fin de la file,
utiliser append(). Pour récupérer un élément du devant de la
file, utilisez pop() avec 0 pour indice. Par exemple;
>>> file = ["Eric", "John", "Michael"]
>>> file.append("Terry") # Terry arrive
>>> file.append("Graham") # Graham arrive
>>> file.pop(0)
'Eric'
>>> file.pop(0)
'John'
>>> file
['Michael', 'Terry', 'Graham']
5.1.3 Outils de Programmation Fonctionnelle
Il y a trois fonctions intégrées qui sont très pratiques avec les
listes: filter(), map(), et reduce().
"filter(fonction, sequence)" renvoit une liste (du
même type, si possible) contenant les seul éléments de la séquence pour
lesquels fonction(element) est vraie. Par exemple,
pour calculer quelques nombres premiers:
>>> def f(x): return x % 2 != 0 and x % 3 != 0
...
>>> filter(f, range(2, 25))
[5, 7, 11, 13, 17, 19, 23]
"map(fonction, sequence)" appelle
fonction(element) pour chacun des éléments de la
séquence et renvoie la liste des valeurs de retour. Par exemple, pour
calculer les cubes:
>>> def cube(x): return x*x*x
...
>>> map(cube, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]
Plusieurs séquences peuvent être passées en paramètre; la fonction doit
alors avoir autant d'arguments qu'il y a de séquences et est appelée
avec les éléments correspondants de chacune des séquences (ou
None si l'une des séquences est plus courte que l'autre). Si
None est passé en tant que fonction, une fonction retournant ses
arguments lui est substituée.
En combinant ces deux cas spéciaux, on voit que "map(None,
liste1, liste2)" est une façon pratique de transformer un
couple de liste en une liste de couples. Par exemple:
>>> seq = range(8)
>>> def carre(x): return x*x
...
>>> map(None, seq, map(carre, seq))
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49)]
"reduce(fonction, sequence)" renvoie une valeur unique
construite par l'appel de la fonction binaire fonction sur les deux
premiers éléments de la séquence, puis sur le résultat et l'élément
suivant, et ainsi de suite. Par exemple, pour calculer la somme des
nombres de 1 à 10:
>>> def ajoute(x,y): return x+y
...
>>> reduce(ajoute, range(1, 11))
55
S'il y a seulement un élément dans la séquence, sa valeur est
renvoyée; si la séquence est vide, une exception est déclenchée.
Un troisième argument peut être transmis pour indiquer la valeur de
départ. Dans ce cas, la valeur de départ est renvoyée pour une
séquence vide, et la fonction est d'abord appliquée à la valeur de
départ et au premier élément de la séquence, puis au résultat et à
l'élément suivant, et ainsi de suite. Par exemple,
>>> def somme(seq):
... def ajoute(x,y): return x+y
... return reduce(ajoute, seq, 0)
...
>>> somme(range(1, 11))
55
>>> somme([])
0
Les list comprehensions fournissent une façon concise de créer
des listes sans avoir recours à map(), filter()
et/ou lambda. La définition de liste qui en résulte a
souvent tendance à être plus claire que des listes construites avec
ces outils. Chaque list comprehension consiste en une
expression suivie d'une clause for, puis zéro ou plus
clauses for ou if. Le résultat sera une liste
résultant de l'évaluation de l'expression dans le contexte des clauses
for et if qui la suivent. Si l'expression s'évalue
en un tuple, elle doit être mise entre parenthèses.
>>> fruitfrais = [' banane', ' myrtille ', 'fruit de la passion ']
>>> [projectile.strip() for projectile in fruitfrais]
['banane', 'myrtille', 'fruit de la passion']
>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]
>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]
>>> [{x: x**2} for x in vec]
[{2: 4}, {4: 16}, {6: 36}]
>>> [[x,x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]
>>> [x, x**2 for x in vec] # erreur - parenthèses obligatoires pour les tuples
File "<stdin>", line 1
[x, x**2 for x in vec]
^
SyntaxError: invalid syntax
>>> [(x, x**2) for x in vec]
[(2, 4), (4, 16), (6, 36)]
>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
5.2 L'instruction del
Il y a un moyen d'enlever un élément d'une liste en ayant son indice
au lieu de sa valeur: l'instruction del . Ceci peut aussi être
utilisé pour enlever des tranches dans une liste (ce que l'on a fait
précédemment par remplacement de la tranche par une liste vide). Par
exemple:
>>> a
[-1, 1, 66.6, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.6, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.6, 1234.5]
del peut aussi être utilisé pour supprimer des variables
complètes:
>>> del a
Faire par la suite référence au nom a est une erreur (au moins
jusqu'à ce qu'une autre valeur ne lui soit affectée). Nous trouverons
d'autres utilisations de del plus tard.
5.3 N-uplets (tuples) et Séquences
Nous avons vu que les listes et les chaînes ont plusieurs propriétés
communes, par ex., l'indexation et les opérations de découpage. Elles
sont deux exemples de types de données de type séquence. Puisque
Python est un langage qui évolue, d'autres types de données de type
séquence pourraient être ajoutés. Il y a aussi un autre type de
données de type séquence standard: le tuple (n-uplet).
Un n-uplet consiste en un ensemble de valeurs séparées par des
virgules, par exemple:
>>> t = 12345, 54321, 'salut!'
>>> t[0]
12345
>>> t
(12345, 54321, 'salut!')
>>> # Les Tuples peuvent être imbriqués:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'salut!'), (1, 2, 3, 4, 5))
Comme vous pouvez le voir, à l'affichage, les tuples sont toujours
entre parenthèses, de façon à ce que des tuples de tuples puissent
être interprétés correctement; ils peuvent être saisis avec ou sans
parenthèses, bien que des parenthèses soient souvent nécessaires (si
le tuple fait partie d'une expression plus complexe).
Les tuples ont plein d'utilisations, par exemple, les couples de
coordonnées (x, y), les enregistrements des employés d'une base de
données, etc. Les tuples, comme les chaînes, sont non-modifiables: il
est impossible d'affecter individuellement une valeur aux éléments
d'un tuple (bien que vous puissiez simuler quasiment cela avec le
découpage et la concaténation).
Un problème particulier consiste à créer des tuples contenant 0 ou 1
élément: la syntaxe reconnaît quelques subtilités pour y arriver. Les
tuples vides sont construits grâce à des parenthèses vides; un tuple
avec un élément est construit en faisant suivre une valeur d'une
virgule (il ne suffit pas de mettre une valeur seule entre
parenthèses). Moche, mais efficace. Par exemple:
>>> empty = ()
>>> singleton = 'salut', # <-- notez la virgule en fin de ligne
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('salut',)
L'instruction t = 12345, 54321, 'salut!' est un exemple d'
emballage en tuple (tuple packing): les valeurs 12345 ,
54321 et 'salut!' sont emballées ensemble dans un tuple.
L'opération inverse est aussi possible, par ex.:
>>> x, y, z = t
Ceci est appelé, fort judicieusement, déballage de
tuple (tuple unpacking). Le déballage d'un tuple nécessite que la
liste des variables à gauche ait un nombre d'éléments égal à la
longueur du tuple. Notez que des affectations multiples ne sont en
réalité qu'une combinaison d'emballage et déballage de tuples!
5.4 Dictionnaires
Un autre type de données intégré à Python est le dictionnaire.
Les dictionnaires sont parfois trouvés dans d'autres langages sous le
nom de ``mémoires associatives'' ou ``tableaux associatifs''. A la
différence des séquences, qui sont indexées par un intervalle
numérique, les dictionnaires sont indexés par des clés, qui
peuvent être de n'importe quel type non-modifiable; les chaînes et les
nombres peuvent toujours être des clés. Les tuples peuvent être
utilisés comme clés s'ils ne contiennent que des chaînes, des nombres
ou des tuples. Vous ne pouvez pas utiliser des listes comme clés,
puisque les listes peuvent être modifiées en utilisant leur méthode
append() .
Il est préférable de considérer les dictionnaires comme des ensembles
non ordonnés de couples clé:valeur, avec la contrainte que les
clés soient uniques (à l'intérieur d'un même dictionnaire). Un couple
d'accolades crée un dictionnaire vide: {} . Placer une liste
de couples clé:valeur séparés par des virgules à l'intérieur des
accolades ajoute les couples initiaux clé:valeur au dictionnaire;
c'est aussi de cette façon que les dictionnaires sont affichés.
Les opérations principales sur un dictionnaire sont le stockage d'une
valeur à l'aide d'une certaine clé et l'extraction de la valeur en
donnant la clé. Il est aussi possible de détruire des couples
clé:valeur avec del . Si vous stockez avec une clé déjà utilisée,
l'ancienne valeur associée à cette clé est oubliée. C'est une erreur
d'extraire une valeur en utilisant une clé qui n'existe pas.
La méthode keys() d'un objet de type dictionnaire retourne une
liste de toutes les clés utilisées dans le dictionnaire, dans un ordre
quelconque (si vous voulez qu'elle soit triée, appliquez juste la
méthode sort() à la liste des clés). Pour savoir si une clé
particulière est dans le dictionnaire, utilisez la méthode
has_key() du dictionnaire.
Voici un petit exemple utilisant un dictionnaire:
>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> tel.keys()
['guido', 'irv', 'jack']
>>> tel.has_key('guido')
1
5.5 Plus de Détails sur les Conditions
Les conditions utilisées dans les instructions while et
if peuvent contenir d'autres opérateurs en dehors des
comparaisons.
Les opérateurs de comparaison in et not in vérifient si
une valeur apparaît (ou non) dans une séquence. Les opérateurs
is et is not vérifient si deux objets sont réellement le
même objet; ceci se justifie seulement pour les objets modifiables
comme les listes. Tous les opérateurs de comparaison ont la même
priorité, qui est plus faible que celle de tous les opérateurs
numériques.
Les comparaisons peuvent être enchaînées: par ex., a < b == c
teste si a est inférieur ou égal à b et de plus si
b est égal à c .
Les comparaisons peuvent être combinées avec les opérateurs Booléens
and (et) et or (ou), et le résultat d'une comparaison (ou
de n'importe quel autre expression Booléenne) peut être inversé avec
not (pas). Ces opérateurs ont encore une fois une priorité
inférieure à celle des opérateurs de comparaison; et entre eux,
not a la plus haute priorité, et or la plus faible, de
sorte que A and not B or C est équivalent à (A and
(not B)) or C . Bien sûr, les parenthèses peuvent être utilisées
pour exprimer les compositions désirées.
Les opérateurs Booléens and et or sont des opérateurs
dits raccourcis : leurs arguments sont évalués de
gauche à droite, et l'évaluation s'arrête dès que le résultat est
trouvé. Par exemple, si A et C sont vrais mais que
B est faux, A and B and C n'évalue pas l'expression C.
En général, la valeur de retour d'un opérateur raccourci, quand elle
est utilisée comme une valeur générale et non comme un Booléen, est celle du
dernier argument évalué.
Il est possible d'affecter le résultat d'une comparaison ou une autre
expression Booléenne à une variable. Par exemple,
>>> chaine1, chaine2, chaine3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = chaine1 or chaine2 or chaine3
>>> non_null
'Trondheim'
Notez qu'en Python, au contraire du C, les affectations ne peuvent
pas être effectuées à l'intérieur des expressions.
5.6 Comparer Les Séquences et d'Autres Types
Les objets de type séquence peuvent être comparés à d'autres objets
appartenant au même type de séquence. La comparaison utilise l'ordre
lexicographique : les deux premiers éléments sont d'abord
comparés, et s'ils diffèrent ceci détermine le résultat de la
comparaison; s'ils sont égaux, les deux éléments suivants sont
comparés, et ainsi de suite, jusqu'à ce que l'une des deux séquences
soit épuisée. Si deux éléments à comparer sont eux-mêmes des séquences
du même type, la comparaison lexicographique est reconsidérée
récursivement. Si la comparaison de tous les éléments de deux
séquences les donne égaux, les séquences sont considérées comme
égales. Si une séquence est une sous-séquence initiale de l'autre, la
séquence écourtée est la plus petite. L'ordonnancement lexicographique
pour les chaînes utilise l'ordonnancement ASCII pour les caractères.
Quelques exemples de comparaisons de séquences du même type:
(1, 2, 3) < (1, 2, 4)
[1, 2, 3] < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4) < (1, 2, 4)
(1, 2) < (1, 2, -1)
(1, 2, 3) == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab')) < (1, 2, ('abc', 'a'), 4)
Notez que la comparaison d'objets de types différents est licite. Le
résultat est déterministe mais arbitraire: les types sont triés selon
leur nom. Ainsi une liste (list) est toujours inférieure à une chaîne
(string), une chaîne (string) est toujours inférieure à un n-uplet
(tuple), etc. Les types numériques mélangés sont comparés en fonction
de leur valeur numérique, ainsi 0 est égal à 0.0, etc.5.1
Notes
- ...5.1
- On ne doit pas se fier aux règles de comparaison pour des
objets de types différents; elles pourraient changer dans une
version ultérieure du langage.
See About this document... for information on suggesting changes.
|