解决系统内存不足异常

本文关键字：异常 内存不足 系统 解决 | 更新日期: 2023-09-27 18:36:35

我们需要找到几个整数排序数组的交集。下面是示例：

例：

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);

但是我的代码在元素计数超过 10000 时因内存不足异常而下降。如何改进我的算法或可以做些什么来解决此问题？

解决系统内存不足异常

使用 Distinct 方法如下：

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

如果您知道数组可以具有的最大整数数，则可以执行以下操作：

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

在这种情况下，您甚至不需要对数组进行排序。

希望对你有帮助

相关文章：