SKU多次元属性状態判定アルゴリズム

問題の説明

この問題は、製品属性を選択するシナリオから発生します。たとえば、服や靴を購入するときは、通常、適切な色、サイズ、その他の属性を選択する必要があります。

まずSKUの学術的概念を理解しましょう

最小在庫管理単位 (SKU) は会計用語で、在庫管理で使用可能な最小単位として定義されます。たとえば、繊維製品の場合、SKU は通常、仕様、色、スタイルを表しますが、チェーン小売店では、単一の製品が SKU と呼ばれることもあります。最小在庫管理単位は、異なる商品の最小販売単位を区別できます。これは、商品の調達、販売、物流、財務管理の科学的管理、および POS および MIS システムのデータ統計の要件です。通常、管理情報システムのコードに対応します。 —— Wikipedia より最小在庫管理単位

簡単に言うと、上記の例を組み合わせると、SKUはショッピングサイトで購入する最終製品であり、上記の画像で選択された対応する属性は、色は黒、サイズは37です。

まず、バックエンドのデータ構造を見てみましょう。一般的には次のようになります。線形配列で、各要素は現在の SKU を記述するマップです。例:

 [
   { "色" : "赤" 、 "サイズ" : "ラージ" 、 "モデル" : "A" 、 "SKUID" : "3158054" },
   { "色" : "白" 、 "サイズ" : "中" 、 "モデル" : "B" 、 "SKUID" : "3133859" },
   { "色" : "青" 、 "サイズ" : "小" 、 "モデル" : "C" 、 "skuId" : "3516833" }
 ]

当然、フロントエンドに表示するときにはグループ化する必要があります。その目的は、ユーザーが属性ディメンションに基づいて選択できるようにすることです。グループ化されたデータは、おおよそ次のようになります。

 {
 "色" : [ "赤" 、 "白" 、 "青" ],
 「サイズ」 : [ 「大」 、 「中」 、 「小」 ],
 「モデル」 : [ 「A」 、 「B」 、 「C」 ]
 }

ウェブページ上の対応するUIはおそらく次のようになります

このとき、問題が生じます。これらのサブ属性が形成できるセット（ユーザーの選択パス）は、実際に形成できるセットよりもはるかに大きくなります。たとえば、上記の属性セットは、直積に組み合わせることができます。次のシーケンスに組み合わせることができます。

 [
    [ "赤" , "大きい" , "A" ], // ✔
    [ "赤" 、 "大きい" 、 "B" ],
    [ "赤" 、 "大きい" 、 "C" ],
    [ "赤" 、 "真ん中" 、 "A" ],
    [ "赤" 、 "中" 、 "B" ],
    [ "赤" 、 "中" 、 "C" ],
    [ "赤" 、 "小さい" 、 "A" ],
    [ "赤" 、 "小さい" 、 "B" ],
    [ "赤" 、 "小さい" 、 "C" ],
    [ "白" 、 "大きい" 、 "A" ],
    [ "白" 、 "大きい" 、 "B" ],
    [ "白" 、 "大きい" 、 "C" ],
    [ "白" 、 "真ん中" 、 "A" ],
    [ "白" , "真ん中" , "B" ], // ✔
    [ "白" 、 "中" 、 "C" ],
    [ "白" 、 "小さい" 、 "A" ],
    [ "白" 、 "小" 、 "B" ],
    [ "白" 、 "小" 、 "C" ],
    [ 「青」 、 「大きい」 、 「A」 ]、
    [ 「青」 、 「大きい」 、 「B」 ]、
    [ 「青」 、 「大きい」 、 「C」 ]、
    [ 「青」 、 「中」 、 「A」 ]、
    [ 「青」 、 「中」 、 「B」 ]、
    [ "青" 、 "中" 、 "C" ]、
    [ 「青」 、 「小」 、 「A」 ]、
    [ "青" 、 "小" 、 "B" ],
    [ "青" 、 "小さい" 、 "C" ] // ✔
 ]

式によれば、それぞれが 3 つの要素のサブセットである 3 つの要素のセットは、3 の 3 乗の直積、つまり 27 を形成できます。ただし、ソースデータでは 3 つの組み合わせしか形成できません。

この場合、使用できないパスを事前に特定し、グレー表示にしてユーザーに通知するのが最善です。そうしないと、誤解を招くことになります。

