改进嵌套循环的性能

本文关键字：性能 嵌套循环 | 更新日期: 2023-09-27 18:17:51

这个逻辑是要在数组中找到n到n + 5之间包含数组中最多数字的数字n。我想出了一个解决方案，但它需要一个嵌套循环，因此它有点慢。有什么方法可以提高它的性能吗?提前谢谢。

保证数组已排序。

int[] myArray = new int[]{1,2,4,5,7,9,15,19};
int bestNumber = 0;
int MaxMatchFound = 0;
for (int o = 0; o < myArray.Length; o++)
{
    int TempMatchFound = 0;
    for (int i = 0; i < myArray.Length; i++)
    {
        if (myArray[i] >= myArray[o] && myArray[i] <= (myArray[o] + 5))
        {
            TempMatchFound++;
        }
    }
    if (TempMatchFound > MaxMatchFound)
    {
        bestNumber = myArray[o];
        MaxMatchFound = TempMatchFound;
    }
}
return bestNumber;

改进嵌套循环的性能

将值存入桶中，然后循环v的值，并对满足v <= w <= v + 5的所有w的值求和，然后找到最大计数:

var buckets = myArray.GroupBy(n => n)
                     .ToDictionary(g => g.Key, g => g.Count());
var rangeCounts = 
    buckets.Keys
           .Select(v =>
               new {
                   Value = v,
                   Count = Enumerable.Range(0, 6)
                                     .Sum(i => buckets.ContainsKey(v + i) ? 
                                               buckets[v + i] : 
                                               0
                                         )
               }
    );
var bestRange = rangeCounts.MaxBy(x => x.Count);

现在，bestRange.Value是最佳范围的起点，bestRange.Count是落在[bestRange.Value, bestRange.Value + 5]范围内的元素数量。这里，我使用MaxBy。

认为这可以获得线性性能。Building dictionary是线性的，Building rangeCounts是线性的，MaxBy是线性的。

这就对了:它运行在O(N)时间和O(1)内存中。这形成了其他解决方案中描述的桶，然后在遍历数组时丢弃它们。Queue用于跟踪哪些bucket是"活动的"，因为它们可以被添加到其中。Dictionary中的条目永远不会超过6个，Queue也不会。

int[] myArray = new int[]{1,2,4,5,7,9,15,19};
Dictionary<int, int> counts = new Dictionary<int, int>();
Queue<int> q = new Queue<int>();
int n = 0;
int currentMaxCount = 0;

for(int i = 0; i < myArray.Length; i++)
{
    var currentNum = myArray[i];
    if(counts.ContainsKey(currentNum))
    {
        counts[currentNum]++;
    }
    else
    {
        counts[currentNum] = 1;
        q.Enqueue(currentNum);
    }
    for(int j = 1; j <= 5; j++)
    {
        if(counts.ContainsKey(currentNum - j))
            counts[currentNum - j]++;
    }
    if(q.Peek() + 5 < currentNum)
    {
        if(counts[q.Peek()] > currentMaxCount)
        {
            currentMaxCount = counts[q.Peek()];
            n = q.Peek();
        }
        counts.Remove(q.Dequeue());
    }
}
while(q.Count > 0)
{
    if(counts[q.Peek()] > currentMaxCount)
    {
        currentMaxCount = counts[q.Peek()];
        n = q.Peek();
    }
    counts.Remove(q.Dequeue());
}
Console.WriteLine("There are {0} matches between {1} and {2}", currentMaxCount, n, n + 5);

这是一个O(n)的解决方案，无论范围如何，都使用O(1)个额外空间。

它只遍历数组一次，总是进行2N次比较。我看不出有任何方法可以改进这个算法，尽管确实有一些微优化可以从实现中挤出更多的速度。

private int FindRange(int[] myArray)
{
    const int range = 5;
    int start = 0;
    int maxMatchFound = 0;
    int maxIndex = 0;
    for (int i = 0; i < myArray.Length; ++i)
    {
        if (myArray[i] > myArray[start] + range)
        {
            int matchLength = i - start;
            if (matchLength > maxMatchFound)
            {
                maxMatchFound = matchLength;
                maxIndex = start;
            }
            // move forward until within range
            do
            {
                ++start;
            } while (myArray[i] > myArray[start] + range);
        }
    }
    // Final check, from myArray[start] to end of array
    int len = myArray.Length - start;
    if (len > maxMatchFound)
    {
        maxMatchFound = len;
        maxIndex = start;
    }
    return maxIndex;

这里的想法是，如果一个特定的数字a[x]落在a[i]的范围内，那么它将落在a[i+1]的范围内，假设x > i。(所以在原始数组中，a[3]的值落在a[0]的范围内，所以它也会落在a[1]和a[2]的范围内)。

因此索引i被递增，直到它引用的值超出a[start]的范围。然后，start被增加，直到a[i]再次进入范围。这两个索引以交替的方式在数组中向前移动。

这是一行LINQ选项。在性能方面不是最好的(它迭代多次)。仍然值得注意。

var result = myArray
             .OrderByDescending(i => myArray.Count(i2 => i2 >= i && i2 <= i + 5))
             .First();
相关文章：