CODEWITHSUNDEEP
c#
Nate
Nate

Reputation: 2326

Max average series in ordered list

I'm trying to get the greatest average values for different duration in a list.

Let's say I have the following data: 

var randomList = new List<int>();
var random = new Random(1969);

for (var i = 0; i < 10; i++)
{
    randomList.Add(random.Next(0, 500));
}

That produces the following list:

190
279
37
413
90
131
64
129
287
172

I'm trying to get the highest average values for the different sets 0-9.

Set 0 (one item in a row) = 413 (index 3)

Set 1 (two items in a row) = 252 (average index 3,4)

Set 9 (10 items in a row) = 179 (average of the entire list)

I've been beating my head on this a while. I'm trying to find an efficient way to write this so I have the least traversals as possible. In production, I'll have lists with 3500-6000 points.

How do I find the highest average values for the different sets 0-9?

Upvotes: 1

Views: 90

Answers (2)

active92
active92

Reputation: 654

In your comment, you mentioned Avg(items:0,1,2) vs Avg(items:1,2,3) vs Avg(items:2,3,4)

Not sure if this is what you want but I came up with this.

First, get random number, then get average of 3 numbers. Then, get the largest average value. 

    static void Main(string[] args)
    {
        var randomList = new List<int>();
        var random = new Random(1969);
        int TotalRandomNumber = 10; //Change this accordingly
        for (var i = 0; i < TotalRandomNumber ; i++)
        {
            randomList.Add(random.Next(0, 500));
        }

        foreach (var item in randomList)
        {
            Console.WriteLine("Random Number: " + item);
        }

        var AveNum = new List<double>();
        int range = 3; //Change this for different range
        for (int i = 1; i < TotalRandomNumber - range; i++)
        {
            var three = randomList.GetRange(i, range);
            double result = three.Average();
            Console.WriteLine("Average Number: " + result);
            AveNum.Add(result);
        }

        Console.WriteLine("Largest: " + AveNum.Max());
    }

Upvotes: 1

Rob
Rob

Reputation: 27357

This probably isn't the most efficient way to do it, but it works fine:

Basically, we use a stack to track the items we've traversed. Then to calculate the average for n last items, we peek at n items from the stack. 

void Main()
{
    var randomList = new List<int>();
    var random = new Random(1969);

    for (var i = 0; i < 10; i++)
    {
        randomList.Add(random.Next(0, 500));
    }

    // Use the values from the original post for validation
    randomList = new List<int> { 190, 279, 37, 413, 90, 131, 64, 129, 287, 172 };

    const int numSets = 9;
    var avgDict = Enumerable.Range(1, numSets).ToDictionary(e => e, e => (double)0);
    var s = new Stack<int>();
    foreach (var item in randomList)
    {
        s.Push(item);
        for (var i = 1; i <= numSets; i++)
        {
            if (s.Count >= i)
            {
                var avg = s.Take(i).Average();
                if (avg > avgDict[i])
                    avgDict[i] = avg;
            }
        }
    }
    avgDict.Dump();
}

Yields the result:

1 413 
2 251.5 
3 243 
4 229.75 
5 201.8 
6 190 
7 183.714285714286 
8 178.75 
9 180

I'm unsure as to the implications of using a Stack for large lists, when we only need 9-10 items. Might be a good case for a custom limited size stack

Upvotes: 1

Related Questions