解決System.OutOfMemoryException

Question

我們需要找到幾個整數排序數組的交集。 這裏是例子：

例子：

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 elementsCount = 10000; 
    var random = new Random(123); 

    // Numbers of each array are unique 
    var sortedArrays = Enumerable.Range(0,elementsCount) 
    .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*****// 

    // This number(max value which array can contains) is known. 
    // Ofcourse we can use dictionary if donnt know maxValue 
    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); 
     } 
    } 


    var resultMatrix = new List<int>[sortedArrays.Count,sortedArrays.Count]; 

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

      for (int k = 0; k < reverseIndexDict[sortedArraysij].Count; k++) 
      { 
       if(resultMatrix[i,reverseIndexDict[sortedArraysij][k]]==null) resultMatrix[i,reverseIndexDict[sortedArraysij][k]] = new List<int>(); 

       resultMatrix[i,reverseIndexDict[sortedArraysij][k]].Add(sortedArraysij);  

      } 
     } 
    } 


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

    sw.Stop(); 

    Console.WriteLine(sw.Elapsed); 

但我的代碼是摔倒與OutOfMemoryException異常時，元素數是高於約10000我怎樣才能提高我的算法或什麼我可以做的來解決這個問題？

Answer 1

使用Distinct方法是這樣的：

... 
var theDistinctListOfInts = new List<int>(); 
foreach(var listOfInts in theListsOfInts) 
{ 
    theDistinctListOfInts = theDistinctListOfInts.Intersect(listOfInts); 
} 
... 

Answer 2

在你知道的最大整數的情況下，陣列可以有你可以做到以下幾點：

var histoMatrix = new int[1000]; // the max number in arrays is 1000 here 

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

     histoMatrix[sortedArraysij]++; 
    } 
} 

var resultMatrix = new List<int>(); 

for (int i = 0; i < 1000; i++) 
{ 
    if (histoMatrix[i] == sortedArrays.Count) 
     resultMatrix.Add(histoMatrix[i]); 
} 

在這種情況下，你不」甚至不需要對數組進行排序。

希望它能幫助的