读lodash源码之从slice看稀疏数组与密集数组

卑鄙是卑鄙者的通行证,高尚是高尚者的墓志铭。 ——北岛《回答》

看北岛就是从这两句诗开始的,高尚者已死,只剩卑鄙者在世间横行。

本文为读 lodash 源码的第一篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

gitbook也会同步仓库的更新,gitbook地址:pocket-lodash

引言

你可能会有点奇怪,原生的 slice 方法基本没有兼容性的问题,为什么 lodash 还要实现一个 slice 方法呢?

这个问题,lodash 的作者已经在 why not the 'baseslice' func use Array.slice(), loop faster than slice? 的 issue 中给出了答案:lodash 的 slice 会将数组当成密集数组对待,原生的 slice 会将数组当成稀疏数组对待。

密集数组VS稀疏数组

我们先来看看犀牛书是怎样定义稀疏数组的:

稀疏数组就是包含从0开始的不连续索引的数组。通常,数组的length属性值代表数组中元素的个数。如果数组是稀疏的,length属性值大于元素的个数。

如果数组是稀疏的,那么这个数组中至少有一个以上的位置不存在元素(包括 undefined )。

例如:

var sparse = new Array(10)
var dense = new Array(10).fill(undefined)

其中 sparselength 为10,但是 sparse 数组中没有元素,是稀疏数组;而 dense 每个位置都是有元素的,虽然每个元素都为undefined,为密集数组 。

那稀疏数组和密集数组有什么区别呢?在 lodash 中最主要考虑的是两者在迭代器中的表现。

稀疏数组在迭代的时候会跳过不存在的元素。

sparse.forEach(function(item){
  console.log(item)
})
dense.forEach(function(item){
  console.log(item)
})

sparse 根本不会调用 console.log 打印任何东西,但是 dense 会打印出10个 undefined

源码总览

当然,除了对待稀疏数组跟原生的 slice 不一致外,其他的规则还是一样的,下面是 lodash 实现 slice 的源码。

function slice(array, start, end) {
  let length = array == null ? 0 : array.length
  if (!length) {
    return []
  }
  start = start == null ? 0 : start
  end = end === undefined ? length : end

  if (start < 0) {
    start = -start > length ? 0 : (length + start)
  }
  end = end > length ? length : end
  if (end < 0) {
    end += length
  }
  length = start > end ? 0 : ((end - start) >>> 0)
  start >>>= 0

  let index = -1
  const result = new Array(length)
  while (++index < length) {
    result[index] = array[index + start]
  }
  return result
}

不传参的情况

let length = array == null ? 0 : array.length
if (!length) {
  return []
}

不传参时,length 默认为0,否则获取数组的长度。注意这里用的是 array == null ,非 array === null ,包含了 undefined 的判断。

所以在不传参调用 lodash 的 slice 时,返回的是空数组,而原生的 slice 没有这种调用方式。

处理start参数

start 参数用来指定截取的开始位置。

先来看下 MDN 对该参数的描述:

如果该参数为负数,则表示从原数组中的倒数第几个元素开始提取。 如果省略,则从索引0开始

start = start == null ? 0 : start

因此这段是处理省略的情况,省略时,默认值为0。

if (start < 0) {
  start = -start > length ? 0 : (length + start)
}

这段是处理负数的情况。

如果负数取反后比数组的长度还要大,即超出了数组的范围,则取值为0,表示从开始的位置截取,否则用 length + start ,即向后倒数。

start >>>= 0

最后,用在 >>> 来确保 start 参数为整数或0。

因为 lodash 的 slice 除了可以处理数组外,也可以处理类数组,因此第一个参数 array 可能为一个对象, length 属性不一定为数字。

处理end参数

end 参数用来指定截取的结束位置。

同样来看下 MDN 对些的描述:

如果该参数为负数,则它表示在原数组中的倒数第几个元素结束制取。 如果end被省略,则slice会一直提取到原数组的末尾。 如果end大于数组长度,slice也会一直提取到原数组末尾。

end = end === undefined ? length : end

这段是处理 end 被省略的情况,省略时,end 默认为为 length,即截取到数组的末尾。

