グループ化されたデータと線形データを効率的に照合する方法

Question

例。

私は2つのデータセットを持っています。 linear_dataとgrouped_dataとしましょう。

linear_dataは1 - 1, 1 - 2, 1 - 3, 2 - 3, 2 - 4, 3 - 6と同じです。 （注：表現の目的のために使用される表記法は、注文IDのようなものです「 - 」プロダクトID）

私はgrouped_dataと、このデータと一致する必要が {1 - 1,2,3}, {2 - 3,4}ようなルールが含まれている（注：表現の目的のために使用される表記は「ルールIDのようなものです - "プロダクトIDの注文リスト）

ルールの最大値は4です。いくつかのプロダクトIDにはルールが関連付けられていないことがあります。たとえば。ここでは、プロダクトID 6にはルールが関連付けられていません。

この2つのデータセットを照合し、完全に一致するルールセットを取得したいと考えています。

私の現在の実装では、

new_data = group linear_data by Order ID 
iterate over new_data 
permuted_data = create permutation of all Product Id in current Order 


matched_rules = {} 
for each permuted_data 
    for each group_data 
     if match 
     matched_rules.add(group_data.Rule_Id) 
     end 
    end 
end 

のようなものですが、このシナリオを実装するには、このアプローチの効率的な方法ですか？この問題を解決するのに最適なアルゴリズムは何ですか？

Answer 1

すべての製品IDをルールにマップするマップ（ハッシュマップ、ツリーマップ）を作成します。
マップmyMap = new HashMap <>（）;
例えば例えば{1 - 1,2,3}, {2 - 3,4}マップがどのように見えるルール：linear_dataからレコードごとに、その後

1 -> { 1 } 
2 -> { 1 } 
3 -> { 1, 2 } 
4 -> { 2 } 

と、それはPRODUCTIDだ取る、このPRODUCTIDのためにマップからルールのセットを取得し、ルールの取得したセットを追加matchedRules

new_data = group linear_data by Order ID 
iterate over new_data 
for each record from linear_data { 
    rules = get all rules from map by ProductId => just: rules = myMap.get(productId); 
    matched_rules.addAll(rules) 
} 

へ======編集==============

あなたがすべてのレコードに一致する共通のルールを検索したい場合は、その後、使用Collection#retainAll方法=>https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html#retainAll(java.util.Collection)

ジャスト：

// create a set of all possible rules 
Set<Intereg> allRules = new HashSet<>(); 
for(Integer ruleId: myRules.keys()){ 
    allRules.addAll(myRules.get(ruleId)); 
} 

new_data = group linear_data by Order ID 
iterate over new_data 
for each record from linear_data { 
    rules = get all rules from map by ProductId => just: rules = myMap.get(productId); 
    // matched_rules.addAll(rules) 
    allRules.retainAll(rules); 
} 
// At this point "allRules" contains only rules that match all processed records