商品规格SKU组合查询算法总结

平时的工作中基本都是业务代码, 很少需要动脑筋. 最近在公司的工作中遇到了关于商品多种规格的SKU组合问题, 感觉还蛮有意思, 借鉴了淘宝UED团队的一篇博文 , 对这个问题进行了一下总结.

SKU定义

SKU(Stock Keeping Unit)的全称解释为: 最小存货单位, 在连锁零售门店中有时称单品为一个SKU,定义为保存库存控制的最小可用单位.

例: 衣服的一个SKU通常为规格、颜色、款式的组合(XL蓝色衬衫)

假设我们的商城中有一款这样的衣服, 它的属性如下:

季度 规格 颜色 款式
2016春季 M 复古
2016秋季 L 绿 流行
2017春季 XL - -
2017秋季 XXL - -

那么衣服的SKU有四个季度、四个规格、两个颜色、两个款式, 季度/规格/颜色/款式四个属性各选一个值构成一个SKU,我们可以说, 这个SKU是描述这款衣服的最小单位.

场景描述

为了方便描述, 先把衣服属性缩小为 2x2 的组合, 用二维数组表示为:

[['L', 'XL'], ['蓝', '红']]

根据之前SKU的定义, 我们可以确定SKU组合为:

['L-蓝', 'L-红', 'XL-蓝', 'XL-红']

假设已有的库存和价格为:

{
  'L-蓝': { remain: 10, price: 12000 },
  'L-红': { remain: 15, price: 13000 },
  'XL-蓝': { remain: 5, price: 11000 }
}

我们可以知道是 XL-红 这个SKU是没有库存的, 其他三个SKU则是有库存的. 那么, 在用户先选择了 XL 属性之后, 属性应该变为不可选状态;同样用户先选择了 属性, XL 属性也应该变为不可选状态.

问题

如何在用户选择了某个属性后, 判断其他属性是否可选? 在场景描述中为了简化,SKU组合只有 2x2 的规模, 还是非常容易计算的. 但是假如情况比较复杂, 比如SKU组合规模是 4x4x4 的时候, 要实现上述场景就会复杂很多.

算法

在UED团队的博文中主要有两种算法, 针对每种算法都有对应的优化

初始条件

已知:

  1. 所有的SKU属性数组 items: [['a', 'A'], ['b', 'B'], ['c', 'C']]

  2. SKU对应的所有价格库存信息

     result: {
       'a-b-c': {remain: 10, price: 1000},
       'a-B-c': {remain: 10, price: 1000},
       'A-B-C': {remain: 10, price: 1000}
     }
    
  3. 用户选择的属性用 selected: ['a'] 表示, selected 可以为空

算法一

算法原理

逐个判断所有的 item 是否可选, 判断依据是 item 和当前已选中的 selected 组合是否在 result 中存在. 需要注意的点是同属性中不能选多个元素, 所以要去掉包含的已选中元素(算法步骤中的第4步)

算法步骤
  1. 声明 item 标注变量 itemStates

  2. 循环 items 数组 for (let currItems of items)

  3. tempSelected = selected

  4. 判断 currItems 中有没有元素存在于 tempSelected 中, 如果存在, 从 tempSelected 中去掉该元素

  5. 循环 currItems 数组 for (let item of currItems)

  6. tempSelecteditem 组合: tempSku = tempSelected.concat(item)

  7. 循环 result : for (let sku in result) 判断 sku 是否包含 tempSku,

    a. 如果存在, 设置 itemStates[item] = true, 退出 result 循环

    b. 如果不存在, 继续 result 循环

  8. 所有循环结束后, 所有 item 状态均标注完成

算法实现
const { difference } = require('lodash')
const result = {
  'a-b-c': { remain: 10, price: 1000 },
  'a-B-c': { remain: 2, price: 1100 },
  'A-B-C': { remain: 10, price: 1000 }
}
const items = [['a', 'A'], ['b', 'B'], ['c', 'C']]

function getItemStates (selected = []) {
  const _itemStates = {}
  for (let currItems of items) {
    tempSelected = difference(selected, currItems) // 步骤3, 4
    for (let item of currItems) {
      const tempSku = tempSelected.concat(item)
      for (let skuKey in result) {
        const sku = skuKey.split('-')
        if (difference(tempSku, sku).length === 0) {
          _itemStates[item] = true
          break
        }
      }
    }
  }
  return _itemStates
}

这样的实现方式简单粗暴, 但是存在以下问题

  1. 比较繁琐, 存在多重循环
  2. 步骤7中判断 tempSkuresult 中是否存在时虽然借助了 lodashdifference 方法简化代码, 但本质是循环比较, 过程比较耗时
优化思路

对于这种算法而言, 问题1的多重循环是无法避免的, 但是问题2是可以优化的. 步骤7本质上是判断集合A是否包含集合B, 即B是否是A的子集.

上面的实现是最简单的方法, 将B中的元素一个个地在A中寻找得出结果, 全部能找到则B是A的子集.

