Ruby Maths Fonction Memoization

Question

J'ai écrit un code qui ressemble à ceci:

def get(x, y) 
    @cachedResults.set(x,y, Math.hypot(x, y)) if @cachedResults.get(x,y).nil? 
    @cachedResults.get(x,y) 
end 

Où @cachedResults contenaient une classe Array 2D je l'ai écrit (en quelques minutes) et le but de cette fonction est de vous assurer que Je n'ai jamais besoin d'appeler Math.hypot deux fois pour n'importe quel (x, y). [Cela pourrait être optimisé davantage en utilisant la symétrie et d'autres choses, mais peu importe]

J'ai donc appelé la fonction et l'ai fait fonctionner 160000 fois; il a couru dans un peu plus de 15 secondes. Ensuite, pour voir combien il était plus rapide que la version non memoized, j'ai changé le code à ceci:

def get(x, y) 
    Math.hypot(x, y) 
end 

Et, à ma grande surprise, il a fallu un peu plus de 15 secondes pour courir à nouveau. Le même moment. Donc, ma question est, sont les fonctions mathématiques en ruby ​​naturellement Memoized? Et, dans l'affirmative, dans quelle mesure le rubis est-il mémorisé?

(Sinon, pourquoi pensez-vous que je reçois ce résultat toujours?)

Answer 1

Faut-il environ 15 secondes pour faire quoi que ce soit 160000 fois pour vous? Benchmark sur votre système en renvoyant simplement x; il se pourrait bien que l'opération hypot (implémentée en C) soit négligeable par rapport au temps système de l'interpréteur.

Ruby 1.8.7 avec la méthode memoized get de Khell, appelant la fonction dans une méthode get, et juste revenir x dans une méthode get, avec 100000 itérations:

 
peregrino:$ time ruby src/memoized_hypot.rb 

real 0m1.714s 
user 0m1.436s 
sys 0m0.080s 
peregrino:$ time ruby src/plain_hypot.rb 

real 0m0.495s 
user 0m0.364s 
sys 0m0.060s 
peregrino:$ time ruby src/empty_hypo.rb 

real 0m0.369s 
user 0m0.220s 
sys 0m0.068s 

de memoization de kheill crée une chaîne sur tous les appel, ce qui est beaucoup plus coûteux que d'appeler la fonction hypot de la bibliothèque C sur chaque appel.

La différence entre l'hypot appelant et le retour juste x indique que hypot ne contribue que 25% du temps d'exécution. Ce n'est pas le code que vous devriez optimiser - essayez à la place d'inlining l'appel à la bibliothèque si vous pouvez plutôt que l'encapsuler dans une autre méthode.

 
peregrino:$ time ruby src/inline_hypot.rb 

real 0m0.365s 
user 0m0.236s 
sys 0m0.044s 

qui est

100000.times{ |i| Math.hypot(i,6) } 

plutôt que

100000.times{ |i| foo.get(i,6) } 

où foo est un objet avec les méthodes affichées.

---

Ces temps étaient sur un netbook (Asus EeePC 900) qui est pas massivement rapide, il est donc un peu bizarre qu'ils sont beaucoup plus rapides que votre temps. Donc, quelque chose d'autre pourrait dominer vos résultats.

Answer 2

Je ne vais pas attendre une mémorisation ici permettra d'améliorer beaucoup dans ce cas.

Ce que Math.hypot fait est juste sqrt(x**2 + y**2). Ce n'est pas un appel récursif à la valeur déjà calculée.

Answer 3

Essayez ceci:

def initialize 
    @cachedResults = {} 
end 

def get(x, y) 
    @cachedResults["#{x}:#{y}"] ||= Math.hypot(x, y) 
end