Tuples, Dictionnaires Et Ensembles

a) TypeError : (1) est l'entier 1
b) 1
c) True   : un ensemble n'est pas ordonne
d) False  : une liste l'est
e) KeyError: 'b'
f) 0
g) set()  : l'ensemble vide
h) <class 'dict'>   : {} est un DICTIONNAIRE vide
i) TypeError: unhashable type: 'list'
j) {(1,): 'x'}      : un tuple est une cle valide
k) 1      : 1 == 1.0 == True, un seul element est conserve
l) {1, 2, 3}

Le point (k) est subtil : l'appartenance a un ensemble se decide par == apres comparaison des hachages. Comme hash(1) == hash(1.0) == hash(True) et que ces trois valeurs sont egales, l'ensemble n'en garde qu'une (la premiere inseree).

from string import ascii_lowercase as ALPHABET

def frequences(texte):
    """Dictionnaire lettre -> occurrences. Theta(n)."""
    f = {}
    for c in texte.lower():
        if c in ALPHABET:
            f[c] = f.get(c, 0) + 1
    return f

def plus_frequente(texte):
    """Lettre la plus frequente (la plus petite en cas d'egalite)."""
    f = frequences(texte)
    if not f:
        return None
    return min(f, key=lambda c: (-f[c], c))

def absentes(texte):
    """Lettres de l'alphabet absentes, triees. Theta(n)."""
    return sorted(set(ALPHABET) - set(texte.lower()))

def est_pangramme(texte):
    """Le texte contient-il les 26 lettres ? Theta(n)."""
    return set(ALPHABET) <= set(texte.lower())

t = "Portez ce vieux whisky au juge blond qui fume"
assert est_pangramme(t)
assert absentes("abc") == sorted(set(ALPHABET) - {"a", "b", "c"})
print(frequences("abracadabra"))     # {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}
print(plus_frequente("abracadabra")) # 'a'

La cle lambda c: (-f[c], c) avec min realise : frequence maximale d'abord, puis ordre alphabetique a egalite. Le test de pangramme en une ligne grace a l'inclusion d'ensembles est bien plus lisible qu'une boucle sur 26 lettres.

def communs(t, u):
    """Theta(n + m)."""
    return sorted(set(t) & set(u))

def dans_t_pas_u(t, u):
    return sorted(set(t) - set(u))

def exclusifs(t, u):
    return sorted(set(t) ^ set(u))

def memes_elements(t, u):
    return set(t) == set(u)

def est_permutation(t, u):
    """Memes elements avec memes multiplicites. Theta(n + m)."""
    if len(t) != len(u):
        return False
    f = {}
    for x in t:
        f[x] = f.get(x, 0) + 1
    for x in u:
        if x not in f:
            return False
        f[x] -= 1
        if f[x] == 0:
            del f[x]
    return not f

assert communs([1, 2, 2, 3], [2, 3, 4]) == [2, 3]
assert memes_elements([1, 1, 2], [2, 1])
assert not est_permutation([1, 1, 2], [2, 1])
assert est_permutation([1, 1, 2], [1, 2, 1])

Les quatre premieres fonctions coutent \(\Theta(n+m)\) en moyenne. Sans ensembles, il faudrait des boucles imbriquees en \(\Theta(nm)\). La cinquieme se resout aussi par sorted(t) == sorted(u), mais en \(\Theta(n\log n)\) au lieu de \(\Theta(n)\).

def degre(G, s):
    """Nombre de voisins de s. Theta(1)."""
    return len(G[s])

def aretes(G):
    """Ensemble des aretes, chacune representee par un frozenset. Theta(|V| + |E|)."""
    E = set()
    for s, vs in G.items():
        for v in vs:
            E.add(frozenset((s, v)))       # frozenset : non oriente et hachable
    return E

def est_coherent(G):
    """Tout voisin declare declare-t-il en retour ?"""
    for s, vs in G.items():
        for v in vs:
            if v not in G or s not in G[v]:
                return False
    return True

def voisins_a_distance_2(G, s):
    """Sommets a distance exactement 2 de s."""
    d1 = G[s]
    d2 = set()
    for v in d1:
        d2 |= G[v]
    return d2 - d1 - {s}

G = {"A": {"B", "C"}, "B": {"A", "D"}, "C": {"A"}, "D": {"B"}}
assert est_coherent(G)
assert len(aretes(G)) == 3
assert sum(degre(G, s) for s in G) == 2 * len(aretes(G))     # poignees de main
assert voisins_a_distance_2(G, "A") == {"D"}

Lemme des poignees de main. Chaque arete \(\{u,v\}\) contribue exactement 1 au degre de \(u\) et 1 a celui de \(v\), donc 2 a la somme totale. D'ou \(\sum_s \deg(s) = 2|E|\). Corollaire immediat : dans tout graphe, le nombre de sommets de degre impair est pair.

