Lodash chain功能(Lazy Evaluation)介绍


原文:http://filimanjaro.com/blog/2…

我曾经一直认为像Lodash这样的库是不可能正的比它们已有的速度更快的。Lodash几乎完美结合了各种各样的技术来榨干了JavaScript的性能。它使用了JavaScript最快的语句,自适应的算法,它甚至进行性能测试以避免在后续发布的版本中意外的降低了性能。

惰性计算Lazy Evaluation

但是貌似我错了——实际上我们能让Lodas运行速度得到明显提升。而你所需要做的仅仅只是停止考虑一些微观的优化,然后找到并使用更好的算法。例如,在一个典型的循环中,我们通常倾向于优化每次迭代的时间:

var len = getLength();
for(var i = 0; i < len; i++) {
    operation(); // <- 10ms - how to make it 9ms?!
}

但是这样的优化很有限而且很难做到优化。相反的,在某些情况下优化getLength()函数却有意义的多。getLength()函数返回的数字越小,我们要执行的10ms的循环次数就越少。
这就是Lodash中lazy evaluation背后的基本思想:减少循环的次数而不是减少每次循环的时间。让我们看一看下面的例子:

function priceLt(x) {
   return function(item) { return item.price < x; };
}
var gems = [
   { name: 'Sunstone', price: 4 }, { name: 'Amethyst', price: 15 },
   { name: 'Prehnite', price: 20}, { name: 'Sugilite', price: 7  },
   { name: 'Diopside', price: 3 }, { name: 'Feldspar', price: 13 },
   { name: 'Dioptase', price: 2 }, { name: 'Sapphire', price: 20 }
];

var chosen = _(gems).filter(priceLt(10)).take(3).value();

我们只想提取3个价格低于$10的宝石(gem)。常规Lodash方法(Strict evaluation)先筛选所有的8个宝石,然后返回前三个通过筛选的宝石。如下图:

然而,这还不够酷。它处理了所有的8个元素,然而实际上我们只需要读取其中的5个元素。相反的,Lazy evaluation算法只处理数组中最少的元素数量即可获得正确的结果,看如下实例:

这样我们就轻松的获取了37.5%的性能提升,但37.5%不是我们所能达到的极限,实际上很容易就能找到一个带来100倍性能提升的例子。让我们看下面的例子:

var phoneNumbers = [5554445555, 1424445656, 5554443333, … ×99,999];

// get 100 phone numbers containing „55”
function contains55(str) {
    return str.contains("55"); 
};

var r = _(phoneNumbers).map(String).filter(contains55).take(100);

在这个例子中,map和filter要在99999个元素上执行,而实际上,它有可能只需要在少数元素,例如1000个元素上运行就足够了,在这个例子中,Lazy evaluation带来的性能提升非常巨大(benchmark

Pipelining

Lazy evaluation带来的另外一个好处被称为“pipelineing”,这个概念背后的思想是避免在链式执行(chain execution)中创建中间数组。我们应该在一个元素上原地执行所有的操作。所以下面的代码

var result = _(source).map(func1).map(func2).map(func3).value();

在regulaer Lodash常规计算中(strict evaluation)将大致的转换为这样:

var result = [], temp1 = [], temp2 = [], temp3 = [];

for(var i = 0; i < source.length; i++) {
   temp1[i] = func1(source[i]);
}

for(i = 0; i < source.length; i++) {
   temp2[i] = func2(temp1[i]);
}

for(i = 0; i < source.length; i++) {
   temp3[i] = func3(temp2[i]);
}
result = temp3;

而如果在惰性计算(lazy evaluation)打开以后,它将像这样执行:

var result = [];
for(var i = 0; i < source.length; i++) {
   result[i] = func3(func2(func1(source[i])));
}

没有临时数组将给我们带来显著的性能提升,当源数组巨大并且内存访问开销很大时提升更加明显。

延迟执行(Deferred execution)

和lazy evaluation一起带来的另外一个好处就是延迟执行(deferred execution),不管什么时候你创建了一个chain,在显式或者隐式调用.value()方法前它都不会计算。这个特性使我们能先准备一个查询,然后再在在最新的数据上执行这个查询。

var wallet = _(assets).filter(ownedBy('me'))
                      .pluck('value')
                      .reduce(sum);

$json.get("/new/assets").success(function(data) {
    assets.push.apply(assets, data); // update assets
    wallet.value(); // returns most up-to-date value
});

同时因为Lazy evaluation可也以加速执行时间,所以在运行时间很重要的时候,我们可以提前创建一个复杂的查询,然后再执行它。

Wrap up

Lazy evaluation在行业中并不是一个新想法,它已经在例如LINQ,Lazy.js和很多其它的优秀的库中存在了。我认为Lodash不同于他们的地方主要在于你仍然拥有一个外表和Underscore一样的API,但内部却是一个新的强大的引擎。不需要学习新的库,不需要更改大量的代码,就像只是一个附加的更新一样。
但是,即使你没有打算使用Lodash,我也希望这篇文章能给你带来一点启发:当你发现你的应用中的瓶颈时,不要在jsperf.com中try/fail的来优化它,而是起身,冲一杯咖啡,然后开始考虑一下算法。在这里创新的确很重要,但是良好的数学背景不会有害(推荐书目),祝你好运!