关于前端:速度提高几百倍记一次数据结构在实际工作中的运用

这段时间写了一堆源码解析,这篇文章想换换口味,跟大家分享一个我工作中遇到的案例。毕竟作为一个打工人,下班除了摸鱼看源码外,砖还是要搬的。本文会分享一个应用失当的数据结构来进行性能优化,从而大幅提高响应速度的故事,进步有几百倍那么多。

事件是这样的,我当初供职一家外企,咱们有一个给外国人用的线下卖货的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白粉,第二层的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(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)$。

两层查找树

为了说明确这个算法,我先简化这个问题,假如咱们当初有两层选项,色彩尺码,每层选项有两个可选项:

  1. 色彩:红色,红色
  2. 尺码:39,40

咱们当初对应有4个商品:

  1. 一号商品:productId为1,红色,39码
  2. 二号商品:productId为2,红色,40码
  3. 三号商品:productId为3,红色,39码
  4. 四号商品: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

上面再来回顾下本文的要点:

  1. 本文要实现的需要是一个商品的三层选项。
  2. 当用户抉择了两层后,第三层选项应该主动计算出哪些能卖,哪些不能卖。
  3. 鉴于后端API返回选项和商品间没有间接的对应关系,为了找出能卖还是不能卖,咱们须要遍历所有商品。
  4. 当总商品数量不多的时候,所有商品遍历可能不会产生显著的性能问题。
  5. 然而当选项减少到三层,商品数量的减少是指数级的,性能问题就会显现出来。
  6. 对于$O(n^3)$这种写代码时就能预感的性能问题,咱们不必等着报BUG了才解决,而是开发时间接就解决了。
  7. 本例要解决的是一个查找问题,所以我想到了建一颗树,间接将$O(n^3)$的复杂度降到了$O(1)$。
  8. 然而一颗树并不能笼罩所有的用户操作,要笼罩所有的用户操作须要6棵树。
  9. 出于偷懒的目标,我跟产品经理磋商,调整了需要和交互砍掉了5颗树。实在起因是树太多了,会占用更多的内存空间,也不好保护。有时候适当的调整需要和交互也能够达到优化性能的成果,性能优化能够将交互和技术联合起来思考。
  10. 这个树的搜寻模块能够独自封装成一个类,内部使用者,不须要晓得细节,间接调用接口查找就行。
  11. 前端会点数据结构还是有用的,本文这种场景下还很有必要。

文章的最初,感激你破费贵重的工夫浏览本文,如果本文给了你一点点帮忙或者启发,请不要悭吝你的赞和GitHub小星星,你的反对是作者继续创作的能源。

作者博文GitHub我的项目地址: https://github.com/dennis-jiang/Front-End-Knowledges

我也搞了个公众号[进击的大前端],不打广告,不写水文,只发高质量原创,欢送关注~

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据