Раздел «Язык Ruby».RubyCourseLecture10:
<<Метапрограммирование на Ruby

Следующая лекция
Предыдущая лекция

Лекция 10: Кэширование значений методов. MakeCached

Идея кэширования 

# без кэширования
def fib(n)
  (n < 2) ? 1 : fib(n-1) + fib(n-2)
end

# с кэшированием (memoization)
def fib(n)
  (@fib ||= {})[n] ||= (
    (n < 2) ? 1 : fib(n-1) + fib(n-2)
  )
end

(1..1000).each do |i|
  p fib(i)
end

Простейший вариант без метапрограммирования

С помощью оператора alias копирования метода (создание копии байткода имеющегося метода под новым именем) можно добавить кэширование к любому методу: 

# библиотечный файл

# без кэширования
def fib(n)
  (n < 2) ? 1 : fib(n-1) + fib(n-2)
end

###################################
# наш файл

# создан метод fib_orig, копия метода fib
# в теле метода fib_orig по-прежнему вызывается функция fib
alias fib_orig fib

def fib(n)
   (@fib ||= {})[n] ||= fib_orig(n)
end

Нужно уметь кэшировать функции с произвольным число аргументов. Звездочка перед именем аргумента в определении метода используется для "сворачивания" всех оставшихся аргументов в массив. Звездочку можно использовать перед массивом при вызове метода, чтобы "развернуть" элементы массива и сделать их отдельными аргументами: 

alias foo_orig foo

def foo(*args)
   (@foo ||= {})[args] ||= foo_orig(*args)
end

Простейший вариант с метапрограммированием — используем eval

Добавление кэширование к методу — стандартная задача. Хотелось бы иметь универсальное решение в одну строку. Например, такое: 

def make_cached(method)
  code = "
    alias foo_orig foo

    def foo(*args)
      (@foo ||= {})[args] ||= foo_orig(*args)
    end
  "
  eval code.gsub('foo', method)
end

nake_cached :fib
make_cached :foo

Решение без eval

Можно обойтись без использования eval. Здесь поможет метод define_method. 

class Module
  # определим метод alias_method,
  # который лучше чем оператор alias тем, что является методом
  # и ему можно передавать не только имена методов, 
  # но и переменные, содержащие имена методов
  def alias_method(a,b)
    class_eval "alias #{a} #{b}"
  end

  def make_cached(method)
    orig_method = "#{method}_orig"
    cache = {}
    alias_method orig_method, method
    define_method(method) do |*args|
      cache[args] ||= send(orig_method, *args)
    end
  end
end


class A
  def fib(n)
    (n < 2) ? 1 : fib(n-1) + fib(n-2)
  end

  make_cached :fib
end

p A.new.fib(1000)

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

Мы не создавали переменную экземпляра класса (instance variable), и тем самым не создавали потенциальной угрозы пересечения имён (разработчик класса мог бы использовать переменную с таким же именем для каких-то своих целей).

Данный код работает только для методов, определенных для заданного класса. Для глобальных методов он не работает.

Решение без использования функции eval, работающее и для глобальных методов 

class Module
  def alias_method(a,b)
    class_eval "alias #{a} #{b}"
  end
end

module MakeCached
  def make_cached(method)
    orig_method = "#{method}_orig"
    cache = {}
    (self.is_a?(Module) ? self : self.singleton_class).class_eval do 
      alias_method orig_method, method
      define_method(method) do |*args|
        cache[args] ||= send(orig_method, *args)
      end
    end
  end
end

class Object
  def singleton_class
    (class << self; self; end)
  end
end

Object.module_eval { include MakeCached }

def fib(n)
  (n < 2) ? 1 : fib(n-1) + fib(n-2)
end
make_cached :fib

p fib(1000)

class A
  def fib2(n)
    (n < 2) ? 1 : fib2(n-1) + fib2(n-2)
  end
  make_cached :fib2
end

p A.new.fib(1000)

alias_method_chain — спасение от коллизий патчей

Модификация существующих методов с помощью alias_method называется monkey patch. Мы модифицируем имеющийся метод, дописывая какой-то код в начало, в конец или окружая метод каким-то кодом.

Другой простейший пример monkey patch — это make_traced: 

module MakeCached
  def make_traced(*methods)
    methods.each do |method|
      orig_method = "#{method}_orig"
      (self.is_a?(Module) ? self : self.singleton_class).class_eval do 
        alias_method orig_method, method
        define_method(method) do |*args|
          puts "#{method}#{args.join(', ')}"
          send(orig_method, *args)
        end
      end
    end
  end
end

Метод make_traced позволяет включить трассировку вызовов определенного метода: 

make_traced :fib

fib(5)

Но попробуйте использовать два патча одновременно: 

make_traced :fib
make_cached:fib

fib(5)

В результате вы получите stack overflow — бесконечную цепочку рекурсивных вызовов.

Объясните почему здесь возникает stack overflow.

Решение этой проблемы заключено в технике alias_method_chain. Вот ее суть: 

def fib(n)
  (n < 2) ? 1 : fib(n-1) + fib(n-2)
end

def fib_with_traced(n)
  puts "fib(#{n})"
  fib_without_traced(n)
end
alias fib_without_traced fib
alias fib fib_with_traced

Метод alias_method выполняется два раза. Вспомогательным методам даются значащие имена вида method_with_feature и method_without_feature. 

# вместо
alias fib_without_traced fib
alias fib fib_with_traced 

# пишут
alias_method_chain :fib, :traced

Определение alias_method_chain см. ниже.

Опция timeout — устаревание закэшированных значений

Добавим новую фичу — устаревание закэшированных значений. 

class Module
  def method_alias(a,b)
    eval "alias #{a} #{b}"
  end
  
  def alias_method_chain(method, feature)
    alias_method "#{method}_without_#{feature}", method
    alias_method method, "#{method}_with_#{feature}"
  end
end

class Object
  def singleton_class
    (class <<self; self; end)
  end
end

def extract_options(args)
  args.last.is_a?(Hash) ? args.pop : {}
end

module MethodModifiers
  def make_cached(*methods)
    options = extract_options(methods)
    cache = {}
    methods.each do |m|
      (self.is_a?(Module) ? self : self.singleton_class).class_eval do
        define_method("#{m}_with_cached") do |*args|
          if options[:timeout]
            if cache.has_key?(args) && cache[args][1] > Time.now
              cache[args]
            else
              res = send("#{m}_without_cached", *args)
              cache[args] = [
                res, 
                Time.now + options[:timeout]
              ]
            end
          else
            if cache.has_key?(args)
              cache[args]
            else
              cache[args] = send("#{m}_without_cached", *args)
            end
          end
        end
        alias_method_chain m, 'cached'
      end
    end
  end  
end

Module.class_eval do 
  include MethodModifiers
end

# пример использования

# закэшируем два метода с устареванием закэшированных значений через 1000 секунд
make_cached :find_user, find_post, :time_out => 1000

В этом коде мы добавили возможность указывать несколько методов в аргументе make_cached. Опции — это просто необязательный последний аргумент класса Hash. Для извлечения опций из массива аргументов используется метод extract_options.

Полезные опции

Следующая лекция
Предыдущая лекция

-- ArtemVoroztsov - 11 Mar 2010