L'usage de frozenset pour une arete non orientee est un idiome utile : frozenset({"A","B"}) == frozenset({"B","A"}), et c'est hachable donc stockable dans un set.

def compteur(sequence):
    c = {}
    for x in sequence:
        c[x] = c.get(x, 0) + 1
    return c

def union_multi(c1, c2):
    """Multiplicite = max des deux (union de multi-ensembles)."""
    return {k: max(c1.get(k, 0), c2.get(k, 0)) for k in c1.keys() | c2.keys()}

def somme_multi(c1, c2):
    """Multiplicite = somme."""
    return {k: c1.get(k, 0) + c2.get(k, 0) for k in c1.keys() | c2.keys()}

def inclus_multi(c1, c2):
    """c1 est-il inclus dans c2 au sens des multiplicites ?"""
    return all(v <= c2.get(k, 0) for k, v in c1.items())

def peut_ecrire(mot, sac):
    """Le mot peut-il etre forme avec les lettres disponibles ?"""
    return inclus_multi(compteur(mot.lower()), compteur(sac.lower()))

assert union_multi({"a": 2}, {"a": 3, "b": 1}) == {"a": 3, "b": 1}
assert somme_multi({"a": 2}, {"a": 3}) == {"a": 5}
assert peut_ecrire("chat", "atchoum")
assert not peut_ecrire("chatte", "atchoum")     # un seul t disponible

c1.keys() | c2.keys() exploite le fait que les vues de cles se comportent comme des ensembles : c'est plus concis et plus rapide que set(c1) | set(c2).

La bibliotheque standard fournit collections.Counter, qui implemente exactement ces operations avec les operateurs |, +, -.

def selection(base, champ, valeur):
    """Lignes dont base[champ] vaut valeur. Equivalent de WHERE."""
    return [l for l in base if l.get(champ) == valeur]

def projection(base, champs):
    """Ne conserve que certaines colonnes. Equivalent de SELECT."""
    return [{c: l[c] for c in champs if c in l} for l in base]

def groupe_par(base, champ):
    """Dictionnaire valeur -> liste des lignes. Equivalent de GROUP BY."""
    g = {}
    for l in base:
        g.setdefault(l[champ], []).append(l)
    return g

def tri(base, champ, decroissant=False):
    """Equivalent de ORDER BY."""
    return sorted(base, key=lambda l: l[champ], reverse=decroissant)

def moyenne_par(base, champ_groupe, champ_valeur):
    """Equivalent de SELECT AVG(...) GROUP BY ..."""
    return {cle: sum(l[champ_valeur] for l in lignes) / len(lignes)
            for cle, lignes in groupe_par(base, champ_groupe).items()}

eleves = [
    {"nom": "Amine",   "classe": "MPSI", "note": 15},
    {"nom": "Sara",    "classe": "PCSI", "note": 18},
    {"nom": "Youssef", "classe": "MPSI", "note": 12},
    {"nom": "Ines",    "classe": "PCSI", "note": 16},
]

assert len(selection(eleves, "classe", "MPSI")) == 2
assert projection(eleves, ["nom"])[0] == {"nom": "Amine"}
assert moyenne_par(eleves, "classe", "note") == {"MPSI": 13.5, "PCSI": 17.0}
print(tri(eleves, "note", decroissant=True)[0]["nom"])     # Sara

5. Ces quatre fonctions sont exactement les operateurs fondamentaux de l'algebre relationnelle : selection \(\sigma\), projection \(\pi\), tri, et agregation. Une requete SQL

SELECT classe, AVG(note) FROM eleves WHERE note >= 12 GROUP BY classe;

se traduit par la composition moyenne_par([l for l in eleves if l["note"] >= 12], "classe", "note"). Le chapitre 16 formalise ce modele et le chapitre 17 en donne la syntaxe SQL. Un SGBD ajoute a cela l'optimisation des requetes, les index (des tables de hachage ou des arbres) et la gestion de la concurrence.

def normalise(texte):
    """Liste des mots en minuscules, ponctuation retiree."""
    propre = "".join(c if c.isalnum() else " " for c in texte.lower())
    return propre.split()

def construire_index(documents):
    """{mot: ensemble des identifiants de documents}. Theta(taille totale)."""
    index = {}
    for ident, texte in documents.items():
        for mot in normalise(texte):
            index.setdefault(mot, set()).add(ident)
    return index

