FizzBuzz en TypeScript, épisode 2 : de la mémoïsation

Dans l'épisode précédent, nous avons créé des listes infinies en TypeScript.

Dans cet épisode, nous allons voir ce qu'est la mémoïsation et en quoi elle peut nous aider à améliorer nos listes.

C'est quoi ?

La mémoïsation est la mise en cache d'une valeur de retour d'une fonction en fonction de ses valeurs d'entrée. Elle permet donc de ne pas lancer à nouveau un calcul s'il a déjà été calculé dans un précédent appel.

Quand l'utiliser ?

Lorsqu'une fonction est dite pure, c'est-à-dire qu'elle retourne toujours la même valeur pour les mêmes arguments en entrée, alors la mémoïsation est une bonne idée.

Cependant, quand elle a des effets de bords, son comportement peut changer d'une exécution à l'autre et sa mémoïsation devient donc problématique.

Concrètement, ça donne quoi ?

Prenons l'exemple de la suite de Fibonacci. Voici une implémentation naïve de la fonction qui calcule le n-ième entier de la suite :

const fibonacci = (integer: number): number => {
  if (integer <= 1) {
    return integer;
  }

  return fibonacci(integer - 1) + fibonacci(integer - 2);
};

Cette implémentation est très lente pour des valeurs d'entiers élevées. En effet, elle calcule plusieurs fois les mêmes valeurs. Par exemple, pour fibonacci(5), elle calcule fibonacci(3) deux fois.

En utilisant la mémoïsation, ça donne :

const cache = new Map<number, number>();

const fibonacci = (number: number): number => {
  if (number <= 1) {
    return number;
  }

  if (!cache.has(number)) {
    cache.set(number, fibonacci(number - 1) + fibonacci(number - 2));
  }

  return cache.get(number);
};

Ainsi, pour fibonacci(5), fibonacci(3) n'est calculé qu'une seule fois.

Dans la liste

Il est nécessaire de se référer au précédent article pour comprendre la structure de la List.

Ajoutons dans List des champs pour enregistrer les états :

export abstract class List<T> {
  #values?: T[];
  #length?: number;
  #at: Map<number, T | undefined> = new Map();

  // …
}

Ici, #values permet de stocker l'ensemble valeurs de la liste, #length sa longueur et #at, via une Map, contient les valeurs indexées.

Pour que l'évaluation reste paresseuse, par défaut, les enregistrements restent soit non définis, soit sans valeur (d'où les ? dans la définition).

Le renommage de la méthode at() en une méthode abstraite et protégée getAt() permet d'isoler l'appel du calcul et ainsi mettre notre enregistrement dans une nouvelle méthode at() qui se base sur getAt() :

export abstract class List<T> {
  // …

  at(index: number): T | undefined {
    if (!this.#at.has(index)) {
      this.#at.set(index, this.getAt(index));
    }
    return this.#at.get(index);
  }

  protected abstract getAt(index: number): T | undefined;

  // …
}

Il en va de même pour le getter get length() :

export abstract class List<T> {
  // …

  get length(): number {
    if (this.#length === undefined) {
      this.#length = this.getLength();
    }
    return this.#length;
  }

  protected abstract getLength(): number;

  // …
}

Comme get values() dépend de getAt(), on peut le modifier pour utiliser at() :

export abstract class List<T> {
  // …

  get values(): T[] {
    if (this.length === +Infinity) {
      throw new Error(`${this.name} list is infinite`);
    }
    if (this.#values === undefined) {
      this.#values = iterate(this.length).map((index) => this.at(index)!);
    }
    return this.#values;
  }
  // …
}

Maintenant, les valeurs sont calculées une seule fois et stockées pour les prochains appels, nous venons de mémoïser notre liste.

Fin du deuxième épisode

Nous venons de voir les notions suivantes :

• Quand est-ce qu'on peut utiliser la mémoïsation ;
• Son application dans notre List.

Nous n'avons toujours pas parlé du FizzBuzz, mais nous y arriverons dans le prochain épisode.