New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

JavaScript 数组展开以及 underscore 重要的内部方法 flatten 详解 #10

Open
hanzichi opened this Issue Jun 11, 2016 · 3 comments

Comments

Projects
None yet
4 participants
@hanzichi
Owner

hanzichi commented Jun 11, 2016

Why underscore

(觉得这一段眼熟的童鞋可以直接跳到正文了...)

最近开始看 underscore.js 源码,并将 underscore.js 源码解读 放在了我的 2016 计划中。

阅读一些著名框架类库的源码,就好像和一个个大师对话,你会学到很多。为什么是 underscore?最主要的原因是 underscore 简短精悍(约 1.5k 行),封装了 100 多个有用的方法,耦合度低,非常适合逐个方法阅读,适合楼主这样的 JavaScript 初学者。从中,你不仅可以学到用 void 0 代替 undefined 避免 undefined 被重写等一些小技巧 ,也可以学到变量类型判断、函数节流&函数去抖等常用的方法,还可以学到很多浏览器兼容的 hack,更可以学到作者的整体设计思路以及 API 设计的原理(向后兼容)。

之后楼主会写一系列的文章跟大家分享在源码阅读中学习到的知识。

欢迎围观~ (如果有兴趣,欢迎 star & watch~)您的关注是楼主继续写作的动力

flatten

端午休息三天,睡了两天,是该有点产出了。

今天要讲的是数组展开以及和数组展开息息相关的一个重要的内部方法 flatten。

什么是数组展开?简单的说就是将嵌套的数组 "铺平",还是举几个简单的例子吧。

[[[1, 2], [1, 2, 3]], [1, 2]] => [1, 2, 1, 2, 3, 1, 2]
[[[1, 2], [1, 2, 3]], [1, 2]] => [[1, 2], [1, 2, 3], 1, 2]

以上两种都是数组展开,第一种我们认为是深度展开,即打破所有嵌套数组,将元素提取出来放入一个数组中;第二种只展开了一层,即只把数组内嵌套的一层数组展开,而没有递归展开下去。

我们首先来看看 flatten 方法的调用形式。

var flatten = function(input, shallow, strict, startIndex) {
  // ...
};

第一个参数 input 即为需要展开的数组,所以 flatten 方法中传入的第一个参数肯定是数组(或者 arguments);第二个参数 shallow 是个布尔值,如果为 false,则表示数组是深度展开,如果为 true 则表示只展开一层;第四个参数表示 input 展开的起始位置,即从 input 数组中第几个元素开始展开。

var ans = flatten([[1, 2], [3, 4]], false, false, 1);
console.log(ans); // => [3, 4]

从第 1 项开始展开数组,即忽略了数组的第 0 项([1, 2])。

以上三个参数还是比较容易理解的,相对来说费劲的是第三个参数 strict。strict 也是个布尔值,当 shallow 为 true 并且 strict 也为 true 时,能过滤 input 参数元素中的非数组元素。好难理解啊!我们举个简单的例子。

var ans = flatten([5, 6, [1, 2], [3, 4]], true, true);
console.log(ans); // => [1, 2, 3, 4]

5 和 6 是 input 参数中的非数组元素,直接过滤掉了。如果 strict 为 true 并且 shallow 为 false,那么调用 flatten 方法的结果只能是 []。所以我们会看到源码里如果 strict 为 true,那么 shallow 也一定是 true。

直接来看源码,加了非常多的注释。

var flatten = function(input, shallow, strict, startIndex) {
  // output 数组保存结果
  // 即 flatten 方法返回数据
  // idx 为 output 的累计数组下标
  var output = [], idx = 0;

  // 根据 startIndex 变量确定需要展开的起始位置
  for (var i = startIndex || 0, length = getLength(input); i < length; i++) {
    var value = input[i];
    // 数组 或者 arguments
    if (isArrayLike(value) && (_.isArray(value) || _.isArguments(value))) {
      // flatten current level of array or arguments object
      // (!shallow === true) => (shallow === false)
      // 则表示需深度展开
      // 继续递归展开
      if (!shallow) 
        // flatten 方法返回数组
        // 将上面定义的 value 重新赋值
        value = flatten(value, shallow, strict);

      // 递归展开到最后一层(没有嵌套的数组了)
      // 或者 (shallow === true) => 只展开一层
      // value 值肯定是一个数组
      var j = 0, len = value.length;

      // 这一步貌似没有必要
      // 毕竟 JavaScript 的数组会自动扩充
      // 但是这样写,感觉比较好,对于元素的 push 过程有个比较清晰的认识
      output.length += len;

      // 将 value 数组的元素添加到 output 数组中
      while (j < len) {
        output[idx++] = value[j++];
      }
    } else if (!strict) { 
      // (!strict === true) => (strict === false)
      // 如果是深度展开,即 shallow 参数为 false
      // 那么当最后 value 不是数组,是基本类型时
      // 肯定会走到这个 else-if 判断中
      // 而如果此时 strict 为 true,则不能跳到这个分支内部
      // 所以 shallow === false 如果和 strict === true 搭配
      // 调用 flatten 方法得到的结果永远是空数组 []
      output[idx++] = value;
    }
  }

  return output;
};

