【bigo】详解矩阵算法在 电商sku组件中的应用

[perryhong]

在电商里，什么是 sku？

简单的来说，比如一件裙子，颜色有红色、白色，码数有 XL、XXL，我们选择红色、XL，那这个规格的组合就是一个 sku。

而 spu 则是指这件裙子，要区分开来。

以前刚开始接触到这种 sku 选择器，还以为只是简简单单的几个 tab 组合后传给后端，但是等到实际开发才知道这种 sku 选择器，是后端告诉你有什么规格，比如颜色有几种，码数有几种，然后再告诉你有几种组合方式：

this.product.skuAttrSortedList = [
  {
    "attrName": "颜色",
    "attrNameId": "1",
    "attrValues": [
      "红",
      "白"
    ]
  },
  {
    "attrName": "码数",
    "attrNameId": "2",
    "attrValues": [
      "XL",
      "XXL"
    ]
  }
];
this.product.skuList = [
  {
    "showPrice": "6.00",
    "favType": 1,
    "skuId": "1234",
    "originalSalePrice": "12.01",
    "salePrice": "11.01",
    "discount": "-40%",
    "saleCurrency": "USD",
    "skuMinVolume": 1,
    "skuIncreaseVolume": 1,
    "maxBuyVolume": 99,
    "skuStatus": 1,
    "skuImg": "https://s4.forcloudcdn.com/item/images/dmc/7cdb5ab0-88b5-45a4-a5af-d683ccbd9336-750x1000.jpeg_750x0c.jpeg",
    "skuAttrList": [
      {
        "attrNameId": "12",
        "attrName": "颜色",
        "attrValue": "红"
      },
      {
        "attrNameId": "13",
        "attrName": "码数",
        "attrValue": "XL"
      }
    ]
  },
  {
    "showPrice": "6.00",
    "favType": 1,
    "skuId": "2345",
    "originalSalePrice": "12.01",
    "salePrice": "11.01",
    "saleCurrency": "USD",
    "discount": "-40%",
    "skuMinVolume": 1,
    "skuIncreaseVolume": 1,
    "maxBuyVolume": 99,
    "skuStatus": 1,
    "skuImg": "https://s4.forcloudcdn.com/item/images/dmc/4a085065-0f92-4406-a55e-ae4150b91def-779x974.jpeg_750x0c.jpeg",
    "skuAttrList": [
      {
        "attrNameId": "12",
        "attrName": "颜色",
        "attrValue": "红"
      },
      {
        "attrNameId": "13",
        "attrName": "码数",
        "attrValue": "XXL"
      }
    ]
  },
  {
    "skuId": "3456",
    "originalSalePrice": "12.01",
    "salePrice": "11.01",
    "saleCurrency": "USD",
    "discount": "-40%",
    "skuMinVolume": 1,
    "skuIncreaseVolume": 1,
    "maxBuyVolume": 99,
    "skuStatus": 1,
    "skuImg": "https://s4.forcloudcdn.com/item/images/dmc/4a085065-0f92-4406-a55e-ae4150b91def-779x974.jpeg_750x0c.jpeg",
    "skuAttrList": [
      {
        "attrNameId": "12",
        "attrName": "颜色",
        "attrValue": "白"
      },
      {
        "attrNameId": "13",
        "attrName": "码数",
        "attrValue": "XXL"
      }
    ]
  }
];

我唯一想到的就只有循环破解，那时间复杂度会随着规格越来越多而变得越来越大，虽然可行，但 js 执行在一些低端机就会有卡顿。

曾经在微信公众号发现一篇文章，讲的是如何用矩阵解决 sku 算法问题，当时粗略看了下，哇塞，好巧妙的办法！如今 stalar 电商项目刚好可以运用一下，说干就干！

产品需求是想，我选择一个规格后，其他可选的规格可点，不可选的规格置灰不可点击，可选不可选就是根据后端返回的组合列表得出的，就像


上面组合列表 skuList 有白色的 sku 只有一个（白色、XXL），所以码数中只有 XXL 可选。那为什么还有个红色可选？当然啦，用户想换种颜色看看你总得允许吧 ~

那我们怎么用矩阵来实现这种筛选呢？

我们画个图，利用矩阵列的求交集即可以得出剩余可选规格，那我们先拿到所有可选规格，定义两个计算属性：

