替代实现
介绍
自从这篇文章发布以来,我在R中的工作频率有所增加,因此我提供了一种基于R基础的替代实现。同样地,我认为如果下降到C扩展级别,你可以获得更好的性能。原始答案在下面。
在基础R中的第一个挑战是缺乏真正的cons
(暴露在R级别上)。R使用c
进行混合cons/concat操作,但这并不创建链接列表,而是创建一个新的向量,其中包含两个参数的元素。特别地,必须知道两个参数的长度,这在惰性序列的情况下并不成立。此外,连续的c
操作表现出二次性能,而不是常数时间。现在,您可以使用长度为两个的“列表”(实际上是向量,而不是链接列表)来模拟cons单元格,但是......
第二个挑战是数据结构中的promise强制。 R使用隐式promise使用一些惰性评估语义,但这些是二等公民。返回显式promise的函数delay
已被弃用,而是使用隐式delayedAssign
,仅执行其副作用--“未评估的promise永远不应可见。”函数参数是隐式promise,因此您可以使用它们,但是您无法将promise放入数据结构中而不强制执行它。
计算机科学101
事实证明,这两个挑战可以通过回想计算机科学101来解决。数据结构可以通过闭包实现。
cons <- function(h,t) function(x) if(x) h else t
first <- function(kons) kons(TRUE)
rest <- function(kons) kons(FALSE)
由于R的惰性函数参数语义,我们的cons函数已经能够处理惰性序列了。
fibonacci <- function(a,b) cons(a, fibonacci(b, a+b))
fibs <- fibonacci(1,1)
为了能够有用,我们需要一套懒序列处理函数。在Clojure中,作为核心语言的序列处理函数也自然地与懒序列配合使用。另一方面,R的序列函数则不会立即兼容。许多函数依赖于预先知道(有限的)序列长度。让我们定义一些能够处理懒序列的函数。
filterz <- function(pred, s) {
if(is.null(s)) return(NULL)
f <- first(s)
r <- rest(s)
if(pred(f)) cons(f, filterz(pred, r)) else filterz(pred, r) }
take_whilez <- function(pred, s) {
if(is.null(s) || !pred(first(s))) return(NULL)
cons(first(s), take_whilez(pred, rest(s))) }
reduce <- function(f, init, s) {
r <- init
while(!is.null(s)) {
r <- f(r, first(s))
s <- rest(s) }
return(r) }
让我们使用我们已经创建的内容来计算所有小于4百万的偶数斐波那契数之和(欧拉计划#2):
reduce(`+`, 0, filterz(function(x) x %% 2 == 0, take_whilez(function(x) x < 4e6, fibs)))
# [1] 4613732
原始回答
我对R语言很生疏,但是既然(1)我熟悉Clojure,(2)我认为你没有向R用户表达清楚你的观点,那么我将尝试根据我的Clojure惰性序列工作示例来进行草图。这仅用于示例目的,不以任何方式调整性能。如果不存在C扩展程序,则最好将其实现为C扩展程序。
惰性序列在thunk中具有生成剩余序列的计算。它不会立即调用。在请求每个元素(或一些元素)时,会调用下一个thunk以检索值。如果它继续,该thunk可能会创建另一个thunk来表示序列的尾部。神奇的是,(1)这些特殊的thunk实现了序列接口,并且可以透明地使用它们,(2)每个thunk只被调用一次——它的值被缓存——因此实现的部分是值序列。
首先是标准示例
自然数
numbers <- function(x) as.LazySeq(c(x, numbers(x+1)))
nums <- numbers(1)
take(10,nums)
sum(take(100000,nums))
斐波那契数列
fibonacci <- function(a,b) {
as.LazySeq(c(a, fibonacci(b, a+b)))}
fibs <- fibonacci(1,1)
take(10, fibs)
nth(fibs, 20)
紧随其后的天真的R实现
惰性序列类
is.LazySeq <- function(x) inherits(x, "LazySeq")
as.LazySeq <- function(s) {
cache <- NULL
value <- function() {
if (is.null(cache)) {
cache <<- force(s)
while (is.LazySeq(cache)) cache <<- cache()}
cache}
structure(value, class="LazySeq")}
一些带有LazySeq实现的通用序列方法。
first <- function(x) UseMethod("first", x)
rest <- function(x) UseMethod("rest", x)
first.default <- function(s) s[1]
rest.default <- function(s) s[-1]
first.LazySeq <- function(s) s()[[1]]
rest.LazySeq <- function(s) s()[[-1]]
nth <- function(s, n) {
while (n > 1) {
n <- n - 1
s <- rest(s) }
first(s) }
#Note: Clojure's take is also lazy, this one is "eager"
take <- function(n, s) {
r <- NULL
while (n > 0) {
n <- n - 1
r <- c(r, first(s))
s <- rest(s) }
r}