查找已排序的整数数组的交集组

Question

让我们来看看一些整数短排序数组，我们需要找到交集等于或多于预定义的常量。 这里是代码，它演示了我想做得更好，然后我可以用文字来解释它。 问题在于SPEED。我的代码工作非常缓慢。在2000元素阵列上（大约需要15秒）（在我的慢速机器上）。当然，我可以实现自己的交集方法并且平行代码，但是它提供了非常有限的改进。执行时间增长为N^2或某些事情，并且已经用于500k阵列需要非常长的时间。那么我怎样才能改写算法来获得更好的性能呢？我不是限制c＃语言，也许CPU或GPU对这样的工作有很好的特别指示。

Example: 

Input: 
1,3,7,8 
2,3,8,10 
3,10,11,12,13,14 

minSupport = 1 

Output: 

1 and 2: 2, 8 
1 and 3: 3 
2 and 3: 3, 10 

---

var minSupport = 2; 
    var random = new Random(DateTime.Now.Millisecond); 

    // Numbers is each array are unique 
    var sortedArrays = Enumerable.Range(0,2000) 
    .Select(x => Enumerable.Range(0,30).Select(t => random.Next(1000)).Distinct() 
    .ToList()).ToList(); 
    var result = new List<int[]>(); 
    var resultIntersection = new List<List<int>>(); 

    foreach (var array in sortedArrays) 
    { 
     array.Sort(); 
    } 

    var sw = Stopwatch.StartNew(); 

    //****MAIN PART*****// 

    for (int i = 0; i < sortedArrays.Count-1; i++) 
    { 
     for (int j = i+1; j < sortedArrays.Count; j++) 
     { 
      var intersect = sortedArrays[i].Intersect(sortedArrays[j]).ToList(); 
      if(intersect.Count()>=minSupport) 
      { 
       result.Add(new []{i,j}); 
       resultIntersection.Add(intersect); 
      } 
     } 
    } 

    //*****************// 

    sw.Stop(); 

    Console.WriteLine(sw.Elapsed); 

编辑：

现在只需要大约9秒对15秒与旧算法2000米的元件。那么......它的速度不够快。

//****MAIN PART*****// 

    // This number(max value which array can contains) is known 
    var maxValue = 1000; 

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

    for (int i = 0; i < maxValue; i++) 
    { 
     reverseIndexDict[i] = new List<int>(); 
    } 

    for (int i = 0; i < sortedArrays.Count; i++) 
    { 
     for (int j = 0; j < sortedArrays[i].Count; j++) 
     { 
      reverseIndexDict[sortedArrays[i][j]].Add(i); 
     } 
    } 

    var tempArr = new List<int>(); 
    for (int i = 0; i < sortedArrays.Count; i++) 
    { 
     tempArr.Clear(); 
     for (int j = 0; j < sortedArrays[i].Count; j++) 
     { 
      tempArr.AddRange(reverseIndexDict[j]); 
     } 

     result.AddRange(tempArr.GroupBy(x => x).Where(x => x.Count()>=minSupport).Select(x => new[]{i,x.Key}).ToList()); 

    } 

    result = result.Where(x => x[0]!=x[1]).ToList(); 


    for (int i = 0; i < result.Count; i++) 
    { 
     resultIntersection.Add(sortedArrays[result[i][0]].Intersect(sortedArrays[result[i][1]]).ToList()); 
    } 



    //*****************// 

编辑：

一些improvent。

//****MAIN PART*****// 

    // This number(max value which array can contains) is known 
    var maxValue = 1000; 

    var reverseIndexDict = new List<int>[maxValue]; 

    for (int i = 0; i < maxValue; i++) 
    { 
     reverseIndexDict[i] = new List<int>(); 
    } 

    for (int i = 0; i < sortedArrays.Count; i++) 
    { 
     for (int j = 0; j < sortedArrays[i].Count; j++) 
     { 
      reverseIndexDict[sortedArrays[i][j]].Add(i); 
     } 
    } 



    for (int i = 0; i < sortedArrays.Count; i++) 
    { 
     var tempArr = new Dictionary<int, List<int>>(); 

     for (int j = 0; j < sortedArrays[i].Count; j++) 
     { 
      var sortedArraysij = sortedArrays[i][j]; 


      for (int k = 0; k < reverseIndexDict[sortedArraysij].Count; k++) 
      { 
       if(!tempArr.ContainsKey(reverseIndexDict[sortedArraysij][k])) 
       { 
        tempArr[reverseIndexDict[sortedArraysij][k]] = new[]{sortedArraysij}.ToList(); 
       } 
       else 
       { 
        tempArr[reverseIndexDict[sortedArraysij][k]].Add(sortedArrays[i][j]); 
       } 

      } 
     } 


     for (int j = 0; j < reverseIndexDict.Length; j++) 
     { 
      if(reverseIndexDict[j].Count>=minSupport) 
      { 
       result.Add(new[]{i,j}); 
       resultIntersection.Add(reverseIndexDict[j]); 
      } 
     } 

    } 

    // and here we are filtering collections 

    //*****************// 

Answer 1

解决办法有两个：

1. 让我们假设你有3个排序的数组，你必须找到两者之间的交集。遍历第一个数组，并在第一个数组中的元素的其余两个数组上运行二分搜索。如果两个列表上的相应二进制搜索结果为正，则增加相交计数器。

   result = List 
   for element in Array1: 
       status1 = binarySearch(element, Array2) 
       status2 = binarySearch(element, Array2) 
       status = status & status 
       if status == True: 
        count++ 
        if count == MAX_INTERSECTION: 
         result.append(element) 
         break 
   

   时间复杂度：N * M *日志（N），
   其中，
   N =元件的阵列中的数
   M =阵列数量

2. 此解决方案仅当数组中的数字是正整数。计算所有排序数组中所有元素的最大值和最小值。当它被排序时，我们可以通过调查给出的排序数组的开始和结束元素来确定它。让最大的数字是最大的，最小的数字是最小的。创建一个大小为max - min的数组，并用零填充。让我们假设你有3个数组，现在开始遍历第一个数组，并且转到相应的索引并增加先前创建的数组中的值。如下所述：

   element is 5 in Array 1, the New_array[5]+=1 
   

   遍历所有三个排序列表并执行上述操作。最后遍历new_array并查找等于3的值，这些索引是交集结果。
   
   时间复杂度：O（N）+ O（N）+ .. = O（N）
   空间复杂度：O（maximum_element - minimum_element）
   其中，
   N =阵列中元素的个数。