samedi 14:45:00–15:10:00
Plus loin que la mémoization : la tabulation
serge sans_paille
- Audience level:
- Intermediate
Description
La mémoisation de fonction est une optimisation classique qui permet de ne calculer qu'une fois une fonction appelée de façon répétée.
Cette présentation essaie d'aller plus loin : ne jamais calculer la fonction à l'execution et n'utiliser qu'une gigantesque lookup table à la place.
Et comme c'est en Python, le tout en quelques centaines de lignes de code !
Abstract
La mémoisation de fonction est une optimisation bien connue qui permet de ne calculer qu'une fois une fonction sans effet de bord pour chaque nouvelle combinaison de paramètre. Depuis python 3.2, cette optimisation est disponible dans la bibliothèque standard Python sous la forme du décorateur functools.lru_cache.
Mais voilà, il faut quand même calculer la fonction au moins une fois pour chaque nouvelle combinaison de paramètres, et ça peut prendre du temps.
Dans cette présentation, on va adopter une mesure encore plus extrème : calculer toutes les valeurs de la fonction pour toutes les entrées. Oui, remplacer un appel de fonction par un (simple) accès mémoire. Ou presque.
On verra que c'est parfois possible, même quand le domaine d'entrée est grand, que ça peut aller vite, et que cela a même des applications en sécurité informatique pour le moins inattendues...
Sponsors
Platinium
Gold
Bronze
Partenaires
