Two arrays lookup

Question

The task is to return array with values which satisfy the condition: for each max the less or equal numbers count.

Example Input: numbers = [1, 2, 1, 4] maxes = [2, 4]. Output: [3, 4]

Explanation => 1, 2 and 1 are 3 numbers less than or equal to 2, and all 4 numbers satisfy the condition for 4.

Here is my naive approach code in C#, I have a feeling there can be an optimization, and would be thankful to see one:

    static int[] counts(int[] nums, int[] maxes)
    {
        int queries = maxes.Length;
        int numsLength = nums.Length;
        int[] counts = new int[queries];

        for (int i = 0; i < queries; i++)
        {
            for (int j = 0; j < numsLength; j++)
            {
                if (nums[j] <= maxes[i])
                {
                    ++counts[i];
                }
            }
        }

        return counts;
    }

Answer 1

In this case performance depends on the number of maxes. The longer the array the more time it takes to check it and the slower it gets.

As an alternative you can group all numbers first and get their counts. Then just sum the counts of the numbers that meet the criteria.

public static int[] counts2(this int[] nums, int[] maxes)
{
    var counts =
        nums
            .GroupBy(
                n => n,
                (k, items) => (num: k, count: items.Count()))
            .ToArray();

    return
        maxes
            .Select(m =>
                counts
                    .Where(x => x.num <= m)
                    .Sum(x => x.count))
            .ToArray();
}

On my machine the results are:

Number of runs: 10000

Test-1:

nums:  1000
maxes: 10

              OP vs t3chb0t

00:00:00.2005513 <  00:00:00.5321118

Test-2:

nums:  1000
maxes: 100

              OP vs t3chb0t

00:00:02.3541534 >  00:00:01.7438213

Test-3:

nums:  1000
maxes: 1000

              OP vs t3chb0t

00:00:22.9002408 >  00:00:12.8527922

Test-4: with AsParallel()

nums:  1000
maxes: 1000

              OP vs t3chb0t

00:00:22.9081026 >  00:00:03.8906315

Chaining AsParallel() to maxes makes it run even faster.

---

As always with performance: test different solutions before you judge which version is the fastest one because it often depends on many other factors. Using plain loops unwisely does not have to be better the using clever linq.

Answer 2

I would rather see different names

int maxesLength = maxes.Length;

static int[] MaxesCounts  

It is efficient enough just a little hard to follow. You could sort and do a binary search but not sure that would be any more efficient.

static int[] MaxesCounts(int[] nums, int[] maxes)
{
    int[] counts = new int[maxes.Length];
    foreach (int num in nums)
    {
        for (int m = 0; m < maxes.Length; m++)
        {
            if (num <= maxes[m])
            {
                counts[m]++;
            }
        }
    }
    return counts;
}

Answer 3

I'm not sure about performance but using a LINQ query will certainly simplify your algorithm:

static int[] counts(int[] nums, int[] maxes)
{
    return (from int max in maxes
            select nums.Count(x => x <= max)).ToArray();
}