Python et les listes

Python possède des types de base qui sont très utiles. Parmi eux, le type list se révèle être très fréquemment utilisé dès qu'il est nécessaire de gérer des collections d'objets. Son usage est simple et assez intuitif : On ajoute des éléments avec append et on accède aux élèments avec l'opérateur []. Mais le type list propose aussi des subtilités dont je vous propose de découvrir quelques unes au cours de cet article.

Triez les élements selon votre propore critère

Trier une liste est quelquchose d'assez fréquent. Python propose donc une méthode sort pour les listes.

ma_liste = [5, 3, 2, 1]
ma_liste.sort()
print ma_liste
>>> [1, 2, 3, 5]

A  noter que pour un tri descendant, il est possible d'appeler la méthode reverse après fait le sort.

ma_liste.reverse()
print ma_liste
>>> [5, 3, 2, 1]

Notez que ces 2 méthodes fonctionnent "sur place". C'est à dire qu'elles modifient l'objet sur lesquel elles sont appelées. Ceci est en contradiction avec le fonctionnement de certaines méthodes sur le type string qui souvent ne modifient pas l'objet mais retourne plutôt la nouvelle valeur.

Le tri fonctionne avec les types de base mais peut aussi être utilisé avec des classes définies par l'utilisateur.

class Ami:
   def __init__(self, nom, age):
   self.nom = nom
   self.age = age

   def __repr__(self):
   return self.nom

ma_liste = [Ami("Bob", 30), Ami("Joe", 20), Ami("Bill", 25)]

Pour que Python sache sur quel critère trier les éléments, il faut lui définir une fonction de comparaison des éléments qui prend 2 arguments et retourne 1 si le 1er argument doit être classé en 1er, -1 si c'est le second et 0 si les 2 éléments sont égaux entre eux.

def cmp_age(p1, p2):
   if p1.age == p2.age: return 0
   if p1.age > p2.age: return 1
   return -1

ma_liste.sort(cmp=cmp_age)
print ma_liste
>>> ["Joe", "Bill", "Bob"]

Python propose une manière parfois plus simple pour définir le critère de tri avec l'agument key. Dans ce cas, on définit simplement une valeur à utiliser pour le tri.

def key_nom(p): return p.nom

ma_liste.sort(key=key_nom)
print ma_liste
>>>["Bill", "Bob", "Joe"]

Donnez des priorités à vos éléments avec heapq

Les fonctions de tri sont très utiles mais peuvent parfois être coûteuse en temps d'exécution sur des listes de taille importante. Python propose donc aussi un mécanisme de liste de priorité qui s'intègre très bien avec les listes.

L'idée d'une liste de priorité est de trier les éléments lors de l'insertion d'un élément. La liste est donc en permanence ordonnée. L'élement d'index 0 sera toujours le plus petit élément.

Afin de ne pas rendre l'insertion d'un élément trop longue sur un tableau de grande taille, l'algorithme d'insertion utilise un arbre mais tout ceci est rendu transparent pour le développeur et une liste de priorité s'utilise de la même manière qu'une liste traditionnelle.

from heapq import heappush, heappop
ma_liste = []
heappush(ma_liste, 5)
heappush(ma_liste, 1)
heappush(ma_liste, 8)
heappush(ma_liste, 3)
print ma_liste
>>> [1, 3, 8, 5]

On est alors surpris de voir que la liste n'est pas ordonnée correctement. Ceci est normal car le heapq ne donnera les éléments ordonnés qu'avec la fonction heappop.

while ma_liste: print heappop(ma_liste)
>>> 1
>>> 3
>>> 5
>>> 8

Une autre manière d'accéder aux éléments de manière ordonnée est d'utiliser la fonction nsmallest en lui donnant la taille de la liste:

from heapq import nsmallest
print nsmallest(len(ma_liste), ma_liste)
>>> [1, 3, 5, 8]

A noter que l'on peut aussi fournir an argument une fonction de "clef" qui retournera une clé utiliser pour le tri:

def key_fct(x): return -x
print nsmallest(len(ma_liste), ma_liste, key=key_fct)
>>> [8, 5, 3, 1]

Le module heapq fait partie de la librairie standard et je vous recommande la lecture de sa page de documentation qui vous expliquera très bien son fonctionnement : http://docs.python.org/library/heapq.html

