本文从应用频率和实用性顺次递加的程序来聊一聊几个Lodash数组类工具函数。对于大多数函数本文不会给出Lodash源码的残缺实现，而更多侧重于实现思路的探讨。
本文共11371字，浏览实现大概须要23分钟。
扁平化(flatten)
用法
flatten这个函数十分实用，面试的时候大家也很喜爱问。先来看下用法, 对于不同深度的嵌套数组Lodash提供了3种调用形式:
// 开展所有的嵌套
_.flattenDeep([1, [2, [3, [4]], 5]]) // [1, 2, 3, 4, 5]
// 开展数组元素最外一层的嵌套
_.flattenDepth([1, [2, [3, [4]], 5]], 1) // [1, 2, [3, [4]], 5]
// 等同于flattenDepth(, 1)，开展元素最外一层的嵌套
_.flatten([1, [2, [3, [4]], 5]]) // [1, 2, [3, [4]], 5]不难看出其余两种调用形式都是由flattenDepth派生进去的, flattenDeep相当于第二个参数传入了无穷大，flatten相当于第二个参数传入1。
实现思路
那么问题来了，这个能够指定开展深度的flattenDepth函数怎么实现呢?
一个简略的思路是: 咱们能够利用开展语法(Spread syntax)/遍历赋值来开展单层的数组, 例如:
const a = [1];
const b = [
...a, 2, 3,
];那么递归地调用单层开展, 咱们天然就能够实现多层的数组开展了。
Lodash的实现形式
在Lodash中这个函数叫baseFlatten, 各位须要对这个函数留点印象，本文前面探讨汇合操作的时候还会看到。
// 保留predicate参数为本文前面几个函数服务
function baseFlatten(array, depth, predicate = Array.isArray, result = []) {
if (array == null) {
return result
}
for (const value of array) {
if (depth > 0 && predicate(value)) {
if (depth > 1) {
// 递归调用, 深度-1
// Recursively flatten arrays (susceptible to call stack limits).
baseFlatten(value, depth - 1, predicate, result)
} else {
// 未达到指定深度开展以后一层
result.push(...value)
}
} else {
// 个别条件
result[result.length] = value
}
}
return result
}典型的迭代+递归函数，迭代时一直将非数组元素推入result实现扁平化。对于指定深度的调用，超出深度的只开展以后一层, 否则深度递加。
另类的实现形式
另外数组扁平化还有一种比拟简短的实现形式, 利用toString()或join()将数组转为字符串, 而后将失去的字符串用split()函数宰割。不过这种形式有个比拟大的问题在于会间接疏忽数组中的null和undefined元素, 且失去的数组是字符串数组，其余根底类型(如布尔值，数字)须要手动转换。
这种写法运行效率与递归差异不大，在特定场景也能够有其应用价值。
[1, [2, [3, [4]], 5]].join().split(',')
// or
[1, [2, [3, [4]], 5]].toString().split(',')去重(uniq)
用法
数组去重也十分的实用，Lodash为不同的数据类型提供了两种调用形式:
_.uniq([2, 1, 2]) // [2, 1]
_.uniqWith([{ 'x': 1, 'y': 2 }, { 'x': 2, 'y': 1 }, { 'x': 1, 'y': 2 }], _.isEqual) // [{ 'x': 1, 'y': 2 }, { 'x': 2, 'y': 1 }]实现思路
数据去重有泛滥的实现思路, 其中流传水平最广的当属利用Set数据结构性质进行去重的实现。
其余的都是对数组进行单次遍历，而后结构新数组或者过滤掉反复元素。
不过有须要留神的点: 如何解决NaN的相等性判断(NaN !== NaN), 延长一下就是如何管制元素相等性判断策略(例如如何能传入一个函数能使得认为[1, 2, 3]和[1, 2, 3]是相等的)。
援用下MDN上的说法, ES2015中有四种相等算法：
- 形象（非严格）相等比拟 (==)
- 严格相等比拟 (===): 用于
Array.prototype.indexOf,Array.prototype.lastIndexOf - 同值零: 用于 TypedArray 和 ArrayBuffer 构造函数、以及Map和Set操作, 并将用于 ES2016/ES7 中的
String.prototype.includes - 同值(Object.is): 用于所有其余中央
实现形式一(Set)
利用Set数据结构性质进行去重最为简洁且大数据量下效率最高:
// 数组转为set后转回数组, 无奈辨别±0
const uniq = (arr) => [...new Set(arr)];须要留神的是Set中的同值零(SameValueZero)相等性判断认为NaN之间，±0之间都是相等的, 因而无奈辨别±0，且无奈传入相等性判断策略。
实现形式二(单次遍历结构新数组)
单次遍历并结构新数组, 空间复杂度O(N)。
须要留神的是NaN的判断，Array.prototype.indexOf应用的是严格相等性判断策略, 无奈正确失去NaN元素的索引。例如:
[1, NaN, 2].indexOf(NaN) // -1于是咱们须要应用Array.prototype.includes的同值零相等性判断策略进行判断:
function unique(array) {
const result = [];
for (const value of array) {
// 同样的, 同值零相等性判断策略无奈辨别±0
if (!result.includes(value)) {
result[result.length] = value;
}
}
return result;
}更进一步，咱们能够实现一个includesWith函数来手动传入相等判断策略:
function includesWith(array, target, comparator) {
if (array == null) return false;
for (const value of array) {
if (comparator(target, value)) return true;
}
return false;
}function unique(array, comparator) {
const result = [];
for (const value of array) {
if (!includesWith(result, value, comparator)) {
result[result.length] = value;
}
}
return result;
}
// 传入同值零相等性判断策略, 能够辨别±0
unique([+0, 1, NaN, NaN, -0, 0], Object.is) // [0, 1, NaN, -0]
// 传入形状相等性判断策略
unique([
[1, 2, 3], {},
[1, 2, 3], {},
], _.isEqual) // [[1, 2, 3], {}]实现形式三(单次遍历过滤反复元素)
单次遍历并过滤反复元素的思路有两种实现形式, 一种是利用哈希表过滤存储遍历过的元素，空间复杂度O(N):
function unique(arr) {
const seen = new Map()
// 遍历时增加至哈希表, 跟Set一样无奈辨别±0
return arr.filter((a) => !seen.has(a) && seen.set(a, 1))
}对于Map咱们尽管不能管制其相等性判断策略，然而咱们能够管制其键值生成策略。例如咱们能够粗犷地利用JSON.stringify来实现一个简陋的”形状”相等性键值生成策略:
function unique(array) {
const seen = new Map()
return array.filter((item) => {
// 如果你须要将根本类型及其包装对象(如`String(1)`与`"1"`)视为同值，那么也能够将其中的`typeof`去掉
const key = typeof item + JSON.stringify(item)
return !seen.has(key) && seen.set(key, 1)
})
}另一种形式是利用Array.prototype.findIndex的性质，空间复杂度O(1):
function unique(array) {
return array.filter((item, index) => {
// 存在反复元素时，findIndex的后果永远是第一个匹配到的元素索引
return array.findIndex(e => Object.is(e, item)) === index; // 利用同值相等性判断解决NaN
});
}Lodash的实现形式
因为IE8及以下不存在Array.prototype.indexOf函数，Lodash抉择应用两层嵌套循环来代替Array.prototype.indexOf:
const LARGE_ARRAY_SIZE = 200
function baseUniq(array, comparator) {
let index = -1
const { length } = array
const result = []
// 超过200应用Set去重
if (length >= LARGE_ARRAY_SIZE && typeof Set !== 'undefined') {
return [...new Set(array)]
}
outer:
while (++index < length) {
let value = array[index]
// Q: 什么值本身不等于本身?
if (value === value) {
let seenIndex = result.length
// 等价于indexOf
while (seenIndex--) {
if (result[seenIndex] === value) {
continue outer
}
}
result.push(value)
// Q: 能够用indexOf吗?
} else if (!includesWith(result, value, comparator)) {
result.push(value)
}
}
return result
}求并集(union)
下文的三个函数是汇合的三个外围操作，对于集合论一图胜千言，我就不画了放个网图。
用法
以同值零相等性判断策略合并数组, Lodash同样为不同的数据类型提供了两种调用形式:
_.union([2, 3], [1, 2]) // [2, 3, 1]
_.union([0], [-0]) // [0]
_.union([1, [2]], [1, [2]]) // [1, [2], [2]]
// 形状相等性判断
_.unionWith([1, [2]], [1, [2]], _.isEqual) // [1, [2]]实现思路
思路很简略，就是将传入的数组开展一层到同一数组后去重。
那不就是利用flatten和unique吗?
是的, Lodash也就是这样实现union函数的。
Lodash的实现形式
上面只给出了Lodah的实现形式，各位能够尝试组合上文中的各种unique与flatten实现。
function union(...arrays) {
// 第三个参数不再是默认的Array.isArray
return baseUniq(baseFlatten(arrays, 1, isArrayLikeObject))
}
function isArrayLikeObject(value) {
return isObjectLike(value) && isLength(value.length)
}
// 非null对象
function isObjectLike(value) {
return typeof value === 'object' && value !== null
}
// 小于2的53次幂的非负整数
function isLength(value) {
return typeof value === 'number' &&
value > -1 && value % 1 == 0 && value <= Number.MAX_SAFE_INTEGER
}求交加(intersection)
用法
求汇合中的共有局部，Lodash同样为不同的数据类型提供了两种调用形式:
intersection([2, 1], [2, 3]) // [2]
intersection([2, 3, [1]], [2, [1]]) // [2]
// 形状相等性判断
_.intersectionWith([2, 3, [1]], [2, [1]], _.isEqual) // [2, [1]]实现思路
汇合中的共有局部，那么咱们只须要遍历一个汇合即可，而后构建新数组/过滤掉其余汇合不存在的元素
函数式实现形式
const intersection = (a, b) => a.filter(x => b.includes(x))
// 还记得上文中的includesWith函数吗?
const intersectionWith = (a, b, comparator = Object.is) => a.filter(x => includesWith(b, x, comparator))求差集(difference)
用法
求汇合中的差别局部，Lodash同样为不同的数据类型提供了两种调用形式:
difference([2, 1], [2, 3]) // 失去[1]
difference([2, 1], [2, 3, 1], [2]) // 失去[]
difference([2, 1, 4, 4], [2, 3, 1]) // 失去[4, 4]须要留神的是差集是存在单个作用主体的，difference的语义是”汇合A绝对与其余汇合的差集”, 所以失去的值必然是传入的第一个参数数组(即汇合A)中的元素，如果汇合A是其余汇合的子集，那么失去的值必然为空数组，了解上有艰难的无妨画图看看。
实现思路
存在单个作用主体的差别局部，那么咱们只须要遍历一个汇合即可，而后构建新数组/过滤掉其余汇合存在的元素
函数式实现形式
const difference = (a, b) => a.filter(x => !b.includes(x))
// 形状相等性判断
const differenceWith = (a, b, comparator = Object.is) => a.filter(x => !includesWith(b, x, comparator))分块(chunk)
用法
就是将数组等分为若干份, 最初一份有余的不进行补齐:
chunk(['a', 'b', 'c', 'd'], 2) // [['a', 'b'], ['c', 'd']]
chunk(['a', 'b', 'c', 'd'], 3) // [['a', 'b', 'c'], ['d']]实现思路
看到执行函数的后果就不难想到它是如何实现的, 遍历时将数组切片(slice)失去的若干份新数组合并即可。
另外，如果我不想应用循环遍历，想用函数式编程的写法用Array.prototype.map与Array.prototype.reduce该怎么做呢?
首先咱们要结构出一个长度等于Math.ceil(arr.length / size)的新数组对象作为map/reduce的调用对象, 而后进行返回数组切片即可。
不过这里有个问题须要留神: 调用Array构造函数只会给这个新数组对象设置length属性，而其索引属性并不会被主动设置。
const a = new Array(3)
// 不存在索引属性
a.hasOwnProperty("0") // false
a.hasOwnProperty(1) // false那么问题来了，如何如何设置新数组对象的索引属性呢?
读者能够先本人思考下，答案在下文中揭晓。
实现形式
function chunk(array, size = 1) {
// toInteger做的就是舍弃小数
size = Math.max(toInteger(size), 0)
const length = array == null ? 0 : array.length
if (!length || size < 1) {
return []
}
let index = 0
let resIndex = 0
const result = new Array(Math.ceil(length / size))
while (index < length) {
// Array.prototype.slice须要解决一些非数组类型元素，小数据规模下性能较差
result[resIndex++] = slice(array, index, (index += size))
}
return result
}函数式实现形式
上文说到调用Array构造函数生成的数组对象不存在索引属性，因而咱们在须要用到索引属性时须要填充数组对象。
一共有三种形式: 数组开展语法, Array.prototype.fill, Array.from。
// 利用开展语法
const chunk = (arr, size) =>
[...Array(Math.ceil(arr.length / size))].map((e, i) => arr.slice(i * size, i * size + size));
// 利用`Array.prototype.fill`
const chunk = (arr, size) =>
Array(Math.ceil(arr.length / size)).fill(0).map((e, i) => arr.slice(i * size, i * size + size));
// 利用`Array.from`的回调函数
const chunk = (arr, size) =>
Array.from({ length: Math.ceil(arr.length / size) }, (e, i) => arr.slice(i * size, i * size + size));
// 利用`Array.from`
const chunk = (arr, size) =>
Array.from({ length: Math.ceil(arr.length / size) }).map((e, i) => arr.slice(i * size, i * size + size));
// 利用`Array.prototype.reduce`, 索引等于size倍数时将以后切片合并进累计器(accumulator)
const chunk = (arr, size) =>
arr.reduce((a, c, i) => !(i % size) ? a.concat([arr.slice(i, i + size)]) : a, []);数组切片(slice)
依据索引失去更小规模的数组:
用法
_.slice([1, 2, 3, 4], 2) // [3, 4]
_.slice([1, 2, 3, 4], 1, 2) // [2]
_.slice([1, 2, 3, 4], -2) // [3, 4]
// 等于 _.slice([1, 2, 3, 4], 4 - 2, 3)
_.slice([1, 2, 3, 4], -2, 3) // [3]
// 等于 _.slice([1, 2, 3, 4], 4 - 3, 3)
_.slice([1, 2, 3, 4], -3, -1) // [2, 3]实现思路
对于数组切片咱们须要记住的是，区间蕴含start不蕴含end, 正数索引等同于数组长度加该数, start绝对值大于数组长度时等同于0, end绝对值大于数组长度时等同于数组长度。
这些策略就是Lodash乃至V8实现数组切片的思路。
Lodash的实现形式
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绝对值大于数组长度时等同于0
start = -start > length ? 0 : (length + start)
}
// end绝对值大于数组长度时等同于数组长度
end = end > length ? length : end
// 正数索引等同于数组长度加该数
if (end < 0) {
end += length
}
length = start > end ? 0 : ((end - start) >>> 0)
// toInt32
start >>>= 0
let index = -1
const result = new Array(length)
while (++index < length) {
result[index] = array[index + start]
}
return result
}一个比拟乏味的点是这里的位运算: 无符号右移(end - start) >>> 0, 它起到的作用是toInt32(因为位运算是32位的), 也就是小数取整。
那么问题来了, 为什么不必封装好的toInteger函数呢?
集体了解一是就JS运行时而言，咱们没有32位以上的数组切片需要；二是作为一个根底专用函数，位运算的运行效率显然更高。
好了，以上就是本文对于Lodash数组类工具函数的全部内容。行文不免有疏漏和谬误，还望读者批评指正。
发表回复