提高算法执行时间

Question

提高算法执行时间

c#algorithmparallel-processing

3

我正在进行数据挖掘项目，选择了Apriori算法来完成关联规则任务。简单地说，我对我实现的执行时间不满意。我只会描述我的代码中有问题的部分。

我有两个列表的列表。

List> one;

List> two;

我必须遍历列表one的元素，并检查one[i]是否是two[j]的子集。

foreach(List<int> items in one)
{

    foreach(List<int> items2 in two)
    {

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

我在思考是否有办法减少这种方法的执行时间。（并行执行、使用字典等）

你们有什么想法可以实现减少执行时间吗？

谢谢！

- John Latham

3个回答

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}

在代码的第二部分：

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

所以L1a包含在L2a和L2c中，但L1b没有包含在其中。

复杂度

现在关于算法的复杂度，假设L1有n1个元素，L2有n2个元素，L1子列表的平均元素数量为m1，L2子列表的平均元素数量为m2。那么：

原始解决方案为：O(n1 x n2 x m1 x m2)，如果containsSetOf方法使用嵌套循环，则最好的情况是O(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很大——接近n2（当每个整数都是L2的每个子列表的一部分时），那么它的速度就像原始算法一样慢。
然而，如果预计nd很小（即L2的子列表彼此非常不同），则所提出的解决方案通常会快得多，特别是当n1和n2很大时。

- i.adri

1

如果您想减少“列表是否在列表中”（或集合是否为子集）的检查次数，一种方法是构建列表的层次结构（树）。当然，性能改进（如果有的话）取决于数据 - 如果没有任何列表包含其他列表，则必须像现在一样进行所有检查。

- Igor

谢谢，伊戈尔。我也在考虑一些类似的方法。但我仍然希望能够在O(N)的时间内完成它。 - John Latham

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Isaac · Accepted Answer

将它们转化为集合列表，利用集合操作来判断一个集合是否是另一个集合的子集或超集。

示例

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
        }
    }
}