有的时候我们需要使用第归算法等, 如果能够把中间的计算结果记录到内存中, 那么下次第归就直接取用而不重新计算, 这样就可以节约时间. R 包 memoise 可以完成这样的事情.
例如, 我们可以用第归的方法计算费波拉契数列. 其中两个方程, 一个方程使用 memoise 函数, 另一个不使用.
slow_fab <- function(x)
{
if (x < 2) return(1)
slow_fab(x - 2) + slow_fab(x - 1)
}
fast_fab <- memoise(
function(x)
{
if (x < 2) return(1)
fast_fab(x - 2) + fast_fab(x - 1)
}
)
system.time(slow_fab(30))
# user system elapsed
# 2.379 0.000 2.379
system.time(fast_fab(30))
# user system elapsed
# 0.004 0.000 0.003
从结果可以看出使用 memoise 函数的运算速度要快于没有使用 memoise 函数的运算速度.
该包中还有函数 forget, 是用来清除存储的函数的计算值. 接着上面的例子.
system.time(slow_fab(40))
# user system elapsed
#272.715 0.279 273.151
system.time(fast_fab(40))
user system elapsed
0.003 0.000 0.003
forget(fast_fab(40))
system.time(fast_fab(40))
# user system elapsed
# 0.008 0.000 0.008
system.time(fast_fab(40))
# user system elapsed
# 0 0 0
从上面的例子, 可以知道, 对于 fast_fab 函数的不同的计算结果都被保存在了内存里面, 之后的调用会直接在以有的函数计算结果的基础上进行计算, 所以计算速度很快. 如果我们使用 forget 函数, 清除内存中保存的计算结果, 那么计算就会重新开始.
memoise 包中也有相应的函数来帮助判断一个函数是否会记录结果.
is.memoised(fast_fab)
#[1] TRUE
is.memoised(slow_fab)
#[1] FALSE
memoise 函数把不同参数的计算结果存储在哈希表中, 可以通过 has_cache 函数来查看. 接着上面的计算来查看.
has_cache(fast_fab)(40)
#[1] TRUE
has_cache(fast_fab)(30)
#[1] TRUE
has_cache(fast_fab)(20)
#[1] TRUE
has_cache(fast_fab)(10)
#[1] TRUE
has_cache(fast_fab)(50)
#[1] FALSE
所以, memoise 函数实际上是用空间来换时间, 把中间计算过程记录在内存的哈希表中, 在下一次用到相同参数的结果时, 直接取出来. 当然, 第一次计算总是需要花和不使用 memoise 一样甚至更多的时间, 不过在未来的计算中就会节约时间. 所以, memoise 包十分适合需要多次使用, 有相同的输入和相应稳定的输出值的函数. 而对于例如随机数产生函数, 我们每次使用均希望获得不一样的值, 则 memoise 不能满足我们的要求, 因为当所输入的参数相同的时候, 它会把之前存储的随机数直接输出.
