1
\$\begingroup\$

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;
    }
\$\endgroup\$
  • \$\begingroup\$ The code gives no idea what it is supposed to accomplish. You didn't state what you are trying to achieve, other than meeting the requirements stated. \$\endgroup\$ – greybeard Jun 4 '18 at 6:10
  • 2
    \$\begingroup\$ Entire method can be replaced with return maxes.Select(max => nums.Count(n => n <= max)); \$\endgroup\$ – Jesse C. Slicer Jun 4 '18 at 16:03
  • \$\begingroup\$ Are there any boundaries? Like whats the maximum number of items that nums and maxes can contain? \$\endgroup\$ – kuskmen Jul 5 '18 at 19:36
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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;
}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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();
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ About performance, LINQ is pretty much always slower than the equivalent code using loops. It's also more memory intensive than iterating an array. \$\endgroup\$ – Alejandro Jun 12 '18 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.