0

我有一个数组数组。内部数组是 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 位整数数学可以使这个速度更快？

4

6 回答 6

0

这几乎和它一样快，比较 javascript 中的数组（与其他语言一样）是非常痛苦的。我假设您无法通过在执行内部循环之前比较长度来获得任何速度优势，因为您的数组是固定大小的？

只有我能想到的“优化”是简化语法，但它不会给你带来任何速度上的好处。你已经在尽你所能尽早返回。

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

于 2010-01-01T21:55:14.307 回答
0

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

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

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

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

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

于 2010-01-01T22:13:03.710 回答
0

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

于 2010-01-01T22:21:16.297 回答
0

我想到的唯一想法是将循环推入实现并用一些内存换取（推测，您必须测试假设）速度增益，这也依赖于非便携式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)
);
于 2010-01-01T22:36:32.163 回答
0 
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;
}
于 2010-01-02T15:31:22.120 回答
0

Knuth-Morris-Pratt 算法

Rumtime: O(n), n = 大海捞针的大小

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

于 2012-05-19T10:42:38.500 回答