然后用上面的API测试数据运行下看下效果，发现构建出来的树完全符合我们的预期：
这就好了吗？
现在我们有了一颗查找树，当用户选择红色，40码后，为了知道对应的男可不可以点，我们不需要去遍历所有的商品了，而是可以直接从这个结构上取值。但是这就大功告成了吗？并没有！再仔细看下我们构建出来的数据结构，层级关系是固定的，第一层是颜色，第二层是尺码，第三层是性别，而对应的商品是放在第三层性别上的。也就是说使用这个结构，用户必须严格按照，先选颜色，再选尺码，然后我们看看性别这里哪个该灰掉。如果他不按照这个顺序，比如他先选了性别男，然后选尺码40，这时候我们应该计算最后一个层级颜色哪些该灰掉。但是使用上面这个结构我们是算不出来的，因为我们并没有tree["性别：男"]["尺码：40"]这个对象。
这怎么办呢？我们没有性别-尺码-颜色这种顺序的树，那我们就建一颗呗！这当然是个方法，但是用户还可能有其他的操作顺序呀，如果我们要覆盖用户所有可能的操作顺序，总共需要多少树呢？这其实是性别，尺码，颜色这三个变量的一个全排列，也就是A33，总共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，大家可以拿下来玩玩：Front-End-Knowledges/Examples/DataStructureAndAlgorithm/OptimizeVariations at master · dennis-jiang/Front-End-Knowledges · GitHub
下面再来回顾下本文的要点：
- 本文要实现的需求是一个商品的三层选项。
- 当用户选择了两层后，第三层选项应该自动计算出哪些能卖，哪些不能卖。
- 鉴于后端API返回选项和商品间没有直接的对应关系，为了找出能卖还是不能卖，我们需要遍历所有商品。
- 当总商品数量不多的时候，所有商品遍历可能不会产生明显的性能问题。
- 但是当选项增加到三层，商品数量的增加是指数级的，性能问题就会显现出来。
- 对于O(n3)这种写代码时就能预见的性能问题，我们不用等着报BUG了才处理，而是开发时直接就解决了。
- 本例要解决的是一个查找问题，所以我想到了建一颗树，直接将O(n3)的复杂度降到了O(1)。
- 但是一颗树并不能覆盖所有的用户操作，要覆盖所有的用户操作需要6棵树。
- 出于偷懒的目的，我跟产品经理商量，调整了需求和交互砍掉了5颗树。真实原因是树太多了，会占用更多的内存空间，也不好维护。有时候适当的调整需求和交互也可以达到优化性能的效果，性能优化可以将交互和技术结合起来思考。
- 这个树的搜索模块可以单独封装成一个类，外部使用者，不需要知道细节，直接调用接口查找就行。
- 前端会点数据结构还是有用的，本文这种场景下还很有必要。