langages de script – Python

Cours 2 – structures de données

M1 Ingénierie Multilingue – INaLCO

clement.plancq@ens.fr

Avant de commencer

Les structures de données sont un point essentiel de tout langage de programmation

Les diapos qui suivent n'offrent qu'une couverture partielle du sujet

Vous devez lire attentivement et vous référer à la documentation officelle de Python :

• le chapitre 5 du tutoriel
• la doc sur les types built-in
• la doc du module collections

Les listes

• Les listes sont des sequences (str, tuple, list)
• Les sequences sont des structures de données indicées qui peuvent contenir des éléments de différents types
• Les sequences sont des iterables, les listes aussi donc

• Les éléments d'une liste peuvent être modifiés (mutable)

• Une liste vide peut se déclarer de deux façons

stack = list()
stack = []

stack = ["le", "guépard", "le", "poursuit"]
stack = list('Perl')
stack

Les listes : fonctions

• Les listes héritent des fonctions des sequences, elles ont également des fonctions propres
• Parmi ces fonctions nous utiliserons principalement :
  • append(x) : ajoute un élément x à la fin de la liste (haut de la pile*)
  • extend([x, y, z]) : ajoute tous les éléments de la liste arg à la fin de la liste
  • pop([index]) : supprime et renvoie le dernier élément de la liste ou les index de la liste argument si arg
  • index(x) : renvoie l'index du premier élément de valeur x
  • count(x) : renvoie le nombre de fois où x apparaît
  • sort() : trie et modifie la liste, lire la doc pour en savoir plus sur les ordres de tri

stack = [12, 15, 12, 7, 18]
stack.index(12)

stack.count(12)

stack.sort()
stack

stack.append(23)
stack

stack.append([35, 46])
stack

stack.extend([51, 52])
stack

Les listes en compréhension

• Elles permettent de définir des listes par filtrage ou opération sur les éléments d'une autre liste
• Elles viennent de la programmation fonctionnelle
• La PEP 202 conseille de préférer les listes en compréhension aux fonctions map() et filter()
• Pas évident-évident de prime abord mais très expressif, élégant et so pythonic. Un dév python doit maîtriser les listes en compréhension

[i ** 2 for i in range(10)]

[i ** 2 for i in range(10) if i % 2 == 0]

[(i, j) for i in range(2) for j in ['a', 'b']]

Attention !

Copie de liste

Dans y = x, y n'est pas un copie de x, les deux pointent vers le même objet

x = [1, 2, 3]
y = x
y[0] = 4
x

Pour copier une liste il faut utiliser :

x = [1, 2, 3]
y = x[:]
# ou
y = list(x)

Les tuples

• Les tuples (tuple) sont des sequences similaires aux listes sauf qu'elles ne peuvent pas être modifiées (immutable)
• Les tuples sont souvent utilisées comme valeur de retour d'une fonction
• Les tuples peuvent être utilisées comme clé de dictionnaire

voyelles = ('a', 'e', 'i', 'o', 'u', 'y')
var = tuple('Perl')
var

Déballage de séquences

• Le sequence unpacking permet d'effectuer plusieurs affectations simultanées
• L'unpacking s'applique souvent sur des tuples

x, y, z = (1, 2, 3)
y

lexique = [("maison", "mEz§"), ("serpent", "sERp@")]
for ortho, phon in lexique:
    print(phon)

Attention !

Tuple à 1 élément

Pour créer un tuple à un élément il faut utiliser la notation (elem, )

var = (1)
type(var)

var = (1, )
type(var)

Parcours de liste

La boucle for est particulièrement adaptée pour parcourir les iterables et donc les listes

for item in voyelles:
    print(item)

La fonction enumerate peut être utile dans certains cas, elle renvoie un tuple contenant l'indice et la valeur de l'item à l'indice concerné

for i, item in enumerate(voyelles):
    print(i, item)

Les ensembles

Les ensembles (set) sont des collections non ordonnées d'élements sans doublons Les ensembles supportent les fonctions mathématiques d'union, d'intersection, de différence (doc)

ens1 = {'le', 'guépard', 'le', 'poursuit'}
ens1

ens2 = {"avec", "le", "chandelier", "dans", "la", "cuisine"}
ens1.intersection(ens2)

Les dictionnaires

• Les dictionnaires (dict) sont des structures de données associatives de type clé: valeur

• Les clés d'un dictionnaire sont uniques, seuls les types immutable peuvent être des clés (doc)

  • key in d retourne True si key est une clé de d
  • keys() retourne la liste des clés
  • values() retourne la liste des valeurs
  • items() retourne la liste des couples clé:valeur (tuple)
  • setdefault(key, default) retourne la valeur associée à la clé. Si la clé n'existe pas, ajoute la clé associée à default

d = {'Perl':'Larry Wall', 'Python':'Guido Van Rossum', 'C++':'Bjarne Stroustrup'}
d['Perl']

d['Ruby']

d.get('Ruby')

Module collections

• Le module collections propose des implémentations de structures de données supplémentaires

• Dans la liste (voir doc), deux pourront nous intéresser :

  • defaultdict

    defauldict est similaire à un dict mais il permet l'autovivification

    Son implémentation le rend plus rapide qu'un dictionnaire utilisé avec la fonction setdefault

import collections
lexique = [("couvent", "kuv"), ("couvent", "kuv@")]
dico = collections.defaultdict(list)
for ortho, phon in lexique:
    dico[ortho].append(phon)
dico

Module collections

• Counter

Counter est un dictionnaire où les valeurs attendues sont les nombres d'occurences des clés

from collections import Counter
cnt = Counter()
list = ['le', 'guépard', 'le', 'poursuit']
for item in list:
    cnt[item] += 1
cnt

Help !

Fonction repr

Dans la console Python les structures de données s'affichent de façon lisible

print(obj) ne donnera pas toujours le résultat escompté

La fonction repr(obj) est à préférer, elle donne une "représentation textuelle" d'un objet

Exos

Vous rendrez des scripts Python3. Avec des commentaires c'est mieux.

1. À partir du fichier tsv sem_Ef9POe.conll
   1. pour chaque POS listez les types classés par ordre d'occurrence décroissante,
   2. pour chaque type de chunk indiquez les longueurs min et max (en nb de mots).
2. Résoudre Mime types sur CodinGame