Resolve 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]); 
} 

В этом случае вы не» t даже нужно отсортировать массивы.

Надеется, что это помогает