电商最小存货-SKU和算法实现

长命皮皮

这是第113篇不掺水的，想要了解更多，请戳上方蓝色字体：政采云前端团队关注我们吧～本文首发于政采云前端团队博客：电商最小存货- SKU 和算法实现https://zoo.team/article/sku-about前言目前电商平台的业务中，只要有商品，不可避免的会遇到 SKU (https://baike.baidu.com/item/%E6%9C%80%E5%B0%8F%E5%AD%98%E8%B4%A7%E5%8D%95%E4%BD%8D/892217fr=aladdin) 方面功能。这篇文章就从理论到实践，从商品创建到商品购买，手把手带你实现 SKU 相关的“核心算法”。让我们看看实际场景：有了上图规格选中预处理，就能够帮助用户在购买商品时，直观的了解到商品是否可以购买。在我们实际开发过程中，商品创建页会先进行规格组装，商品购买页会对规格选择做处理。规格组装通过规格组合成 SKU 集合，规格选择根据规格内容获取库存数据量，计算 SKU 是否可被选择，两者功能在电商流程中缺一不可。组装 SKU 实践属性描述根据百度百科解释的 SKU最小存货单位( Stock Keeping Unit )在连锁零售门店中有时称单品为一个 SKU，定义为保存库存控制的最小可用单位，例如纺织品中一个 SKU 通常表示规格、颜色、款式。业务场景只要是做电商类相关的产品，比如购物 APP、购物网站等等，都会遇到这么一个场景，每个商品对应着多个规格，用户可以根据不同的规格组合，选择出自己想要的产品。我们自己在生活中也会经常用到这个功能。通过上面描述，让我们把概念和实际数据关联起来，下面让我们来举个 ：现有规格consttype=["男裤","女裤"]constcolor=["黑色","白色"]constsize=["S","L"]那么根据现有规格，可以得到所有的 SKU 为：[["男裤","黑色","S"],["男裤","黑色","L"],["男裤","白色","S"],["男裤","白色","L"],["女裤","黑色","S"],["女裤","黑色","L"],["女裤","白色","S"],["女裤","白色","L"],]上述 SKU 是如何得到的呢，让我们一起看看实现思路，并且通过上面的 来计算一遍。SKU 组合实现思路笛卡尔积首先让我们来看看笛卡尔积的描述笛卡尔乘积是指在数学中，两个[集合] X 和 Y 的笛卡尔积(Cartesian product)，又称 [ 直积 ] ，表示为 X × Y，第一个对象是 X 的成员而第二个对象是 Y 的所有可能 [ 有序对 ] 的其中一个成员假设集合 A = { a, b }，集合 B = { 0, 1, 2 }，则两个集合的笛卡尔积为 { ( a, 0 ), ( a, 1 ), ( a, 2), ( b, 0), ( b, 1), ( b, 2) }看来笛卡尔积满足组合计算的条件，那么下面先来一波思维碰撞，先通过导图，看看怎么实现通过上面的思维导图，可以看出这种规格组合是一个经典的排列组合，去组合每一个规格值得到最终 SKU。那么让我们来进行代码实现，看看代码如何实现笛卡尔积。实现代码/***笛卡尔积组装*@param{Array}list*@returns[]*/functiondescartes(list){//parent上一级索引;count指针计数letpoint={};//准备移动指针letresult=[];//准备返回数据letpIndex=null;//准备父级指针lettempCount=0;//每层指针坐标lettemp=[];//组装当个sku结果//一：根据参数列生成指针对象for(letindexinlist){if(typeoflist[index]==='object'){point[index]={parent:pIndex,count:0};pIndex=index;}}//单维度数据结构直接返回if(pIndex===null){returnlist;}//动态生成笛卡尔积while(true){//二：生成结果letindex;for(indexinlist){tempCount=point[index].count;temp.push(list[index][tempCount]);}//压入结果数组result.push(temp);temp=[];//三：检查指针最大值问题，移动指针while(true){if(point[index].count+1>=list[index].length){point[index].count=0;pIndex=point[index].parent;if(pIndex===null){returnresult;}//赋值parent进行再次检查index=pIndex;}else{point[index].count++;break;}}}}让我们看看实际的输入输出和调用结果。那么这个经典的排列组合问题就这样解决啦。接下来，让我们再看看，如何在商品购买中，去处理商品多规格选择。商品多规格选择开始前回顾下使用场景这个图片已经能很明确的展示业务需求了。结合上述动图可知，在用户每次选择了某一规格后，需要通过程序的计算去处理其他规格情况，以便给用户提供当前情况下可供选择的其他规格。那么让我们来看看实现思路，首先在初始化中，提供可选择的 SKU，从可选择的 SKU 中去剔除不包含的规格内容，在剔除后，提供可以进行下一步选择的规格，后续在每次用户点击情况下，处理可能选中的 SKU，最终在全部规格选择完成后，得到选中的 SKU。商品多规格选择实现思路邻接矩阵首先，看下什么是邻接矩阵，来自百度百科的解释用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。逻辑结构分为两部分：V 和 E 集合，其中，V 是顶点，E 是边。因此，用一个一维数组存放图中所有顶点数据。字面描述可能比较晦涩难懂，那么让我们来看看图片帮助理解，如果两个顶点互通（有连线），那么它们对应下标的值则为 1，否则为 0。让我们继续前面的 数据来看规格consttype=["男裤","女裤"]constcolor=["黑色","白色"]constsize=["S","L"]假设总 SKU 的库存值为下面示例，可选为有库存，不可选为某项规格无库存[["男裤","黑色","S"],//S无号["男裤","黑色","L"],["男裤","白色","S"],//S无号["男裤","白色","L"],["女裤","黑色","S"],//S无号["女裤","黑色","L"],["女裤","白色","S"],//S无号["女裤","白色","L"],]那么根据邻接矩阵思想，可以得到结果图：从图中可以看出，SKU 中每两规格都可选择，那么相对的标志值为 1，否则为 0，当整条规格选中都是 1，才会使整条 SKU 链路可选。思路是有了，但是如何通过代码去实现呢，想必大家也有各种方式去实现，那么我就介绍下自己的实现方式：集合。计算思路集合高中过去好多年了，难免忘记，这里通过集合说明图一起回顾下集合的定义上图来自百度图片想起集合，那么计算思路算是有了，这边我们需要用集合相等的情况，去处理 SKU 和规格值的计算。实现思维导图假设一个集合 A{a, b, c} 和另外一个集合 B{a, e}，如何快速判断 B 是否是 A 的子集。这个问题比较简单的方法是用 B 中所有元素依次和 A 中的元素进行比较，对于集合中的元素，每个元素值都是唯一的。通过这样的特性，我们可以把所有字母转换为一个质数，那么 集合 A 可以表示为集合元素(质数)的积，B 同样，B 是否是 A 的子集，这个只需要将 B 除以 A，看看是否可以整除 ，如果可以那么说明，B 是 A 的子集。那么根据邻接矩阵思路，整条 SKU 都会有一个集合值，集合值由所有涉及规格对应乘积得到的结果，在选择规格过程中，每次选择去根据集合值去反向整除规格对应值去判断是否是子集，是否为 1。现在根据乘法算法，有了以上的分析，我们可以整理下算法过程：数据预处理，把所有需要处理的规格内容一一对应一个不重复的质数，把 ITEM 组合转换为每个质数的积根据用户已经选择的 ITEM 进行扫描所有的 ITEM，如果 ITEM 已经被选中，则退出，如果没有， 则和所有已经选择的 ITEM 进行相乘 (因为一个组合不可能出现两个类目相同的 ITEM，所以选中的 ITEM 需要去掉和当前匹配的 ITEM 在同一个类目中的 ITEM ) ，这个乘积就是上文中的集合 B把集合 B 依次和 SKU 组合构成的积 (相当于上文中的集合 A) 进行相除，比较，如果整除，则退出，当前匹配的 SKU 可以被选中，如果一直到最后还没有匹配上，则当前匹配的 SKU 不可被选中。我们通过集合的思想，看看核心代码吧。核心代码计算质数方法：/***准备质数*@param{Int}num质数范围*@returns*/getPrime:function(num){//从第一个质数2开始leti=2;constarr=[];/***检查是否是质数*@param{Int}number*@returns*/constisPrime=(number)=>{for(letii=2;ii//08)[2,3,5,7,11,13,17,19]//18)[23,29,31,37,41,43,47,53]//28)[59,61,67,71,73,79,83,89]//38)[97,101,103,107,109,113,127,131]//48)[137,139,149,151,157,163,167,173]//58)[179,181,191,193,197,199,211,223]//68)[227,229,233,239,241,251,257,263]初始化处理，得到第一批邻接矩阵结果：/***初始化，格式需要对比数据，并进行初始化是否可选计算*/init:function(){this.light=util.cloneTwo(this.maps,true);varlight=this.light;//默认每个规则都可以选中，即赋值为1for(vari=0;ieval(2*3*5*7*11*13*17*19)this.openway[i]=eval(this.openway[i].join('*'));}//return初始化得到规格位置，规格默认可选处理，可选SKU的规格对应的质数合集this._check();}计算是否可选方法：/***检查是否可以选择，更新邻接矩阵对应结果值*@param{Boolean}isAdd是否新增状态*@returns*/_check:function(isAdd){varlight=this.light;varmaps=this.maps;for(vari=0;i