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 предназначена не только для математических функций. Ее можно использовать для запоминания результатов работы любого вычислительно сложного метода.