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

让我们有一些整数短排序数组，我们需要找到等于或大于预定义常量的交集。这是代码，它展示了我想做得更好的地方，然后我可以用文字解释它。问题是速度。我的代码运行非常慢。在 15 个元素数组上大约需要 2000 秒（在我的慢速机器上）。当然，我可以实现自己的交集方法并平行化代码，但它提供的改进非常有限。执行时间增长为 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 秒，而旧算法在 2000 个元素上需要 15 秒。井。。。当然还不够快。

//****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());
    }

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

编辑：

一些改进。

//****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
    //*****************//