vertex() {
      return (this.product.skuAttrSortedList || []).reduce((total, current) => [...total, ...(current.attrValues || [])], []);
},
len() {
      return this.vertex.length;
}

接下来就是利用这个 vertex 建立一个全为 0 的邻接矩阵，这个可以用一个一维数组表示。

this.adjoinArray = Array(this.len * this.len).fill(0);

所以就有了下面这样一个矩阵：

其实把矩阵的行与行首尾相连就是我们的一维数组了，也就是说 this.adjoinArray[4] 指的是 矩阵 B3 位置的值，那我们反过来，B3 位置的值对应的是数组哪个索引呢？我们可以先想想怎么算到这个索引，也就是怎么把矩阵每个点的位置映射成一维数组的索引）

接着我们得定义一个数组 specsS，存对应属性已选择的规格

specsS: [];

并且初始化它

this.specsS = Array(this.product.skuAttrSortedList.length).fill('');

我们需要把可以组合的点填充为 1，比如我们以红色为点，根据 skuList 这个组合列表，得到可到达的点有 XL 和 XXL，当然还有同级的白色(后面需要一个方法专门填充同级点)。

利用邻接矩阵的对称性（其实就是可以反过来选择）可变成

我们需要把 skuList 这个组合列表整个转成 矩阵填充 1 的展示，这个怎么用代码实现呢？首先定义一个填写 1 的方法

setAdjoinVertexs(side, sides) {
      let pIndex = '';
      for (let i = 0; i < this.vertex.length; i += 1) {
        if (side === this.vertex[i]) {
          pIndex = i;
          break;
        }
      }
      sides.forEach((item) => {
        let index = '';
        for (let i = 0; i < this.vertex.length; i += 1) {
          if (item === this.vertex[i]) {
            index = i;
            break;
          }
        }
        this.adjoinArray[pIndex * this.len + index] = 1;
      });
    }

我们先来看下两个循环干了些啥，如果我们传入 side = '红色'，sides = [‘红色’,'XL']
第一个循环其实是在矩阵中找到红色这一行，pIndex 得到的是 0

第二个循环则是在矩阵中找到可到达点所在列，比如找到 XL 所在列索引 index 是 2

找到了起始点的行，可到达点的列，那我们就可以把他们的交点填充为 1

还记得前面我让大家想如何将矩阵的点位置映射成数组的索引么？其实就是这里的 pIndex * this.len + index

知道原理了，赶紧上代码：

initSpec() {
      this.specCombinationList.forEach((item) => this.fillInSpec(item.skuAttrValueList));
    },
fillInSpec(params) {
      params.forEach((param) => {
        this.setAdjoinVertexs(param, params);
      });
    },
setAdjoinVertexs(side, sides) {
      let pIndex = '';
      for (let i = 0; i < this.vertex.length; i += 1) {
        if (side === this.vertex[i]) {
          pIndex = i;
          break;
        }
      }
      sides.forEach((item) => {
        let index = '';
        for (let i = 0; i < this.vertex.length; i += 1) {
          if (item === this.vertex[i]) {
            index = i;
            break;
          }
        }
        this.adjoinArray[pIndex * this.len + index] = 1;
      });
}

(注：initSpec 方法里的 specCombinationList 是处理过的 skuList 组合列表)

但实际上我们选了红色，白色依旧是可选项，所以我们需要填充同级点

initSameLevel() {
      this.product.skuAttrSortedList.forEach((item) => {
        const params = [];
        // 获取同级别顶点
        item.attrValues.forEach((val) => {
          if (this.optionSpecs.includes(val)) params.push(val);
        });
        // 同级点位创建
        this.fillInSpec(params);
      });
    }

这里的 optionSpecs 数组是什么呢？
其实就是可到达点数组，也就是可选规格，是我们本次算法的目的

所以我们需要定义一个计算属性，optionSpecs，它是根据用户选择动态变化的。我们想，那它的初始值是什么呢？

当我们执行完 initSpec 后，就能知道初始的可选规格有哪些

根据该矩阵我们就能找到最一开始可选的规格有哪些。

怎么找？我们可以把所有列求并集，上图矩阵所有列求并集就能得到[1, 1, 1, 1]
也就是，只要那一行某一列是 1，并集的结果就是 1，并集是 1 代表那一行的规格最一开始是可选的，这样看我们最一开始 4 个规格都是可点击的。

代码如何求列的并集呢
我们把每一列当成一个数组，第 x 行并集就是这 4 个数组的索引 x-1 对应值相加，相加结果大于等于 1 即可。

