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

5.1.4 List Comprehensions

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.