Войти на сайт

Авторизация, ждите ...
×

ТЕМА: Мемоизация

Мемоизация 7 года 8 мес. назад #75302

  • Iren_Rin
  • Iren_Rin аватар
  • Вне сайта
  • Мастер
  • Сообщений: 247
  • Спасибо получено: 536
  • Проект месяца 1 местоПроект года 1 местоПрограммист RubyКоммерсантУчитель
После непродолжительного отпуска сначала в горах, потом на острове решил выложить небольшую статью о том, с чем я сталкиваюсь каждый день - о мемоизации.
И так, мемоизация - запоминание (кэширование) результата исполнения какого нибудь куска кода, в нашем случае - метода. Если применять ее умело, то выгода велика, как впрочем и опасность возможных веселых багов. И так, ближе к делу, давайте рассмотрим следующий код.
class Dog
  def bar
    sleep 3
    'bar!'
  end
end
Метод #bar у нас будет представлять медленный метод, предположим что в нем происходит сложное вычисление, результат которого в принципе будет постоянным для данного объекта, т.е. не поменяется за время его жизни. Каждый раз при вызове #bar мы будем ждать 3 секунды, а в реальности еще будем тратить ресурсы машины. Хотелось бы как нибудь сохранить результат исполнения метода, и при следующем вызове возвращать его, а не исполнять все заново. И вот к нам на помощь приходят инстанс переменные, они имеют значение nil по умолчанию.
# тут и дальше представьте что мы пишем внутри класса Bar
def bar
  unless @bar
    @bar = begin
      sleep 3
      'bar!' #мы запишем в @bar строку, и в следующий раз руби не пойдет в unless
    end
  end
  @bar
end
Этот некрасивый участок кода уже будет работать, но хотелось бы то нибудь покороче. Упростим:
def bar
  @bar || @bar = begin
     sleep 3
     'bar!'
  end
end
Вот это уже куда ближе. Когда в @bar ничего нет - выполнится вторая часть, когда там будет строка - метод вернет эту строка и остановится.
В руби есть еще более сокращенная запись - выражение ||=. Используем его, и вместо блока с begin - end вынесем медленное вычисление в отдельный приватный метод
def bar
  @bar ||= calculate_bar # ||= следует понимать как “верни мне значение переменной или,
                                        # если там nil или false,- вычисли правую часть, запиши результат в
                                        # переменную, и верни его
end
 
private
 
def calculate_bar
  sleep 3
  'bar!'
end

Поговорим теперь о подводных камнях, которые тут легко упустить
1 Приватный метод исполниться только один раз. Не используйте мемоизацию если не уверены что результат исполнения будет постоянным.
2 И менее очевидная вещь - если результатом исполнение медленной части является булево значение ( True или False ) то такая мемоизация сработает только если метод возращает True. Мой прошлый проект жил с такими методами где то с год, и все удивлялись, почему же так медленно)
def fast_part
  @result ||= slow_part
end
 
private
 
def slow_part
  sleep 3
  false
end

И так, вызываем первый раз #fast_part и записываем в @result false. Вызываем следующий раз и фактически будет исполнено следующее:
  false ||= slow_part # и как результат руби всегда будет исполнять slow_part
                                 # и записывать результат в result

Для мемоизации булевых методов нужно делать так
def fast_part
  @result = slow_part unless defined? @result # defined? уже просто так не обдурить))
  @result
end

А что делать если метод принимает аргументы и его результат будет зависеть от их? Воспользуемся хэшами, ведь они тоже возвращают nil для несуществующего ключа (по умолчанию). Так же ключами хэшей могут быть почти все объекты, в том числе и массивы.
def fast_part(a, b)
  @results ||= {} #инициализируем @results пустым хэшем, если нужно
  @results[[a, b]] ||= slow_part(a, b) # записываем результат в хэш с ключем - массивом из аргументов
end
 
private
 
def slow_part(a, b)
  sleep 3
  "#{a} #{b}"
end

Вариант fast_part для булевых методов будет таким
def fast_part(a, b)
  @results ||= {}
  @results[[a, b]] = slow_part(a, b) unless @results.has_key?([a, b])
  @results[[a, b]]
end
Вот и все, используйте мемоизацию с умом и да ускорятся скрипты ваши.
Последнее редактирование: 7 года 8 мес. назад от Iren_Rin.
Администратор запретил публиковать записи гостям.
За этот пост поблагодарили: Lekste, Ren310, strelokhalfer, caveman, Amphilohiy, poca, yuryol, MaltonTheWarrior

Мемоизация 7 года 8 мес. назад #75304

  • Lekste
  • Lekste аватар
  • Вне сайта
  • Светлый дракон
  • Сообщений: 909
  • Спасибо получено: 561
  • Программист JavaScript ОраторВетеранПрограммист RubyДаритель Стимкея
Очевидно, но полезно.
Как ж я не любил раньше скрипты за сокращения эти... :)
Администратор запретил публиковать записи гостям.

Мемоизация 5 года 11 мес. назад #93381

  • Amphilohiy
  • Amphilohiy аватар
  • Вне сайта
  • Светлый дракон
  • Сообщений: 547
  • Спасибо получено: 665
  • ОраторПрограммист Ruby2 место ГотвПобедитель Сбитой кодировкиУчитель
Внезапно наткнулся на мемоизацию в Хэше. По большому счету средствами руби. Надыбал тут такой кусок кода:
# While this creates a new default object each time
h = Hash.new { |hash, key| hash[key] = "Go Fish: #{key}" }
h["c"]           #=> "Go Fish: c"
h["c"].upcase!   #=> "GO FISH: C"
h["d"]           #=> "Go Fish: d"
h.keys           #=> ["c", "d"]
Изначально идея класть значения по умолчанию в хэшЮ при обращении по некоторому ключу. Однако применение в мемоизации кажется (во всяком случае мне) очевидным. Например рекурсивное вычисление числа фибоначчи:
cache = Hash.new do |hash, key|
	puts "evaluate value for #{key}"
	hash[key] = [0, 1].include?(key) ? 1 : hash[key-1] + hash[key-2]
end
 
puts cache # => {}
# > evaluate value for 10
# > evaluate value for 9
# > evaluate value for 8
# > evaluate value for 7
# > evaluate value for 6
# > evaluate value for 5
# > evaluate value for 4
# > evaluate value for 3
# > evaluate value for 2
# > evaluate value for 1
# > evaluate value for 0
puts cache[10] # => 89
puts cache # => {1=>1, 0=>1, 2=>2, 3=>3, 4=>5, 5=>8, 6=>13, 7=>21, 8=>34, 9=>55, 10=>89}
# > evaluate value for 12
# > evaluate value for 11
puts cache[12] # => 233
puts cache # => {1=>1, 0=>1, 2=>2, 3=>3, 4=>5, 5=>8, 6=>13, 7=>21, 8=>34, 9=>55, 10=>89, 11=>144, 12=>233}
Значения добавляются только при обращении к хэшу (что полезно знать, если вы решите пробегать по этому хэшу), и только при отсутствии значения. Так значение числа фибоначчи 10 высчитывало значения для 0-10, в то время как следующее вычисление 12 считало только 11-12.
Я верю, что иногда компьютер сбоит, и он выдает неожиданные результаты, но остальные 100% случаев это чья-то криворукость.
Администратор запретил публиковать записи гостям.
За этот пост поблагодарили: poca, EvilCat
Время создания страницы: 0.650 секунд