Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет kouzdra ([info]kouzdra)
@ 2011-08-09 16:01:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
про кэширование рекурсивных функций:
В процессе поигранок с той же задачкой я поигрался естественно с кэшированием значений функции. Довольно очевидно, что на самом деле ее сложность n² (для кэша достаточно матрицы n×n, даже половинки), но мне стало интересно нарисовать "общее решение" - функцию, которая кэширует любую рекурсивную функцию. Получилось немножко через жопу, но забавно:

Как сделать оборачивалку функции в кэшик понятно -
let memo fn = 
   let tab = Hashtbl.create 47 in
   fun arg ->
    try Hashtbl.find tab arg with 
      Not_found -> let res = fn arg in Hashtbl.add tab arg res; res
Но у нас функция рекурсивная:
let rec count (n, m) =
      if n = m then 1
      else if n < m then 0
      else count (n - m, m) + count (n, m+1)
Понятно, что memo count работать будет - а вот кэшировать рекурсивные вызовы не будет и что в таком виде ничего не сделаешь. Надо что-то менять. Можно вспомнить, что мешающая нам рекурсия вовсе не является такой уж фундаментальной вещью и есть такая штука - Y-комбинатор, который реализует рекурсию подавая функцию ей же на вход первым параметром:
let rec y fn arg = fn (y fn) arg
Переписываем функцию в виде пригодном для его употребления:
let count count' (n, m) =
      if n = m then 1
      else if n < m then 0
      else count' (n - m, m) + count' (n, m+1)
y count n у нас считает тоже самое, что count_rec n.

Остается последний шаг - превратить Y-комбинатор в кэширующий Y-комбинатор:
let rec memo fn = 
   let tab = Hashtbl.create 1000_000 in
   let rec fn' arg =
    try Hashtbl.find tab arg with 
      Not_found -> let res = fn fn' arg in Hashtbl.add tab arg res; res
   in fn'
Ну и теперь memo count и есть то, что нам надо. Написав простенкий тестик:
let run fn n = 
    let start = Sys.time () in
    let res = fn  (n, 1) in
    printf "n=%d cnt=%d time=%f\n" n res (Sys.time () -. start); flush stdout

let _ = 
    run count_rec 110;
    run (   y count) 110;
    run (memo count) 110
Имеем на выходе:
make -k 
ocamlopt -inline 9 nums.cmxa -rectypes gil.ml -o gil
./gil
n=110 cnt=607163746 time=71.000437
n=110 cnt=607163746 time=227.194198
n=110 cnt=607163746 time=0.008001
Что можно сказать по этому поводу - оверхед от Y весьма преизрядный, от memo, понятное дело не меньше - но даже в таком лобовом исполнении ее применение более чем оправдано, а применяется оно сугубо механически.

Впрочем расписывание руками будет эффективнее, но не так поучительно.