最初のキーの出現を見つける効率的な方法：オブジェクト内の値

Question

以下は、少なくとも1つのオカレンスを見つける必要があるオブジェクトです。isSelected: true。

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

上記目的は、その中にN要素を有することができ、各要素はそうでN子供とを有することができます。すべての要素に対して、値が「true/false」のisSelectedキーがあります。

私は、真値を持つisSelectedキーが少なくとも1つ見つかった場合にtrueを返す関数をJavaScriptで作成しようとしています。

は JSON.stringify()を使用して機能の下に書いて、文字列を検索「isSelected：真」の文字列は、それが

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

わからないJSON.stringify()場合に大きなオブジェクトのために効率的になります。

サードパーティのライブラリを使用せずにJavaScriptで解決策を見つけようとしています。

Answer 1

あなたはすべての子供たちの上に「isSelected」値とループを確認するために、再帰的なアルゴリズムを使用することができます。

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ですが、最悪の場合のために非常に簡単なベンチマークを作成してみましょう：私のコンピュータ上の

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

結果は（あなたがそれらを実行するたびに変更するが、あなたのアイデアを得る）：

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

---

これは最悪のケースのためでした。今、最良の場合（最初のisSelectedが「真」である）を持つ：

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

結果：@Juniorの答えに

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

Answer 2

ビル - 再帰が、ここでそれを行うための最速の方法ですが、 tail call optimizationを使用して、よりパフォーマンスの高いバージョンは次のとおりです。trueが発見されたとして

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; 
} 

もう一つの重要なトリックは、すぐにループを停止することです。ここで

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

がjsperf test次のとおりです。

Answer 3

再帰はそれを行うための最善の方法となります。

を追加しました。Array.isArray(X)は、X instanceof Arrayの約3.3倍です。ここにはjsperf test confirming thatがあります。