wall-wxk / the-road-to-lodash Goto Github PK

View Code? Open in Web Editor NEW

1.0 2.0 0.0 116 KB

深入解读Lodash源码

License: Other

JavaScript 100.00%

lodash-analysis

the-road-to-lodash's Introduction

the-road-to-lodash

—— 该Repo用于记录解读Lodash源码的过程

如果这个Repo让您有所收获，请点击右上角的「Star」支持下我
如果您想持续关注最新文章，请点击右上角的「Watch」订阅

Lodash version

4.17.5

Article

License

CC-BY-NC-SA 3.0

the-road-to-lodash's People

Contributors

Stargazers

Watchers

the-road-to-lodash's Issues

前言

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），取出符合条件的数据：

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

然后，执行take方法，提取前3个数据。

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

总共遍历的次数为：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完整源码：
https://github.com/wall-wxk/blogDemo/blob/master/lodash/lazy.js

模块化的基础——IIFE

IIFE（Immediately Invoked Function Expression），中文一般翻译为匿名立即执行函数

IIFE详解

构成

IIFE包含两部分。
第一部分是一个匿名函数，它包裹在分组操作符()中，拥有独立的词法作用域。
第二部分是再一次使用分组操作符()，创建一个立即执行函数表达式。Javascript引擎到此将立即执行函数。
大体结构如下所示：

;(function(){
    // code
})();

优点

匿名函数中的变量和方法，不能从外部访问

(function () { 
    var name = 'wall';

    function sayHello(){
        console.log('hello');
    }
})();
// 外部不能访问变量 name 和方法 sayHello
name // undefined
sayHello() // sayHello is not defined

因为匿名函数有自己独立的词法作用域，所以会产生这种现象。

匿名函数中可以正常访问更高词法作用域中的变量和方法

// 浏览器环境下
var name = 'wall';

(function(){
    console.log(name); // 在控制台正常输出`wall`
})();

所以，IIFE并不是双向封闭的一个模块。模块内部可以有自己的私有方法和私有变量，也可以正常使用外部环境的变量和方法。

其他表现形式

!function(){

}();

+function(){

}();

(function(){

}());

本质上，都是先将匿名函数转变为可执行的表达式，然后再用分组操作符执行。

IIFE在lodash中的应用

先上源码：

;(function(){
    // code
}.call(this))();

第一个`;`的作用

工具库的源码，一般都是;开始。为什么要以这个符号作为开始，其实别有深意。

第一个涉及到的是概念：语句

语句：是构成程序的基本单位，一条语句完成某种特定的操作。一般语句以分号;结束。

另一个涉及到的是代码的优化手段：压缩合并
在前端的铁器时代，YaHoo出了一个著名的压缩代码工具——YUI Compressor。它的作用之一，就是将多个js文件源码，合并到一起，变成一个新文件。以此来减少页面加载时的HTTP请求数。
多个js文件压缩，总不免会出现黑天鹅，比如以下这种：

// a.js
function say(){
    // code
}

// b.js
(function(){
    // code
})();

// a.js和b.js合并成c.js
// c.js
function say(){
    // code
}(function(){
    // code
})();

JavaScript引擎，解析c.js文件时，误将say方法进行执行，导致不可思议的事情发生。
而加上分号之后，则可以杜绝这种情况。

call的作用

call的使用，是为了显式指定当前匿名函数的上下文（context），由引用该工具库的环境所决定。

function Foo(){
    (function(){
        console.log(this);  //Foo
    }).call(this);

    (function(){
        console.log(this); //undefined in strict or global
    })();
}

var test = new Foo;

参考

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.