0

シナリオ: ディープ オブジェクトで特定のオブジェクトを検索しています。私は、子供たちを調べて、子供たちを探しているのか、子供や孫を探しているのかなどを尋ねる再帰関数を使用しています。見つかった場合は見つかった obj が返され、そうでない場合は false が返されます。基本的にこれ：

obj.find = function (match_id) {
    if (this.id == match_id) return this;
    for (var i = 0; i < this.length; i++) {
        var result = this[i].find(match_id);
        if (result !== false) return result;
    };
    return false;
}​

私は疑問に思っています、これより簡単なものはありますか?:

var result = this[i].find(match_id);
if (result) return result;

結果を（各レベルで）変数に保存するのは面倒です。それがfalseでないかどうかを確認して結果を返したいだけです。次のことも考えましたが、明らかな理由でさらに嫌いです。

if (this[i].find(match_id)) return this[i].find(match_id);

ところで、私も疑問に思っていますが、このアプローチは「再帰的」ですか? あまり自称していませんが…

どうもありがとうございました。

[編集]

check_findif ステートメントで別の関数 (見つかった場合にのみ true を返す) を使用する別の可能性があります。いくつかの非常に複雑なケース (例えば、オブジェクトを見つけるだけでなく変更も行う場合) では、これが最善のアプローチかもしれません。それとも私が間違っていますか？D:

4

3 に答える 3

3

検索アルゴリズムに関する限り、あなたが持っている解決策はおそらく「最良」であり、必ずしもそれを変更することを提案するわけではありません（または、アルゴリズムの代わりにマップを使用するように変更します）が、質問は特に興味深いものですJavaScript 言語の機能特性に関連して、いくつかの考えを提供したいと思います。

方法 1

以下は、代わりに関数の引数として使用されますが、関数内で変数を明示的に宣言しなくても機能するはずです。また、少し簡潔ではありますが、非常に簡潔です。

var map = Function.prototype.call.bind(Array.prototype.map);

obj.find = function find(match_id) {
    return this.id == match_id ? this : map(this, function(u) {
        return find.call(u, match_id);
    }).filter(function(u) { return u; })[0];
};​

使い方：

  1. かどうかをテストしthis.id == match_id、そうであれば を返しthisます。
  2. メソッドの再帰呼び出しを使用して見つかった「見つかった項目」の配列に変換するために、 map( 経由で) を使用します。(おそらく、これらの再帰呼び出しの 1 つが答えを返します。答えにならないものは を返します。)Array.prototype.mapthisfindundefined
  3. 「見つかった項目」配列をフィルタリングしてundefined、配列内の結果が削除されるようにします。
  4. 配列の最初の項目を返し、それを終了します。
    • 配列に最初の項目がない場合は、undefinedが返されます。

方法 2

この問題を解決するための別の試みは、次のようになります。

var concat = Function.prototype.call.bind(Array.prototype.concat),
    map = Function.prototype.call.bind(Array.prototype.map);

obj.find = function find(match_id) {
    return (function buildObjArray(o) {
        return concat([ o ], map(o, buildObjArray));
    })(this).filter(function(u) { return u.id == match_id })[0];
};

使い方：

  1. buildObjArrayobjと のすべての子を含む単一の大きな 1 次元配列を作成しobjます。
  2. 次に、配列内のオブジェクトにof がfilter必要であるという基準に基づいています。idmatch_id
  3. 最初の試合を返します。

方法 1と方法 2はどちらも興味深いものですが、一致する ID が見つかった後も検索を続けるというパフォーマンス上の欠点があります。彼らは検索が終わるまで自分が必要なものを持っていることに気付きません。これはあまり効率的ではありません。

方法 3

確かに効率化は可能ですし、これであなたが興味を持っていたものにかなり近づいたと思います。

var forEach = Function.prototype.call.bind(Array.prototype.forEach);

obj.find = function(match_id) {
    try {
        (function find(obj) {
            if(obj.id == match_id) throw this;
            forEach(obj, find);
        })(obj);
    } catch(found) {
        return found;
    }
};​

使い方：

  1. find関数全体をtry/ブロックでラップしてcatch、項目が見つかったらthrow実行を停止できるようにします。
  2. 再帰呼び出しを行うために参照する内部find関数 (IIFE) を内部に作成します。try
  3. の場合this.id == match_id、throw this検索アルゴリズムを停止します。
  4. 一致しない場合は、find各子を再帰的に呼び出します。
  5. 一致した場合は、ブロックthrowによってキャッチされ、オブジェクトが返されます。catchfound

tryこのアルゴリズムは、オブジェクトが見つかると実行を停止できるため、 /catchブロックのオーバーヘッド (古いブラウザーではコストがかかる可能性があります) が依然としてあり、通常のループforEachよりも低速ですが、パフォーマンスはユーザーのアルゴリズムに近くなります。forそれでも、これらは非常に小さなパフォーマンスの損失です。

方法 4

最後に、このメソッドはリクエストの範囲に適合しませんが、アプリケーションで可能であればはるかに優れたパフォーマンスであり、考慮すべき点です。オブジェクトにマップする ID のマップに依存しています。次のようになります。

// Declare a map object.
var map = { };

// ...
// Whenever you add a child to an object...
obj[0] = new MyObject();
// .. also store it in the map.
map[obj[0].id] = obj[0];

// ...
// Whenever you want to find the object with a specific id, refer to the map:
console.log(map[match_id]); // <- This is the "found" object.

このように、findメソッドはまったく必要ありません。

この方法を使用すると、アプリケーションのパフォーマンスが大幅に向上します。可能であれば、真剣に検討してください。

ただし、そのオブジェクトを参照する必要がなくなるたびに、そのオブジェクトをマップから削除するように注意してください。

delete map[obj.id];

これは、メモリリークを防ぐために必要です。

于 2012-09-27T04:20:09.827 に答える
2

いいえ、他に明確な方法はありません。結果を変数に格納することはそれほど問題ではありません。実際、これが変数の用途です。

はい、そのアプローチは再帰的です。

  • あなたはベースケースを持っていますif (this.id==match_id) return this
  • 自分自身を呼び出す再帰的なステップがありますobj.find(match_id) { ... var result = this[i].find(match_id); }
于 2012-09-26T23:20:51.240 に答える
1

変数の保存が悪い理由はわかりません。コピペではなく参考になるので効率的です。さらに、一時変数は、私が今見ることができる唯一の方法です (ただし、間違っている可能性があります)。

check_findそれを念頭に置いて、メソッドがあまり意味をなさないとは思いません(おそらく基本的に同じ実装です)。したがって、このcheck_findメソッドが本当に必要な場合は、次のように実装します。

return this.find(match_id) !== false;

メソッドが再帰的であるかどうかはわかりません。「find」の実装はすべてのオブジェクトで同じであるため、基本的にはそうです。

function find(obj, match_id) {
    if (obj.id == match_id) return obj;
    for (var i = 0; i < obj.length; ++i) {
        var result = find(obj[i], match_id);
        if (result !== false) return result;
    }
}

これは間違いなく再帰的です (関数はそれ自体を呼び出します)。

ただし、そうする場合は

onesingleobjectinmydeepobject.find = function(x) { return this; }

これを再帰的と呼ぶかどうかはよくわかりません。

于 2012-09-26T23:37:43.560 に答える