Optimizing code for range selection

Question

Given an array and two more arrays i need to find the range of elements in the first array

For e.g. MainArray={2,4,6,5,8,9}, range1={4,5,6}, range2={6,9,8}

for First-Iteration i have to select elements in MainArray in range [4,6] ->[4,6,5] --[3] is the output

for second-Iteration i have to select elements in MainArray in range [5,9] ->[5,8,9]--[3] is the output

for third-Iteration i have to select elements in MainArray in range [6,8] ->[6,8]--[2] is the output

array returned [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();
    }

The code runs fine when numbers are small but once they >50,000 the program becomes slow. How can I optimize this solution ?

`for First-Iteration i have to select elements in MainArray in range [4,6] ->[4,6,5] --[3] is the output` Why is 3 the output? — mjwills, Dec 11 '17 at 03:03
Are you sure you've chosen the best way to accomplish your task? What, at a slightly higher level, are you trying to do? — Rufus L, Dec 11 '17 at 03:12
What if Range1 and Range2 are different lengths, or if one of them is null or empty? — Rufus L, Dec 11 '17 at 03:14
Range1 and Range2 will be same length. I want to know if this is the best way ? — Rohit, Dec 11 '17 at 03:15

mjwills · Accepted Answer · 2017-12-11T04:54:12.110

2

Assuming l and r have the same length, consider this approach:

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 and max are used to ignore irrelevant (too large or too small) numbers. grouped is used to pre-calculate the counts and put them in order. Zip is used to line up the l and r values and sum the counts together.

This solution is roughly 2-3 times faster on my machine than the original code (and most of the remaining time being spent is actually setting up the parameters, rather than in the function itself).

edited Dec 11 '17 at 04:54

answered Dec 11 '17 at 03:16

mjwills

23,389
6
40
63

Can you try with `var result = processFunc(new int[] {4,8,7 }, new int[] { 2,4}, new int[] { 8,4});` I am getting keyNotFound error – Rohit Dec 11 '17 at 03:30
When I run your code against `var result = processFunc(new int[] {4,8,7 }, new int[] { 2,4}, new int[] { 8,4});` the output is `{2,1}` that means when we take [2,8] as range we get 2 elements which is wrong because in the range of [2,8] there are 3 elements [4,8,7] – Rohit Dec 11 '17 at 03:50
they must be between two values and they can also be that two values..Does that make sense ?..BTW fantastic solution – Rohit Dec 11 '17 at 03:56

Optimizing code for range selection

1 Answers1