淘宝sku算法浅析
最近项目遇到了一个难题，就是模仿淘宝上的选择规格，首先我先来解释下什么是sku，sku（Stock Keeping Unit 库存量单位）即库存进出计量的基本单元，可以是以件，盒，托盘等为单位。sku这是对于大型连锁超市DC（配送中心）物流管理的一个必要的方法。上面的话可能你们没有听懂是什么意思,具体请打开手淘，选择服装类的产品（由于服装类的产品可选规格较多，比较容易进行比较）。
当时项目开始并不是采用这个sku算法，而是采用遍历查询的方式,将所有结果进行拆分，拆分成几个不同属性的集合；例如颜色、内存、大小等；然后通过用户点击按钮，去遍历后台有无包括这种规格的商品（除了库存为0）；如果没有则把按钮变成灰色（即改变状态）；让我们来分析下这种方案的优缺点。
尺寸：5.0寸、4.5寸
型号：土豪金、红、黑
内存：128G、64G
image.png
后台可选的规格：
[
["4.5寸", "红", "64G"],
["5.0寸", "土豪金", "128G"], //
["5.0寸", "黑", "128G"]
]
现在这几种类型一共有2 * 3 * 2 = 12种排列组合，然而只有3种组合是正确的（其中还要排除库存为0的情况）一开始先保存好每一个按钮和每一列的位置进入一个List<List<TagEnable>> 的数组中，TagEnable记录着每一个按钮的状态（0代表者正常，1代表选中，2代表不可选（库存为0||无规格））；然后当用户点击的时候，用Map<Integer,String> 记录选中的按钮和文字；并把每一个按钮先设置为不可点击，之后根据文字去对按钮进行设置状态。
这种算法是比较直接的一种实现，但是很繁琐，循环嵌套循环，可以简单分析下算法复杂度，如果sku属性组合元素的总和数用m来表示，可选的数据的长度是n的话，那么算法的步骤大概是m*n，这看起来好像不怎么复杂；不过，每次判断一个sku组合是否和result中的 组合匹配，却不是一个简单的过程，实际上，这可以看做是一个字符串匹配的一个算法了， 最简单的还是使用正则匹配，m * n次正则匹配，这样就不怎么快了吧。正则表达式很不稳定，万一sku组合中有一些特殊字符，就可能导致一个正则匹配没能匹配到我们想要的表达式。
而且，当用户全部选中的时候，根据这种算法，只会出现一种情况，就是未选中的全部都变成不可选（即变成灰色），这大大影响了用户的体验。如下图：
第一种方案
sku算法是利用数学的集合思想来写的。即先把可能的排列组合列出来，即取出集合中的所有子集，数学上叫做幂集。
就是如果第一条数据["5.0寸", "黑", "128G"]可选，
那么以下的组合肯定存在：
- 5.0寸
- 黑
- 128G
- 5.0寸、黑
- 5.0寸、128G
- 黑、128G
- 5.0寸、黑、128G
所以，我们可以利用sku算法取出所有的组合，再根据这些组合的集合，记为U，去判断用户点击按钮时，去设置其他按钮的状态；
集合U.png
例如：当用户进行如下的选择：5.0寸、128G
那么如何判断 4.5寸这个按钮的状态呢？只需判断4.5寸、128G是否可选（集合U是否存在（4.5寸-128G）这个组合并且库存不为0），以此类推：
4.5寸: U是否包含于 4.5寸-128G false
土豪金: U是否包含于 5.0寸-土豪金-128G true
红: U是否包含于 5.0寸-红-128G false
黑: U是否包含于 5.0寸-黑-128G true
64G: U是否包含于 5.0寸-64G false
于是乎，我们可以得出下列的结果：
图3.png
优化：
在使用淘宝的过程中，我发现他们可以根据用户选择按钮的唯一值确定图像（例如在这案例中，颜色是唯一的），当用户只选择唯一值时，便可以确定其图像
图4.png
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < mUiData.getAdapters().size(); i++) {
if (mUiData.getAdapters().get(i).getCurrentSelectedItem()!=null)
stringBuilder.append(mUiData.getAdapters().get(i)
.getCurrentSelectedItem().getAttributeMemberId()+";");
}
if (stringBuilder.length()!=0) {
List<String> pricelist = new ArrayList<String>();
for (Map.Entry<String, BaseSkuModel> entry : mUiData.getResult().entrySet()) {
// System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
if (mUiData.getSelectedEntities().size() == 1) {
if (entry.getKey().contains(stringBuilder.toString())) {
pricelist.add(entry.getValue().getPicture());
}
} else {
if (entry.getKey().contains(stringBuilder.substring(0, stringBuilder.length() - 1).toString())) {
pricelist.add(entry.getValue().getPicture());
}
}
}
List<String> newlist = ifRepeat(pricelist);
BaseSkuModel baseSkuModel = new BaseSkuModel();
if (newlist.size() == 1) {
// Toast.makeText(MainActivity.this,""+,Toast.LENGTH_SHORT).show();
baseSkuModel.setPicture(newlist.get(0));
baseSkuModel.setPrice(mUiData.getBaseSkuModel().getPrice());
baseSkuModel.setFormatNum(mUiData.getBaseSkuModel().getFormatNum());
baseSkuModel.setStock(mUiData.getBaseSkuModel().getStock());
} else {
baseSkuModel = mUiData.getBaseSkuModel();
}
mUiData.setCurrentskumodel(baseSkuModel);
}else{
mUiData.setCurrentskumodel(mUiData.getBaseSkuModel());
}
做法是这样子的：先遍历原始数据，如果用户选择的组合在原数据中是唯一的话，则可以确定其图像。
