Tuples, Dictionnaires Et Ensembles

1Les tuples : sequences immuables

t = (1, 2, 3)
t = 1, 2, 3            # les parentheses sont facultatives
t = ()                 # tuple vide
t = (5,)               # tuple a UN element : la virgule est obligatoire
t = (5)                # ce n'est PAS un tuple, c'est l'entier 5
len((5,)), len((5))    # TypeError sur le second : un int n'a pas de longueur

t = (10, 20, 30)
t[0]           # 10        indexation comme une liste
t[1:]          # (20, 30)  tranche
len(t)         # 3
20 in t        # True
t[0] = 99      # TypeError : les tuples sont immuables
t = t + (40,)  # on construit un NOUVEAU tuple

Pourquoi des tuples ?

grille = {}
grille[(0, 0)] = "depart"            # cle-tuple : coordonnees
grille[(3, 4)] = "arrivee"
grille[[0, 0]]                       # TypeError: unhashable type: 'list'

Deballage (unpacking)

a, b = (1, 2)                  # deballage
a, b = b, a                    # echange (le membre droit est un tuple)
q, r = divmod(17, 5)           # une fonction renvoyant deux valeurs
x, *reste = (1, 2, 3, 4)       # x = 1, reste = [2, 3, 4]
*debut, z = (1, 2, 3)          # debut = [1, 2], z = 3
(a, b), c = (1, 2), 3          # deballage imbrique

for i, (nom, note) in enumerate([("Sara", 18), ("Amine", 15)]):
    print(i, nom, note)

t = (1, [2, 3])
t[1].append(4)         # AUTORISE : on modifie la LISTE, pas le tuple
print(t)               # (1, [2, 3, 4])
hash(t)                # TypeError : le tuple n'est pas hachable

2Les dictionnaires : associer une valeur a une cle

d = {}                                    # vide
d = {"a": 1, "b": 2}                      # en extension
d = dict(a=1, b=2)                        # par mots-cles
d = dict([("a", 1), ("b", 2)])            # depuis une liste de couples
d = {c: ord(c) for c in "abc"}            # en comprehension

Operations

d = {"a": 1, "b": 2}

d["a"]              # 1
d["z"]              # KeyError !
d.get("z")          # None       : pas d'exception
d.get("z", 0)       # 0          : valeur par defaut
d["c"] = 3          # ajout
d["a"] = 10         # modification
del d["b"]          # suppression   (KeyError si absente)
d.pop("b", None)    # suppression sans risque
"a" in d            # True        : le test porte sur les CLES
len(d)              # nombre de couples

Parcours

d = {"a": 1, "b": 2, "c": 3}

for cle in d:                       # par defaut : les CLES
    print(cle, d[cle])

for cle in d.keys():                # explicite
    ...
for valeur in d.values():
    ...
for cle, valeur in d.items():       # la forme la plus utile
    print(f"{cle} -> {valeur}")

sorted(d)                           # ['a', 'b', 'c'] : les cles triees
sorted(d.items(), key=lambda c: -c[1])   # par valeur decroissante

Depuis Python 3.7, un dictionnaire conserve l'ordre d'insertion des cles. C'est une garantie du langage, mais il ne faut pas confondre cela avec un ordre trie.

Motifs indispensables

def frequences(sequence):
    """Dictionnaire element -> nombre d'occurrences. Theta(n)."""
    f = {}
    for x in sequence:
        f[x] = f.get(x, 0) + 1      # get evite le KeyError au premier passage
    return f

assert frequences("abracadabra")["a"] == 5

def regroupe(couples):
    """[(cle, val), ...] -> {cle: [val, ...]}"""
    d = {}
    for cle, val in couples:
        d.setdefault(cle, []).append(val)
    return d

assert regroupe([("a", 1), ("b", 2), ("a", 3)]) == {"a": [1, 3], "b": [2]}

cache = {}
def fib(n):
    """Fibonacci memoise : Theta(n) au lieu de Theta(phi^n)."""
    if n < 2:
        return n
    if n not in cache:
        cache[n] = fib(n-1) + fib(n-2)
    return cache[n]

assert fib(100) == 354224848179261915075

Inversion et indexation

d = {"a": 1, "b": 2}
inverse = {v: k for k, v in d.items()}        # {1: 'a', 2: 'b'}

3Les ensembles et synthese des structures

e = set()                    # ensemble VIDE ({} donnerait un dictionnaire !)
e = {1, 2, 3}
e = set([1, 2, 2, 3])        # {1, 2, 3} : les doublons disparaissent
e = {c for c in "abracadabra"}   # {'a', 'b', 'r', 'c', 'd'}

e.add(4)                     # ajout
e.discard(9)                 # suppression sans erreur si absent
e.remove(9)                  # KeyError si absent
3 in e                       # Theta(1)
len(e)

Operations ensemblistes

A = {1, 2, 3, 4}
B = {3, 4, 5}
A | B      # {1, 2, 3, 4, 5}
A & B      # {3, 4}
A - B      # {1, 2}
A ^ B      # {1, 2, 5}
{1, 2} <= A    # True

Ces operations coutent \(\Theta(|A| + |B|)\) : elles sont bien plus rapides que les boucles imbriquees equivalentes, en \(\Theta(|A|\cdot|B|)\).

Tableau de synthese

* si tous ses elements le sont — ** un frozenset, lui, est hachable.