1

是否有另一种更快的方法来返回另一个数组中的部分数组的位置/索引（多个值匹配）？它在我的寻路算法中被调用了很多，因此可以尽可能快地完成。

我目前的功能是：

// Haystack can be e.g. [[0,1,278.9],[4,4,22.1212]]

function coordinate_location_in_array(needle,haystack){
    for(n in haystack){
        if(haystack[n][0]==needle[0] && haystack[n][1]==needle[1]) return n;
    }
    return false;
}

// Needle of [0,1]: returns 0
// Needle of [4,4]: returns 1
// Needle of [6,7]: returns false

编辑：

我一直在搞砸，想出了一个（相当可怕的）基于字符串操作的方法（从而避免了代价高昂的for循环）。我认为它仍然稍微慢一些。有人可以对这些方法进行基准测试吗？

function coordinate_location_in_array(needle,haystack) {
    var str1 = ':' + haystack.join(':');
    var str2 = str1.replace(':'+needle[0]+','+needle[1],'*').split('*')[0]; 
    if(str2.length == str1.length) return false;
    var preceedingElements = str2.match(/:/g);
    return preceedingElements!=null?preceedingElements.length:0;
}

也许通过一些改进，第二种方法可能会提供一些性能提升？

编辑2：

Bench 使用 jsperf.com 标记了所有 3 种描述的方法（初始方法最快）：http: //jsperf.com/finding-matched-array-within-array/3

编辑3：

刚刚用for(..in..)循环替换了for(..;..;..)循环（因为我知道haystack数组永远不会有“间隙”），性能似乎有了显着提高：

function coordinate_location_in_array(needle,haystack){
    for(var n=0;n<haystack.length;n++){
        if(haystack[n][0]==needle[0] && haystack[n][1]==needle[1]) return n;
    }
    return false;
}

我已经更新了 jsperf 页面以包含这个最新的方法。

4

4 回答 4

2

如果“干草堆”没有排序，那么就没有办法让它更快。不知道集合中的元素是如何排序的，因此从本质上可以线性地找到一些东西，因为你只需要检查每一件事。

如果您一遍又一遍地在同一个“干草堆”上使用此功能，您可以对集合进行排序，并使用排序来更快地找到“针”（查找不同的排序和搜索算法以找到适合您的需要最好的，例如在草垛排序后使用二进制搜索找到“针”。）

于 2012-07-02T20:06:26.073 回答
0

使用for(..;..;..)循环而不是for(..in..)循环产生了最大的不同。

（见问题末尾的编辑 3）

于 2012-07-04T09:22:15.203 回答
0

我不知道它是否更快，但您可以执行以下操作：

[1,2,3,4].slice(0,2).toString() == [1,2].toString()

在您的情况下，它将是：

function coordinate_location_in_array(needle,haystack){
for(n in haystack){
    if(haystack[n].slice(0,2).toString() == needle.toString()) return n
}
return false;

}

还发现了这篇文章，其中涵盖了 JS 数组的比较：compare-two-arrays-javascript-associative

干杯悠闲

于 2012-07-02T20:07:16.447 回答
0

在我看来，这只是一个子字符串搜索，但数字而不是字符是字符串的组成部分。因此，Boyer-Moore可能适用，尤其是当你的针和干草堆变大时。

于 2012-07-04T11:19:39.437 回答