javascript - javascript: 迅速な Array.contains(otherArray)?

Question

私は配列の配列を持っています。内側の配列は 16 個のスロットで、それぞれに 0..15 の番号が付いています。単純な置換。

外側の配列に含まれる配列のいずれかに、テスト配列 (16 個の値の順列) と同じ値があるかどうかを確認したい。

私はこれを次のように簡単に行うことができます：

var containsArray = function (outer, inner) {
    var len = inner.length;
    for (var i=0; i<outer.length;  i++) {
        var n = outer[i];
        var equal = true;
        for (var x=0; x<len; x++) {
            if (n[x] != inner[x]) {
                equal = false;
                break;
            }
        }
        if (equal) return true;
    }
    return false;
}

しかし、より速い方法はありますか？

各順列に整数値 (実際には 64 ビット整数) を割り当てることはできますか?

スロットの各値は 0..15 で、4 ビットで表現できることを意味します。16 個のスロットがあり、これは合計 64 ビットの情報を意味します。

C# では、Int64 型を使用するこのアプローチを使用して、内側の配列 (または順列) のハッシュを計算して格納するのは簡単です。Javascriptには、これを高速にする64ビット整数演算がありますか?

score 0 · Accepted Answer

私が思いついた唯一のアイデアは、ループを実装にプッシュし、メモリを（推測では、仮定をテストする必要があります）速度の向上と交換することです。これもポータブルではありませんArray.prototype.{toSource,map}。

var to_str = function (a) {
    a.sort();
    return a.toSource();
}
var containsString = function (outer, inner) {
    var len = outer.length;
    for (var i=0; i<len;  ++i) {
        if (outer[i] == inner)
            return true;
    }
    return false;
}

var found = containsString(
    outer.map(to_str)
  , to_str(inner)
);

score 0 · Accepted Answer

Knuth–Morris–Prattアルゴリズム

ラムタイム：O（n）、n=干し草の山のサイズ

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

score 0 · Accepted Answer

var containsArray = function (outer, inner) {
    var innerLen  = inner.length, 
        innerLast = inner.length-1, 
        outerLen  = outer.length;

    outerLoop: for (var i=0; i<outerLen;  i++) {
        var n = outer[i];

        for (var x = 0; x < innerLen; x++) {
            if (n[x] != inner[x]) {
                continue outerLoop;
            }
            if (x == innerLast) return true;
        }
    }
    return false;
}

score 0 · Accepted Answer

外部配列内の特定の配列インスタンスを本当に探していますか? つまり、innerが一致する場合、一致したネストされた配列と同じ参照を共有しますか? その場合は、内部比較ループをスキップして、次のようにするだけです。

var containsArray = function (outer, inner) {
    var len = inner.length;
    for (var i=0; i<outer.length;  i++) {
        if (outer[i] === inner) return true;
    }
    return false;
}

これができない場合でも、ループの反復ごとに .length フィールドを参照しないことで、いくらか前進することができます。これは、参照されるたびに長さが再計算されるため、コストのかかる参照です。

var containsArray = function (outer, inner) {
    var innerLen = inner.length, outerLen = outer.length;
    for (var i=0; i<outerLen;  i++) {
        var n = outer[i];
        var equal = true;

        for (var x=0; x<innerLen; x++) {
            if (n[x] != inner[x]) {
                equal = false;
            }
        }
        if (equal) return true;
    }
    return false;
}

また、この形式のループの方が高速であるという主張を見てきましたが、測定可能な違いが生じるケースは見たことがありません。

var i = 0;
while (i++ < outerLen) {
   //...
}

編集equal: いいえ、変数を削除しないでください。それは私の悪い考えでした。

score 0 · Accepted Answer

の文字列値を比較するのはどうですかmyInnerArray.join('##') == myCompareArray.join('##');（もちろん、後者の結合は、そのような反復ごとではなく、一度実行して変数に格納する必要があります）。

実際のパフォーマンスの違いがどうなるかはわかりませんが、コードはより簡潔になります。何度も比較を行っている場合は、これらの値をどこかに保存しておくことができ、少なくとも 2 回目はおそらく比較が速くなります。

ここでの明らかな問題は、比較が誤検知を起こしやすいことです。

var array1 = ["a", "b"];
var array2 = ["a##b"];

しかし、データを十分に信頼できる場合、それを無視できるでしょうか? それ以外の場合は、結合結果と長さを常に比較する場合、これは問題になりません。

score 0 · Accepted Answer

JavaScript で配列を比較するのは (他の言語と同様に) 非常に苦痛です。配列のサイズが固定されているため、内側のループを実行する前に長さを比較しても、速度の利点は得られないと思いますか?

私が考えることができる唯一の「最適化」は構文を単純化することですが、速度の利点はありません。できるだけ早く戻ることで、あなたはすでにできる限りのことをしています。

64ビット整数を使用するというあなたの提案は興味深いように聞こえますが、javascriptには(私の知る限り)Int64型がないため、より複雑なものが必要になり、実際の使用では現在の方法よりも遅くなる可能性があります.

javascript - javascript: 迅速な Array.contains(otherArray)?

6 に答える 6

Related

Reference