范围选择的优化代码

Question

给定一个数组和另外两个数组，我需要在第一个数组中找到元素的范围。

例如MainArray={2,4,6,5,8,9}，range1={4,5,6}，range2={6,9,8}

对于第一次迭代，我必须在MainArray中选择范围为4,6 ->4,6,5 -3的元素。

对于第二次迭代，我必须在MainArray中选择范围为5、9->5、8、9-3的元素。

对于第三次迭代，我必须在MainArray中选择范围为6、8->6、8-2的元素。

数组返回3,3,2

static void Main(string[] args)
    {

        var rng = new Random();

        var result = processFunc(Enumerable.Range(0, 5000000).OrderBy(x => rng.Next()).ToArray(),
            Enumerable.Range(0, 20000).OrderBy(x => rng.Next()).Take(200).ToArray(),
            Enumerable.Range(0, 20000).OrderBy(x => rng.Next()).Take(200).ToArray());
    }
    public static int[] processFunc(int[] scores,int[] l,int[] r)
    {
        IList<int> output = new List<int>();
        for (int i = 0; i < l.Length; i++)
        {
            var bestMatch = scores.Where(x => x >= l[i] && x <= r[i]);
            output.Add(bestMatch.Count());
        }

        return output.ToArray();
    }

当数字很小时，代码运行良好，但一旦它们超过5万，程序就会变慢。如何优化此解决方案？

Answer 1

假设l和r具有相同的长度，请考虑以下方法：

public static int[] processFunc(int[] scores, int[] l, int[] r)
{
    var min = Math.Min(l.Min(z => z), r.Min(z => z));
    var max = Math.Max(l.Max(z => z), r.Max(z => z));

    var grouped = scores.Where(z => z >= min && z <= max).GroupBy(z => z).Select(val => Tuple.Create(val.Key, val.Count())).OrderBy(z => z.Item1).ToList();

    return l.Zip(r, (left, right) =>
    {
        var matching = grouped.Where(z => z.Item1 >= left).TakeWhile(z => z.Item1 <= right);
        return matching.Sum(z => z.Item2);
    }).ToArray();
}

min和max用来忽略不相关的数字(太大或太小)。grouped用于预先计算计数并将其排序。Zip用于对齐l和r值，并将计数相加。

这个解决方案在我的机器上比原始代码快2-3倍(剩下的大部分时间实际上是设置参数，而不是函数本身)。