javascript - 参照と等しいプリミティブが正確な位置を維持するように、配列 A の後に配列 B を並べ替えます。

Question

更新 2

以前のソート関数はすべての型を考慮していなかったので、安定性だけでなくパフォーマンスも約 100% 向上させました1 == "1"。 @Esailja は指摘します。

質問の意図は、私のこの回答を改善することです。私はその質問が好きで、それが受け入れられて以来、ソート機能から絞り出すパフォーマンスがあるように感じました。どこから手をつければよいのか手がかりがあまりなかったので、ここでこの質問をしました。
_{多分これも物事を明確にする}

アップデート

多くの人が私が十分に具体的ではないと述べたので、私は完全な質問を言い換えました。sortまた、質問の意図をよりよく表現するために関数を書き直しました。

arrayPrevを配列 ( A ) とします。ここで、Aは0 から n 個の要素' ( E ) で構成されます。
- 要素を次のいずれかにします
  - プリミティブ型の
    - ブール値、文字列、数値、未定義、null
  - オブジェクトO への参照。ここで、O .type = [object Object]であり、Oは以下で構成できます。
    - 0 から n までのプロパティ P。ここで、PはElement plus のように定義されます。
      - O内の任意のPへの循環参照
    - 任意のOを 1 ～ n 回含むことができます。GetReferencedName(E1) === GetReferencedName(E2) ...という意味で
  - Oへの参照。ここで、O .type = [object Array]であり、OはA のように定義されます
  - A内の任意のEへの循環参照
arrayCurr をarrayPrevと同じ長さの配列にする

次の例で説明します

var x = {
    a:"A Property",
    x:"24th Property",
    obj: {
        a: "A Property"
    },
    prim : 1,
}
x.obj.circ = x;

var y = {
    a:"A Property",
    x:"24th Property",
    obj: {
        a: "A Property"
    },
    prim : 1,
}
y.obj.circ = y;
var z = {};

var a = [x,x,x,null,undefined,1,y,"2",x,z]
var b = [z,x,x,y,undefined,1,null,"2",x,x]    
console.log (sort(a),sort(b,a))

問題は、オブジェクトへの参照またはプリミティブの値が以前とまったく同じ位置を共有するように、配列Bを効率的にソートするにはどうすればよいかということです。

上記の例のように

コンソールログ

結果の配列がルールに該当する場所。

arrayPrevにElementが含まれ、arrayCurrにElementが含まれますab
1. arrayPrevをCompareFunction Cでソートします。
2. arrayCurrを同じCでソートします。
  - arrayCurの並べ替えの結果を、 arrayCurの位置nでEにアクセスするときに、nを5 などとします。
    - Eの型がObjectの場合 GetReferencedName(arrayCurr[n]) === GetReferencedName(arrayPrev[n])
    - Eの型がプリミティブの場合 GetValue(arrayCurr[n]) === GetValue(arrayPrev[n])
    - 例b[n] === a[n]：b[5] === a[5]
  - つまり、すべての要素をタイプ別にグループ化し、値でソートする必要があります。
  - Cの関数 Fへの呼び出しは、シムを必要とせずに互換性が得られるように、少なくとも ES5 より前に実装する必要があります。

私の現在のアプローチは、arrayPrev でオブジェクトをマークして、arrayCurrでそれに応じて並べ替え、後で再度マーカーを削除することです。しかし、それはむしろそれほど効率的ではないようです。現在sort使用されている関数は次のとおりです。

function sort3 (curr,prev) {
         var weight = {
            "[object Undefined]":6,         
            "[object Object]":5,
            "[object Null]":4,
            "[object String]":3,
            "[object Number]":2,
            "[object Boolean]":1
        }
        if (prev) { //mark the objects
            for (var i = prev.length,j,t;i>0;i--) {
                t = typeof (j = prev[i]);
                if (j != null && t === "object") {
                     j._pos = i;   
                } else if (t !== "object" && t != "undefined" ) break;
            }
        }

        curr.sort (sorter);

        if (prev) {
            for (var k = prev.length,l,t;k>0;k--) {
                t = typeof (l = prev[k]);
                if (t === "object" && l != null) {
                    delete l._pos;
                } else if (t !== "object" && t != "undefined" ) break;
            }
        }
        return curr;

        function sorter (a,b) {

             var tStr = Object.prototype.toString
             var types = [tStr.call(a),tStr.call(b)]
             var ret = [0,0];
             if (types[0] === types[1] && types[0] === "[object Object]") {
                 if (prev) return a._pos - b._pos
                 else {
                     return a === b ? 0 : 1;
                 }
             } else if (types [0] !== types [1]){
                     return weight[types[0]] - weight[types[1]]
             }



            return a>b?1:a<b?-1:0;
        }

    }

Fiddleと JSPerf があります( _{自由にスニペットを追加してください)}
_{そして古いFiddle}

javascript - 参照と等しいプリミティブが正確な位置を維持するように、配列 A の後に配列 B を並べ替えます。

アップデート

4 に答える 4

Related

Reference