ルールを決める

下の図を見てください。現在選択されている製品の属性として red を定義した場合、つまり現在選択されている製品は red-big-A である場合、選択されていない他の属性がオプションのパスを形成できるかどうかをどのように確認できるでしょうか。

ルールは次のとおりです。現在のユーザーが白-大きい-A を選択したいが、この選択パスが存在しない場合は、白をグレー表示します。

同様に、blue 属性が使用可能かどうかを確認する場合は、blue-big-A パスが存在するかどうかを確認する必要があります。

…

回避策

上記のロジックコードによれば、次のようになります。

選択されていないすべての要素をトラバースします: "white", "blue", "medium", "small", "B", "C" すべての属性行をトラバースします: "color", "size", "model" 取得: a) 現在の要素 b) 選択された要素の、現在の要素ではない他の属性 (パスを形成する)

このパスが存在するかどうかを判断します。存在しない場合は、現在の要素をグレー表示します。

a. 問題は解決したようですが…

非常に重要な点を見落としていました。上記の例では白い要素がグレー表示されていますが、実際にはクリック可能です。ユーザーはwhite-middle-Bというパスを選択できるためです。

ユーザーが白をクリックすると、状況はさらに複雑になります。ユーザーが白の要素のみを選択したと仮定します。選択されていない他の要素が選択可能かどうかをどのように判断するのでしょうか。

つまり、「大」、「中」、「小」、「A」、「B」、「C」をグレー表示する必要があるかどうかをどのように判断するのでしょうか。属性内の要素はすべて単一選択であり、現在の属性内の任意の要素が選択可能であるため、「赤」と「青」が選択可能かどうかを確認する必要がないことに注意してください。

問題の大きさを縮小する

まず問題を絞り込みましょう。現在の状況 (白が 1 つだけ選択されている) では、サイズ「大」をグレー表示する必要があることをどのように判断すればよいでしょうか。私たちのロジックによれば、個別に検索する必要があると思われるかもしれません。

ホワイト - ラージ - A
ホワイト - ビッグ - B
ホワイト - 大 - C

存在しない場合は、サイズをグレー表示にすると問題が解決するようです。実際には、これは間違っています。モデルが選択されていないため、white-large が使用可能かどうかのみを知る必要があります。

同時に、別の疑問もあります。選択された項目の数が不確実であり、次元を不確実な数まで増やすことができる場合はどうなるでしょうか?

この場合、以前のアルゴリズムに従うと、実装は非常に複雑になります。今こそ、考え方を変えることを検討する時です。

考え方を調整する

以前は、常に逆の考え方で、グレー表示にして選択できないようにする要素を見つけていました。現在、属性がオプションかどうかを判断する方法を検討しています。さらに、複数の次元の場合、ユーザーはジャンプして選択できます。例えば、ユーザーは2つの要素WhiteとBを選択します。

図1

元のデータを振り返ってみましょう。

 [
   { "色" : "赤" 、 "サイズ" : "ラージ" 、 "モデル" : "A" 、 "SKUID" : "3158054" },
   { "色" : "白" 、 "サイズ" : "中" 、 "モデル" : "B" 、 "SKUID" : "3133859" },
   { "色" : "青" 、 "サイズ" : "小" 、 "モデル" : "C" 、 "skuId" : "3516833" }
 ]
 // 今すぐ
[
   [ "red" , "big" , "A" ], // 存在する
   [ "白" , "中" , "B" ], // 存在する
   [ "青" , "小" , "C" ] // 存在する
]

明らかに、最初のデータ「赤」、「大きい」、「A」が存在する場合、次のサブ組み合わせが存在する必要があります。

赤
大きい
あ
赤 - 大
赤 - A
ビッグ - A
赤 - ビッグ - A

同様に、2 番目のデータ「白」、「中」、「B」が存在する場合、次のサブ組み合わせが存在する必要があります。

白
真ん中
B
ホワイト - ミディアム
ホワイト - B
ミドル - B
ホワイト - ミディアム - B

…

