Blog ENI : Toute la veille numérique !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Python 3
  3. Séquences et algorithmes appliqués
Extrait - Python 3 Les fondamentaux du langage (4e édition)
Extraits du livre
Python 3 Les fondamentaux du langage (4e édition)
3 avis
Revenir à la page d'achat du livre

Séquences et algorithmes appliqués

Présentation des différents types de séquences

1. Généralités

Une séquence est un conteneur d’objets (qui ne sont pas forcément uniques) disposant d’une relation d’ordre. Cela signifie que les objets peuvent être de tout type, et qu’ils sont stockés dans un ordre précis. Plusieurs objets peuvent ainsi être plusieurs fois dans la même séquence, à des positions différentes.

On distingue deux types de séquences, celles modifiables ou mutables, les listes et celles non modifiables ou non mutables, les n-uplets ou tuple en anglais.

Les premières sont utilisées pour gérer une séquence d’objets qui est destinée à « vivre », c’est-à-dire à être modifiée régulièrement ; les secondes sont utilisées pour regrouper des données, lorsque les valeurs ont un sens plus large que simplement une succession d’objets ordonnés ou pour des raisons de performances. La conservation de la sémantique nécessite que l’objet ne puisse être modifié.

Ainsi, lorsqu’une fonction ou une méthode retourne plusieurs valeurs, elle retourne en réalité un n-uplet de valeurs :

>>> def test(): 
...     return 1, 2, 3 
...  
>>> test() 
(1, 2, 3) 
>>> a, b, c = test() 
>>> a 
1  
>>> b 
2  
>>> c 
3 

Pour exprimer, par exemple, les coordonnées d’un point, dans le plan ou dans l’espace, le n-uplet est plus volontiers utilisé que la liste, car il a un sens plus fort :

>>> o=(0,0)  
>>> p=(1,6) 

Travailler avec les listes peut s’effectuer par la programmation objet, mais aussi par la programmation...

Notion d’itérateur

Un itérateur est un générateur qui permet de parcourir une séquence :

>>> l=[1, 2, 3] 
>>> it=iter(l) 
>>> next(it) 
1 
>>> next(it) 
2 
>>> next(it) 
3 
>>> next(it) 
Traceback (most recent call last): 
File "<stdin>", line 1, in <module> 
StopIteration 

La primitive next permet de passer d’un élément au suivant. Elle utilise la méthode spéciale __next__ de l’itérateur. Voici d’ailleurs l’intégralité de ses attributs et méthodes :

>>> dir(iter) 
['__call__', '__class__', '__delattr__', '__doc__', '__eq__', 
'__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', 
'__init__', '__le__', '__lt__', '__module__', '__name__', '__ne__', 
'__new__', '__reduce__', '__reduce_ex__', '__repr__', '__self__', 
'__setattr__', '__sizeof__', '__str__', '__subclasshook__'] 

Ces deux extraits de code sont exactement équivalents :

>>> for i in l: 
...     print(i) 
...  
1 
2 
3 
>>> for i in iter(l): 
...     print(i) 
...  
1 
2 
3 

Lorsque for est utilisé, il va chercher la méthode spéciale __iter__ de l’objet placé après le mot-clé in. La séquence renvoie un itérateur sur elle-même et l’itérateur se renvoie lui-même. Le résultat final est identique.

L’avantage d’utiliser un itérateur est que la boucle se termine...

Utilisation des indices et des tranches

1. Définition de l’indice d’un objet et des occurrences

L’indice (index en anglais) est le numéro de l’emplacement d’un objet dans la séquence, en partant de son début et en suivant la relation d’ordre.

Il peut être obtenu simplement, par l’utilisation de la méthode index en y passant en argument l’objet souhaité :

>>> l = [42, 74, 34] 
>>> l.index(34) 
2 

Si l’indice d’un objet non présent est demandé, une exception est alors obtenue :

>>> l.index(13) 
Traceback (most recent call last): 
File "<stdin>", line 1, in <module> 
ValueError: 13 is not in list 

Si un objet est présent plusieurs fois dans une liste, le second paramètre de la méthode index est utilisé, qui n’est pas le numéro de l’occurrence, mais le rang à partir duquel chercher :