简化思路是: 由于属性值的唯一性, 可以在初始化时给每个属性值分配一个质数, 那么问题就可以简化成为乘除法运算.

一个例子(具体实现就不写了, 很简单):

A: {1, 2, 3, 5, 7} = 1 * 2 * 3 * 5 * 7
B: {1, 2, 5} = 1 * 2 * 5
B只要可以被A整除, 就可以说明B是A的子集

算法二

算法原理

假设已选中 a , 要判断 b 是否可以选中时, 只需要获取到 ab 组合的所有商品数目, 就可以知道 b 是否可以选择. 在初始条件中可知, ab 的组合可能有: a-b-c, a-b-C. 这些组合是可以直接在 result 中获取结果的, 并且是获取对象属性, 速度很快.

算法思路

假如当前已选中的 itema , 要计算 b 是否可以被选择, 那么如果能获取到 ab 所有组合的商品数目, 就可以知道 b 是否可以被选择. 可以知道 ab 的所有组合为: a-b-c , a-b-C , 这些组合是可以直接在 result 中查找结果的.

总的来说, 主要是采用递归的方式. 比如初始化计算 a 是否可以被选中, 则需要计算 a-b, a-B 的数量. 要计算 a-b 的数量, 则需要计算 a-b-c , a-b-C 的数量, 而这些计算结果都是可以缓存起来的, 可以省去很多重复计算.

算法实现
const result = {
  'a-b-c': { remain: 10, price: 1000 },
  'a-B-c': { remain: 2, price: 1100 },
  'A-B-C': { remain: 10, price: 1000 }
}
const items = [['a', 'A'], ['b', 'B'], ['c', 'C']]
const data = {}

function getRemainByKey (selected) {
  const key = selected.join('-')
  if (typeof data[key] !== 'undefined') {
    return data[key]
  }

  if (selected.length === items.length) {
    return result[key] ? data[key] = result[key].remain : data[key] = 0
  }

  let remain = 0
  let tempSelected = []

  for (let i = 0; i < items.length; i++) {
    const exist = items[i].find(_item => _item === selected[0])
    if (exist && selected.length > 0) {
      tempSelected.push(selected.shift())
    } else {
      items[i].forEach(_item => {
        remain += getRemainByKey(tempSelected.concat(_item, selected))
      })
      break
    }
  }
  return data[key] = remain
}

console.log(getRemainByKey(['a']))
优化思路

第二种算法实现思路很有意思, 它使用的其实是动态规划法, 就是我们在算法中常说的背包问题, 将原问题分解为相似的子问题, 通过子问题的解来解出原问题的解. 但是它的存在问题也很明显, 主要在于它初始化的时间复杂度和空间复杂度.

在如今的硬件条件下空间复杂度的问题大部分都够不上硬伤, 我们来看看时间复杂度. 对于 n*n 的数据输入, 计算量是 n + n^2 + n^3 + ... + n^n , 用 O(n^n) 来表示的复杂度显然是无法接受的. 但是在初始化完成后, 获取数据就非常简单快速了. 那么有什么办法可以简化初始化过程吗? 答案是有的.

在上面的算法实现中, 我们采用的是自上而下不断拆分SKU, 这样的实现导致运算复杂度是指数型增长的. 既然 result 中已经有所有的结果, 那只需要遍历一遍 result , 所有的可能组合都可以计算出来了. 之后所有的判断都只需要判断在缓存的 data 对象中是否存在对应的结果.

优化思路的栗子

初始化结果集 result :

const result = {
  'a-b-c': { remain: 10, price: 1000 },
  'a-B-c': { remain: 2, price: 1100 },
  'A-B-C': { remain: 10, price: 1000 }
}
  1. 分解 a-b-c :

    data = {
      'a': 10,
      'b': 10,
      'c': 10,
      'a-b': 10,
      'a-c': 10,
      'b-c': 10,
      'a-b-c': 10
    }
    
  2. 分解 a-B-c :

    data = {
      'a': 12, // 10 + 2
      'b': 10,
      'B': 2, // +2
      'c': 12, // 10 + 2
      'a-b': 10,
      'a-B': 2, // +2
      'a-c': 12, // 10 + 2
      'b-c': 10,
      'B-c': 2, // +2
      'a-b-c': 10,
      'a-B-c': 2 // +2
    }
    
  3. 分解 A-B-C :

    data = {
      'A': 10, // +10
      'a': 12,
      'b': 10,
      'B': 12, // 2 + 10
      'c': 12,
      'a-b': 10,
      'a-B': 2,
      'A-B': 10, // +10
      'a-c': 12,
      'A-C': 10, // +10
      'b-c': 10,
      'B-c': 2,
      'B-C': 10, // +10
      'a-b-c': 10,
      'a-B-c': 2,
      'A-B-C': 10 // +10
    }
    

三次循环分解后, 得到的 data 就是所有存在的组合情况. 初始化完成后想要判断一个SKU key 是否存在, 只需判断 data[key] 是否存在.

参考文章

0%