1

Even though I'm an artist I find the need to return the statistical mode from an array of numbers. I want the function to avoid using associative arrays (as I need version to run in JavaScript as well as Maxscript and it would be better to use the same codebase) Maxscript doesn't use associative arrays; which is a pity as this is a rather good solution.

The code below works in the first example, but not in the second. At a guess I'd say the array needs sorting beforehand but that didn't work (and I've omitted it from the code) Can anyone point out where I am going wrong? Thank you.

var textArr = new Array();

arrOne = [0,1,0,2,3,10,10]
arrTwo = [1,2,3,1,1,1]

mode_without_associative_arrays(arrOne) // works fine
mode_without_associative_arrays(arrTwo) // doesn't work

function mode_without_associative_arrays(arr)
{
    if(arr.length == 0)
    return null;

    var collectArr = []; // array
    var countArr = []  // array to hold the count of each element in collectArr
    collectArr[0] = arr[0]
    countArr[0] = 1
    var mode = arr[0]
    maxCount = 1;

    for(var i = 0; i < arr.length; i++)
    {
        var ele = arr[i];

        for(var j = 0; j < collectArr.length; j++)
        {
            var addMe = false;
            if (collectArr[j] != ele) addMe = true
        }

            if (addMe == true)
            {
                collectArr.push(ele)
                countArr.push(1)
            }
            else
            {
                // count it up
                countArr[j]+=1
                if (countArr[j] > maxCount) 
                {
                    maxCount = countArr[j]
                    mode = ele
                }
            }
        }

        alert("Mode is " + mode + " which appears " + maxCount + " times!")
        return mode;
}
Community
  • 1
  • 1
Ghoul Fool
  • 6,249
  • 10
  • 67
  • 125

2 Answers2

1

Without an associative array, I think the optimal algorithm would be:

  1. Sort the array - O(n log n)
  2. Linearly scan the array counting consecutive occurrences - O(n)

For step 2, compare the current element to the previous. If it's the same, increment your counter. If the counter exceeds the current maximum, remember the current element's value (that being the current mode). If the elements are different, reset your counter back to 1.

Alnitak
  • 334,560
  • 70
  • 407
  • 495
  • That sounds like a good approach to take. What happens if there are two numbers that are the mode [2,2,4,4] for example? – Ghoul Fool Sep 11 '13 at 13:56
  • @GhoulFool if there are two mode numbers, you'll have to decide which one to pick... – Alnitak Sep 11 '13 at 15:22
0

Something like this?

var arrayMode = function ( sequence ) {
    if ( sequence.length === 0)
        return 0;
    var collector = [];
    var instances = [];
    var max = 1;
    collector.push(sequence[0]);
    var mode = sequence[0];
    instances.push(1);

    for (var i = 1; i < sequence.length; i++ ) {
        var index = collector.indexOf( sequence[i] );
        if ( index === -1 ) {
            collector.push( sequence[i] );
            instances.push( 1 );
        } else {
            instances[ index ]++;
            if ( instances[ index ] > max ) {
                max = instances[ index ];
                mode = collector[ index ];
            }
        }
    }
    return mode;
}

In collector I'll keep a unique instance of the elements in sequence, and in instances, I have the number of ocurrences of each different instance in sequence.

Juan Manuel Cruz
  • 26
  • 3