关于递归函数的记事

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)时已经完成了...

记忆递归

以下是我通过memoized进行的操作：

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 

我认为我在某处完全错了...我可以将输出存储在全局变量中，但我真的想让它与memoization或连续样式传递一起使用并避免冗余计算！

如果有人有想法，我将非常感激！

Answer 1

好的，首先，我在auxiliaryCompute函数上放了一些loginfo：

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不是一种强类型语言，而且主要是因为我对“令人困惑”的日期和字符串编码非常糟糕！