CHAPITRE 9 : LA MÉMOIRE AUSSI SE COMPTE

Un algorithme consomme deux ressources. On s'intéresse beaucoup au temps ; la mémoire est tout aussi capable de faire tomber un programme : plus brutalement, même.

Espace total, espace auxiliaire

Deux mesures, à ne pas confondre.

• Espace total : tout ce que le programme occupe, les données d'entrée comprises.
• Espace auxiliaire : ce que l'algorithme réclame en plus de l'entrée.

C'est le second qui intéresse, parce que l'entrée, on ne la choisit pas.

def somme(tab):
    total = 0            # une variable
    for x in tab:        # pas de nouvelle structure
        total += x
    return total
# espace total     : O(n)  : le tableau est là
# espace auxiliaire: O(1)  : une seule variable

On dira donc que cette fonction est « en espace constant », ou qu'elle travaille sur place.

Quand l'algorithme réclame de la place

def doubler(tab):
    sortie = []              # nouvelle liste
    for x in tab:
        sortie.append(x * 2) # elle grandit jusqu'à n
    return sortie
# espace auxiliaire : O(n)

La version sur place évite ce coût :

def doubler_sur_place(tab):
    for i in range(len(tab)):
        tab[i] *= 2
# espace auxiliaire : O(1)

Ce n'est pas toujours souhaitable : modifier l'entrée du client est parfois inacceptable. Mais quand c'est permis, le gain est franc.

La récursion coûte de la mémoire

Voilà ce qu'on oublie le plus souvent. Chaque appel en attente occupe un cadre sur la pile d'appels : ses paramètres, ses variables locales, l'adresse de retour.

def factorielle(n):
    if n <= 1:
        return 1
    return n * factorielle(n - 1)

Au moment le plus profond, n appels attendent simultanément. L'espace auxiliaire est donc O(n), alors qu'aucune structure de données n'apparaît dans le code.

factorielle(5) attend factorielle(4)
               qui attend factorielle(3)
                          qui attend factorielle(2)
                                     qui attend factorielle(1)
→ 5 cadres empilés en même temps

La version itérative, elle, est en O(1) :

def factorielle(n):
    r = 1
    for i in range(2, n + 1):
        r *= i
    return r
# espace auxiliaire : O(1)

Récursivité terminale

Quand l'appel récursif est la toute dernière chose que fait la fonction, le cadre courant ne sert plus à rien : certains compilateurs le réutilisent, et la pile reste constante.

# non terminal : il reste la multiplication à faire après l'appel
return n * factorielle(n - 1)

# terminal : l'appel est la dernière action
def factorielle(n, acc=1):
    if n <= 1:
        return acc
    return factorielle(n - 1, n * acc)

Attention : cette optimisation existe en C, en Scala, en OCaml, et dans la plupart des langages fonctionnels, mais pas en Python, dont l'auteur l'a refusée délibérément pour préserver la lisibilité des traces d'erreur. Écrire une récursion terminale en Python ne fait rien gagner.

Quelques espaces de référence

Cette colonne de droite explique un choix d'ingénierie réel : le tri par tas et le tri fusion ont le même temps, mais le tri fusion réclame un tableau auxiliaire de taille n. Sur un système contraint en mémoire, le tri par tas gagne. C'est aussi pourquoi le sort() de C++ n'est pas un tri fusion.

L'échange temps contre mémoire

Les deux ressources se négocient presque toujours l'une contre l'autre.

# peu de mémoire, beaucoup de temps : on recalcule
def est_premier(n):
    if n < 2: return False
    i = 2
    while i * i <= n:
        if n % i == 0: return False
        i += 1
    return True
# O(√n) par appel, O(1) de mémoire

# beaucoup de mémoire, peu de temps : on précalcule tout
def crible(limite):
    p = [True] * (limite + 1)
    p[0] = p[1] = False
    for i in range(2, int(limite ** 0.5) + 1):
        if p[i]:
            for j in range(i * i, limite + 1, i):
                p[j] = False
    return p
# O(limite log log limite) une fois, puis O(1) par question
# mais O(limite) de mémoire

Pour une question isolée, la première. Pour un million de questions, la seconde. Il n'y a pas de bonne réponse dans l'abstrait : il y a un usage.

def inverser_sur_place(tab):
    g, d = 0, len(tab) - 1
    while g < d:
        tab[g], tab[d] = tab[d], tab[g]
        g += 1
        d -= 1

# temps O(n), espace auxiliaire O(1)

while debut <= fin:
    m = (debut + fin) // 2
    ...
    debut = m + 1   # ou fin = m - 1