ARTICLE DETAIL

资讯详情

深耕网站视觉设计与运营推广的一线实战洞察。

冴羽 JavaScript 专题:数组扁平化从递归手写到 underscore 源码解读

冴羽 JavaScript 专题:数组扁平化从递归手写到 underscore 源码解读 技术博客文档教程【免费下载链接】Blog冴羽写博客的地方预计写四个系列JavaScript深入系列、JavaScript专题系列、ES6系列、React系列。项目地址https://gitcode.com/GitHub_Trending/blo/Blog点击查看免费下载本篇是冴羽「JavaScript 专题系列」中关于数组扁平化的完整技术指南围绕 articles/专题系列文章/JavaScript专题之数组扁平化.md 展开。文章从扁平化的基本定义出发依次讲解递归、toString、reduce、扩展运算符四种手写实现并深入剖析 underscore 内部flatten函数的shallow、strict、output三个参数设计最终带你读懂_.flatten、_.union、_.difference是如何复用同一个底层函数的。读完本文你将能够独立写出适用于任意嵌套层数的扁平化工具函数并理解 underscore 中一个内部函数服务多个 API的抽象思路。什么是数组扁平化数组的扁平化flatten就是将一个嵌套多层的数组 array嵌套可以是任何层数转换为只有一层的数组。举个例子假设有个名为flatten的函数可以做到数组扁平化效果就会如下var arr [1, [2, [3, 4]]]; console.log(flatten(arr)) // [1, 2, 3, 4]知道了效果是什么样的了我们就可以尝试着去写这个flatten函数了。下面按实现思路的演进给出四种常见写法每种写法都有其适用场景与局限性。方法一递归实现我们最一开始能想到的莫过于循环数组元素如果遍历到的元素还是一个数组就递归调用该方法// 方法 1 var arr [1, [2, [3, 4]]]; function flatten(arr) { var result []; for (var i 0, len arr.length; i len; i) { if (Array.isArray(arr[i])) { result result.concat(flatten(arr[i])) } else { result.push(arr[i]) } } return result; } console.log(flatten(arr))实现要点用Array.isArray判断当前元素是否是数组这是比instanceof更可靠的判断方式跨 iframe 环境下依然准确是数组则递归调用flatten并把返回结果concat到结果数组中不是数组则直接push进结果数组每一层递归都会创建新的result数组最终逐层合并返回。递归写法逻辑最直观、适用范围最广不依赖元素类型是后续所有写法的思想基础。方法二toString split仅限数字数组如果数组的元素都是数字那么我们可以考虑使用toString方法因为[1, [2, [3, 4]]].toString() // 1,2,3,4调用toString方法返回了一个逗号分隔的扁平的字符串这时候我们再split然后转成数字不就可以实现扁平化了吗// 方法2 var arr [1, [2, [3, 4]]]; function flatten(arr) { return arr.toString().split(,).map(function(item){ return item }) } console.log(flatten(arr))然而这种方法使用的场景却非常有限如果数组是[1, 1, 2, 2]的话这种方法就会产生错误的结果。原因在于toString会把字符串元素1原样保留不带引号split后无法区分原始的数字1和字符串1更严重的是如果元素本身就是包含逗号的字符串如a,bsplit会把它拆成多个元素item一元运算符会把1强转回数字1丢失类型信息对于null、undefined、对象等元素结果同样不可控。所以toString方案只适合已知数组内全部为数字的特定场景一般不建议在生产代码中使用。方法三reduce 实现既然是对数组进行处理最终返回一个值我们就可以考虑使用reduce来简化代码// 方法3 var arr [1, [2, [3, 4]]]; function flatten(arr) { return arr.reduce(function(prev, next){ return prev.concat(Array.isArray(next) ? flatten(next) : next) }, []) } console.log(flatten(arr))实现要点以空数组[]作为reduce的初始值即prev遍历每个元素next如果是数组递归调用flatten(next)后concat否则直接concat该元素相比方法一省去了显式的for循环和push代码更简洁。这个写法在本文关联的系列文章《JavaScript专题之递归》中也被作为利用递归解决扁平化问题的典型示例再次提及可见它是递归思想的经典落地。方法四扩展运算符 ...ES6 增加了扩展运算符spread operator用于取出参数对象的所有可遍历属性拷贝到当前对象之中var arr [1, [2, [3, 4]]]; console.log([].concat(...arr)); // [1, 2, [3, 4]]注意看输出结果[].concat(...arr)把arr的第一层元素展开后依次concat因此只扁平了一层——[3, 4]依然保持着内层数组的形态。我们用这种方法只可以扁平一层但是顺着这个方法一直思考我们可以写出这样的方法// 方法4 var arr [1, [2, [3, 4]]]; function flatten(arr) { while (arr.some(item Array.isArray(item))) { arr [].concat(...arr); } return arr; } console.log(flatten(arr))实现要点用Array.prototype.some检测数组中是否还存在数组元素只要存在就用[].concat(...arr)展开一层并重新赋值给arr循环直到数组中不再有任何数组元素为止天然支持任意嵌套层数全程原地迭代、无需递归代码量最小是手写扁平化中最推荐的一版。// 等价于逐层展开的过程 // [1, [2, [3, 4]]] - [1, 2, [3, 4]] - [1, 2, 3, 4]underscore 的内部 flatten 函数那么如何写一个抽象的扁平函数来方便我们的开发呢又到了研究借鉴underscore的时候了。这里直接给出带注释的源码。要注意这里的flatten函数并不是最终的_.flatten为了方便多个 API 进行调用它对外暴露了更多配置项/** * 数组扁平化 * param {Array} input 要处理的数组 * param {boolean} shallow 是否只扁平一层 * param {boolean} strict 是否严格处理元素下面有解释 * param {Array} output 这是为了方便递归而传递的参数 */ function flatten(input, shallow, strict, output) { // 递归使用的时候会用到output output output || []; var idx output.length; for (var i 0, len input.length; i len; i) { var value input[i]; // 如果是数组就进行处理 if (Array.isArray(value)) { // 如果是只扁平一层遍历该数组依此填入 output if (shallow) { var j 0, len value.length; while (j len) output[idx] value[j]; } // 如果是全部扁平就递归传入已经处理的 output递归中接着处理 output else { flatten(value, shallow, strict, output); idx output.length; } } // 不是数组根据 strict 的值判断是跳过不处理还是放入 output else if (!strict){ output[idx] value; } } return output; }三个关键参数shallow / strict / outputinput要处理的数组可能是嵌套数组也可能是arguments之类类数组shallow布尔值true表示只扁平一层false表示递归扁平所有层strict布尔值true表示严格模式——跳过所有非数组元素false表示把非数组元素正常放入结果output递归时复用的结果数组。递归调用时把已经处理好的output传下去内层递归直接向同一个数组追加元素避免每次递归都新建数组、再逐层合并这是与前面方法一每层新建result再concat的关键区别性能更好。strict 到底有什么用解释下strict在代码里我们可以看出当遍历数组元素时如果元素不是数组就会对strict取反的结果进行判断如果设置strict为true就会跳过不进行任何处理这意味着可以过滤非数组的元素。举个例子var arr [1, 2, [3, 4]]; console.log(flatten(arr, true, true)); // [3, 4]那么设置strict到底有什么用呢我们先看下shallow和strict各种值对应的结果shallowstrict行为示例[1, 2, [3, 4]]truefalse正常扁平一层[1, 2, 3, 4]falsefalse正常扁平所有层[1, 2, 3, 4]truetrue去掉非数组元素[3, 4]falsetrue返回一个[][]最后一行的false true组合值得注意因为严格模式下非数组元素被全部跳过而递归扁平所有层又意味着所有数组最终都会被拆成单个元素单个元素不是数组同样被跳过所以结果恒为空数组[]。这个组合在 underscore 中不会被直接调用但理解它可以加深对参数语义的把握。下面我们看看 underscore 中哪些方法调用了flatten这个基本函数。_.flatten首先就是_.flatten_.flatten function(array, shallow) { return flatten(array, shallow, false); };在正常的扁平中我们并不需要去掉非数组元素所以strict固定传false第二个参数shallow由调用方决定是扁平一层还是扁平所有层默认undefined即递归全部扁平。_.union接下来是_.union该函数传入多个数组然后返回传入的数组的并集去重后的合集。举个例子_.union([1, 2, 3], [101, 2, 1, 10], [2, 1]); [1, 2, 3, 101, 10]如果传入的参数并不是数组就会将该参数跳过_.union([1, 2, 3], [101, 2, 1, 10], 4, 5); [1, 2, 3, 101, 10]为了实现这个效果我们可以将传入的所有数组扁平化然后去重。因为_.union只接受数组作为有效参数这时候我们直接设置strict为true就可以跳过传入的非数组元素如上例中的4和5。// 关于 unique 可以查看《JavaScript专题之数组去重》 function unique(array) { return Array.from(new Set(array)); } _.union function() { return unique(flatten(arguments, true, true)); }这里的flatten(arguments, true, true)语义是把arguments视为一个数组其中每个元素都是传入的数组shallow true只扁平一层即把数组的数组变成元素的数组strict true过滤掉非数组的参数最终交给unique去重。去重的详细实现可见系列文章《JavaScript专题之数组去重》。_.difference是不是感觉折腾strict有点用处了我们再看一个_.difference语法为_.difference(array, *others)效果是取出来自array数组并且不存在于多个other数组的元素。跟_.union一样都会排除掉不是数组的元素。举个例子_.difference([1, 2, 3, 4, 5], [5, 2, 10], [4], 3); [1, 3]注意上例中array为[1, 2, 3, 4, 5]其余参数中3不是数组被忽略5、2、4分别出现在others数组中被排除最终只剩1和3。实现方法也很简单扁平others的数组筛选出array中不在扁平化数组中的值function difference(array, ...rest) { rest flatten(rest, true, true); return array.filter(function(item){ return rest.indexOf(item) -1; }) }这里的flatten(rest, true, true)与_.union中的用法一致只扁平一层 严格模式过滤非数组参数。得到扁平的rest后用array.filter配合indexOf剔除存在于rest中的元素即可。仓库源码佐证underscore 本地副本中的真实实现本仓库的 demos/debounce/underscore.js 内置了一份 underscore 源码副本其中包含真实的内部flatten实现可以作为上述讲解的源码级印证内部flatten函数定义位于 demos/debounce/underscore.js#L489-L507注释明确写着 Internal implementation of a recursiveflattenfunction_.flatten的定义位于 demos/debounce/underscore.js#L510-L512与上文展示的flatten(array, shallow, false)完全一致_.union位于 demos/debounce/underscore.js#L551-L553实现为_.uniq(flatten(arguments, true, true))印证了扁平一层 严格过滤 去重的组合_.difference位于 demos/debounce/underscore.js#L573-L578实现为flatten(arguments, true, true, 1)。从源码结构看还有两点值得注意真实副本的签名略有不同仓库副本中的内部函数签名是flatten(input, shallow, strict, startIndex)用startIndex控制从第几个参数开始处理而本文讲解的教学版本用output传递递归结果。两者思路等价教学版本更容易理解递归时如何共享结果数组。这也说明以上实现的细节并不是完全按照 underscore真实细节以源码为准。flatten不止服务三个 API在 demos/debounce/underscore.js#L1030_.pick和 demos/debounce/underscore.js#L1047_.omit中同样以flatten(arguments, false, false, 1)的形式被调用用来把多个键名参数展平成数组。这说明 underscore 把flatten设计成一个高度抽象的底层工具多个公开 API 通过不同的shallow/strict/startIndex组合复用它——这正是抽象扁平函数的价值所在。小结回顾本篇我们从把嵌套数组变成一层数组这一需求出发走完了从朴素实现到源码级抽象的全过程四种手写实现递归通用、直观、toString仅限纯数字数组、不推荐、reduce更简洁的递归、while some 扩展运算符非递归、任意层数、推荐underscore 的内部flatten用shallow控制扁平深度、用strict控制是否过滤非数组元素、用output实现递归共享结果数组四种参数组合的行为各不相同三个复用场景_.flattenstrict false、_.uniontrue, true 去重、_.differencetrue, true filter以及_.pick/_.omit中的键名展平。掌握flatten的内部参数设计本质上就掌握了 underscore 中一个内部函数通过参数组合服务多个 API的抽象方法论这对阅读其他工具库源码、设计自己的工具函数都很有帮助。本文所属的 JavaScript 专题系列还包含防抖、节流、去重、类型判断、深浅拷贝、柯里化、递归、乱序、排序等主题全部文章位于 articles/专题系列文章 目录下可以配合阅读。赞分享技术博客文档教程【免费下载链接】Blog冴羽写博客的地方预计写四个系列JavaScript深入系列、JavaScript专题系列、ES6系列、React系列。项目地址https://gitcode.com/GitHub_Trending/blo/Blog点击查看免费下载相关推荐googleapis 的 BCR 发布实战用 publish-to-bcr.sh 把 Bazel 模块发布到 Bazel Central Registrygoogleapis 的 BCR 发布实战用 publish to bcr.sh 把 Bazel 模块发布到 Bazel Central Registry 导技术博客文档教程冴羽博客GitHub_Trending/blo/BlogJavaScript深入系列源码解读冴羽博客GitHub_Trending/blo/BlogJavaScript深入系列源码解读 冴羽博客的JavaScript深入系列是前端开发者理解JavaS技术博客文档教程Effect v4 Cause 扁平化迁移指南从递归树到 Reasons 数组的 API 全面对照Effect v4 Cause 扁平化迁移指南从递归树到 Reasons 数组的 API 全面对照 本文基于 effect smol 仓库的 v3 到 v4AI Agent代码智能体后端前端移动开发桌面应用上一篇Photoshop-CC2022-Linux替代方案5款Linux图像编辑软件对比推荐下一篇osquery社区贡献终极指南如何参与开源项目开发创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
返回列表