Les sommes cumulées, et les requêtes en temps constant

Exercice d'entraînement · niveau 3 (difficile) · mathématiques appliquées (ECG 1re année), chapitre 11 — Informatique et algorithmique · Parcours de listes et coût

Énoncé

Écrire cumul(L) renvoyant la liste $C$ telle que $C_{k} = L_{0} + \dots + L_{k}$ , puis somme_tranche(C, i, j) qui rend $L_{i} + \dots + L_{j}$ sans boucle. Justifier la formule et comparer le coût de $q$ requêtes avec et sans prétraitement.

Corrigé

Le code.

def cumul(L):
    C = []
    total = 0
    for x in L:
        total = total + x
        C.append(total)
    return C

def somme_tranche(C, i, j):
    # somme des L[i] a L[j] inclus, en temps constant
    if i == 0:
        return C[j]
    return C[j] - C[i - 1]

L = [3, 1, 4, 1, 5, 9, 2, 6]
C = cumul(L)
print(C)                          # [3, 4, 8, 9, 14, 23, 25, 31]
print(somme_tranche(C, 2, 5))     # 4 + 1 + 5 + 9 = 19

La formule. Par construction, $C_{j} = \sum_{k = 0}^{j} L_{k}$ et $C_{i - 1} = \sum_{k = 0}^{i - 1} L_{k}$ . En soustrayant, tous les termes d'indice inférieur à $i$ se compensent :

$C_{j} - C_{i - 1} = k = 0 \sum j L_{k} - k = 0 \sum i - 1 L_{k} = k = i \sum j L_{k} .$

C'est un télescopage, le même mécanisme que celui des séries : une somme de tranche s'obtient comme différence de deux sommes depuis le début.

Le cas $i = 0$ est à traiter à part. L'indice $i - 1$ vaudrait alors $- 1$ , et en Python C[-1] désigne le dernier élément de la liste : la fonction renverrait $C_{j} - C_{n - 1}$ , un résultat faux, souvent négatif, et sans le moindre message d'erreur. C'est le piège de cet exercice.

Vérification sur l'exemple. $C_{5} - C_{1} = 23 - 4 = 19$ , et $L_{2} + L_{3} + L_{4} + L_{5} = 4 + 1 + 5 + 9 = 19$ . ✔

Le coût. Sans prétraitement, chaque requête demande de parcourir la tranche, soit jusqu'à $n$ additions ; $q$ requêtes coûtent donc de l'ordre de $q n$ opérations. Avec le prétraitement, on paie $n$ opérations une fois, puis chaque requête coûte une soustraction : total de l'ordre de $n + q$ .

Sur $n = 1 0^{4}$ et $q = 1 0^{4}$ , cela fait $1 0^{8}$ opérations contre $2 \times 1 0^{4}$ : plusieurs minutes contre une fraction de seconde. C'est le principe du prétraitement — investir un parcours pour rendre les interrogations suivantes immédiates.

À noter. La bibliothèque numpy propose np.cumsum(L), qui produit exactement la liste $C$ . La programmer soi-même une fois éclaire ce qu'elle fait ; l'utiliser ensuite est parfaitement légitime.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.