C# How to make recursive function to return the nth most common integer in an array of integers

Question

I am using c# and I am looking for the most memory efficient way to sort a list of integers by how often they appear in an integer array and then return the nth array element where nth is an integer represent the descending order key of choice (most used integer, 2nd most used integer, 3rd most used integer, etc.

I can do this using linq with something like this...

public static void Main(string[] args)
{
    int x = NthMostCommon(new int[] { 5, 4, 3, 2, 1, 5, 4, 3, 2, 5, 4, 3, 5, 4, 5 }, 2);
    Console.WriteLine(x);
}

private static int NthMostCommon(int[] a, int k)
{
    int result = 0;
    var query = a.GroupBy(item => item).OrderByDescending(g => g.Count());
    if (query.Count() >= k)
    {
        result = query.ElementAt(k - 1).Key;
    }
    return result;
}

This works, but I have been told that this is not the most memory efficient way of getting the desired result when working with larger integer arrays. I cannot see how I can reduce the memory footprint. I have to iterate the entire array, regardless of the size. Yes?

Any ideas?

Thanks in advance.

Well, i think this is just a question about sorting algorithms. There is a extensive literature on that field, and i think this question exceeds SO purpose. — Pikoh
– Pikoh, Commented Oct 11, 2016 at 7:05
I don't think there's any simple to express recurrent relationship between the i-th most common and the i + 1 most common. — Christo S. Christov
– Christo S. Christov, Commented Oct 11, 2016 at 7:23
I think the memory bloat actually comes from GroupBy, on the other hand I don't believe recursive operation would be more efficient (on the contrary even). — Martheen
– Martheen, Commented Oct 11, 2016 at 7:25
The comment I get back from the reviewer is that the code uses too much memory when ran against a large number of elements in the array. I am supposed to analyze how the code allocates and deallocates memory during execution. I just do not see how to make it more memory effectient. — Dave Adler
– Dave Adler, Commented Oct 11, 2016 at 14:52
What is the point of the function being "recursive"? Can that requirement be eliminated? — user2864740
– user2864740, Commented Oct 15, 2016 at 23:10

Liu · Accepted Answer · 2016-10-15 22:52:30Z

This article may help you.

http://www.developerfusion.com/article/84468/linq-to-log-files/

the most common integer could be more than 1 integer (see the int array in my code), so I make the function to return int[] instead of just int.

I also have GroupBy which in worst case (identical integer in the input array) could be the same efficient as the previous one. You may also be able to rewrite it.

    public static void Main(string[] args)
    {
        int[] x = NthMostCommon(new int[] { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6 }, 2);
        Console.WriteLine(x);
    }

    private static int[] NthMostCommon(int[] a, int k)
    {

        var query = GroupAndCount(a)
            .GroupBy(x => x.Value)
            .ToDictionary(x => x.Key, x => x.Select(n => n.Key))
            .OrderByDescending(x => x.Key);
        if (query.Count() >= k)
        {
            return query.ElementAt(k-1).Value.ToArray();
        }
        return null;
    }

    public static IEnumerable<KeyValuePair<T, int>> GroupAndCount<T>
    (IEnumerable<T> source)
    {
        Dictionary<T, int> dictionary =
            new Dictionary<T, int>();
        foreach (T element in source)
        {
            if (dictionary.ContainsKey(element))
            {
                dictionary[element]++;
            }
            else {
                dictionary[element] = 1;
            }
        }
        return dictionary;
    }

Community · Accepted Answer · 2020-06-20 09:12:55Z

0

Where k << n and 0 < x < k, where x is an integer, start with a Counting Sort and modify it.

A counting sort takes O(n + k) memory and O(n + k) time.

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence.

Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.

After the items are sorted according to frequency it's simply a matter of walking the result.

If there is really a "requirement" to be recursive the procedural loop code can be converted into recursive calls, at the expense of stackframes. Using LINQ - which provides various higher-order functions - often trivial eliminates the need for recursion.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Oct 15, 2016 at 23:13

user2864740

62.5k15 gold badges159 silver badges234 bronze badges

1 Comment

Dave Adler Over a year ago

recursive requirement can be eliminated as it was a suggestion but it does not seem to have merit here.

Collectives™ on Stack Overflow

C# How to make recursive function to return the nth most common integer in an array of integers

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related