读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 条评论
登录 后参与评论

相关文章

来自专栏技术沉淀

Python: 函数式编程

1534
来自专栏SeanCheney的专栏

《Pandas Cookbook》第03章 数据分析入门1. 规划数据分析路线2. 改变数据类型,降低内存消耗3. 从最大中选择最小4. 通过排序选取每组的最大值5. 用sort_values复现nl

1212
来自专栏章鱼的慢慢技术路

蓝桥杯题库基础练习:进制转换

1804
来自专栏Java 源码分析

排序算法

选择排序: ​ 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。 ​ 但是这个算法的复杂...

3626
来自专栏Aloys的开发之路

华为面试题——一道关于指针方面的编程题(C/C++)

    int A[nSize],其中隐藏着若干0,其余非0整数,写一个函数int Func(int* A, int nSize),使A把0移至后面,非0整数...

2448
来自专栏人工智能LeadAI

查找排序数组的最小值(js)

在由小到大已排序的未知数组中,以某个元素为支点旋转(好比将序列沿着前后顺序围成环移动)得到了一个数组,请找出该数组的最小值。比如倘若原数组(对我们而言,并不知道...

1434
来自专栏武培轩的专栏

排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 1 移动有序区的元素,效率不高,下面我们来介绍一种新的插入排序算法...

3274
来自专栏C语言及其他语言

数组

1、 一维数组的定义和使用 通过对前面知识的学习,我们已经知道如何定义和使用一个一个的各种变量,但总有不够用的时候。举个例子,我要记录一个班32个同学C语...

3898
来自专栏数据结构与算法

BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

可以证明,对于\(m\)个仅有一个元素,权值范围在\([1, n]\)的线段树合并的复杂度为\(mlogn\)

632
来自专栏简书专栏

Numpy入门2

标题中的英文首字母大写比较规范,但在python实际使用中均为小写。 2018年7月26日笔记

1123

扫码关注云+社区