def recherche_et(index, mots):
    """Documents contenant TOUS les mots. Theta(somme des tailles des postings)."""
    mots = [m.lower() for m in mots]
    if not mots:
        return set()
    if any(m not in index for m in mots):
        return set()
    # on commence par le mot le plus rare : l'intersection reste petite
    mots.sort(key=lambda m: len(index[m]))
    res = set(index[mots[0]])
    for m in mots[1:]:
        res &= index[m]
        if not res:
            break
    return res

def recherche_ou(index, mots):
    res = set()
    for m in mots:
        res |= index.get(m.lower(), set())
    return res

docs = {
    1: "Le chat dort sur le tapis",
    2: "Le chien dort dans le jardin",
    3: "Le chat et le chien jouent dans le jardin",
}
idx = construire_index(docs)
assert idx["chat"] == {1, 3}
assert recherche_et(idx, ["chat", "jardin"]) == {3}
assert recherche_ou(idx, ["tapis", "jardin"]) == {1, 2, 3}
assert recherche_et(idx, ["licorne"]) == set()

4. La recherche naive parcourt les \(D\) documents et, pour chacun, le texte entier : \(\Theta(N)\) ou \(N\) est la taille totale du corpus, a chaque requete. Avec un index, la construction coute \(\Theta(N)\) une seule fois, puis chaque requete ne coute que la somme des tailles des listes de documents (postings) des mots cherches, qui est generalement minuscule devant \(N\).

L'optimisation consistant a trier les mots par frequence croissante est celle qu'emploient les vrais moteurs : l'intersection se reduit des la premiere etape, et la boucle s'interrompt des que le resultat est vide.

1. Examiner toutes les paires : \(\binom{n}{2} = \Theta(n^2)\) distances. Pour \(n = 10^5\), cela fait \(5\cdot10^9\) calculs : plusieurs heures.

2. On decoupe le plan en cellules carrees de cote \(d\). Le point \((x,y)\) appartient a la cellule \(\bigl(\lfloor x/d\rfloor, \lfloor y/d\rfloor\bigr)\). Si deux points sont a distance \(\le d\), alors leurs coordonnees de cellule different d'au plus 1 en \(x\) et en \(y\) : en effet \(|x_1 - x_2| \le d\) entraine \(\bigl|\lfloor x_1/d\rfloor - \lfloor x_2/d\rfloor\bigr| \le 1\). Il suffit donc, pour chaque point, d'examiner sa cellule et les 8 adjacentes.

from math import floor, hypot

def paires_proches(points, d):
    """Toutes les paires d'indices de points a distance <= d. Theta(n) en moyenne."""
    grille = {}
    for i, (x, y) in enumerate(points):
        cle = (floor(x / d), floor(y / d))
        grille.setdefault(cle, []).append(i)

    res = set()
    for (cx, cy), indices in grille.items():
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                voisine = grille.get((cx + dx, cy + dy))
                if not voisine:
                    continue
                for i in indices:
                    for j in voisine:
                        if i < j:                      # chaque paire une seule fois
                            xi, yi = points[i]
                            xj, yj = points[j]
                            if hypot(xi - xj, yi - yj) <= d:
                                res.add((i, j))
    return res

import random
def naif(points, d):
    n = len(points)
    return {(i, j) for i in range(n) for j in range(i+1, n)
            if hypot(points[i][0]-points[j][0], points[i][1]-points[j][1]) <= d}

for _ in range(60):
    P = [(random.uniform(0, 5), random.uniform(0, 5)) for _ in range(random.randint(0, 40))]
    assert paires_proches(P, 0.7) == naif(P, 0.7)
print("partitionnement en cellules valide")

3. Exhaustivite. Soit \((i,j)\) une paire a distance \(\le d\), de cellules \(c_i\) et \(c_j\). D'apres le point 2, \(c_j\) est l'une des 9 cellules du voisinage de \(c_i\). Lorsque la boucle externe traite la cellule \(c_i\), elle explore ce voisinage, rencontre donc \(c_j\), et teste la paire \((i,j)\). Aucune paire proche n'est manquee. Reciproquement, toute paire ajoutee a res a passe le test de distance : l'algorithme est exact.

4. Notons \(m\) le nombre moyen de points par cellule non vide. Le travail total est \(\Theta(9 n m)\). Si les points sont uniformement repartis sur un domaine borne et si \(d\) est choisi de sorte que \(m = O(1)\) (c'est-a-dire que le nombre de cellules est proportionnel a \(n\)), la complexite est \(\Theta(n)\) en moyenne.

Dans le pire cas, tous les points sont dans la meme cellule (par exemple tous confondus, ou \(d\) trop grand) : on retombe a \(\Theta(n^2)\) — ce qui est inevitable puisqu'il y a alors \(\Theta(n^2)\) paires a produire en sortie. La complexite est donc \(\Theta(n + k)\) ou \(k\) est la taille du resultat : l'algorithme est output-sensitive, ce qui est optimal.