Памятка о рекурсивной функции

Question

Вступление

У меня есть функция, принимающая дату в качестве входных данных, выполняющая некоторые вычисления, занимающие определенное время - Sys.sleep() - удаляя все '-' в дату и возвращая символ:

library(maggritr)

auxialiaryCompute = function(vDate)
{
    Sys.sleep(1)
    vDate %>% as.character %>% gsub("-", "", .)
}

> auxialiaryCompute(as.Date("2015-01-14"))
[1] "20150114"

Здорово. Результатом вышесказанного является '20150114', Теперь я хотел бы включить предыдущий вывод в эту функцию. Или два предыдущих дня, или.. n предыдущие результаты до ограниченного дня в прошлом называется loopBackMaxDate,

Грубая рекурсия

Вот один из возможных рекурсивных кодов:

compute = function(vDate, loopBackMaxDate=vDate, loopBackDays=0)
{
    d = as.Date # short alias

    dates = Filter(function(x) x>d(loopBackMaxDate), 
                   getPreviousDates(loopBackDays, d(vDate))) 

    if(length(dates)==0)
        return(auxialiaryCompute(vDate=vDate, previousOutputs=list()))

    previousOutputs = lapply(dates, function(u) compute(u, loopBackMaxDate, loopBackDays))

    auxialiaryCompute(vDate=vDate, previousOutputs=previousOutputs)
}

auxialiaryCompute = function(vDate, previousOutputs=list())
{
    Sys.sleep(1)
    vDate %>% as.character %>% gsub("-", "", .)
}

getPreviousDates = function(loopBackDays, vDate)
{
    if(loopBackDays==0) return()
    seq.Date(from=vDate-loopBackDays, to=vDate-1, by="days")
}

При этом у меня тот же результат, что и раньше (в среднем 1 секунда):

> compute(as.Date("2015-01-14"))
[1] "20150114"

И следующее занимает эффективно 4 секунды:

> system.time(compute("2014-05-05", loopBackMaxDate="2014-05-01", loopBackDays=1))
   user  system elapsed 
   0.00    0.00    3.99 

Я хочу вычислить следующее, это займет 3 секунды:

> system.time(compute("2014-05-04", loopBackMaxDate="2014-05-01", loopBackDays=1))
   user  system elapsed 
   0.02    0.00    3.01 

Это очень плохо, потому что я снова вычисляю результаты vDate="2014-05-04", vDate="2014-05-03" а также vDate="2014-05-02" в то время как это было сделано при звонке compute("2014-05-05", loopBackMaxDate="2014-05-01", loopBackDays=1)...

Памятная рекурсия

Вот как я прошел через запоминание:

library(memoise)

compute = memoise(function(vDate, loopBackMaxDate=vDate, loopBackDays=0)
{
    d = as.Date # short alias

    dates = Filter(function(x) x>d(loopBackMaxDate), getPreviousDates(loopBackDays, d(vDate))) 

    if(length(dates)==0)
        return(auxialiaryCompute(vDate=vDate, previousOutputs=list()))

    previousOutputs = lapply(dates, function(u) compute(u, loopBackMaxDate, loopBackDays))

    auxialiaryCompute(vDate=vDate, previousOutputs=previousOutputs)
})

auxialiaryCompute = memoise(function(vDate, previousOutputs=list())
{
    Sys.sleep(1)
    vDate %>% as.character %>% gsub("-", "", .)
})

Первый запуск (эффективно 4 секунды):

> system.time(compute("2014-05-05", loopBackMaxDate="2014-05-01", loopBackDays=1))
  user  system elapsed 
  0.00    0.00    4.01 

Второй запуск занимает 1 секунду, тогда как я ожидал, что это займет 0 секунд:

> system.time(compute("2014-05-04", loopBackMaxDate="2014-05-01", loopBackDays=1))
   user  system elapsed 
   0.00    0.00    0.99 

Я думаю, что где-то совершенно не прав... Я мог бы хранить выходные данные в глобальной переменной, но я действительно хотел бы, чтобы она работала с запоминанием или передачей в непрерывном стиле и избегала избыточных вычислений!

Если у кого есть идеи, буду очень признателен!

Answer 1

Итак, во-первых, я положил немного логинфо на auxiliaryCompute функция:

compute = memoise(function(vDate, loopBackMaxDate=vDate, loopBackDays=0)
{
    d = as.Date # short alias

    dates = Filter(function(x) x>d(loopBackMaxDate), getPreviousDates(loopBackDays, d(vDate))) 

    if(length(dates)==0)
    {
        loginfo("I reached the tail!")
        return(auxiliaryCompute(vDate=vDate, previousOutputs=0))
    }

    previousOutputs = lapply(dates, function(u){
                    compute(vDate=u, loopBackMaxDate=loopBackMaxDate, loopBackDays)
                  })

    auxiliaryCompute(vDate2=vDate, previousOutputs=previousOutputs)
})

auxiliaryCompute = memoise(function(vDate2, previousOutputs)
{
    loginfo("-------arguments in auxiliaryCompute are: vDate %s , previousOutputs %s", vDate2, unlist(previousOutputs))
#   Sys.sleep(1)
    vDate2 %>% as.character %>% gsub("-", "", .)
})

> compute("2015-01-10", "2015-01-01", 2)
2015-01-20 18:53:12 INFO::I reached the tail!
2015-01-20 18:53:12 INFO::-------arguments: vDate 2015-01-02 , previousOutputs 0
2015-01-20 18:53:12 INFO::-------arguments: vDate 2015-01-03 , previousOutputs 20150102
2015-01-20 18:53:12 INFO::-------arguments: vDate 2015-01-04 , previousOutputs 20150102,20150103
2015-01-20 18:53:12 INFO::-------arguments: vDate 2015-01-05 , previousOutputs 20150103,20150104
2015-01-20 18:53:12 INFO::-------arguments: vDate 2015-01-06 , previousOutputs 20150104,20150105
2015-01-20 18:53:12 INFO::-------arguments: vDate 2015-01-07 , previousOutputs 20150105,20150106
2015-01-20 18:53:12 INFO::-------arguments: vDate 2015-01-08 , previousOutputs 20150106,20150107
2015-01-20 18:53:12 INFO::-------arguments: vDate 2015-01-09 , previousOutputs 20150107,20150108
2015-01-20 18:53:12 INFO::-------arguments: vDate 2015-01-10 , previousOutputs 20150108,20150109
[1] "20150110"

> compute("2015-01-08", "2015-01-01", 2)
2015-01-20 18:54:11 INFO::-------arguments: vDate 2015-01-08 , previousOutputs 20150106,20150107
[1] "20150108"

Первый журнал хорош, мы идем каждый раз только один раз за каждую дату (не повторение с memoize). Однако странно, что во втором журнале функция auxiliaryCompute вызывается с аргументами vDate 2015-01-08 , previousOutputs 20150106,20150107 так как он уже был выполнен (появился в первом логе).

И другие даты запоминаются корректно... только первые ошибки... потому что это строка, а другая дата в рекурсии приводится к формату даты.

Помещая в параметры только даты, это работает:

> compute(as.Date("2015-01-08"), "2015-01-01", 2)
[1] "20150108"

Это действительно подлый, потому что R не является строго типизированным языком, и в основном потому, что я очень плохо кодировал, "путая" даты и строки!