Écrire histogramme(t, k) , qui renvoie le tableau des effectifs des…

def histogramme(t, k):
    """Effectifs des valeurs 0 a k-1 presentes dans t.

    Precondition  : tout element de t est un entier de 0 a k-1.
    Postcondition : le resultat a k cases, et la somme de ses valeurs
                    vaut len(t).
    """
    assert all(isinstance(x, int) and 0 <= x < k for x in t), "valeur hors domaine"
    h = [0] * k
    for x in t:
        h[x] = h[x] + 1
    assert sum(h) == len(t)
    return h

L'idée maîtresse : la valeur sert d'indice. La ligne h[x] = h[x] + 1 utilise l'élément x comme position dans le tableau des effectifs. C'est l'accès calculé direct du cours mis au service d'un comptage : aucun parcours de recherche, une seule passe sur t, coût proportionnel à $n+k$.

La précondition est indispensable. Sans elle, une valeur hors domaine ferait de deux choses l'une, et les deux sont mauvaises : h[7] sur un tableau de $3$ cases lève IndexError — bruyant, donc acceptable — mais h[-1] incrémenterait la dernière case, silencieusement, en Python. Un indice négatif ne provoque pas d'erreur ; il désigne l'autre bout du tableau.

Vérification.

assert histogramme([0, 2, 2, 1, 2], 3) == [1, 1, 3]
assert histogramme([], 3) == [0, 0, 0]

for _ in range(1000):
    k = random.randint(1, 6)
    t = [random.randint(0, k - 1) for _ in range(random.randint(0, 20))]
    h = histogramme(t, k)
    assert sum(h) == len(t)
    for v in range(k):
        assert h[v] == t.count(v)

Les $1000$ cas passent, et histogramme([0, 5], 3) est bien refusé.

La limite, et ce qu'elle annonce. Ce tableau ne sait compter que des entiers d'un intervalle connu d'avance et petit. Compter les lettres d'un texte demanderait de transformer chaque caractère en indice ; compter des mots serait impossible ; et compter des valeurs de $0$ à $10^9$ exigerait un milliard de cases pour quelques dizaines de valeurs présentes. Le dictionnaire du chapitre 5 lève exactement ces trois limites : la clé peut être n'importe quelle valeur non modifiable, et seules les clés présentes occupent de la place.