既存のパスのすべてのサブ組み合わせを事前に計算します。これは、アルゴリズムではセットのすべてのサブセットを取得すること、数学ではべき乗セットと呼ばれます。これにより、既存のすべてのパスのテーブルが作成されます。アルゴリズムは次のとおりです。

 /**
 * 集合（べき集合）のすべての部分集合を取得する
 arr = [1,2,3] 
 
     i = 0、ps = [[]]:
         j = 0; j < ps.length => j < 1:
             i=0、j=0 ps.push(ps[0].concat(arr[0])) => ps.push([].concat(1)) => [1]
                      ps = [[], [1]] 
 
     i = 1, ps = [[], [1]] :
         j = 0; j < ps.length => j < 2
             i=1、j=0 ps.push(ps[0].concat(arr[1])) => ps.push([].concat(2)) => [2]
             i=1、j=1 ps.push(ps[1].concat(arr[1])) => ps.push([1].concat(2)) => [1,2]
                      ps = [[], [1], [2], [1,2]] 
 
     i = 2、ps = [[]、[1]、[2]、[1,2]]
         j = 0; j < ps.length => j < 4
             i=2、j=0 ps.push(ps[0].concat(arr[2])) => ps.push([3]) => [3]
             i=2、j=1 ps.push(ps[1].concat(arr[2])) => ps.push([1, 3]) => [1, 3]
             i=2、j=2 ps.push(ps[2].concat(arr[2])) => ps.push([2, 3]) => [2, 3]
             i=2、j=3 ps.push(ps[3].concat(arr[2])) => ps.push([2, 3]) => [1, 2, 3]
                      ps = [[], [1], [2], [1,2], [3], [1, 3], [2, 3], [1, 2, 3]]
 */
関数powerset(arr) {
    var ps = [[]];
 (var i=0; i < arr.length; i++)の場合{
 ( var j = 0, len = ps.length; j < len; j++) {
            ps.push(ps[j].concat(arr[i]));
        }
    }
 psを返します。
 }

この既存のサブセットセットを使用して、たとえば図 1 をもう一度見てみましょう。

図1

赤が利用可能かどうかをどのように判断しますか？赤Bが利用可能かどうかを判断するだけです
中央が利用可能かどうかをどのように判断しますか？白-中央-Bが利用可能かどうかを判断する必要があります
2Gがオプションであることを確認するには？ White-B-2Gがオプションであることを確認する必要があります

アルゴリズムは次のように説明されます。

選択されていないすべての要素を反復処理する

a. すべての属性行を走査する

a) 現在の要素、b) 現在の要素以外の属性で選択された他の要素（現在の属性で選択された要素がない場合はスキップ）を取得してパスを形成します。

このパスが存在するかどうかを確認します（既存のすべてのパステーブルを照会します）。存在しない場合は、現在の要素をグレー表示します。

初期バックエンドデータを例にとると、生成されるオプションのパステーブルは次のようになります。パスをトラバーサルせずに検索できるように、パスは区切り文字 "-" で区切られていることに注意してください。

 {
 "" : {
 "SKU" : [ "3158054" , "3133859" , "3516833" ]
    },
 "赤" ： {
 "SKU" : [ "3158054" ]
    },
 "大きい" ： {
 "SKU" : [ "3158054" ]
    },
 「赤-大」 :{
 "SKU" : [ "3158054" ]
    },
 「あ」 :{
 "SKU" : [ "3158054" ]
    },
 「赤A」 :{
 "SKU" : [ "3158054" ]
    },
 「ビッグA」 :{
 "SKU" : [ "3158054" ]
    },
 「レッドビッグA」 :{
 "SKU" : [ "3158054" ]
    },
 "白" ： {
 "SKU" : [ "3133859" ]
    },
 "真ん中" ： {
 "SKU" : [ "3133859" ]
    },
 「白-真ん中」 :{
 "SKU" : [ "3133859" ]
    },
 「B」 :{
 "SKU" : [ "3133859" ]
    },
 「ホワイトB」 :{
 "SKU" : [ "3133859" ]
    },
 「中B」 ：{
 "SKU" : [ "3133859" ]
    },
 「白-ミドル-B」 : {
 "SKU" : [ "3133859" ]
    },
 "青" ： {
 "SKU" : [ "3516833" ]
    },
 "小さい" ： {
 "SKU" : [ "3516833" ]
    },
 「青-小」 :{
 "SKU" : [ "3516833" ]
    },
 「C」 :{
 "SKU" : [ "3516833" ]
    },
 「ブルーC」 :{
 "SKU" : [ "3516833" ]
    },
 「小文字のC」 :{
 "SKU" : [ "3516833" ]
    },
 「青-小-C」 : {
 "SKU" : [ "3516833" ]
    }
 }

