Javascript 返回数组中“匹配”数组的位置索引

Javascript return position index of "matched" array within array

本文关键字：数组 位置 索引 返回 Javascript 匹配      更新时间：2023-09-26

是否有另一种更快的方法来返回另一个数组中数组的一部分的位置/索引（其中多个值匹配）？在我的寻路算法中，它被称为很多，所以可以尽可能快地做。

我目前的函数是：

// 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：

使用 jsperf.com 对所有 3 种描述的方法进行工作台标记（初始方法是最快的）：http://jsperf.com/finding-matched-array-within-array/3

编辑3：

刚刚用for(..;..;..)循环替换了for(..in..)循环（因为我知道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页面以包含此最新方法。

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

如果你在同一个"haystack"上一遍又

一遍地使用这个函数，你可以对集合进行排序，并使用排序来更快地找到"针"（查找不同的排序和搜索算法，以找到最适合你需求的算法，例如在haystack排序后使用二叉搜索来查找"针"。

我不知道

它是否更快，但你可以做这样的事情：

[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

干杯悠闲

使用 for(..;..;..) 循环而不是 for(..in..) 循环会产生最大的差异。

（请参阅问题末尾的编辑 3）

在我看来，

这只是一个子字符串搜索，但字符串的组成部分是数字而不是字符。因此，Boyer-Moore可能适用，特别是如果您的针头和大海捞针变大。

相关文章：