Programme Leçon 53 sur 148 · La vitesse sans le cache
La vitesse sans le cache

Pourquoi ne pas simplement mettre en cache ?

Pourquoi c'est important Demande à un assistant de rendre quelque chose plus rapide et la première réponse est très souvent « ajoute un cache ». Parfois c'est juste. Souvent, le problème a une règle qui le rend faux, et le chemin le plus rapide est de faire moins de travail, pas d'en retenir davantage.

Un cache échange de la mémoire contre du travail répété. Il est rentable quand la même question revient de nombreuses fois, que la réponse ne se périme pas, et qu'il y a de la place pour garder les réponses. Retire une seule de ces conditions et le cache devient un coût : il grossit sans limite, sert des données anciennes, ou ne sert jamais.

Cache : un stockage de réponses déjà calculées, gardées pour que la même question puisse recevoir une réponse sans refaire le travail.

Des chemins qui n'ont pas besoin de cache

  • Précalculer une fois : un passage qui construit exactement ce dont les questions ont besoin, comme des totaux courants.
  • Utiliser l'ordre qu'on t'a donné : des données triées permettent à deux pointeurs ou à une recherche dichotomique d'en sauter la plus grande partie.
  • Lire en flux : garder un résumé courant et ne jamais garder toute l'entrée.
  • Borner la recherche : s'arrêter dès que plus rien de ce qui reste ne peut battre la meilleure réponse jusqu'ici.

Dans ce module, les données arrivent sous forme de Tape, qui compte chaque valeur que tu lis, et certains problèmes plafonnent la mémoire que ta fonction peut utiliser pendant son exécution. Le plafond est mesuré avec le propre tracemalloc de Python, qui voit aussi les copies faites dans les fonctions natives : list(tape) et set(tape) ne sont pas gratuits.

import tracemalloc
tracemalloc.start()
result = my_function(tape)
peak_bytes = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()

Récap Un cache a besoin de répétitions, de fraîcheur et de place. Quand un problème exclut l'une d'elles, cherche du travail que tu peux sauter au lieu de travail que tu peux retenir.

Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon

Cet exercice s'ouvre bientôt

Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.