Efficient way of iterating over a array of objects in javascript/node.js

Question

I've defined an object

var Person = function(name,age,group){
this.name = name,
this.age = age,
this.group = group
}

var ArrPerson = [];
ArrPerson.push(new Person("john",12,"M1"));
ArrPerson.push(new Person("sam",2,"M0"));

Now I need an efficient mechanism to identify if the array of objects ArrPerson contains a particular name or not?

I know we can iterate over the array using for loop and check.Assuming the array is huge,is there any other efficient way of doing this?

Answer 1

You can use the array filter or find methods

ArrPerson.find(p=>p.name=='john')
ArrPerson.filter(p=>p.name=='john')

The find method searches the array from the beginning and stops when it finds one element that matches. In the worst case where the element that is being searched is the last in the array or it is not present this method will do O(n).This means that this method will do n checks (n as the length of the array) until it stops.

The filter method always does O(n) because every time it will search the whole array to find every element that matches.

Although you can make something much more faster(in theory) by creating a new data stucture.Example:

var hashmap = new Map();
var ArrPerson = [];
ArrPerson.push(new Person("john",12,"M1"));
hashmap.set("john",true);

This ES6 Map will keep an index of the whole array based on the names it contains. And if you want to see if your array contains a name you can do:

hashmap.has('john')//true

This approach will do O(1). It will only check once on the map to see if this name exists in your array. Also, you can track the array indexes inside the map:

var index = ArrPerson.push(new Person("john",12,"M1"));
var map_indexes = hashmap.get("john");
if(map_indexes){
  map_indexes.push(index-1);
  hashmap.set("john",map_indexes);
}else{
  hashmap.set("john",[index-1]);
}
map_indexes = hashmap.get("john"); //an array containing the ArrPerson indexes of the people named john
//ArrPerson[map_indexes[0]] => a person named john
//ArrPerson[map_indexes[1]] => another person named john ...

With this approach not only you can tell if there is a person in the array with the specific name but you can also find the whole object with O(1). Take into account that this map will only index people by name if you want other criteria you need another map. Also keeping two data structures synchronized is not easy(deleting one element from array should also be deleted from the map, etc)

In conclusion, as always increasing speed ends sacrificing something else, memory and code complexity in our example.