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 位整数数学可以让这个速度更快？

Answer 1

这已经是最快的了，在 javascript 中比较数组（就像在其他语言中一样）是相当痛苦的。我假设在执行内部循环之前比较长度无法获得任何速度优势，因为您的数组具有固定大小？

我能想到的唯一“优化”是简化语法，但它不会给你带来任何速度上的好处。您已经尽一切努力尽早返回。

您使用 64 位整数的建议听起来很有趣，但由于 javascript 没有 Int64 类型（据我所知），这将需要更复杂的东西，并且在实际使用中实际上可能比您当前的方法更慢。

Answer 2

如何比较 myInnerArray.join('##') == myCompareArray.join('##'); 的字符串值（当然后一个连接应该完成一次并存储在变量中） ，而不是每次迭代都这样）。

我不知道实际的性能差异是什么，但代码会更简洁。如果您多次进行比较，则可以将这些值保存在某个地方，并且至少第二次比较可能会更快。

这里明显的问题是比较容易出现误报，请考虑

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

但是如果您可以充分依赖您的数据，您可能可以忽略这一点？否则，如果您总是比较连接结果和长度，这不会成为问题。

Answer 3

您真的在外部数组中寻找特定的数组实例吗？也就是说，如果 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< /代码> 变量；对我来说这是一个坏主意。

Answer 4

我唯一的想法是将循环推入实现中，并用一些内存换取（推测，你必须测试假设）速度增益，这也依赖于不可移植的 Array.prototype。{ toSource，地图}：

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

Answer 5

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

Answer 6

Knuth–Morris–Pratt 算法

Rumtime：O(n)，n = 干草堆的大小

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