Speed differences in JavaScript functions finding the most common element in an array

Question

I'm studying for an interview and have been working through some practice questions. The question is:

Find the most repeated integer in an array.

Here is the function I created and the one they created. They are appropriately named.

var arr = [3, 6, 6, 1, 5, 8, 9, 6, 6]

function mine(arr) {
  arr.sort()
  var count = 0;
  var integer = 0;
  var tempCount = 1;
  var tempInteger = 0;
  var prevInt = null
  for (var i = 0; i < arr.length; i++) {
    tempInteger = arr[i]
    if (i > 0) {
      prevInt = arr[i - 1]
    }
    if (prevInt == arr[i]) {
      tempCount += 1
      if (tempCount > count) {
        count = tempCount
        integer = tempInteger
      }
    } else {
      tempCount = 1
    }
  }
  console.log("most repeated is: " + integer)
}

function theirs(a) {
  var count = 1,
    tempCount;
  var popular = a[0];
  var temp = 0;
  for (var i = 0; i < (a.length - 1); i++) {
    temp = a[i];
    tempCount = 0;
    for (var j = 1; j < a.length; j++) {
      if (temp == a[j])
        tempCount++;
    }
    if (tempCount > count) {
      popular = temp;
      count = tempCount;
    }
  }
  console.log("most repeated is: " + popular)
}
console.time("mine")
mine(arr)
console.timeEnd("mine")
console.time("theirs")
theirs(arr)
console.timeEnd("theirs")

These are the results:

most repeated is: 6
mine: 16.929ms
most repeated is: 6
theirs: 0.760ms

What makes my function slower than their?

Answer 1

My test results

I get the following results when I test (JSFiddle) it for a random array with 50 000 elements:

mine:     28.18 ms
theirs: 5374.69 ms

In other words, your algorithm seems to be much faster. That is expected.

Why is your algorithm faster?

You sort the array first, and then loop through it once. Firefox uses merge sort and Chrome uses a variant of quick sort (according to this question). Both take O(n*log(n)) time on average. Then you loop through the array, taking O(n) time. In total you get O(n*log(n)) + O(n), that can be simplified to just O(n*log(n)).

Their solution, on the other hand, have a nested loop where both the outer and inner loops itterate over all the elements. That should take O(n^2). In other words, it is slower.

Why does your test results differ?

So why does your test results differ from mine? I see a number of possibilities:

• You used a to small sample. If you just used the nine numbers in your code, that is definately the case. When you use short arrays in the test, overheads (like running the console.log as suggested by Gundy in comments) dominate the time it takes. This can make the result appear completely random.
• neuronaut suggests that it is related to the fact that their code operates on the array that is already sorted by your code. While that is a bad way of testing, I fail to see how it would affect the result.
• Browser differences of some kind.

A note on .sort()

A further note: You should not use .sort() for sorting numbers, since it sorts things alphabetically. Instead, use .sort(function(a, b){return a-b}). Read more here.

A further note on the further note: In this particular case, just using .sort() might actually be smarter. Since you do not care about the sorting, only the grouping, it doesnt matter that it sort the numbers wrong. It will still group elements with the same value together. If it is faster without the comparison function (i suspect it is), then it makes sense to sort without one.

An even faster algorithm

You solved the problem in O(n*log(n)), but you can do it in just O(n). The algorithm to do that is quite intuitive. Loop through the array, and keep track of how many times each number appears. Then pick the number that appears the most times.

Lets say there are m different numbers in the array. Looping through the array takes O(n) and finding the max takes O(m). That gives you O(n) + O(m) that simplifies to O(n) since m < n.

This is the code:

function anders(arr) {

    //Instead of an array we use an object and properties.
    //It works like a dictionary in other languages.
    var counts = new Object();

    //Count how many of each number there is.
    for(var i=0; i<arr.length; i++) {
        //Make sure the property is defined.
        if(typeof counts[arr[i]] === 'undefined')
            counts[arr[i]] = 0;
        //Increase the counter.
        counts[arr[i]]++;
    }

    var max;             //The number with the largest count.
    var max_count = -1;  //The largest count.

    //Iterate through all of the properties of the counts object
    //to find the number with the largerst count.
    for (var num in counts) {
        if (counts.hasOwnProperty(num)) {
            if(counts[num] > max_count) {
                max_count = counts[num];
                max = num;
            }
        }
    }

    //Return the result.
    return max;

}

Running this on a random array with 50 000 elements between 0 and 49 takes just 3.99 ms on my computer. In other words, it is the fastest. The backside is that you need O(m) memory to store how many time each number appears.

Answer 2

It looks like this isn't a fair test. When you run your function first, it sorts the array. This means their function ends up using already sorted data but doesn't suffer the time cost of performing the sort. I tried swapping the order in which the tests were run and got nearly identical timings:

console.time("theirs")
theirs(arr)
console.timeEnd("theirs")
console.time("mine")
mine(arr)
console.timeEnd("mine")

most repeated is: 6
theirs: 0.307ms
most repeated is: 6
mine: 0.366ms

Also, if you use two separate arrays you'll see that your function and theirs run in the same amount of time, approximately.

Lastly, see Anders' answer -- it demonstrates that larger data sets reveal your function's O(n*log(n)) + O(n) performance vs their function's O(n^2) performance.