// 获取某一规格所在那一列
getVertexCol(param) {
      let idx = '';
      for (let i = 0; i < this.vertex.length; i += 1) {
        if (param === this.vertex[i]) {
          idx = i;
          break;
        }
      }
      const col = [];
      this.vertex.forEach((item, pIndex) => {
        col.push(this.adjoinArray[idx + this.len * pIndex]);
      });
      return col;
    },
// 得到每一行格子的和，然后放进一个数组
    getColSum(params) {
      const paramsVertex = params.map((param) => this.getVertexCol(param));
      const paramsVertexSum = [];
      this.vertex.forEach((item, index) => {
        const rowTotal = paramsVertex
          .map((value) => value[index])
          .reduce((total, current) => {
            let newTotal = total;
            newTotal += current || 0;
            return newTotal;
          }, 0);
        paramsVertexSum.push(rowTotal);
      });
      return paramsVertexSum;
    },
// 把paramsVertexSum数组中值为1的索引找出来，然后到规格列表数组中匹配得到并集
    getUnion(params) {
      const paramsColSum = this.getColSum(params);
      const union = [];
      paramsColSum.forEach((item, index) => {
        if (item && this.vertex[index]) union.push(this.vertex[index]);
      });
      return union;
    }

那初始化时的可选规格列表我们顺利拿到了，也就是上面我们提到的 optionSpecs = 四个规格的数组，我们就可以填充同级点了，这是因为要排除掉一开始就不可选的属性值。最终初始化的矩阵如下：

当用户点击某一个规格时，我们怎样得到剩余可选规格呢？

当我们选中红色这一列就可以知道，这时为 1 的有红色、白色、XL 和 XXL，那剩余可选规格就是红色、白色、XL 和 XXL。

因为这个例子只有 color 和 size 两个规格，所以只要我们选中 color 一列，就可以知道 size 可选是哪些

如果再多一个规格，比如是套餐

所以不难看出，我们选泽红色、XL 后，剩余可选可以通过求交集得出。
聚焦每一行，当这一行每个格子都为 1，这一行的交集的结果才是 1。

所以红色列和 XL 列的交集结果是[1, 0, 1, 1, 1, 1]，即可选的有红色、XL、XXL、套餐 1、套餐 2。

三个规格的选择变化其实不能这么简单的求交集，我将在第二篇里为大家说明，但原理是一样的，当前篇所讲的方法只适用于两个规格！！第二篇链接：

到这里大家应该知道了，这个 sku 选择器采用矩阵算法的原理了，就是用户每次选择一个属性值后，都能动态得到一个剩余可选属性的数组
代码上如何求交集

getIntersection(params) {
      const paramsColSum = this.getColSum(params);
      const intersection = [];
      paramsColSum.forEach((item, index) => {
        if (item >= params.length && this.vertex[index]) intersection.push(this.vertex[index]);
      });
      return intersection;
    }

我们也是要跟上面求并集那样，拿到每一行所有格子值的和，如果和大于等于已选规格列数（item >= params.length 其实就是这一行每个格子是否都为 1），交集则为 1。交集为 1 的行对应的规格就 push 到剩余可选规格数组。

这样我们就可以完善之前说的计算属性 optionSpecs 可选规格数组的获取方法了

computed: {
     optionSpecs() {  
 	return this.getSpecOptions(this.specsS);  
     }
},
methods: {
    getSpecOptions(params) {
      let specOptionCanChoose = [];
      if (params.some(Boolean)) {
	specOptionCanChoose = this.getIntersection(params.filter(Boolean));
      } else {
        specOptionCanChoose = this.getUnion(this.vertex);
      }
      return specOptionCanChoose;
    }
}

最后我们需要两个方法来判断该规格是否是可选规格以及判断该规格是否已选

isActive(val, idx) {
      return this.specsS[idx] === val;
    },
    isOption(val) {
      return this.optionSpecs.includes(val);
    }

这样我们就能 disable 掉不可选的规格，以及高亮已选规格。

以上主要参考的是掘金大神写的关于 sku 选择组件如何利用图和矩阵算法实现的文章
https://juejin.cn/post/6844904196349640718
我只是捋清他的思路，并转换成了 vue 的组件在电商项目中实际运用，大家可以思考下 sku 组件可否用链表的方式来实现呢哈哈？

[ghyghoo8]

高级~