Count unique elements in array without sorting
In JavaScript the following will find the number of elements in the array. Assuming there to be a minimum of one element in the array
arr = ["jam", "beef", "cream", "jam"]
arr.sort();
var count = 1;
var results = "";
for (var i = 0; i < arr.length; i++)
{
if (arr[i] == arr[i+1])
{
count +=1;
}
else
{
results += arr[i] + " --> " + count + " times\n" ;
count=1;
}
}
Is it possible to do this without using sort() or without mutating the array in any way? I would imagine that the array would have to be re-created and then sort could be done on the newly created array, but I want to know what's the best way without sorting. And yes, I'm an artist, not a programmer, your honour.
The fast way to do this is with a new Set()
object.
Sets are awesome and we should use them more often. They are fast, and supported by Chrome, Firefox, Microsoft Edge, and node.js.
— What is faster Set or Object? by Andrei Kashcha
The items in a Set
will always be unique, as it only keeps one copy of each value you put in. Here's a function that uses this property:
function countUnique(iterable) {
return new Set(iterable).size;
}
console.log(countUnique('banana')); //=> 3
console.log(countUnique([5,6,5,6])); //=> 2
console.log(countUnique([window, document, window])); //=> 2
This can be used to count the items in any iterable (including an Array, String, TypedArray, and arguments object).
A quick way to do this is to copy the unique elements into an Object.
var counts = {};
for (var i = 0; i < arr.length; i++) {
counts[arr[i]] = 1 + (counts[arr[i]] || 0);
}
When this loop is complete the counts
object will have the count of each distinct element of the array.