SKUアルゴリズム検討(Android版)
8686 ワード
二年前にタオバオUIDオープンソースのskyuアルゴリズム(js実現)を見ましたが、その時は落ち着いて詳しく研究していませんでした.一見難しいと思います.この二日間、何気なくgithubを探してみました.Javaの実現版を探してみたいです.本当に見つけられました.そこで落ち着いてアルゴリズムの深さを教えてもらいました.
よく考えた後で、やっとその真意を見抜きました.言葉を整理して、理解した内容を記録することにしました.
コアクラスSKU.javaは、バックグラウンドを介して同様の を取得する.私たちがやるべきことは、上のmapのkeyを分割して新しいmapを構成することで、すべての属性グループを得ることと、SKuオブジェクトに対応する(priceとcountを含むオブジェクトをカスタマイズすること)を追加することです.バックグラウンドを属性グループ[3,4,2]にすると、アルゴリズムを通じて[3]、[4]、[2]、[3,4]を得ることになります.そしてこの二次配列の各配列をkeyとして新しいmapを構成する. コア方法
具体的な行列を使ってアルゴリズム全体を説明します.もっとはっきりしているように見えます.
属性セット[3,4,2]を例にとって
SKuKeyAttrs=[3,4,2]に参加します.は、下付き1から配列の最後のビットにループし、 サイクル に預け入れられる.
get CommbFlags
ここで直接に注釈で説明します.
これでやっと
礼を述べる
N.Sunさんがjava githubプロジェクトの住所に翻訳してくれてありがとうございます.
みなさん、ありがとうございます.
以上
よく考えた後で、やっとその真意を見抜きました.言葉を整理して、理解した内容を記録することにしました.
コアクラスSKU.java
public class Sku {
/**
*
*
* @param initData hashMap
* @return ( )
*/
public static Map skuCollection(Map initData) {
//
HashMap result = new HashMap<>();
//
for (String subKey : initData.keySet()) {
BaseSkuModel skuModel = initData.get(subKey);
// ; key
String[] skuKeyAttrs = subKey.split(";");
//
ArrayList> combArr = combInArray(skuKeyAttrs);
//
for (int i = 0; i < combArr.size(); i++) {
add2SKUResult(result, combArr.get(i), skuModel);
}
//
String key = TextUtils.join(";", skuKeyAttrs);
result.put(key, skuModel);
}
return result;
}
/**
* ArrayList
*
* @param skuKeyAttrs key ;
* @return ArrayList
*/
private static ArrayList> combInArray(String[] skuKeyAttrs) {
if (skuKeyAttrs == null || skuKeyAttrs.length <= 0)
return null;
int len = skuKeyAttrs.length;
ArrayList> aResult = new ArrayList<>();
for (int n = 1; n < len; n++) {
ArrayList aaFlags = getCombFlags(len, n);
for (int i = 0; i < aaFlags.size(); i++) {
Integer[] aFlag = aaFlags.get(i);
ArrayList aComb = new ArrayList<>();
for (int j = 0; j < aFlag.length; j++) {
if (aFlag[j] == 1) {
aComb.add(skuKeyAttrs[j]);
}
}
aResult.add(aComb);
}
}
return aResult;
}
private static ArrayList getCombFlags(int len, int n) {
if (n <= 0) {
return new ArrayList<>();
}
ArrayList aResult = new ArrayList<>();
Integer[] aFlag = new Integer[len];
boolean bNext = true;
int iCnt1 = 0;
//
for (int i = 0; i < len; i++) {
aFlag[i] = i < n ? 1 : 0;
}
aResult.add(aFlag.clone());
while (bNext) {
iCnt1 = 0;
for (int i = 0; i < len - 1; i++) {
if (aFlag[i] == 1 && aFlag[i + 1] == 0) {
for (int j = 0; j < i; j++) {
aFlag[j] = j < iCnt1 ? 1 : 0;
}
aFlag[i] = 0;
aFlag[i + 1] = 1;
Integer[] aTmp = aFlag.clone();
aResult.add(aTmp);
if (!TextUtils.join("", aTmp).substring(len - n).contains("0")) {
bNext = false;
}
break;
}
if (aFlag[i] == 1) {
iCnt1++;
}
}
}
return aResult;
}
/**
*
*
* @param result
* @param newKeyList
* @param skuModel
*/
private static void add2SKUResult(HashMap result, ArrayList newKeyList, BaseSkuModel skuModel) {
String key = TextUtils.join(";", newKeyList);
if (result.keySet().contains(key)) {
result.get(key).setStock(result.get(key).getStock() + skuModel.getStock());
result.get(key).setPrice(skuModel.getPrice());
} else {
result.put(key, new BaseSkuModel(skuModel.getPrice(), skuModel.getStock()));
}
}
}
まず大体の考えを言います.{
"1;4":{"price":10,"count":10}
"1;5":{"price":10,"count":20}
"1;7":{"price":10,"count":30}
}
このようなデータ構造.クライアントはデータに基づいて辞書を作成し、HashMapの中に置いています.add2SKUResult()
方法でやったことです.combInArray(String[] skuKeyAttrs)
この方法でやっていることを要約すると、m個の中からn個を取るすべての組み合わせが得られます.簡単に聞こえますか実はそうではない.(黒板を叩く)具体的な行列を使ってアルゴリズム全体を説明します.もっとはっきりしているように見えます.
属性セット[3,4,2]を例にとって
SKuKeyAttrs=[3,4,2]に参加します.
for (int n = 1; n < len; n++) {
ArrayList aaFlags = getCombFlags(len, n);
for (int i = 0; i < aaFlags.size(); i++) {
Integer[] aFlag = aaFlags.get(i);
ArrayList aComb = new ArrayList<>();
for (int j = 0; j < aFlag.length; j++) {
if (aFlag[j] == 1) {
aComb.add(skuKeyAttrs[j]);
}
}
aResult.add(aComb);
}
}
getCombFlags()
は「ラベル」skuKeyAttrs
の「n個の数の組み合わせの結果」に使用される.この文はちょっと分かりにくいです.(ブロガーも言語で説明するのが難しいと思います.-)、詳しく述べます.getCombFlags()
の結果セット、二次配列aaFlags
は、各配列aFlag
を循環させ、aFlag
に値=1がある場合、skuKeyAttrs[ ]
を取り出して結果セットif (aFlag[j] == 1) {
aComb.add(skuKeyAttrs[j]);
}
まず、getCombFlags()
という方法を理解して、この方法を理解したら、クラス全体が90%も理解できます.get CommbFlags
ここで直接に注釈で説明します.
ArrayList aResult = new ArrayList<>();
Integer[] aFlag = new Integer[len];
boolean bNext = true;
/*
* "1"
* = "1" -1
*
* */
int iCnt1 = 0;
//
/*
* n=1:
* aFlag=[1,0,0]
* n=2:
* aFlag=[1,1,0]
*
* */
for (int i = 0; i < len; i++) {
aFlag[i] = i < n ? 1 : 0;
}
aResult.add(aFlag.clone());
while (bNext) {
iCnt1 = 0;
/*
* i =1,i+1 =0 i 1 i 0
*
*
* */
for (int i = 0; i < len - 1; i++) {
if (aFlag[i] == 1 && aFlag[i + 1] == 0) {
/*
* "1"
* */
for (int j = 0; j < i; j++) {
aFlag[j] = j < iCnt1 ? 1 : 0;
}
// aResult
/*
* i i+1
* ( 0 1)
*
* aFlag=[1,0,0]
* i=0:
* aFlag=[0,1,0]
* */
aFlag[i] = 0;
aFlag[i + 1] = 1;
Integer[] aTmp = aFlag.clone();
aResult.add(aTmp);
/*
* len-n , 0
* 1 , n 。
*
* */
if (!TextUtils.join("", aTmp).substring(len - n).contains("0")) {
bNext = false;
}
break;
}
if (aFlag[i] == 1) {
iCnt1++;
}
}
}
コメントを見終わったかもしれませんが、まだ少しぼんやりしています.もう一度整理します.len=3,n=1の場合、私たちが戻ってくる配列は[[1,0,0],[0,1,0],[0,1]です.combInArray
で[3],[4],[2]]を取るとlen=3,n=2となりますが、私たちが戻ってくる配列は[1,1,0],[1,0,1],[0,1,1,1]です.combInArray
で[3,4],[3,2],[4,2]を取ります.getCombFlags()
は、最終的なセットを構成するためにどのような下付きスケーリングを使用するかを教えている.これでやっと
combInArray
の各文の目的が分かりました.他の方法を信じるのも難しくないです.本編もこれ以上説明しなくなりました.私はこのような考えがどのようにして生まれたのかを知りたいです.アルゴリズムの巧妙さを感嘆しなければならないし、本編を見ている人にも教えてほしいです.礼を述べる
N.Sunさんがjava githubプロジェクトの住所に翻訳してくれてありがとうございます.
みなさん、ありがとうございます.
以上