博客 / 詳情

返回

lodash的lazyValue(惰性求值)

前言

lodash受歡迎的一個原因，是其優異的計算性能。而其性能能有這麼突出的表現，很大部分就來源於其使用的算法——惰性求值。
本文將講述lodash源碼中，惰性求值的原理和實現。
個人理解

這個惰性求值使用了js克隆了對象進行操作，在性能上沒直接操作那麼快，但是優化了維護，類似於真實DOM與虛擬DOM，直接操作真實DOM更快，但是虛擬DOM能提供看得過去的性能的情況下給出更好的維護

一、惰性求值的原理分析

惰性求值（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。
執行的示例圖如下：
img

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次，就把結果拿到。
執行的示例圖如下：
img

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完整源碼：

lodash , Javascript
user avatar
0 位用戶收藏了這個故事！

發佈 評論

Some HTML is okay.