乐趣区

关于javascript:lodash的lazyValue惰性求值

jiezi

前言

lodash 受欢迎的一个起因，是其优异的计算性能。而其性能能有这么突出的体现，很大部分就来源于其应用的算法——惰性求值。
本文将讲述 lodash 源码中，惰性求值的原理和实现。

一、惰性求值的原理剖析

惰性求值（Lazy Evaluation），又译为惰性计算、懈怠求值，也称为传需要调用（call-by-need），是计算机编程中的一个概念，它的目标是要最小化计算机要做的工作。
惰性求值中的参数直到须要时才会进行计算。这种程序实际上是从开端开始反向执行的。它会判断本人须要返回什么，并持续向后执行来确定要这样做须要哪些值。

以下是 How to Speed Up Lo-Dash ×100? Introducing Lazy Evaluation.（如何晋升 Lo-Dash 百倍算力？惰性计算的简介）文中的示例，形象地展现惰性求值。

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();

程序的目标，是对数据集 gems 进行筛选，选出 3 个 price 小于 10 的数据。

1.1 个别的做法

如果抛开 lodash 这个工具库，让你用一般的形式实现 var chosen = _(gems).filter(priceLt(10)).take(3); 那么，能够用以下形式：_(gems)拿到数据集，缓存起来。再执行 filter 办法，遍历 gems 数组（长度为 10），取出符合条件的数据：

而后，执行 take 办法，提取前 3 个数据。

[{ name: 'Sunstone', price: 4},
   {name: 'Sugilite', price: 7},
   {name: 'Diopside', price: 3},
   {name: 'Dioptase', price: 2}
]

总共遍历的次数为：10+3。
执行的示例图如下：

1.2 惰性求值做法(缓存)

一般的做法存在一个问题：每个办法各做各的事，没有协调起来节约了很多资源。
如果能先把要做的事，用小本本记下来😎，而后等到真正要出数据时，再用起码的次数达到目标，岂不是更好。
惰性计算就是这么做的。
以下是实现的思路：

  • _(gems)拿到数据集，缓存起来
  • 遇到 filter 办法，先记下来
  • 遇到 take 办法，先记下来
  • 遇到 value 办法，阐明机会到了
  • 把小本本拿进去，看下要求：要取出 3 个数，price<10
  • 应用 filter 办法里的判断办法 priceLt 对数据进行一一裁决
[{ name: 'Sunstone', price: 4}, => priceLt 裁决 => 符合要求，通过 => 拿到 1 个
    {name: 'Amethyst', price: 15}, => priceLt 裁决 => 不符合要求
    {name: 'Prehnite', price: 20}, => priceLt 裁决 => 不符合要求
    {name: 'Sugilite', price: 7}, => priceLt 裁决 => 符合要求，通过 => 拿到 2 个
    {name: 'Diopside', price: 3}, => priceLt 裁决 => 符合要求，通过 => 拿到 3 个 => 够了，出工！{name: 'Feldspar', price: 13},
    {name: 'Dioptase', price: 2},
    {name: 'Sapphire', price: 20}
]

如上所示，一共只执行了 5 次，就把后果拿到。
执行的示例图如下：

1.3 小结

从下面的例子能够失去惰性计算的特点：

  • 提早计算，把要做的计算先缓存，不执行
  • 数据管道，一一数据通过“裁决”办法，在这个相似安检的过程中，进行过关的操作，最初只留下符合要求的数据
  • 触发机会，办法缓存，那么就须要一个办法来触发执行。lodash 就是应用 value 办法，告诉真正开始计算

二、惰性求值的实现

根据上述的特点，我将 lodash 的惰性求值实现进行抽离为以下几个局部：

2.1 实现提早计算的缓存

实现_(gems)。我这里为了语义明确，采纳 lazy(gems)代替。

var MAX_ARRAY_LENGTH = 4294967295; // 最大的数组长度

// 缓存数据构造体
function LazyWrapper(value){
    this.__wrapped__ = value;
    this.__iteratees__ = [];
    this.__takeCount__ = MAX_ARRAY_LENGTH;
}

// 惰性求值的入口
function lazy(value){return new LazyWrapper(value);
}
  • this.__wrapped__ 缓存数据
  • this.__iteratees__ 缓存数据管道中进行“裁决”的办法
  • this.__takeCount__ 记录须要拿的符合要求的数据集个数

这样，一个根本的构造就实现了。

2.2 实现 filter 办法

var LAZY_FILTER_FLAG = 1; // filter 办法的标记

