Hey everyone, I'm currently working on some behaviours for non playable characters in a game, and I need to find a reliable and fast method for finding the mode specific average of a set of values. This is not really a mathematics specific question rather a performance once, see the code must be per-formant in various situations where creating things like hash tables or anything else that creates orphan garbage to an extent that has potential to slow the game down to a crawl.

So far, I've found 4 different approaches to the issue as follows:

static int ModeA(int[] items)
{
    var groups = items.GroupBy(t => t);
    int maxCount = groups.Max(g => g.Count());
    return groups.First(g => g.Count() == maxCount).Key;
}
 
static int ModeB(IEnumerable<int> items)
{
    int maxVal = 0, maxCount = 0, curCount;
    var iter = items.GetEnumerator();
    while (iter.MoveNext())
    {
        curCount = items.Count(t => t == iter.Current);
        if (curCount > maxCount)
        {
            maxVal = iter.Current;
            maxCount = curCount;
        }
    }
    return maxVal;
}
 
static int ModeC(int[] items)
{
    int maxVal, maxCount, curCount;
    for (int i = maxVal = curCount = maxCount = 0; i < items.Length; i++)
    {
        var curVal = items[i];
        if ((curCount = items.Count(t => t == curVal)) > maxCount)
        {
            maxVal = curVal;
            maxCount = curCount;
        }
    }
    return maxVal;
}
 
static int ModeD(int[] items)
{
    int maxVal = 0, maxCount = 0, curCount = 0, curVal = 0, i = 0, j = 0;
    for (i = 0, j = 0; i < items.Length; i++, curCount = 0)
    {
        curVal = items[i]; 
 
        for (j = 0; j < items.Length; j++)
            if (items[j] == curVal) 
                curCount++;
 
        if (curCount > maxCount)
        {
            maxVal = curVal;
            maxCount = curCount;
        }
    }
    return maxVal;
}

And here is what I get performance wise if I ask each function to return the mode for 10,000 elements (timed with the Stopwatch class):

OK maybe I am definately looking too far into this lol, I've found another method that's even faster than method A, except it does what I was trying to avoid by using a dictionary as follows:

static Dictionary<int, int> table = new Dictionary<int, int>();

static int ModeE(int[] items)
{
    table.Clear();
    for (int i = 0; i < items.Length; i++)
    {
        var item = items[i];
        if (!table.ContainsKey(item)) table.Add(item, 0);
        table[item]++;
    }
    return table.First(t => t.Value == table.Max(u => u.Value)).Key;
}

Does anyone see anything here that I'm missing that could cause unwanted garbage?

Aimee

Do any of those functions work correctly? If there's a tie for the most popular value don't you have to take the mean of the tied values?

EDIT: Apparently not, although that makes the data multimodal... and you probably want to report all the modes of a data set in that case...