Pourquoi la récursivité de hachage est-elle plus rapide que la récursivité lambda?

J'ai trouvé deux solutions différentes sur StackOverflow pour calculer un nombre de Fibonacci. On utilise un lambda, comme ceci:Pourquoi la récursivité de hachage est-elle plus rapide que la récursivité lambda?

f = ->(x){ x < 2 ? x : f[x-1] + f[x-2] } 
f[6] # => 8

L'autre utilise un Hash:

f = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] } 
f[6] # => 8

La version Hash est plus rapide que la version lambda.

Benchmark.bm do |x| 
    x.report { f[35] } 
    x.report { fibonacci[35] } 
end 

user  system  total  real 
7.332000 0.000000 7.332000 (7.349421) 
0.000000 0.000000 0.000000 (0.000000)

La version lambda ne peut pas calculer même f[100] dans un laps de temps raisonnable, alors que la version Hash peut calculer fibonacci[1000] en moins d'une microseconde. Pourquoi la version Hash est-elle plus rapide?

Source

2013-06-17 fbonetti

Quelle version de Ruby avez-vous utilisé pour votre test de performance? –

@tlewin Ma version Ruby est 1.9.3 – fbonetti

Une partie de la raison est que la version lambda doit recalculer f[x-1] + f[x-2] pour chaque nouveau nombre, et il doit le faire récursivement lorsque x devient plus grand.

La version de hachage se souvient de ces calculs précédents et n'a besoin que d'une recherche de hachage extrêmement rapide.

La version lambda pourrait être modifiée pour court-circuiter les recalculs en utilisant la mémorisation ou via un hachage externe utilisé comme antémémoire. Il faudrait un peu plus de code, et un peu plus de mémoire, mais ce serait à la hauteur de la version de hachage.

Source

2013-06-17 17:53:05

Wikipedia a un article sur [memoization] (http://en.wikipedia.org/wiki/Memoization) qui est utile. La mise en œuvre d'un simple mémo est facile et prend peu de code. L'implémentation d'un système complet qui ne consomme pas tout l'espace disponible dans une application à exécution longue constitue un autre problème. Pour un générateur de Fibonacci, je pense qu'il est logique de conserver des valeurs précalculées dans une fourchette raisonnable, mais garder des plages arbitrairement grandes peut vous ouvrir à une attaque DOS si quelqu'un lui dit de générer 100 000 qui remplissent votre RAM. C'est un équilibre entre la vitesse et le bon sens. –

La version Hash conserve les données calculées en mémoire et pas la version lambda.

Si vous exécutez hash_fibonnacci [10] et imprimez l'objet: "p hash_fibonnacci", vous verrez tous les résultats intermédiaires calculés. Chaque appel lambda refera tout le calcul, récursivement, jusqu'au numéro 2. Quand vous appelez lambda_fibonnacci [10], il l'a calculé, environ, 170 fois et l'implémentation de Hash seulement 10 fois.

Source

2013-06-17 17:52:26

Juste un mauvais moyen de faire de la récursivité pour Fibonacci, vous créez un arbre d'appels énorme avant d'arriver aux conditions de bord. Peut être facilement évité en utilisant la récursivité de la queue (non optimisée dans Ruby):

f = 
    lambda do |x| 
    f0 = 
     lambda do |a, b, y| 
     y > 0 ? f0[b, a + b, y - 1] : a 
     end 
    f0[0, 1, x] 
    end 
p (0..100).map(&f)

Source

2013-06-17 20:14:43

Pourquoi la récursivité de hachage est-elle plus rapide que la récursivité lambda?

Répondre

Questions connexes