这段时间写了一堆源码解析这篇文章想换换口味跟大家分享一个我工作中遇到的案例。毕竟作为一个打工人上班除了摸鱼看源码外砖还是要搬的。本文会分享一个使用恰当的数据结构来进行性能优化从而大幅提高响应速度的故事提高有几百倍那么多。事情是这样的我现在供职一家外企我们有一个给外国人用的线下卖货的APP卖的商品有衣服鞋子可乐什么的。某天产品经理找到我提了一个需求需要支持三层的产品选项。听到这个需求我第一反应是我好像没有见到过三层的产品选项毕竟我也是一个十来年的资深剁手党一般的产品选项好像最多两层比如下面是某电商APP一个典型的鞋子的选项这个鞋子就是两层产品选项一个是颜色一个是尺码颜色总共有11种尺码总共也是11种。为了验证我的直觉我把我手机上所有的购物APP啥淘宝京东拼多多苏宁易购全部打开看了一遍。在我看过的商品中没有发现一个商品有三层选项的最多也就两层。本文可运行的示例代码已经上传GitHub大家可以拿下来玩玩Front-End-Knowledges/Examples/DataStructureAndAlgorithm/OptimizeVariations at master · dennis-jiang/Front-End-Knowledges · GitHub为什么没人做三层选项一两家不做这个可能是各家的需求不一样但是大家都不做感觉事情不对头。经过仔细分析后我觉得不做三层选项可能有以下两个原因1. 这可能是个伪需求上面这个鞋子有11种颜色11种尺码意味着这些选项后面对应的是11 * 11总共121个商品。如果再来个第三层选项假设第三层也有11个选项那对应的商品总共就是11 * 11 * 11也就是1331个商品好多店铺总共可能都没有1331个商品。也就是说第三层选项可能是个伪需求用户并没有那么多选项放在第三层还是以上面的鞋子为例除了颜色尺码外非要再添一个层级那只能是性别了也就是男鞋和女鞋。对于男鞋和女鞋来说版型尺码这些很不一样一般都不会放到一个商品下面更常用的做法是分成两个商品各自有自己的颜色和尺码。2. 有性能问题仅仅是加上第三层选项这个功能并没有什么难的也就是多展示几个可以点击的按钮而已点击逻辑跟两层选项并没有太大区别。但是细想下去我发现了他有潜在的性能问题。以上面这双鞋子为例我从后端API拿到的数据是这样的const merchandise { // variations存放的是所有选项 variations: [ { name: 颜色, values: [ { name: 限量版574海军蓝 }, { name: 限量版574白粉 }, // 下面还有9个 ] }, { name: 尺码, values: [ { name: 38 }, { name: 39 }, // 下面还有9个 ] }, ], // products数组存放的是所有商品 products: [ { id: 1, price: 208, // 与上面variations的对应关系在每个商品的variationMappings里面 variationMappings: [ { name: 颜色, value: 限量版574白粉 }, { name: 尺码, value: 38}, ] }, // 下面还有一百多个产品 ] }上面这个结构本身还是挺清晰的merchandise.variations是一个数组有几层选项这个数组就有几个对象每个对象的name就是当前层级的名字values就是当前层级包含的选项所以merchandise.variations可以直接拿来显示在UI上将他们按照层级渲染成按钮就行。上面图片中用户选择了第一层的限量版574白粉第二层的4041等不存在的商品就自动灰掉了。用上面的数据结构可以做到这个功能当用户选择限量版574白粉的时候我们就去遍历merchandise.products这个数组这个数组的一个项就是一个商品这个商品上的variationMappings会有当前商品的颜色和尺码信息。对于我当前的项目来说如果这个商品可以卖他就会在merchandise.products这个数组里面如果不可以卖这个数组里面压根就不会有这个商品。比如上图的限量版574白粉40码的组合就不会出现在merchandise.products里面查找的时候找不到这个组合那就会将它变为灰色不可以点。所以对于限量版574白粉40这个鞋子来说为了知道它需不需要灰掉我需要整个遍历merchandise.products这个数组。按照前面说的11个颜色11个尺码来说最多会有121个商品也就是最多查找121次。同样的要知道限量版574白粉41这个商品可以不可以卖又要整个遍历商品数组11个尺码就需要将商品数组整个遍历11次。对于两层选项来说11 * 11已经算比较多的了每个尺码百来次运算可能还不会有严重的性能问题。但是如果再加一层选项新加这层假如也有11个可选项这复杂度瞬间就增加了一个指数从O(n2)变成O(n3)现在我们的商品总数是11 * 11 * 11也就是1331个商品假如第三层是性别现在为了知道限量版574白粉40男性这个商品可不可以卖我需要遍历1331个商品如果遍历121个商品需要20ms还比较流畅那遍历1331个商品就需要220ms这明显可以感觉到卡顿了在某些硬件较差的设备上这种卡顿会更严重变得不可接受了。而且我们APP使用的技术是React Native本身性能就比原生差这样一来用户可能就怒而卸载了我拿着上述对需求的疑问和对性能的担心找到了产品经理发生了如下对话我大佬我发现市面上好像没有APP支持三层选项的这个需求是不是有问题哦而且三层选项相较于两层选项来说复杂度是指数增长可能会有性能问题用户用起来会卡的。产品经理兄弟你看的都是国内的APP但是我们这个是给外国人用的人家外国人就是习惯这么用咱要想卖的出去就得满足他们的需求。太卡了肯定不行性能问题想办法解决嘛这就是在UI上再加几个按钮设计图都跟以前是一样的给你两天时间够了吧~我啊额。。。哦。。。咱也不认识几个外国人咱也不敢再问都说了是用户需求咱必须满足了产品才卖的出去产品卖出去了咱才有饭吃想办法解决吧解决方案看来这个需求是必须要做了这个功能并不复杂因为三层选项可以沿用两层选项的方案继续去遍历商品数组但是这个复杂度增长是指数级的即从O(n2)变成O(n3)用户用起来会卡。现在我需要思考一下有没有其他方案可以提高性能。经过仔细思考我发现这种指数级的复杂度增长是来自于我们整个数组的遍历如果我能够找到一个方法不去遍历这个数组立即就能找到限量版574白粉40男性对应的商品存不存在就好了。这个具体的问题转换一下其实就是在一个数组中通过特定的过滤条件查找符合条件的一个项。嗯查找听起来蛮耳熟的现在我之所以需要去遍历这个数组是因为这些查找条件跟商品间没有一个直接的对应关系如果我能建立一个直接的对应关系不就可以一下就找到了吗我想到了查找树。假如我重组这些层级关系将它们组织为一颗树每个商品都对应树上的一个叶子节点我可以将三层选项的查找复杂度从O(n3)降到O(1)。两层查找树为了说明白这个算法我先简化这个问题假设我们现在有两层选项颜色和尺码每层选项有两个可选项颜色白色红色尺码3940我们现在对应有4个商品一号商品productId为1白色39码二号商品productId为2白色40码三号商品productId为3红色39码四号商品productId为4红色40码如果按照最简单的做法为了查找红色的39码鞋子存不存在我们需要遍历所有的这四个商品这时候的时间复杂度为O(n2)。但是如果我们构建像下面这样一颗树可以将时间复杂度降到O(1)上面这颗树我们忽略root节点在本例中他并没有什么用仅仅是一个树的入口这棵树的第一层淡黄色节点是我们第一层选项颜色第二层淡蓝色节点是我们的第二层选项尺码只是每个颜色节点都会对应所有的尺码这样我们最后第二层的叶子节点其实就对应了具体的商品。现在我们要查找红色的39码鞋子只需要看图中红色箭头指向的节点上有没有商品就行了。那这种数据结构在JS中该怎么表示呢其实很简单一个对象就行了像这样const tree { 颜色白色: { 尺码39: { productId: 1 }, 尺码40: { productId: 2 } }, 颜色红色: { 尺码39: { productId: 3 }, 尺码40: { productId: 4 } } }有了上面这个数据结构我们要查找红色的39码直接取值tree[颜色红色][尺码39]就行了这个复杂度瞬间就变为O(1)了。三层查找树理解了上面的两层查找树要将它扩展到三层就简单了直接再加一层就行了。假如我们现在第三层选项是性别有两个可选项男和女那我们的查找树就是这样子的对应的JS对象const tree { 颜色白色: { 尺码39: { 性别男: { productId: 1 }, 性别女: { productId: 2 }, }, 尺码40: { 性别男: { productId: 3 }, 性别女: { productId: 4 }, } }, 颜色红色: { 尺码39: { 性别男: { productId: 5 }, 性别女: { productId: 6 }, }, 尺码40: { 性别男: { productId: 7 }, 性别女: { productId: 8 }, } } }同样的假如我们要查找一个白色的39码男的鞋子直接tree[颜色白色][尺码39][性别男]就行了这个时间复杂度也是O(1)。写代码上面算法都弄明白了剩下的就是写代码了我们主要需要写的代码就是用API返回的数据构建一个上面的tree这种结构就行了一次遍历就可以做到。比如上面这个三层查找树对应的API返回的结构是这样的const merchandise { variations: [ { name: 颜色, values: [ { name: 白色 }, { name: 红色 }, ] }, { name: 尺码, values: [ { name: 39 }, { name: 40 }, ] }, { name: 性别, values: [ { name: 男 }, { name: 女 }, ] }, ], products: [ { id: 1, variationMappings: [ { name: 颜色, value: 白色 }, { name: 尺码, value: 39 }, { name: 性别, value: 男 } ] } // 下面还有7个商品我就不重复了 ] }为了将API返回的数据转换为我们的树形结构数据我们写一个方法function buildTree(apiData) { const tree {}; const { variations, products } apiData; // 先用variations将树形结构构建出来叶子节点默认值为null addNode(tree, 0); function addNode(root, deep) { const variationName variations[deep].name; const variationValues variations[deep].values; for (let i 0; i variationValues.length; i) { const nodeName ${variationName}${variationValues[i].name}; if (deep 2) { root[nodeName] null } else { root[nodeName] {}; addNode(root[nodeName], deep 1); } } } // 然后遍历一次products给树的叶子节点填上值 for (let i 0; i products.length; i) { const product products[i]; const { variationMappings } product; const level1Name ${variationMappings[0].name}${variationMappings[0].value}; const level2Name ${variationMappings[1].name}${variationMappings[1].value}; const level3Name ${variationMappings[2].name}${variationMappings[2].value}; tree[level1Name][level2Name][level3Name] product; } // 最后返回构建好的树 return tree;