このアルゴリズムをより明確に説明するために、別の図を使って説明しましょう。

したがって、上記のロジックによれば、ステータスを計算した後のインターフェースは次のようになります。

さて、この場合、ユーザーがサイズをクリックした場合、どのように操作すればよいでしょうか?

体験を最適化する

現状ではパス red-middle-A が存在しないため、middle をクリックすると、サイズ middle 以外の他の属性の少なくとも 1 つがパス middle に存在しません。

対話型の要件は、現在の属性行が存在しない場合はそれを強調表示し、ユーザーが既存の属性と組み合わせることができる属性を選択できるようにすることです。ユーザーが選択した属性は一度キャッシュされる必要がある

したがって、存在しない属性をクリックすると、インタラクションフローは次のようになります。

現在の属性が存在するかどうかに関係なく、まず現在の属性を強調表示（選択）します。
選択した他の属性をすべてクリア
現在のステータスの下にある他の属性のオプションステータスを更新します (現在の属性のみを選択します)
非現在の属性行の他の属性を走査して、キャッシュ内の対応する選択された属性を検索します。
対応する属性がキャッシュ内に存在する場合 (オプション)、キャッシュ属性がデフォルトで選択され、その他のオプションの状態が再度更新されます。存在しない場合は、現在の属性行が強調表示されます（暗い背景）

このプロセスのフローチャートはおおよそ次のようになります。存在しない属性をクリックすると、「単一選択プロセス」に入ります。

バックエンドデータが次のようになっていると仮定します。

 [
   { "色" : "赤" 、 "サイズ" : "ラージ" 、 "モデル" : "A" 、 "SKUID" : "3158054" },
   { "color" : "white" , "size" : "large" , "model" : "A" , "skuId" : "3158054" }, // アイテムをもう 1 つ追加しました
   { "色" : "白" 、 "サイズ" : "中" 、 "モデル" : "B" 、 "SKUID" : "3133859" },
   { "色" : "青" 、 "サイズ" : "小" 、 "モデル" : "C" 、 "skuId" : "3516833" }
 ]

現在選択されている状態は、白-ビッグ-Aです。

ユーザーがクリックした場合。この時点では、White-Middle は存在しますが、Middle-A は存在しないため、色は白のままにして、モデル属性行を強調表示します。

ホワイトミディアムとマッチできるモデルはBのみであることがわかります。キャッシュの役割は、ユーザーが色を選択する頻度を減らすことです。この時点で、主な機能は基本的に達成されています。例えば、在庫ロジックの処理方法は、属性が存在しないときと同じなので、詳細は説明しません。注意すべき唯一の点は、パワーセットを見つけることの複雑さです。

アルゴリズムの複雑さ

べき乗集合アルゴリズムの時間計算量は O(2^n) です。つまり、各データの属性 (次元) が多いほど、計算量も高くなります。 SKUデータの量は重要ではありません。これは一定の線形成長ですが、ディメンションは指数関数的に増加するためです。

 {1} 2^1 = 2
 => {},{1}
 {1,2} 2^2 = 4
 => {},{1},{2},{1,2}
 {1,2,3} 2^3 = 8
 => {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}
 ...

Chrome でいくつかのテストケースを実行した後、このアルゴリズムは非常に非効率的であることがわかります。このアルゴリズムを使用する場合は、次元を合理的な範囲内で制御する必要があります。アルゴリズムの時間計算量が非常に高いだけでなく、生成されるパステーブルも非常に大きくなり、対応するメモリ使用量も高くなります。

たとえば、10 次元の SKU がある場合、結果のパステーブルには 2^10 (1024) 個のキー/値のペアが含まれます。

最終的なデモは、こちらでご覧いただけます: sku 多次元属性ステータス判定

関連情報: SKU 組み合わせクエリアルゴリズムの調査

[この記事は51CTOコラムニストの周其立氏によるオリジナル記事です。転載の際は出典を明記してください。]

この著者の他の記事を読むにはここをクリックしてください

<<: Java 配列から HashMap へのアルゴリズムの説明

>>: Tofsee ボットネットは独自のドメイン名生成アルゴリズムを使用する