共计 9499 个字符，预计需要花费 24 分钟才能阅读完成。
这段时间写了一堆源码解析，这篇文章想换换口味，跟大家分享一个我工作中遇到的案例。毕竟作为一个打工人，下班除了摸鱼看源码外，砖还是要搬的。本文会分享一个应用失当的数据结构来进行性能优化，从而大幅提高响应速度的故事，进步有几百倍那么多。
事件是这样的，我当初供职一家外企，咱们有一个给外国人用的线下卖货的 APP，卖的商品有衣服，鞋子，可乐什么的。某天，产品经理找到我，提了一个需要：须要反对三层的产品选项。听到这个需要，我第一反馈是我如同没有见到过三层的产品选项，毕竟我也是一个十来年的资深剁手党，个别的产品选项如同最多两层，比方上面是某电商 APP 一个典型的鞋子的选项：
这个鞋子就是两层产品选项，一个是色彩，一个是尺码，色彩总共有 11 种，尺码总共也是 11 种。为了验证我的直觉，我把我手机上所有的购物 APP，啥淘宝，京东，拼多多，苏宁易购全副关上看了一遍。在我看过的商品中，没有发现一个商品有三层选项的，最多也就两层。
本文可运行的示例代码曾经上传 GitHub，大家能够拿下来玩玩：https://github.com/dennis-jiang/Front-End-Knowledges/tree/master/Examples/DataStructureAndAlgorithm/OptimizeVariations
为什么没人做三层选项？
一两家不做这个，可能是各家的需要不一样，然而大家都不做，感觉事件不对头。通过仔细分析后，我感觉不做三层选项可能有以下两个起因：
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 白粉 ，第二层的40，41 等不存在的商品就主动灰掉了。用下面的数据结构能够做到这个性能，当用户抉择 限量版 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(n^2)$ 变成 $O(n^3)$！当初咱们的商品总数是 11 * 11 * 11，也就是1331 个商品，如果第三层是 性别 ，当初为了晓得 限量版 574 白粉 ，40， 男性 这个商品可不可以卖，我须要遍历 1331 个商品，如果遍历 121 个商品须要 20ms，还比拟晦涩，那遍历1331 个商品就须要220ms，这显著能够感觉到卡顿了，在某些硬件较差的设施上，这种卡顿会更重大，变得不可承受了。而且咱们 APP 应用的技术是 React Native，自身性能就比原生差，这样一来，用户可能就怒而卸载了！
我拿着上述对需要的疑难，和对性能的放心找到了产品经理，产生了如下对话：
我：大佬，我发现市面上如同没有 APP 反对三层选项的，这个需要是不是有问题哦，而且三层选项相较于两层选项来说，复杂度是指数增长，可能会有性能问题，用户用起来会卡的。
产品经理：兄弟，你看的都是国内的 APP，然而咱们这个是给外国人用的，人家外国人就是习惯这么用，咱要想卖的进来就得满足他们的需要。太卡了必定不行，性能问题，想方法解决嘛，这就是在 UI 上再加几个按钮，设计图都跟以前是一样的，给你两天工夫够了吧~
我：啊！？额。。。哦。。。
咱也不意识几个外国人，咱也不敢再问，都说了是用户需要，咱必须满足了产品才卖的进来，产品卖出去了咱才有饭吃，想方法解决吧！
解决方案
看来这个需要是必须要做了，这个性能并不简单，因为三层选项能够沿用两层选项的计划，持续去遍历商品数组，然而这个复杂度增长是指数级的，即从 $O(n^2)$ 变成 $O(n^3)$，用户用起来会卡。当初，我须要思考一下，有没有其余计划能够进步性能。通过认真思考，我发现，这种指数级的复杂度增长是来自于咱们整个数组的遍历，如果我可能找到一个办法不去遍历这个数组，立刻就能找到 限量版 574 白粉 ，40， 男性 对应的商品存不存在就好了。
这个具体的问题转换一下，其实就是：在一个数组中，通过特定的过滤条件，查找符合条件的一个项 。嗯，查找，听起来蛮耳熟的，当初我之所以须要去遍历这个数组，是因为这些查找条件跟商品间没有一个间接的对应关系，如果我能建设一个间接的对应关系，不就能够一下就找到了吗？我想到了： 查找树 。 如果我重组这些层级关系，将它们组织为一颗树，每个商品都对应树上的一个叶子节点，我能够将三层选项的查找复杂度从 $O(n^3)$ 降到 $O(1)$。
两层查找树
为了说明确这个算法，我先简化这个问题，假如咱们当初有两层选项，色彩 和尺码，每层选项有两个可选项：
- 色彩：红色，红色
- 尺码：39，40
咱们当初对应有 4 个商品：
- 一号商品：productId 为 1，红色，39 码
- 二号商品：productId 为 2，红色，40 码
- 三号商品：productId 为 3，红色，39 码
- 四号商品：productId 为 4，红色，40 码
如果依照最简略的做法，为了查找 红色 的39 码 鞋子存不存在，咱们须要遍历所有的这四个商品，这时候的工夫复杂度为 $O(n^2)$。然而如果咱们构建像上面这样一颗树，能够将工夫复杂度降到 $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;
}而后用下面的 API 测试数据运行下看下成果，发现构建进去的树完全符合咱们的预期：
这就好了吗？
当初咱们有了一颗查找树，当用户抉择 红色 ，40 码后，为了晓得对应的 男可不可以点，咱们不须要去遍历所有的商品了，而是能够间接从这个构造上取值。然而这就功败垂成了吗？并没有 ！再认真看下咱们构建进去的数据结构，层级关系是固定的，第一层是色彩，第二层是尺码，第三层是性别，而对应的商品是放在第三层性别上的。 也就是说应用这个构造，用户必须严格依照，先选色彩，再选尺码，而后咱们看看性别这里哪个该灰掉。如果他不依照这个程序，比方他先选了性别 男，而后选尺码 40，这时候咱们应该计算最初一个层级 色彩 哪些该灰掉。然而应用下面这个构造咱们是算不进去的，因为咱们并没有 tree["性别：男"]["尺码：40"] 这个对象。
这怎么办呢？咱们没有 性别 - 尺码 - 色彩 这种程序的树，那咱们就建一颗呗！这当然是个办法，然而用户还可能有其余的操作程序呀，如果咱们要笼罩用户所有可能的操作程序，总共须要多少树呢？这其实是 性别 ， 尺码 ， 色彩 这三个变量的一个全排列，也就是 $A_3^3$，总共 6 颗树。像我这样的懒人，让我建 6 棵树，我切实懒得干。如果不建这么多树，需要又笼罩不了，怎么办呢，有没有偷懒的方法呢？如果我能在需要上动点手脚，是不是能够躲避这个问题？带着这个思路，我想到了两点：
1. 给一个默认值。
用户关上商品详情页的时候，默认选中第一个可售商品。这样就相当于咱们一开始就帮用户依照 色彩 - 尺码 - 性别 这个程序选中了一个值，给了他一个默认的操作程序。
2. 不提供勾销性能，只能切换选项
如果提供勾销性能，他将咱们提供的 色彩 - 尺码 - 性别 默认选项勾销掉，又能够选成 性别 - 尺码 - 色彩 了。不提供勾销性能，只能通过抉择其余选项来切换，只能从 红色 换成 红色 ，而不能取消 红色 ，其余的一样。这样咱们就能永远保障 色彩 - 尺码 - 性别 这个程序，用户操作只是只是每个层级选中的值不一样，层级程序并不会变动，咱们的查找树就始终无效了。而且我发现某些购物网站也不能取消选项，不晓得他们是不是也遇到了相似的问题。
对需要做这两点批改并不会对用户体验造成多大影响，跟产品经理磋商后，她也批准了。这样我就从需要上干掉了另外 5 棵树，偷懒胜利！
上面是三层选项跑起来的样子：
还有一件事
后面的计划咱们解决了查找的性能问题，然而引入了一个新问题，那就是须要创立这颗查找树。创立这颗查找树还是须要对商品列表进行一次遍历，这是不可避免的，为了更顺滑的用户体验，咱们应该尽量将这个创立过程暗藏在用户感知不到的中央。我这里是将它整合到了商品详情页的加载状态中，用户点击进入商品详情页，咱们要去 API 取数据，不可避免的会有一个加载状态，会转个圈什么的。我将这个遍历过程也做到了这个转圈中，当 API 数据返回，并且查找树创立实现后，转圈才会完结。这在实践上会缩短转圈的工夫，然而本地的遍历再慢也会比网络申请快点，所以用户感知并不显著。当转圈完结后，所有数据都准备就绪了，用户操作都是 $O(1)$ 的复杂度，做到了真正的丝般顺滑~
为什么不让后端创立这棵树？
下面的计划都是在前端创立这颗树，那有没有可能后端一开始返回的数据就是这样的，我间接拿来用就行，这样我又能够偷懒了~ 我还真去找过后端，可他给我说：“我也想偷懒！”开个玩笑，真是状况是，这个商品 API 是另一个团队保护的微服务，他们提供的数据不仅仅给我这一个终端 APP 应用，也给公司其余产品应用，所以要改返回构造涉及面太大，基本改不动。
封装代码
其实咱们这个计划实现自身是比拟独立的，其他人要是用的话，他也不关怀你外面是棵树还是颗草，只有传入抉择条件，可能返回正确的商品就行，所以咱们能够将它封装成一个类。
class VariationSearchMap {constructor(apiData) {this.tree = this.buildTree(apiData);
}
// 这就是后面那个结构树的办法
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 === variations.length - 1) {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;
}
// 增加一个办法来搜寻商品，参数构造和 API 数据的 variationMappings 一样
findProductByVariationMappings(variationMappings) {const level1Name = `${variationMappings[0].name}：${variationMappings[0].value}`;
const level2Name = `${variationMappings[1].name}：${variationMappings[1].value}`;
const level3Name = `${variationMappings[2].name}：${variationMappings[2].value}`;
const product = this.tree[level1Name][level2Name][level3Name];
return product;
}
}而后应用的时候间接 new 一下就行：
const variationSearchMap = new VariationSearchMap(apiData); // new 一个实例进去
// 而后就能够用这个实例进行搜寻了
const searchCriteria = [{ name: '色彩', value: '红色'},
{name: '尺码', value: '40'},
{name: '性别', value: '女'}
];
const matchedProduct = variationSearchMap.findProductByVariationMappings(searchCriteria);
console.log('matchedProduct', matchedProduct); // {productId: 8}总结
本文讲述了一个我工作中理论遇到的需要，分享了我的实现和优化思路，供大家参考。我的实现计划不肯定完满，如果大家有更好的计划，欢送在评论区探讨~
本文可运行的示例代码曾经上传 GitHub，大家能够拿下来玩玩：https://github.com/dennis-jiang/Front-End-Knowledges/tree/master/Examples/DataStructureAndAlgorithm/OptimizeVariations
上面再来回顾下本文的要点：
- 本文要实现的需要是一个商品的三层选项。
- 当用户抉择了两层后，第三层选项应该主动计算出哪些能卖，哪些不能卖。
- 鉴于后端 API 返回选项和商品间没有间接的对应关系，为了找出能卖还是不能卖，咱们须要遍历所有商品。
- 当总商品数量不多的时候，所有商品遍历可能不会产生显著的性能问题。
- 然而当选项减少到三层，商品数量的减少是指数级的，性能问题就会显现出来。
- 对于 $O(n^3)$ 这种写代码时就能预感的性能问题，咱们不必等着报 BUG 了才解决，而是开发时间接就解决了。
- 本例要解决的是一个查找问题，所以我想到了建一颗树，间接将 $O(n^3)$ 的复杂度降到了 $O(1)$。
- 然而一颗树并不能笼罩所有的用户操作，要笼罩所有的用户操作须要 6 棵树。
- 出于偷懒的目标，我跟产品经理磋商，调整了需要和交互砍掉了 5 颗树。实在起因是树太多了，会占用更多的内存空间，也不好保护。有时候适当的调整需要和交互也能够达到优化性能的成果，性能优化能够将交互和技术联合起来思考。
- 这个树的搜寻模块能够独自封装成一个类，内部使用者，不须要晓得细节，间接调用接口查找就行。
- 前端会点数据结构还是有用的，本文这种场景下还很有必要。
文章的最初，感激你破费贵重的工夫浏览本文，如果本文给了你一点点帮忙或者启发，请不要悭吝你的赞和 GitHub 小星星，你的反对是作者继续创作的能源。
作者博文 GitHub 我的项目地址：https://github.com/dennis-jiang/Front-End-Knowledges
我也搞了个公众号[进击的大前端]，不打广告，不写水文，只发高质量原创，欢送关注~