Запоминание функции Ruby Maths

Question

Я написал код, который выглядит следующим образом:

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

Где @cachedResults содержал класс 2D Array, который я написал (через несколько минут), и цель этой функции - убедиться, что мне никогда не придется вызывать Math.hypot дважды для любого заданного (x, y). [Это можно было бы оптимизировать дальше, используя симметрию и другие вещи, но неважно]

Итак, я вызвал функцию и позволил ей работать 160000 раз; он побежал чуть более 15 секунд. Затем, чтобы увидеть, насколько это было быстрее, чем версия без Memoized, я изменил код так:

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

И, к моему удивлению, потребовалось чуть более 15 секунд, чтобы снова бежать. Точно такое же время. Итак, мой вопрос: математические функции в ruby ​​естественно запоминаются? И если да, то в какой степени рубин запоминается?

(Если нет, то почему вы думаете, что я постоянно получаю этот результат?)

Answer 1

Требуется ли около 15 секунд, чтобы сделать что-нибудь 160000 раз для вас? Оцените его в своей системе, просто возвращая x; вполне может быть, что операция гипотета (реализованная в C) незначительна, чем издержки интерпретатора.

Для ruby ​​1.8.7 с запомненным методом get из khell, вызывающим функцию внутри метода get и просто возвращающим x внутри метода get с 100000 итерациями:

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

Запоминание kheill создает строку при каждом вызове, что намного дороже, чем вызов гипотетической функции библиотеки C при каждом вызове.

Разница между вызывающей гипотезой и просто возвращением x указывает на то, что она вносит только 25% времени выполнения. Это не тот код, который вы должны оптимизировать - вместо этого попробуйте встроить вызов в библиотеку, если можете, вместо того, чтобы переносить его в другой метод.

peregrino:$ time ruby src/inline_hypot.rb 

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

что составляет

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

вместо

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

где foo - объект с опубликованными методами.

---

Эти времена были на нетбуках (Asus eeepc 900), которые не очень быстры, поэтому немного странно, что они намного быстрее, чем ваши. Так что что-то еще может доминировать над вашими результатами.

Answer 2

Попробуйте это:

def initialize
  @cachedResults = {}
end

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

Answer 3

Я не ожидаю, что запоминание здесь улучшит много в этом случае.

То, что Math.hypot делает, это просто sqrt(x**2 + y**2). Это не рекурсивный вызов уже вычисленного значения.