>>> l = [42, 74, 34, 42, 51] 
>>> l.index(42, 0) 
0 
>>> l.index(42, 1) 
3 
>>> l.index(42, 2) 
3 
>>> l.index(42, 3) 
3 
>>> l.index(42, 4) 
Traceback (most recent call last): 
File "<stdin>", line 1, in <module> 
ValueError: 42 is not in list 

Voici comment trouver simplement les indices de toutes les occurrences :

>>> def indices(l, o, i=-1): 
...     while 1: 
...         try: 
...             i=l.index(o, i+1) 
...         except: 
...             return 
...         yield i 
...  
>>> for i in indices(l, 42): 
...     print(i) 
...  
0 
3 

Il est également possible de compter...

Utilisation des opérateurs

1. Opérateur +

L’opérateur + a une signification particulière pour la séquence : la concaténation.

Les deux opérandes doivent forcément être homogènes :

>>> [1, 2]+(3, 4) 
Traceback (most recent call last): 
File "<stdin>", line 1, in <module> 
TypeError: can only concatenate list (not "tuple") to list 
>>> (1, 2)+[3, 4] 
Traceback (most recent call last): 
File "<stdin>", line 1, in <module> 
TypeError: can only concatenate tuple (not "list") to tuple 

Le résultat de l’utilisation de l’opérateur + sur de deux séquences est une séquence contenant l’ensemble des éléments de l’opérande de gauche, dans l’ordre, suivi de l’ensemble de ceux de droite, dans l’ordre. La relation d’ordre est donc conservée :

>>> [1, 2]+[3, 4] 
[1, 2, 3, 4] 

L’opérateur + se connecte à la méthode __add__ de la liste. Comme les deux opérandes sont forcément homogènes, il n’est pas nécessaire d’avoir une méthode __radd__ qui est présente lorsque l’opérande de gauche ne possède pas __add__. Ceci permet de surcharger l’opérateur simplement, pour lui donner une autre signification.

Un exemple classique en est de reporter la signification de l’opérateur sur tous les membres de la séquence :

