Counting things in Javascript

If you want to count how many items of a specific variety are in an array, you could filter that array and check the length of the result.

const letters = ['a','b','b','c','c','c'];
const numberOfC = letters.filter(letter => letter === 'c').length;
console.log(numberOfC); // 3

This has a time complexity of O(n), which is the theoretical ideal for this type of problem. It does use some extra memory to hold a second array, but for counting only one variety of items, this is a common approach and efficient enough in most situations. However, it is not an efficient approach if you want counts of every variety of items in the array.

The problem with filter

If we wanted counts not only of 'c' but of every letter in the array, the naive application of this technique would be something like this:

const letters = ['a','b','b','c','c','c'];
letters.forEach((letter, _, arr) => {
   const count = arr.filter(otherLetter => otherLetter === letter).length;
   console.log(letter, count);
});

This produces the following output:

a 1
b 2
b 2
c 3
c 3
c 3

The counts are correct, but there is redundancy, which can be fixed by first using a Set.

const letters = ['a','b','b','c','c','c'];
const uniqueLetters = new Set(letters);
for(const letter of uniqueLetters){
   const count = letters.filter(otherLetter => otherLetter === letter).length;
   console.log(letter, count);
};

The resulting output has no duplicates:

a 1
b 2
c 3

However, it does have a time complexity of O(n^2), because each filter iterates through the whole array, and it must do that for each unique letter.

A more efficient approach

It is possible to perform this count with O(n) time complexity. The general principle is to iterate the array only once. For each item encountered, check if you already have a count for that item. If you do, increment it by 1. If you don't, add a count for that item with a value set to 1.

Javascript has two different mechanisms that are suitable for storing the counts. We can use objects or Maps. Note that this is a reference to the Map data structure and not the map() method of arrays. Using a Map is more efficient, but using objects for this is still quite common, so we will look at how to count with both.

Counting with a Map

const letters = ['a','b','b','c','c','c'];
const counts = new Map(); // Creates an empty Map
letters.forEach(letter => {
    if(counts.has(letter)) {//Determine if the letter already has a count
        counts.set(letter, counts.get(letter) + 1);//Increment existing count
    }
    else counts.set(letter, 1);//Set new count to 1
});
console.log(counts); //Map(3) { 'a' => 1, 'b' => 2, 'c' => 3 }

The has() checks if the value is already in the Map. The set() stores a value in the Map, either creating a new value or overwriting an existing one. The get() obtains the current value. Note that has(), set(), and get() are O(1) time complexity, because a hash is used internally.

If we wanted to later extract a specific letter's count, we could do something like:

console.log(counts.get('c'));//3

Counting with an object

Although counting with objects is slower, the difference in performance might not be noticeable if you aren't counting a tremendous quantity of items. Objects also have more browser support than Maps, although that difference has becomes almost inconsequential at this point. According to caniuse.com, Map is supported in 96.28% of browsers at the time of this writing. Objects are an integral part of the Javascript language and should have 100% browser support, but caniuse.com does not have a listing for it. The main reason for learning how to use objects for counts is because a lot of old code exists that use this technique. Some people who learned from old code also write new code using this approach.

const letters = ['a','b','b','c','c','c'];
const counts = {};//Create empty object for holding counts
letters.forEach(letter => {
    if(letter in counts) {//Check if the count exists
        counts[letter]++;//Increment the count
    }
    else counts[letter] = 1;//Set new count to 1
});
console.log(counts);//{ a: 1, b: 2, c: 3 }

This code follows the same structure as the code using a Map. The differences are in syntax for Maps and objects. The "in" keyword is used to test if the object has a key with that name. Bracket syntax is used both to get and set the values. Note that testing for membership, setting, and getting values from an object are O(1) time complexity operations, because objects internally use a hash for the keys.

The problem of counting objects

If the things that you are counting are objects, extra care is required. Maps are capable of storing objects as keys, and they preserve the type, but that creates a problem for equality comparison if you have a totally different object that has all the exact same keys and values.

const m = new Map();
m.set({name: "John"}, 5);
console.log(m.has({name: "John"}));//false

This code outputs "false", because the two objects do not have referential equality. The two objects are identical in keys and values, but they aren't the exact same object.

const m = new Map();
const obj = {name: "John"}
m.set(obj, 5);
console.log(m.has(obj));//true

This version of the code outputs "true", because the value set is the exact same object being tested for membership.

The result of trying to count objects with Maps in most cases is all objects will end up with a count of 1, because every has() returns false.

Using objects for counting objects has a related but slightly different problem. Object keys are automatically coerced to string (Except when they are symbols). If you try to use an object as the key of another object, that type coercion creates a key equal to "[object Object]".

const obj = {name: "John"}
const count = {};
count[obj] = 5;
console.log(count);// { '[object Object]': 5 }

The result of trying to count objects using objects is you will end up with an object that has "[object Object]" as the key, and the value will be the total number of all the things that were counted. There won't be any individual counts, because every item is treated as "[object Object]".

How to count objects

It is not common that you would need to count objects. If the need arises, the solution depends on whether or not the objects have a unique property that is guaranteed to be unique. For example, objects that have an id number could be counted by counting the id number occurrences instead of counting occurrences of the whole object.

const employees = [
    {id: 1, name: "John"},
    {id: 1, name: "John"},
    {id: 2, name: "Mary"},
    {id: 2, name: "Mary"},
    {id: 2, name: "Mary"},
]
const counts = new Map();
employees.forEach(employee => {
    if(counts.has(employee.id)) {
        counts.set(employee.id, counts.get(employee.id) + 1);
    }
    else counts.set(employee.id, 1);
});
console.log(counts);//Map(2) { 1 => 2, 2 => 3 }

This only gives counts with ids and an extra lookup would be needed to associate the counts with names, but we can fix that with a bit more code:

const countsWithNames = [];
for(const count of counts) {
    const employee = employees.find((employee) => employee.id === count[0]);
    countsWithNames.push({employee, count: count[1]});
}
console.log(countsWithNames);

The resulting output is:

[
  { employee: { id: 1, name: 'John' }, count: 2 },
  { employee: { id: 2, name: 'Mary' }, count: 3 }
]

If there isn't anything like an id that guarantees uniqueness, the only remaining practical option would be to first convert the object to JSON.

const people = [
    {name: "John Doe", age: 25},
    {name: "John Doe", age: 25},
    {name: "Mary Jane", age: 24},
    {name: "Mary Jane", age: 24},
    {name: "Mary Jane", age: 24}
]
const counts = new Map();
people.forEach(person => {
    const personString = JSON.stringify(person);
    if(counts.has(personString)) {
        counts.set(personString, counts.get(personString) + 1);
    }
    else counts.set(personString, 1);
});
console.log(counts);

The resulting output is:

Map(2) {
  '{"name":"John Doe","age":25}' => 2,
  '{"name":"Mary Jane","age":24}' => 3
}

Note that there are limitations to this approach. For example, objects with circular references cannot be stringified using JSON.stringify().

Counting non-array items

Both the techniques for counting with Maps and for counting with objects can be used to count anything, as long as you can find a way to iterate through the items. Some types of data can be converted to an array, for example, strings can be split, and keys of objects can be accessed as an array via Object.keys().

There are also some iterables that don't need to be converted into an array. For example, it's possible to iterate through the characters of a string by using an index. The same principle can be used in array-like structures like HTML Collections.

The above is the detailed content of Counting things in Javascript. For more information, please follow other related articles on the PHP Chinese website!