15

際限なく循環しているライブラリ コードがいくつかあります。

javascript でサイクルの検出と回避を最適に実行する方法がよくわかりません。つまり、オブジェクトが「this」参照からのものかどうかを調べるプログラム的な方法はありません。

これがコードです。ありがとう！

setAttrs: function(config) {
    var go = Kinetic.GlobalObject;
    var that = this;

    // set properties from config
    if(config !== undefined) {
        function setAttrs(obj, c) {
            for(var key in c) {
                var val = c[key];

                /*
                 * if property is an object, then add an empty object
                 * to the node and then traverse
                 */
                if(go._isObject(val) && !go._isArray(val) && !go._isElement(val)) {
                    if(obj[key] === undefined) {
                        obj[key] = {};
                    }
                    setAttrs(obj[key], val);  // <--- offending code; 
                                              // one of my "val"s is a "this" reference
                                              // to an enclosing object
                }
4

5 に答える 5

10

この状況に対処するために私が知っている「信頼性が高くクリーンな」方法は、「訪問された」オブジェクトのコレクションを使用してから、現在のオブジェクトがすでに「訪問されているかどうか」に基づいて、終了、シンボリック参照の挿入などに反応することです。 " か否か。

Crockford 氏は、cycle.jsでこのアプローチを使用し、コレクションに Array を使用しています。抜粋：

// If the value is an object or array, look to see if we have already
// encountered it. If so, return a $ref/path object. This is a hard way,
// linear search that will get slower as the number of unique objects grows.

for (i = 0; i < objects.length; i += 1) {
    if (objects[i] === value) {
        return {$ref: paths[i]};
    }
}

残念ながら、JavaScript でこれにプリミティブな「ハッシュ」アプローチを使用することはできません。これには Identity-Map がないためです。配列コレクションの境界は次のとおりですがO(n^2)、これは思ったほど悪くはありません。

これは、「訪問された」コレクションが単なるガードである場合、 の値nは単にスタックの深さであるためです。同じオブジェクトを複数回コピーすることは重要ではなく、循環のみが重要です。つまり、「訪問済み」コレクション内のオブジェクトは、スタックアンワインドでプルーニングできます。

cycle.js コードでは、特定のオブジェクトに対して同じシンボリック名が常に使用されていることを確認する必要があるため、「訪問された」コレクションをプルーニングすることはできません。ただし、この場合でも、通過した一意の非プリミティブ値の数のみnです。

私が考えることができる唯一の他の方法は、トラバースされるオブジェクトに「訪問済みプロパティ」を直接追加する必要があることです。これは、一般的に望ましくない機能と考えられます。(ただし、このアーティファクトが [比較的] 簡単にクリーンアップされていることについての Bergi のコメントを参照してください。)

ハッピーコーディング。

于 2012-05-23T22:03:02.527 に答える
4

OK、@ pstが言及した「訪問済み」プロパティがどのように見えるかに興味を持ったので、これをコーディングしました。

Object.copyCircular = function deepCircularCopy(o) {
    const gdcc = "__getDeepCircularCopy__";
    if (o !== Object(o))
        return o; // primitive value
    var set = gdcc in o,
        cache = o[gdcc],
        result;
    if (set && typeof cache == "function")
        return cache();
    // else
    o[gdcc] = function() { return result; }; // overwrite
    if (o instanceof Array) {
        result = [];
        for (var i=0; i<o.length; i++) {
            result[i] = deepCircularCopy(o[i]);
    } else {
        result = {};
        for (var prop in o)
            if (prop != gdcc)
                result[prop] = deepCircularCopy(o[prop]);
            else if (set)
                result[prop] = deepCircularCopy(cache);
    }
    if (set)
        o[gdcc] = cache; // reset
    else
        delete o[gdcc]; // unset again
    return result;
};

これは単なる例であることに注意してください。以下をサポートしていません：

  • 非プレーンオブジェクト。プロトタイプ（配列を除く）を持つものはすべて複製されず、new Object！にコピーされます。これには機能が含まれます！
  • cross-global-scopeオブジェクト：を使用しますinstanceof Array。
  • セッター/ゲッター、書き込み不可および無数のプロパティなどのプロパティ記述子

グッズ：

  • オブジェクトに遭遇するたびに検索する必要のある大きな配列は使用しません。

欠点：

  • __getDeepCircularCopy__主張するものとは異なるメソッドを持つオブジェクトでは機能しません。メソッド（値として関数を持つプロパティ）は、この軽量バージョンではとにかくサポートされていませんが。

このソリューションは、無限ループで終了することなく、循環構造をコピーして、循環参照を持つオブジェクトで機能します。ここで「循環」とは、プロパティが「ツリー」内の「親」の1つを参照することを意味することに注意してください。

   [Object]_            [Object]_
     /    |\              /    |\
   prop     |           prop    |
     \_____/             |      |
                        \|/     |
                      [Object]  |
                          \     |
                         prop   |
                            \___/

葉を共有する木の構造はコピーされず、2つの独立した葉になります。

            [Object]                     [Object]
             /    \                       /    \
            /      \                     /      \
          |/_      _\|                 |/_      _\|  
      [Object]    [Object]   ===>  [Object]    [Object]
           \        /                 |           |
            \      /                  |           |
            _\|  |/_                 \|/         \|/
            [Object]               [Object]    [Object]
于 2012-05-23T23:24:50.827 に答える
2

コピーされたすべてのプロパティを追跡したい場合を除きます。

nullただし、すべてのプロパティが文字列、数値、配列、または単純なオブジェクトのいずれかであることが確実な場合は、次JSON.stringifyのように例外をキャッチして、後方参照があるかどうかを確認できます。

try {
    JSON.stringify(obj);
    // It's ok to make a deep copy of obj
} catch (e) {
    // obj has back references and a deep copy would generate an infinite loop
    // Or finite, i.e. until the stack space is full.
}

それは単なるアイデアであり、パフォーマンスについてはわかりません。大きなオブジェクトではかなり遅いのではないかと心配しています。

于 2012-05-23T22:03:29.517 に答える