7

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?

5
  • are you looking only for name or other properties? Commented Jan 29, 2016 at 12:17
  • Thomas has it right - if efficiency is the prime criteria you shouldn't be using a plain array. Commented Jan 29, 2016 at 12:26
  • 1
    If you've only got an (unsorted) array, there's not much else you can do but to iterate it. Commented Jan 29, 2016 at 12:29
  • The regular for loop will be the fastest way. Also if you need just one item you would be able to break the loop Commented Jan 29, 2016 at 13:00
  • I need to first check on name and if name matches i need to retrieve age and group. Commented Feb 1, 2016 at 5:30

4 Answers 4

9

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.

Sign up to request clarification or add additional context in comments.

Comments

6
  • use ES5 array methods like map ,filter ,reduce etc
  • use forEach
  • native for loop

Example : filter , map, reduce etc. methods iterate over each item or object in an array,

ArrPerson.filter(function(item){
       console.log(item)
   });

forEach : also iterates over each item/object in an array

 ArrPerson.forEach(function(key,value){
     console.log(key);
     console.log(value)
  })

The question said huge array , so

native for loop is way faster than any of the above and caching the length can improve by a few ms (milliseconds).

https://jsperf.com/native-map-versus-array-looping

for(var i = 0, len = ArrPerson.length; i < len; i++){

}

1 Comment

The ES5 array methods are not async. They do take a callback, but that callback is invoked synchronously!
0

Considering you want to check all and assuming no other indexing then the problem is still O(n). You can use .filter() to filter and return an array where they meet that condition. Alternatively, you can index using some other data structure by what you want to search.

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"));

function findByName(arr, name) {
  return arr.filter(function(o) {
    return o.name == name;
  });
}

document.write(JSON.stringify(findByName(ArrPerson, "john")));

Comments

0

Something like this should work.

    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"));

    for(var key in ArrPerson){
        if(ArrPerson[key].name === 'john'){
        //do something
          alert(ArrPerson[key].name);
        }
        }

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.