CODEWITHSUNDEEP
arraysjsonnode.jssearch
Ayush Gupta
Ayush Gupta

Reputation: 9295

Most efficient way to check if any element in a JSON array contains a specific id?

I am using Node v8.1.3

I have a JSON array as following:

[
  {
    "id":99,
    "name": "ABC"
  },
  {
    "id": 187,
    "name": "AXZ"
  }
]

This array has around 213000 e=objects in it.

Also, the ids in the objects are not in any order or pattern.

Now, I want to find if a particular id matches any ID in the array? what is the fastest wait to do it?

I tried

isIdValid(id) {
    console.log(id)
    return this.list.filter((elem) => {
        return elem.id == id
    }).length > 0;
}

But this is taking over 4 seconds.

Upvotes: 0

Views: 863

Answers (2)

Sina Mansour L.
Sina Mansour L.

Reputation: 428

One option is to first sort the whole list (or insert it into a binary search tree) which takes some time but is only done once. and from there you can use binary search for the ID which is way faster.

here is a sample bst code for node: js-bst

also here is a package that can be used to query json data list very faster: Defiant

Edit

actually creating a hash table is a faster solution than a bst; here is a sample code that does the job:

data = [
    {
        "id":99,
        "name": "ABC"
    },
    {
        "id": 187,
        "name": "AXZ"
    }
]

var hashCache = {};
data.forEach(function(item){
    hashCache[item.id] = item.name
});

// Usage:
var id = '99';
var record = hashCache[id];
if (record) {
    alert(record);
} else {
    console.log('no match found');
}

you should also consider that this hash table only works if the IDs are unique. otherwise, you need to store a list of names in the hash table for each ID.

Upvotes: 1

Diego ZoracKy
Diego ZoracKy

Reputation: 2285

These are not the "Most efficient way to check". I'm posting here just as a reference about some ways to prepare the data to have a more performant search by a specific key.

Also is worth considering that in this script, Map can have a better performance, just because it is the last of all the executions. When its turn comes, V8 would have already been done some optimizations internally. So try to run each of them separately to have better findings.

'use strict';

////////////////////////
// GENERATE TEST DATA //
////////////////////////
const dataSet = [];
let count = 213000;
while(count--) dataSet.push({id: count});
let idToBeFound = 212999;


// //////////////////////////
// // Using Literal Object //
// //////////////////////////
console.time('creatingIndexAsLiteralObject');
const literalObjectKeyedByID = dataSet.map(item => ({[item.id]: true}));
console.timeEnd('creatingIndexAsLiteralObject');

console.time('isIdValidSeekingOnLiteralObject');
console.log('isIdValidSeekingOnLiteralObject :: Found?', isIdValidSeekingOnLiteralObject(idToBeFound, literalObjectKeyedByID));
console.timeEnd('isIdValidSeekingOnLiteralObject');
function isIdValidSeekingOnLiteralObject(id, list) {
    return !!list[id];
}

// //////////////////////
// // Using Set Object //
// //////////////////////
console.time('creatingIndexAsSetObject');
const setObject = new Set(dataSet.map(item => item.id));
console.timeEnd('creatingIndexAsSetObject');

console.time('isIdValidSeekingOnSet');
console.log('isIdValidSeekingOnSet :: Found?', isIdValidSeekingOnSet(idToBeFound, setObject));
console.timeEnd('isIdValidSeekingOnSet');
function isIdValidSeekingOnSet(id, list) {
    return list.has(id);
}

//////////////////////
// Using Map Object //
//////////////////////
console.time('creatingIndexAsMapObject');
const mapObjectKeyedByID = new Map();
dataSet.forEach(item => mapObjectKeyedByID.set(item.id));
console.timeEnd('creatingIndexAsMapObject');

console.time('isIdValidSeekingOnMap');
console.log('isIdValidSeekingOnMap :: Found?', isIdValidSeekingOnMap(idToBeFound, mapObjectKeyedByID));
console.timeEnd('isIdValidSeekingOnMap');
function isIdValidSeekingOnMap(id, list) {
    return list.has(id);
}

Upvotes: 0

Related Questions