Écrire cle du maximum(d)

def cle_du_maximum(d):
    """Une cle de d dont la valeur est maximale, et cette valeur.

    Precondition : d est NON VIDE (sans element, pas de maximum).
    Renvoie un couple (cle, valeur). En cas d'ex aequo, la premiere
    rencontree -- on ne promet pas laquelle.
    """
    assert len(d) > 0, "dictionnaire vide : pas de maximum"
    meilleure = None
    record = None
    for cle, valeur in d.items():
        if record is None or valeur > record:
            meilleure, record = cle, valeur
    assert record == max(d.values())
    return meilleure, record

Pourquoi record = None et non $0$. Sur {"a": -3, "b": -7}, une initialisation à $0$ ne verrait jamais aucune valeur la dépasser : la fonction renverrait (None, 0) — une clé qui n'existe pas et une valeur qui n'est dans le dictionnaire. C'est le défaut de maximum_faux du chapitre 3, transposé aux dictionnaires. None n'est comparable à rien, d'où le test record is None or ... : la première branche accepte inconditionnellement le premier couple, la seconde n'est évaluée qu'ensuite.

Pourquoi items() et non keys(). On a besoin des deux : la clé pour la renvoyer, la valeur pour comparer. Écrire for cle in d: valeur = d[cle] donnerait le même résultat au prix d'un accès par clé à chaque tour — celui que items() offrait déjà.

L'ex aequo, et l'honnêteté de la docstring. Sur {"x": 4, "y": 4}, la comparaison est > strict : le second $4$ ne détrône pas le premier, et la fonction renvoie "x". Mais ce « premier » est celui de l'ordre d'insertion, qui est une commodité de Python et non une propriété du dictionnaire. La docstring dit donc « la première rencontrée » et se garde de promettre x. Une spécification ne doit pas promettre plus que ce que l'algorithme garantit.

Vérification.

assert cle_du_maximum({"a": 3, "b": 7, "c": 5}) == ("b", 7)
assert cle_du_maximum({"a": -3, "b": -7}) == ("a", -3)  # un record a 0 echouerait
assert cle_du_maximum({"seul": 0}) == ("seul", 0)
assert cle_du_maximum({"x": 4, "y": 4}) == ("x", 4)     # ex aequo : le premier

try:
    cle_du_maximum({})
    assert False, "le dictionnaire vide aurait du etre refuse"
except AssertionError as e:
    assert "vide" in str(e)

for _ in range(2000):
    d = {i: random.randint(-50, 50) for i in range(random.randint(1, 10))}
    c, v = cle_du_maximum(d)
    assert d[c] == v == max(d.values())

Le test aléatoire vérifie les deux moitiés de la postcondition d'un coup : la valeur rendue est bien le maximum, et c'est bien celle de la clé rendue. Sans la première égalité, une fonction qui renverrait n'importe quel couple (c, d[c]) passerait.