>>> class test(list): 
...     HETEROGENE_ERROR='can only concatenate test (not "%s") to test' 
...     def __add__(self, other): 
...         if not isinstance(other, test): 
...             raise TypeError(test.HETEROGENE_ERROR...

Méthodes de modifications

1. Ajouter des éléments dans une liste et un n-uplet

Il n’est pas possible d’ajouter un nouvel objet à la liste par l’utilisation d’un indice hors d’une liste ou par l’utilisation de l’opérateur crochet sans arguments, cette syntaxe existant dans d’autres langages tels que PHP :

>>> l 
[42, 74, 34] 
>>> l[3] = 42 
Traceback (most recent call last): 
File "<stdin>", line 1, in <module> 
IndexError: list assignment index out of range 
>>> l[] = 42 
File "<stdin>", line 1 
l[] = 42 
 ^ 
SyntaxError: invalid syntax 

Pour ajouter un nouvel élément dans une liste, il faut alors se reporter sur les méthodes classiques de la liste.

La méthode append rajoute un élément en fin de liste :

>>> l = [1, 2, 3] 
>>> l.append(4) 
>>> l 
[1, 2, 3, 4] 

La méthode insert rajoute un élément, en précisant son index. Voici comment ajouter un objet en début de liste, par exemple :

>>> l = [1, 2, 3] 
>>> l.insert(0, 4) 
>>> l 
[4, 1, 2, 3] 

Comme pour les autres méthodes, l’utilisation de l’indice négatif est permise :

>>> l.insert(-2, 5) 
>>> l 
[4, 1, 5, 2, 3] 

L’objet entier 5 est ajouté deux places avant la fin, soit à la troisième position de la liste à 4 éléments ou à l’index 2.

Ces méthodes sont les seules méthodes permettant de rajouter un objet à une liste par des traitements unitaires.

Il n’est pas permis d’utiliser des slices pour rajouter plusieurs valeurs :

>>> l.insert(slice(1, 2), [1]) 
Traceback (most recent call last): ...

Utilisation avancée des listes

1. Opérations d’ensemble

Voici trois opérations d’ensemble sur les membres de la liste déjà vues dans le chapitre Nombres, booléens et algorithmes appliqués - section Opérations mathématiques n-aires :

>>> l = [1, 2, 3] 
>>> max(l) 
3 
>>> min(l) 
1 
>>> sum(l) 
6 

Ces opérations ne sont utilisables que pour des objets disposant d’une relation d’ordre, pour les deux premiers ou additionnables entre eux, pour la somme.

De plus, tous les objets Python ont une valeur booléenne, comme nous l’avons vu dans le chapitre précédent. Soit trois listes ainsi déclarées :

>>> l1 = [1, 2, 3] 
>>> l2 = [0, 1] 
>>> l3 = [0, ''] 

Il est donc possible de savoir si tous les éléments de la liste sont vrais :

>>> all(l1) 
True 
>>> all(l2) 
False 
>>> all(l3) 
False 

Il est aussi possible de savoir si au moins un membre de la liste est vrai :

>>> any(l1) 
True 
>>> any(l2) 
True 
>>> any(l3) 
False 

Et bien sûr, cela peut s’utiliser en combinaison avec le mot-clé not, permettant d’avoir la réponse aux questions « aucun élément n’est vrai » :

>>> not any(l3) 
True 
>>> not any(l2) 
False 
>>> not any(l1) 
False 

Et « Au moins un élément est faux » :

>>> not all(l3) 
True 
>>> not all(l2) 
True 
>>> not all(l1) 
False 

2. Pivoter une séquence

La primitive zip est une des particularités de Python qui permet de grandement simplifier la manipulation croisée...

Adapter les listes à des besoins spécifiques

1. Liste d’entiers

L’idée est de contrôler les données mises dans la liste de manière à s’assurer qu’elles ne contiennent que des nombres (entiers ou flottants) :

class intlist(list): 
   """Liste de nombres""" 
 
   __types__ = [int, float] 
 
    def __init__(self, *args, **kwargs): 
           """Surcharge générique du constructeur""" 
           list.__init__(self, *args, **kwargs) 
           for index, value in enumerate(self): 
                  if type(value) not in self.__types__: 
                         raise TypeError("l'objet %s d'index %s de  
la séquence n'est pas un nombre" % (value, index)) 
 
    def append(self, value): 
           """Surcharge de la méthode d'ajout d'éléments en fin de  
liste""" 
           if type(value) not in self.__types__: 
                 raise TypeError("%s n'est pas un nombre" % value) 
           list.append(self, value) 
 
    def insert(self, index, value): 
           """Surcharge de la méthode d'ajout d'éléments à un index 
donné""" 
           if type(value) not in self.__types__: 
   ...

Autres types de données

Si la liste et le n-uplet sont les collections par excellence, on a vu que pour certains besoins particuliers, des objets comme le deque sont bien mieux indiqués. Il existe également beaucoup d’autres objets qui peuvent présenter un intérêt, et parmi ceux-ci nous allons en présenter deux.

Tout d’abord, dans le module collections, nous allons présenter le namedtuple. On a vu que les n-uplets permettent de représenter une donnée en listant ses composantes et que l’ordre dans lequel apparaissent ces composantes est essentiel à la compréhension de l’objet.

Ainsi, lorsque l’on parle d’un point dans un plan, on comprend que le n-uplet (4,2) représente le point d’abscisse 4 et d’ordonnée 2.

L’idée de base derrière le namedtuple est extrêmement simple. Il s’agit tout simplement de permettre une meilleure sémantique pour de telles données sans recourir à l’écriture d’une classe particulière et sans perdre les avantages des n-uplets en termes de performances et de facilité d’utilisation.

Si on reprend l’exemple du point dans le plan, on peut définir ceci :

>>> Point = namedtuple('Point', ['x', 'y']) 

On se retrouve alors avec un objet qui possède sa propre sémantique (il est nommé Point et a deux attributs x et y qui sont ordonnés).

On peut créer un tel objet selon les manières suivantes :

>>> p = Point(4, 2) 
>>> p = Point(x=4, y=2) 
>>> p = Point(4, y=2) 
>>> p = Point(y=2, x=4) 

On peut accéder à ses attributs comme s’il s’agissait d’un n-uplet, mais aussi en utilisant la sémantique définie :

>>> print(p[0], p[1]) ...