3

私はデータマイニングプロジェクトに取り組んでおり、アソシエーションルールタスクにAprioriアルゴリズムを選択しました。簡単に言うと、実行時間は実装方法に満足していません。コードの問題のある部分だけを説明します。

リストのリストが2つあります。

List<List<int>> one;

List<List<int>> two;

リストの要素を反復処理して、がサブセットであるoneかどうかを確認する必要がありますone[i]two[j]

foreach(List<int> items in one)
{

    foreach(List<int> items2 in two)
    {

        if(items2.ContainsSetOf(items1))
        {
            //do something
        }
}

そのようなアプローチの実行時間を短縮する方法があるかどうかを考えていました。（並列実行、辞書の使用など）

どうすればそれを減らすことができるのか、皆さんは何か考えがありますか？

ありがとう！

4

3 に答える 3

4

セットのリストを作成し、セット操作を使用して、別のサブセットのセットかどうかを確認します。

例

HashSet<int> set1 = new HashSet<int>();
set1.Add(1);
set1.Add(2);

HashSet<int> set2 = new HashSet<int>();
set2.Add(1);
set2.Add(2);
set2.Add(3);

List<HashSet<int>> one = new List<HashSet<int>>();
one.add(set1);
one.add(set2);

List<HashSet<int>> two = new List<HashSet<int>>();
two.add(set1);
two.add(set2);

foreach(Set<int> setA in one) {
    foreach(Set<int> setB in two) {
        if(setA.IsSubsetOf(setB)) {
            // do something
        }
    }
}
于 2012-12-02T02:30:24.467 に答える
1

「リストにリストされている」（またはサブセットに設定されている）チェックの数を減らしたい場合、1つの方法は、リストの階層（ツリー）を構築することです。もちろん、パフォーマンスの向上（ある場合）はデータに依存します。どのリストにも他のリストが含まれていない場合は、今のようにすべてのチェックを行う必要があります。

于 2012-12-02T02:58:56.170 に答える
1

C# コード スニペット

var dict = new Dictionary<int, HashSet<List<int>>>();

foreach (List<int> list2 in two) {
   foreach (int i in list2) {
      if(dict.ContainsKey(i) == FALSE) {
         //create empty HashSet dict[i]
         dict.Add(i, new HashSet<List<int>>());
      }
      //add reference to list2 to the HashSet dict[i]
      dict[i].Add(list2); 
   }
}

foreach (List<int> list1 in one) {
   HashSet<List<int>> listsInTwoContainingList1 = null;
   foreach (int i in list1) {
      if (listsInTwoContainingList1 == null) {
         listsInTwoContainingList1 = new HashSet<List<int>>(dict[i]);
      } else {
         listsInTwoContainingList1.IntersectWith(dict[i]);
      }
      if(listsInTwoContainingList1.Count == 0) {   //optimization :p
         break;
      }
   }
   foreach (List<int> list2 in listsInTwoContainingList1) {
      //list2 contains list1
      //do something
   }   
}

例

L2= {
L2a = {10, 20, 30, 40}
L2b = {30, 40, 50, 60}
L2c = {10, 25, 30, 40}
}

L1 = {
L1a = {10, 30, 40}
L1b = {30, 25, 50}
}

コードの最初の部分の後:

dict[10] = {L2a, L2c}
dict[20] = {L2a}
dict[25] = {L2c}
dict[30] = {L2a, L2b, L2c}
dict[40] = {L2a, L2b, L2c}
dict[50] = {L2c}
dict[60] = {L2c}

コードの 2 番目の部分:

L1a: dict[10] n dict[30] n dict[40] = {L2a, L2c}
L1b: dict[30] n dict[25] n dict[50] = { }

SoはとL1aに含まれていますが、どれにも含まれていません。L2aL2cL1b

複雑

アルゴリズムの複雑さに関して、L1hasn1要素、L2hasn2要素、 is のサブリストの要素の平均数、 L1isのサブm1リストの要素の平均数であるL2としm2ます。それで：

  • 元の解決策は O(n1 x n2 x m1 x m2)、containsSetOfO(n1 x n2 x (m1 + m2))メソッドがネストされたループを実行する場合、またはHashSet を使用する場合、せいぜいです。Is7aq のソリューションもO(n1 x n2 x (m1 + m2)).

  • 提案された解決策は次 O(n2 x m2 + n1 x (m1 x nd + n2))のとおりです。ここndで、 はセットの要素の平均数ですdict[i]。

提案されたソリューションの効率は、これに大きく依存しますnd。

  • が大きい場合(すべての整数が のすべてのサブリストの一部である場合) にnd近い場合、元のものと同じくらい遅くなります。n2L2

  • ただし、ndが小さいことが予想される場合 (つまり、 のサブリストがL2互いにまったく異なる場合)、提案されたソリューションは通常、特にn1およびn2が大きい場合にはるかに高速になります。

于 2012-12-04T23:06:57.917 に答える