end = end > length ? length : end

这是处理 end 比数组长度大的情况,如果被数组长度大,也会截取到数组的末尾。

if (end < 0) {
  end += length
}

这段是处理负值的情况,如果为负值,则从数组末尾开始向前倒数。

这里没有像 start 一样控制 end 的向前倒数完后是否为负数,因为后面还有一层控制。

获取新数组的长度

length = start > end ? 0 : ((end - start) >>> 0)

新数组的长度计算方式很简单,就是用 edn - start 即可得出。

上面说到,没有控制最终 end 是否为负数的情况。这里用的是 startend 的比较,如果 startend 大,则新数组长度为0,即返回一个空数组。否则用 end - start 来计算。

这里同样用了无符号右移位运算符来确保 length 为正数或0。

截取并返回新数组

let index = -1
const result = new Array(length)
while (++index < length) {
  result[index] = array[index + start]
}
return result

result 为新数组容器。

while 循环,从 start 位置开始,获取原数组的值,依次存入新的数组中。

因为是通过索引取值,如果遇到稀疏数组,对应的索引值上没有元素时,通过数组索引取值返回的是 undefined, 但这并不是说稀疏数组中该位置的值为 undefined

最后将 result 返回。

参考

  1. javascript权威指南(第6版), David Flanagan著,淘宝前端团队译,机械工业出版社
  2. why not the 'baseslice' func use Array.slice(), loop faster than slice?
  3. Array.prototype.slice()
  4. JavaScript: sparse arrays vs. dense arrays
  5. [译]JavaScript中的稀疏数组与密集数组

License

署名-非商业性使用-禁止演绎 4.0 国际 (CC BY-NC-ND 4.0)

作者:对角另一面

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

每周学点大数据 | No.8基础数据结构之线性表

No.8期 基础数据结构之线性表 Mr. 王:为了以后的知识描述方便,这里简单介绍一下数据结构的概念。数据结构是一个广泛存在于计算机科学中的概念。曾经有一位计...

32911
来自专栏微信公众号:Java团长

Java基础09 类数据与类方法

我们一直是为了产生对象而定义类(class)的。对象是具有功能的实体,而类是对象的类型分类。这是面向对象的一个基本概念。

431
来自专栏社区的朋友们

sizeof 知多少? (上)

稍熟悉 C/C++ 的朋友,对于 sizeof 肯定不陌生,通过它我们可以知晓某个类型或者实例的内存大小( 以字节计 ),网上关于这个话题的信息其实挺多的,但是...

1140
来自专栏用户2442861的专栏

从头到尾彻底理解KMP(2014年8月22日版)

作者:July 时间:最初写于2011年12月,2014年7月21日晚10点 全部删除重写成此文,随后的半个多月不断反复改进。

953
来自专栏听雨堂

深入理解字符串和字节数组转换

      前文中,论及字符串和字节数组的转换,虽然能够找到某个代码页,保证转换的可逆,但是在实际处理中,仍然还有一些细节问题需要注意.       最重要的...

1668
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 五、高阶函数

27810
来自专栏老司机的技术博客

人人都能学会的python编程教程7:元祖(tuple)

为什么报错呢?因为元祖的一大特点就是不可更改,字符串和数字也是一样。虽然可以通过变量让它指向不同的字符串、数值或元祖内,但是不能改变数字本身。

4358
来自专栏nummy

Iterables vs. Iterables vs. Generators

容器是用来储存元素的一种数据结构,它支持隶属测试,容器将所有数据保存在内存中,在Python中典型的容器有:

492
来自专栏racaljk

探索C++对象模型

只说C++对象模型在内存中如何分配这是不现实的,所以这里选择VS 2013作为调试环境具体探讨object在内存中分配情况.目录给出了具体要探讨的所有模型,正...

723
来自专栏HTML5学堂

游戏开发 - Math对象相关知识讲解

前几期小编给大家总结了JavaScript的基础知识,为我们后期深入学习JS打下了一定的基础。在后面的几期文章当中我们要来进行JS小游戏的开发,但是开发小游戏的...

27410

扫码关注云+社区