La mémoire, ligne par ligne

La programmation dynamique · niveau 3 (difficile)

Énoncé

(a) Optimiser le calcul de Fibonacci pour n'utiliser qu'un espace mémoire en $O (1)$ . (b) Modifier l'implémentation de la distance de Levenshtein pour qu'elle s'exécute en n'utilisant que deux lignes de tableau, amenant l'espace mémoire à $O (min (n, m))$ . (c) Expliquer ce que cette optimisation de l'espace mémoire sacrifie et comment y remédier si nécessaire.

Corrigé

(a)

def fib_optimal(n: int) -> int:
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

(b)

def levenshtein_2lignes(u: str, v: str) -> int:
    if len(v) > len(u):
        u, v = v, u  # Assure que v est la chaîne la plus courte
    prec = list(range(len(v) + 1))
    for i in range(1, len(u) + 1):
        cour = [i] + [0] * len(v)
        for j in range(1, len(v) + 1):
            cout = 0 if u[i - 1] == v[j - 1] else 1
            cour[j] = min(prec[j] + 1,          # suppression
                          cour[j - 1] + 1,      # insertion
                          prec[j - 1] + cout)   # substitution
        prec = cour
    return prec[len(v)]

(c) Cette réduction d'espace mémoire sacrifie la possibilité de reconstruire la solution optimale (la suite des opérations d'édition). On ne conserve que la valeur finale de la distance. Si l'on souhaite à la fois économiser la mémoire et reconstruire la solution, il faut utiliser des approches de type "diviser pour régner" (comme l'algorithme de Hirschberg, hors programme) qui reconstruisent la solution en mémoire linéaire au prix d'un doublement du temps de calcul.

Énoncé

Corrigé

Exercices semblables