CODEWITHSUNDEEP
javascript
raoul.nair
raoul.nair

Reputation: 489

Efficient way to find first occurrence of key:value inside object

Below is the object in which I need to find at least one occurrence of isSelected: true.

 [
  {
    "isSelected": true,
    "child": [
      {
        "isSelected": true,
        "child": [
          {
            "isSelected": true,
            "child": [
              {
                "isSelected": true
              }
            ]
          }
        ]
      }
    ]
  }
]

The above object can have n elements in it and each element can have n children and so on. For every element there will be an isSelected key with value "true/false".

I am trying to write a function in JavaScript that will return true if it finds at least one occurrence of isSelected key with true value.

Wrote below function using JSON.stringify() and search for string "isSelected:true" string in it

function hasIsSelected(data){
  return (JSON.stringify(data)).search('"isSelected":true') > -1 ? true: false
}

Not sure if JSON.stringify() will be efficient for large objects.

Trying to find solution in JavaScript without using third party library.

Upvotes: 1

Views: 2390

Answers (3)

Styx
Styx

Reputation: 10076

Recursion will be the best way to do that:

const deepSearch = (arr) => {
  return arr.some((v) => {
    if (v.isSelected === true) {
      return true;
    }
    if (Array.isArray(v.child) && v.child.length > 0) {
      return deepSearch(v.child);
    }
    return false;
  });
};

Here is jsperf test.

Added: Array.isArray(X) is ≈3.3 times faster than X instanceof Array. Here is jsperf test confirming that.

Upvotes: 1

Junior Dussouillez
Junior Dussouillez

Reputation: 2397

You can use a recursive algorithm to check the "isSelected" value and loop over all the children : 

function hasIsSelected(data) {
    if (data.isSelected) {
        return true;
    }
    if (data.child) {
        for (var i = 0; i < data.child.length; i++) {
            if (hasIsSelected(data.child[i])) {
                return true;
            }
        }
    }
    return false;
}


var json = [...]; // Your value
hasIsSelected(json[0]);

EDIT : Ok let's make a very simple benchmark for the worst case :

function createTestData(depth) {
    var obj = { isSelected: depth === 0 };
    if (depth > 0) {
        obj.child = [createTestData(depth - 1)];
    }
    return obj;
}
var testData = [createTestData(1000)]; // Big object, the "true" value is in the deepest child.


function hasIsSelectedStrinfigy(data){
    return (JSON.stringify(data)).search('"isSelected":true') > -1;
}

function hasIsSelectedRec(data) {
    if (data.isSelected) {
        return true;
    }
    if (data.child) {
        for (var i = 0; i < data.child.length; i++) {
            if (hasIsSelectedRec(data.child[i])) {
                return true;
            }
        }
    }
    return false;
}

// Using NicolaeS's solution 
function hasIsSelectedRecTOC(data) {
    if (data.isSelected === true) {
        return true;
    }
    if (data.child instanceof Array) {
        // stops after the first valid element
        return data.child.some(hasIsSelectedRecTOC);
    }
    return false;
}


// Run tests
function runTest(fun) {
    var t0 = performance.now();
    fun(testData[0]);
    var t1 = performance.now();
    return t1 - t0;
}

console.log("Exec time using stringify : %o", runTest(hasIsSelectedStrinfigy));
console.log("Exec time using recursion : %o", runTest(hasIsSelectedRec));
console.log("Exec time using recursion with TOC : %o", runTest(hasIsSelectedRecTOC));

Results on my computer (change every time you run them but you get the idea) : 

Exec time using stringify : 6.785000000000004
Exec time using recursion : 0.36999999999999034
Exec time using recursion with TOC : 0.37999999999999545

This was for the worst case. Now with the best case (the first isSelected is "true") :

function createTestData(depth) {
    var obj = { isSelected: true }; // isSelected is always true
    if (depth > 0) {
        obj.child = [createTestData(depth - 1)];
    }
    return obj;
}
var testData = [createTestData(1000)];

Results :

Exec time using stringify : 3.980000000000002
Exec time using recursion : 0.040000000000000924
Exec time using recursion with TOC : 0.02499999999999858

Upvotes: 2

NicolaeS
NicolaeS

Reputation: 463

Building on the answer of @Junior - recursion is the fastest way to do it, but here is a more performant version using tail call optimization:

function hasIsSelected(data) {
  if (data.isSelected === true) {
    return true;
  } else if (data.child instanceof Array) {
    return data.child.some(hasIsSelected); // stops after the first selected element
  } else return false;
}

Another important trick is to stop the loop as soon as a true is found.

Upvotes: 1

Related Questions