Chocoblog

Chocoblog

Billets sur l'informatique, les logiciels libres et retours d'utilisation sont au programme avec la possibilité de publier des billets de copains.

Fonctions récursives plus rapides en Perl qu'en C : Memoize

Memoize est un module Perl pouvant rendre votre fonction récursive infiniment plus rapide qu'en langage bas niveau comme C par exemple (hé oui Perl > all).

Le concept est tout bête mais terriblement efficace. En réalité le module va enregistrer les arguments et valeurs de retour de tous vos appels de fonction dans un cache (hashmap). Et du coup quand vous rappelez la fonction avec les mêmes arguments, au lieu de faire le calcul Memoize va simplement vous retourner le résultat qui était en cache.

Prenons un exemple frappant que l'on peut d'ailleurs trouver sur la page du module : Fibonacci. On va l'appeler f pour éviter de fatiguer mes petits doigts.

Petit rappel : pour calculer Fibonacci à un rang n, il faut ajouter la valeur de retour de la fonction au rang n-1 et n-2 en sachant que f(1) vaut 1 et f(0) 0. Par exemple, si vous voulez calculer f(4) vous devez ajouter f(3) et f(2). Récursivement pour calculer f(3) il vous faudra faire f(2) + f(1) et ainsi de suite. Autant dire qu'on fait beaucoup de calculs répétitifs.

Prenons par exemple le programme C suivant :

#include <stdio.h>

int fibo (int n){
    return (n < 2) ? n : fibo(n-1) + fibo(n-2);
}

int main(int argc, char **argv){
    fprintf(stderr, "%d\n", fibo(atoi(argv[1])));

    return 0;
}

Compilons le en O3 (oui je suis un aventurier) et mesurons le temps à l'arrache en calculant Fibonacci au rang 42 (simple hasard).

21:31:47 130 [florian@:~/Coding/]% time ./fibo 42
267914296
./fibo 42  3,59s user 0,01s system 97% cpu 3,712 total

Maintenant en Perl :

#!/usr/bin/perl -w
use strict;
use Memoize;
memoize('fibo');

my $val = shift;
say(fibo($val));

sub fibo {
    my $n = shift;
    return ($n < 2) ? $n : fibo($n-1) + fibo($n-2);
}

Quelle beauté, quelle volupté.

21:34:56 127 [florian@:~/Coding/Perl/]% time ./fibo_ameliore 42
267914296
./fibo_ameliore 42  0,03s user 0,00s system 77% cpu 0,043 total

Tranquille.

On a donc un temps d'environ 3,5 secondes en C et de presque 0,05 secondes en Perl pour calculer Fibonacci au rang 42. Je sais pas vous mais moi je trouve ça impressionnant.

J'ai voulu tester sans le module, mais au bout de 10min j'ai arrêté l'expérience :p