// 依据 筛选办法 iteratee 筛选数据
function filter(iteratee){
    this.__iteratees__.push({
        'iteratee': iteratee,
        'type': LAZY_FILTER_FLAG
    });
    return this;
}

// 绑定办法到原型链上
LazyWrapper.prototype.filter = filter;

filter办法，将裁决办法 iteratee 缓存起来。这里有一个重要的点，就是须要记录 iteratee 的类型 type。
因为在 lodash 中, 还有 map 等筛选数据的办法，也是会传入一个裁决办法 iteratee。因为filter 办法和 map 办法筛选形式不同，所以要用 type 进行标记。
这里还有一个技巧：

(function(){
    // 公有办法
    function filter(iteratee){/* code */}

    // 绑定办法到原型链上
    LazyWrapper.prototype.filter = filter;
})();

原型上的办法，先用一般的函数申明，而后再绑定到原型上。如果工具外部须要应用 filter，则应用申明好的公有办法。
这样的益处是，内部如果扭转 LazyWrapper.prototype.filter，对工具外部，是没有任何影响的。

2.3 实现 take 办法

// 截取 n 个数据
function take(n){
    this.__takeCount__ = n;
    return this;
};

LazyWrapper.prototype.take = take;

2.4 实现 value 办法

// 惰性求值
function lazyValue(){
    var array = this.__wrapped__;
    var length = array.length;
    var resIndex = 0;
    var takeCount = this.__takeCount__;
    var iteratees = this.__iteratees__;
    var iterLength = iteratees.length;
    var index = -1;
    var dir = 1;
    var result = [];

    // 标签语句
    outer:
    while(length-- && resIndex < takeCount){
        // 外层循环待处理的数组
        index += dir;

        var iterIndex = -1;
        var value = array[index];

        while(++iterIndex < iterLength){
            // 内层循环解决链上的办法
            var data = iteratees[iterIndex];
            var iteratee = data.iteratee;
            var type = data.type;
            var computed = iteratee(value);

            // 解决数据不符合要求的状况
            if(!computed){if(type == LAZY_FILTER_FLAG){continue outer;}else{break outer;}
            }
        }

        // 通过内层循环，符合要求的数据
        result[resIndex++] = value;
    }

    return result;
}

LazyWrapper.prototype.value = lazyValue;

这里的一个重点就是：标签语句

outer:
while(length-- && resIndex < takeCount){
    // 外层循环待处理的数组
    index += dir;

    var iterIndex = -1;
    var value = array[index];

    while(++iterIndex < iterLength){
        // 内层循环解决链上的办法
        var data = iteratees[iterIndex];
        var iteratee = data.iteratee;
        var type = data.type;
        var computed = iteratee(value);

        // 解决数据不符合要求的状况
        if(!computed){if(type == LAZY_FILTER_FLAG){continue outer;}else{break outer;}
        }
    }

    // 通过内层循环，符合要求的数据
    result[resIndex++] = value;
}

以后办法的数据管道实现，其实就是内层的 while 循环。通过取出缓存在 iteratees 中的裁决办法取出，对以后数据 value 进行裁决。
如果裁决后果是不合乎，也即为 false。那么这个时候，就没必要用后续的裁决办法进行判断了。而是应该跳出以后循环。
而如果用 break 跳出内层循环后，外层循环中的 result[resIndex++] = value; 还是会被执行，这是咱们不心愿看到的。
应该一次性跳出内外两层循环，并且持续外层循环，才是正确的。
标签语句，刚好能够满足这个要求。

2.5 小检测

var testArr = [1, 19, 30, 2, 12, 5, 28, 4];

lazy(testArr)
    .filter(function(x){console.log('check x='+x);
        return x < 10
    })
    .take(2)
    .value();

// 输入如下：check x=1
check x=19
check x=30
check x=2

// 失去后果：[1, 2]

2.6 小结

整个惰性求值的实现，重点还是在数据管道这块。以及，标签语句在这里的妙用。其实实现的形式，不只以后这种。然而，要点还是后面讲到的三个。把握精华，变通就很容易了。

结语

惰性求值，是我在浏览 lodash 源码中，发现的最大闪光点。
当初对惰性求值不甚了解，想看下 javascript 的实现，但网上也只找到上文提到的一篇文献。
那剩下的抉择，就是对 lodash 进行剖离剖析。也因为这，才有本文的诞生。
心愿这篇文章能对你有所帮忙。如果能够的话，给个 star 😃

最初，附上本文实现的简易版 lazy.js 残缺源码：

退出移动版