Utilisez les compréhension de listes en Python

Une compréhension de liste est une construction qui permet de définir une liste à partir d'une ou plusieurs caractéristiques de ses éléments. En Python, une liste est hétérogène et peut stocker des éléments de natures différentes. Une compréhension de liste va permettre de générer une liste à partir des propriétés des éléments d'une séquence.

Prenons un exemple pour essayer d'être un peu plus clair.

Soit une liste, ['ABC', [0, 1, 2], {1: 'Hello'}], à partir de laquelle nous voudrions créer une autre liste dont les éléments correspondrait à l'élement d'index 1 des éléments de notre liste initiale.

Python propose d'utiliser une compréhension de liste pour ceci avec la syntaxe suivante:

print [x[1] for x in ['ABC', [0, 1, 2], {1: 'Hello'}]]
>>> ['B', 1, 'Hello']

On voit que cette syntaxe permet de réaliser en une seule ligne un traitement qui pourrait aussi s'exprimer:

l = []
for c in ['ABC', [0, 1, 2], {1: 'Hello'}]:
   l.append(l[1])
print l

La compréhension de liste facilite la lisibilité et la concision du code ce qui est un des buts de Python. Cette technique est donc en général très appréciée des développeurs Python.

La compréhension de liste, appelée aussi parfois liste interprêtée, a remplacé avantageusement deux fonctions de Python map et filter dont elle combine les effets. map permet d'effectuer un traitement sur les éléments d'une liste. filter permet d'éliminer des éléments qui ne correspondent pas à un critère.

On peut ainsi par exemple obtenir la racine carrée des éléments positifs d'une liste grâce à la compréhension de liste suivante:

import math
print [int(math.sqrt(x)) for x in [4, 9, -5, 16, 25, -9] if x>0]
>>> [2, 3, 4, 5]

On peut de plus générer une liste à partir de plusieurs listes

print [x*y for x in [1, 2, 3] for y in [1, 2, 3] ]
>>> [1, 2, 3, 2, 4, 6, 3, 6, 9]

Elles peuvent s'utiliser avec n'importe quelle séquence comme les chaînes de caractères par exemple:

print [ord(x) for x in 'Hello']
>>> [72, 101, 108, 108, 111]

Les compréhensions sont une notion très puissante du langage Python. A utiliser sans modération.

Passez une liste en argument d'une fonction

Les listes sont des objects et peuvent donc être passé en argument à une fonction. Attention toutefois à ce piège du au fonctionnement de l'interprêteur:

Créer une fonction qui prend une liste vide comme argument par défaut:

def affiche_liste(liste=[]):
   liste.append(1)
   print liste

et appelez la pluseurs fois sans argument

affiche_liste()
>>> [1]
affiche_liste()
>>> [1, 1]
affiche_liste()
>>> [1, 1, 1]

Ce phénomêne connu sous le nom du "mutable default argument" est la source de bugs vicieux. Prenez y garde!

Autre spécificité de l'utilisation d'une liste en argument: l'opérateur * permet de passer les éléments d'une liste comme arguments d'une fonction.

l = ["Hello", "World", 2]
def affiche(a, b, c): print a, b, c
affiche(*l)
>>> Hello World 2

Utilisez les listes comme des ensembles

Les listes peuvent être utiliseés en combinaison avec le type de données set afin de gérer des ensembles. Le type set est un type standard de Python. Il est crée à partir d'une séquence et correspond à un dictionnaire "sans valeurs" dont on n'utiliserait que les clés. Les éléments d'un set sont ainsi uniques.

print set(['A', 'B', 'C', 'B', 'A'])
>>> set(['A', 'C', 'B'])

Les set peuvent être utilisé pour des calculs sur des ensembles:

print set(['A', 'B', 'C']).intersection(['B', 'D'])
>>> set(['B'])

print set(['A', 'B', 'C']).union(['B', 'D'])
>>> set(['A', 'B', 'C', 'D'])

Le type set possède de nombreuses méthodes dont l'utilisation peut se révéler très utile pour certains algorithmes.

Voici donc quelques trucs pour l'utilisation des listes en Python. Ce type est à mon avis un des points forts du langage. La syntaxe est simple, l'utilisation souple et les possibilités très grandes.