总的来说,就是持续递归调用 flatten,直到不能展开为止。给出 flatten 方法的实现源码位置 https://github.com/hanzichi/underscore-analysis/blob/master/underscore-1.8.3.js/src/underscore-1.8.3.js#L489-L507。

接着我们来看看源码中有用到这个内部方法的 API。

首先是 _.flatten 方法,非常简单,用了 flatten 的前三个参数。

_.flatten = function(array, shallow) {
  // array => 需要展开的数组
  // shallow => 是否只展开一层
  // false 为 flatten 方法 strict 变量
  return flatten(array, shallow, false);
};

前面说了,strict 为 true 只和 shallow 为 true 一起使用,所以没有特殊情况的话 strict 默认为 false。

_.union 方法同样用到了 flatten,这个方法的作用是传入多个数组,然后对数组元素去重。

var ans = _.union([[1]], [1, 2], 3, 4);
console.log(ans); // => [[1], 1, 2]

首先并不需要对数组深度展开,其次 _.union 传入的是数组,对于非数组元素可以直接忽略。这两点直接对应了 shallow 参数和 strict 参数均为 true(都不用做容错处理了)。对于一个数组的去重,最后调用 _.unique 即可。

_.union = function() {
  // 首先用 flatten 方法将传入的数组展开成一个数组
  // 然后就可以愉快地调用 _.uniq 方法了
  // 假设 _.union([1, 2, 3], [101, 2, 1, 10], [2, 1]);
  // arguments 为 [[1, 2, 3], [101, 2, 1, 10], [2, 1]]
  // shallow 参数为 true,展开一层
  // 结果为 [1, 2, 3, 101, 2, 1, 10, 2, 1]
  // 然后对其去重
  return _.uniq(flatten(arguments, true, true));
};

而 _.difference,_.pick,_.omit 方法,大家可以自己进源码去看,都大同小异,没什么特别要注意的点。(注意下 startIndex 参数即可)

对于内部方法 flatten,我要总结的是,可能某个内部方法会被多个 API 调用,如何设计地合理,优雅,如何兼顾到各种情况,真的需要强大的实践以及代码能力,这点还需要日后多加摸索。

@hanzichi hanzichi changed the title from JavaScript 数组展开以及重要的内部方法 flatten to JavaScript 数组展开以及 underscore 重要的内部方法 flatten Jun 11, 2016

@hanzichi hanzichi changed the title from JavaScript 数组展开以及 underscore 重要的内部方法 flatten to JavaScript 数组展开以及 underscore 重要的内部方法 flatten 详解 Jun 11, 2016

@yeahsgz

This comment has been minimized.

yeahsgz commented Nov 7, 2016

知道数组的长度,用下标赋值比push要快;但是数组的长度更改耗时比较大。在chrome上小测了一下是这样子

@luoliqiang luoliqiang referenced this issue Feb 9, 2017

Open

文章1 #1

@Arvinzhu

This comment has been minimized.

Arvinzhu commented Sep 19, 2017

  var flatten = function(input, shallow, strict, output) {
    output = output || [];
    var idx = output.length;
    for (var i = 0, length = getLength(input); i < length; i++) {
      var value = input[i];
      if (isArrayLike(value) && (_.isArray(value) || _.isArguments(value))) {
        // Flatten current level of array or arguments object.
        if (shallow) {
          var j = 0, len = value.length;
          while (j < len) output[idx++] = value[j++];
        } else {
          flatten(value, shallow, strict, output);
          idx = output.length;
        }
      } else if (!strict) {
        output[idx++] = value;
      }
    }
    return output;
  };

github上面最新的代码发生了一些变化,第四个参数不是startIndex,而是输出数组output。循环初始值i直接就是0。那么这个传入的output,好像没什么意义,传入一个非空数组也并不会处理,不懂这样改有什么意义

@L-Chris

This comment has been minimized.

L-Chris commented Mar 16, 2018

@Arvinzhu 我的想法是
1.首先,去除startIndex,实际应用没有这样的需求
2.output改为参数传入,修改output时就不用寻址到顶部的output,还去除了value重新赋值,效率更高

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment