2
\$\begingroup\$

Exercise description:

Find the most common number in an array of numbers.

Create a software that takes an array of numbers as parameter. The return of the function shall be the most common number.

Example: Assume that the list is ... 1, 5, 1, 3, 5, 5, 2.

The program will output 5, because this is the most common number.

Note that if there is more than one most common number, the program will just print one of the most common numbers.

My solution (written in TypeScript):

let numbers: number[] = [1, 5, 1, 3, 5, 5, 2];

namespace Main {
  export function searchMostCommonNumber(arr: number[] = []): number {
    let current: number = 0;
    let max: number = 0;
    let mostCommonNumber: number = 0;
    let i: number;

    for (i = 0; i < arr.length - 1; i++) {
      let current: number = 1;
      let j: number;

      for (j = i + 1; j < arr.length; j++) {
        if (arr[i] === arr[j]) {
          current++;
        }
      }

      if (current > max) {
        max = current;
        mostCommonNumber = arr[i];
      }
    }

    return mostCommonNumber;
  }
}

console.log(Main.searchMostCommonNumber(numbers));

Live demo (with compiled code):

var numbers = [1, 5, 1, 3, 5, 5, 2];
var Main;
(function(Main) {
  function searchMostCommonNumber(arr) {
    if (arr === void 0) {
      arr = [];
    }
    var current = 0;
    var max = 0;
    var mostCommonNumber = 0;
    var i;
    for (i = 0; i < arr.length - 1; i++) {
      var current_1 = 1;
      var j = void 0;
      for (j = i + 1; j < arr.length; j++) {
        if (arr[i] === arr[j]) {
          current_1++;
        }
      }
      if (current_1 > max) {
        max = current_1;
        mostCommonNumber = arr[i];
      }
    }
    return mostCommonNumber;
  }
  Main.searchMostCommonNumber = searchMostCommonNumber;
})(Main || (Main = {}));
console.log('The most common number is :', Main.searchMostCommonNumber(numbers));

What do you think about my solution?

Is there a better way to accomplish the task? What would you have done differently?

Looking forward to reading your comments and answers.

\$\endgroup\$
5
\$\begingroup\$

For small arrays as input your script's performance is very good. Let me show you a different approach which might especially improve readability and might also increase performance for larger inputs and multiple runs.

.reduce()

Instead of iterating through the elements manually, I've used Array.prototype.reduce():

The reduce() method applies a function against an accumulator and each element in the array (from left to right) to reduce it to a single value.

The function has two steps now which both use reduce():

  1. Reduce the input into an object that holds each number and its count as key/value-pairs.
  2. Reduce this object to find the key with the highest value.

function findMode(numbers) {
    let counted = numbers.reduce((acc, curr) => { 
        if (curr in acc) {
            acc[curr]++;
        } else {
            acc[curr] = 1;
        }

        return acc;
    }, {});

    let mode = Object.keys(counted).reduce((a, b) => counted[a] > counted[b] ? a : b);

    return mode;
}

Performance

In the comments we had a lot of discussion about performance about this and other solutions.

One requested improvement was to calculate the mode directly in the first reduce call. It could look like this:

function findModeAlternative(numbers) {
    let max = 0;
    let mode = null;
    let counted = numbers.reduce((acc, curr) => { 
        if (curr in acc) {
            acc[curr]++;
        } else {
            acc[curr] = 1;
        }

        if (max < acc[curr]) {
            max = acc[curr];
            mode = curr;
        }

        return acc;
    }, {});

    return mode;
}

Unfortunately it didn't improve performance in Chrome and Firefox.


Then Blindman67 suggested the naive approach with this solution:

function findCommon(arr) {
    var max = 1,
        m = [],
        val = arr[0],
        i, x;

    for(i = 0; i < arr.length; i ++) {
        x = arr[i]
        if (m[x]) {
            ++m[x] > max && (max = m[i], val = x);
        } else {
            m[x] = 1;
        }
    } return val;    
}

Which will increase performance significantly in Firefox, but performs about the same in Chrome. Keep in mind, that functions like reduce, map etc. come with some overhead.


Finally the approach using map in Gerrit0's answer also increases the performance drastically opposed to the original.


Test

I've created a test, so you can check the performance of each variant yourself. The test uses two different arrays with ca. 500 elements each and runs every function 100000 times:

  • test array A is kind of mixed
  • test array B contains mostly one number with a few exceptions

These are the results from Chrome 61 on macOS:

  • array A "findMode": 1000ms
  • array B "findMode": 950ms
  • array A "findModeAlternative": 1200 ms
  • array B "findModeAlternative": 1100 ms
  • array A "findCommon": 930 ms
  • array B "findCommon": 960 ms
  • array A "mostCommonNumber": 1700 ms
  • array B "mostCommonNumber": 1300 ms
  • array A "searchMostCommonNumber": 12697 ms
  • array B "searchMostCommonNumber": 13400 ms

Try it yourself

Of course you can tweak the test and try different inputs etc.

The functions's name

As this is called mode in statistics, you could use a shorter function name like findMode()

Unfortunately this doesn't improve performance. This is just a personal preference


I only included the ES6 version of the script in this answer. I didn't add the check whether the array is an array and not empty, as this will be added when compiling from TypeScript to JavaScript

\$\endgroup\$
  • \$\begingroup\$ Worth mentioning: findMode will throw for an empty array, while the OP's function will not. \$\endgroup\$ – Gerrit0 Oct 16 '17 at 1:24
  • \$\begingroup\$ Also, regarding your benchmark, which implementation is faster depends heavily on the type of data you are working with. With a small number of different numbers, findMode will be faster. With nearly as many different numbers as elements in the array, the implementation using a Map will be faster. \$\endgroup\$ – Gerrit0 Oct 16 '17 at 1:43
  • \$\begingroup\$ Loops for(...,while( outperform iterators forEach, reduce, map at about 2 to 1. Your code also loops over the final reduced array, this is not need as you hold each max when you count them. the max and its number value can be found during the reduction. Applying both improvements the following runs 3 times faster than you findMode function function findCommon(arr){ var max = 1, m = [], val = arr[0], i, x; for(i = 0; i < arr.length; i ++){ x = arr[i++]; if (m[x]) { ++m[x] > max && (max = m[idx], val = x) } else { m[x] = 1 } } return val; } \$\endgroup\$ – Blindman67 Oct 16 '17 at 6:50
  • \$\begingroup\$ @Blindman67 You should add this as an answer. It's fast and easy to read. And you're right, every one of those optimized for-solutions will be faster than reduce, map etc. I think I will remove my answer. :D It's kinda biased. \$\endgroup\$ – insertusernamehere Oct 16 '17 at 6:56
  • 1
    \$\begingroup\$ +1 Good stuff. Odd about the alternative findMode tests I ran showed 25-30% faster on Chrome, though I used the short form if(curr in acc) { ++acc[curr] > max && (max = acc[curr], mode = curr) } the advantage is not having to index the acc array a second time to test against max If memory was the bench then a mod on OPs code would be best. As each item is tested non matching items are moved down the array to take the place of the tested numbers. Then each iteration the length of the search is reduced, plus early exit if max > then remaining numbers. \$\endgroup\$ – Blindman67 Oct 16 '17 at 10:29
3
\$\begingroup\$

My approach would be slightly different.

  1. Efficiency, though your current approach is memory efficient, it is O(n^2) which will make it rather slow for large arrays.

  2. I don't see any reason to include a namespace. With module support, namespaces seem to add unnecessary complexity in most cases.

  3. Scope variables properly. There's no reason to declare i and j outside of the loops.

  4. Avoid adding types where they can be inferred. let n: number = 0 can be written as let n = 0 and Typescript can infer the type of n to be number without needing to explicitly type it (note that for complex types it is still sometimes a good idea to explicitly state the type).

  5. Returning 0 for the empty array seems odd. There is no "most common number" if there are no numbers. Granted, returning NaN isn't much better (if it even is better).

Here's how I would implement this function.

function mostCommonNumber(numbers: number[]): number {
    let map = new Map<number, number>()
    for (let num of numbers) {
        map.set(num, (map.get(num) || 0) + 1)
    }

    let mostCommonNumber = NaN
    let maxCount = -1
    for (let [num, count] of map.entries()) {
        if (count > maxCount) {
            maxCount = count
            mostCommonNumber = num
        }
    }

    return mostCommonNumber
}

Demo:

function mostCommonNumber(numbers) {
    let map = new Map()
    for (let num of numbers) {
        map.set(num, (map.get(num) || 0) + 1)
    }

    let mostCommonNumber = NaN
    let maxCount = -1
    for (let [num, count] of map.entries()) {
        if (count > maxCount) {
            maxCount = count
            mostCommonNumber = num
        }
    }

    return mostCommonNumber
}

let tests = [
  [],
  [1, 2, 3, 4, 5],
  [1, 2, 3, 1, 2, 3, 1],
  [1, 5, 1, 3, 5, 5, 2]
]

for (let test of tests) {
  console.log(`[${test}] --> ${mostCommonNumber(test)}`)
}

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.