Aad*_*hah 31 javascript lazy-evaluation immutable.js lazy.js
首先,让我为那些不认识的人定义什么是捷径融合.在JavaScript中考虑以下数组转换:
var a = [1,2,3,4,5].map(square).map(increment);
console.log(a);
function square(x) {
return x * x;
}
function increment(x) {
return x + 1;
}这里我们有一个数组,[1,2,3,4,5]其元素首先被平方,[1,4,9,16,25]然后递增[2,5,10,17,26].因此,虽然我们不需要中间数组[1,4,9,16,25],但我们仍然创建它.
捷径融合是一种优化技术,它可以通过将一些函数调用合并为一个来消除中间数据结构.例如,可以将快捷融合应用于上述代码以产生:
var a = [1,2,3,4,5].map(compose(square, increment));
console.log(a);
function square(x) {
return x * x;
}
function increment(x) {
return x + 1;
}
function compose(g, f) {
return function (x) {
return f(g(x));
};
}如您所见,通过组合和函数将两个单独的map调用融合到一个map调用中.因此,不创建中间阵列.squareincrement
现在,我理解像Immutable.js和Lazy.js这样的库在JavaScript中模仿延迟评估.延迟评估意味着仅在需要时计算结果.
例如,考虑上面的代码.虽然我们square和increment数组的每个元素,但我们可能不需要所有的结果.
假设我们只想要前3个结果.使用Immutable.js或Lazy.js,我们可以获得前3个结果,[2,5,10]而不计算最后2个结果[17,26],因为它们不是必需的.
但是,懒惰评估只会延迟结果计算直到需要.它不会通过融合函数来删除中间数据结构.
为了清楚地说明这一点,请考虑以下代码来模拟延迟评估:
var List = defclass({
constructor: function (head, tail) {
if (typeof head !== "function" || head.length > 0)
Object.defineProperty(this, "head", { value: head });
else Object.defineProperty(this, "head", { get: head });
if (typeof tail !== "function" || tail.length > 0)
Object.defineProperty(this, "tail", { value: tail });
else Object.defineProperty(this, "tail", { get: tail });
},
map: function (f) {
var l = this;
if (l === nil) return nil;
return cons(function () {
return f(l.head);
}, function () {
return l.tail.map(f);
});
},
take: function (n) {
var l = this;
if (l === nil || n === 0) return nil;
return cons(function () {
return l.head;
}, function () {
return l.tail.take(n - 1);
});
},
mapSeq: function (f) {
var l = this;
if (l === nil) return nil;
return cons(f(l.head), l.tail.mapSeq(f));
}
});
var nil = Object.create(List.prototype);
list([1,2,3,4,5])
.map(trace(square))
.map(trace(increment))
.take(3)
.mapSeq(log);
function cons(head, tail) {
return new List(head, tail);
}
function list(a) {
return toList(a, a.length, 0);
}
function toList(a, length, i) {
if (i >= length) return nil;
return cons(a[i], function () {
return toList(a, length, i + 1);
});
}
function square(x) {
return x * x;
}
function increment(x) {
return x + 1;
}
function log(a) {
console.log(a);
}
function trace(f) {
return function () {
var result = f.apply(this, arguments);
console.log(f.name, JSON.stringify([...arguments]), result);
return result;
};
}
function defclass(prototype) {
var constructor = prototype.constructor;
constructor.prototype = prototype;
return constructor;
}如您所见,函数调用是交错的,只处理数组的前三个元素,证明结果确实是懒惰地计算的:
square [1] 1
increment [1] 2
2
square [2] 4
increment [4] 5
5
square [3] 9
increment [9] 10
10
如果不使用延迟评估,那么结果将是:
square [1] 1
square [2] 4
square [3] 9
square [4] 16
square [5] 25
increment [1] 2
increment [4] 5
increment [9] 10
increment [16] 17
increment [25] 26
2
5
10
但是,如果看源代码然后每个功能list,map,take并mapSeq返回一个中间List数据结构.没有进行捷径融合.
这让我想到了我的主要问题:像Immutable.js和Lazy.js这样的库是否会执行捷径融合？
我问的原因是因为根据文档,他们"显然"做了.但是,我持怀疑态度.我怀疑他们是否真的进行了短切融合.
例如,这取自Immutable.js 的README.md文件:
Immutable还提供了一个惰性Seq,允许有效链接收集方法map,filter无论是否创建中间表示.Seq用Range和创建一些Repeat.
因此,Immutable.js的开发人员声称他们的Seq数据结构允许有效链接收集方法map,filter 无论是否创建中间表示(即它们执行快捷融合).
但是,我没有看到他们在任何地方的代码中这样做.也许我找不到它,因为他们使用的是ES6,我的眼睛并不太熟悉ES6语法.
此外,在他们的Lazy Seq文档中,他们提到:
Seq描述了一个惰性操作,允许它们有效地链接使用所有Iterable方法(例如map和filter).Seq是不可变的 - 一旦创建了Seq,它就不能被改变,附加,重新排列或以其他方式修改.相反,在Seq上调用的任何变异方法都将返回一个新的Seq.
Seq是懒惰的 - Seq尽可能少地响应任何方法调用.
所以确定它Seq确实是懒惰的.但是,没有示例表明确实没有创建中间表示(他们声称正在进行中间表示).
继续使用Lazy.js,我们也有同样的情况.值得庆幸的是,Daniel Tao撰写了一篇关于Lazy.js如何运作的博客文章,其中他提到Lazy.js的核心功能组合.他给出了以下例子:
Lazy.range(1, 1000)
.map(square)
.filter(multipleOf3)
.take(10)
.each(log);
function square(x) {
return x * x;
}
function multipleOf3(x) {
return x % 3 === 0;
}
function log(a) {
console.log(a);
}<script src="https://rawgit.com/dtao/lazy.js/master/lazy.min.js"></script>这里map,filter和take功能产生中间MappedSequence,FilteredSequence和TakeSequence对象.这些Sequence对象本质上是迭代器,不需要中间数组.
但是,据我所知,仍然没有发生捷径融合.中间阵列结构简单地用Sequence未熔合的中间结构代替.
我可能是错的,但我相信表达式会Lazy(array).map(f).map(g)产生两个单独的MappedSequence对象,其中第一个MappedSequence对象将其值提供给第二个对象,而不是第二个通过执行两者的工作(通过函数组合)替换第一个对象.
TLDR: Immutable.js和Lazy.js确实执行捷径融合吗？据我所知,他们通过序列对象(即迭代器)模拟延迟评估来摆脱中间数组.但是,我相信这些迭代器是链接的:一个迭代器懒洋洋地将它的值提供给下一个迭代器.它们不会合并为单个迭代器.因此,他们不"消除中间表征".它们只将数组转换为常量空间序列对象.
Lee*_*ron 35
我是Immutable.js的作者(和Lazy.js的粉丝).
Lazy.js和Immutable.js的Seq是否使用捷径融合？不,不完全是.但他们确实删除了操作结果的中间表示.
捷径融合是一种代码编译/转换技术.你的榜样很好:
var a = [1,2,3,4,5].map(square).map(increment);
Transpiled:
var a = [1,2,3,4,5].map(compose(square, increment));
Lazy.js和Immutable.js不是转换器,也不会重写代码.它们是运行时库.因此,它们使用可迭代组合(运行时技术)而不是快捷融合(编译器技术).
你在TLDR中回答这个问题:
据我所知,他们通过序列对象(即迭代器)模拟延迟评估来摆脱中间数组.但是,我相信这些迭代器是链接的:一个迭代器懒洋洋地将它的值提供给下一个迭代器.它们不会合并为单个迭代器.因此,他们不"消除中间表征".它们只将数组转换为常量空间序列对象.
这是完全正确的.
我们打开包装:
链接时,数组存储中间结果:
var a = [1,2,3,4,5];
var b = a.map(square); // b: [1,4,6,8,10] created in O(n)
var c = b.map(increment); // c: [2,5,7,9,11] created in O(n)
快捷融合转化创造了中间功能:
var a = [1,2,3,4,5];
var f = compose(square, increment); // f: Function created in O(1)
var c = a.map(f); // c: [2,5,7,9,11] created in O(n)
可迭代组合创建中间可迭代:
var a = [1,2,3,4,5];
var i = lazyMap(a, square); // i: Iterable created in O(1)
var j = lazyMap(i, increment); // j: Iterable created in O(1)
var c = Array.from(j); // c: [2,5,7,9,11] created in O(n)
请注意,使用可迭代合成,我们还没有创建中间结果的存储.当这些库表示他们不创建中间表示时 - 他们的意思正是这个例子中描述的内容.没有创建包含值的数据结构[1,4,6,8,10].
但是,当然会进行一些中间表示.每个"懒惰"操作必须返回一些东西.他们返回一个可迭代的.创建这些非常便宜并且与正在操作的数据的大小无关.注意,在短切融合转录中,还进行了中间表示.结果compose是一个新功能.功能组合(手写或快捷融合编译器的结果)与可重复组合非常相关.
删除中间表示的目标是性能,特别是关于内存.可迭代组合是一种实现此功能的强大方法,并且不需要解析和重写优化编译器代码的开销,这些代码在运行时库中是不合适的.
APPX:
这是一个简单的实现lazyMap可能看起来像:
function lazyMap(iterable, mapper) {
return {
"@@iterator": function() {
var iterator = iterable["@@iterator"]();
return {
next: function() {
var step = iterator.next();
return step.done ? step : { done: false, value: mapper(step.value) }
}
};
}
};
}