Книга: Программирование на языке Ruby

5.29. Кэширование функций с помощью метода memoize

5.29. Кэширование функций с помощью метода memoize

Пусть имеется вычислительно сложная математическая функция, которую нужно многократно вызывать по ходу работы программы. Если быстродействие критично и при этом можно пожертвовать небольшим количеством памяти, то имеет смысл сохранить результаты вычисления функции в таблице и обращаться к ней во время выполнения. (Тут неявно предполагается, что функция будет часто вызываться с одними и теми же параметрами, то есть получается, что мы «выбрасываем» результат дорогостоящего вычисления и снова повторяем его позже.) Такая техника иногда называется запоминанием (memoizing), отсюда и название библиотеки memoize.

Эта библиотека не входит в стандартный дистрибутив, поэтому придется установить ее вручную.

В следующем примере демонстрируется сложная функция zeta. Она применяется при решении одной задачи из области популяционной генетики, но вдаваться в объяснения мы не станем.

require 'memoize'
include Memoize
def zeta(x,y,z)
 lim = 0.0001
 gen = 0
 loop do
  gen += 1
  p,q = x + y/2.0, z + y/2.0
  x1, y1, z1 = p*p*1.0, 2*p*q*1.0, q*q*0.9
  sum = x1 + y1 + z1
  x1 /= sum
  y1 /= sum
  z1 /= sum
  delta = [[x1,x],[y1,y],[z1,z]]
  break if delta.all? {|a,b| (a-b).abs < lim }
  x,y,z = x1,y1,z1
 end
 gen
end
g1 = zeta(0.8,0.1,0.1)
memoize(:zeta)           # Сохранить таблицу в памяти.
g2 = zeta(0.8,0.1,0.1)
memoize(:zeta,"z.cache") # Сохранить таблицу на диске.
g3 = zeta(0.8,0.1,0.1)

Обратите внимание, что можно задать имя файла. Это может несколько замедлить работу, зато экономится память, и таким образом мы можем сохранить запомненные результаты и воспользоваться ими при следующих вызовах программы.

В ходе неформального тестирования мы вызывали функцию 50000 раз в цикле. Оказалось, что g2 вычисляется примерно в 1100 раз быстрее, чем g1, а g3 — примерно в 700 раз. На вашей машине может получиться иной результат.

Отметим еще, что библиотека memoize предназначена не только для математических функций. Ее можно использовать для запоминания результатов работы любого вычислительно сложного метода.

Оглавление книги