是否有另一種更快的方法返回另一個數組中某個數組的部分位置/索引（其中多個值匹配）？這在我的尋路算法中被稱爲很多，因此可以儘可能快地完成。數組中「匹配」數組的Javascript返回位置索引

我目前的功能是：

// 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(..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頁面以包含此最新方法。

來源

2012-07-02 Alex

可能要發佈到http://codereview.stackexchange.com/。 – j08691

謝謝，剛剛發佈了整個尋路代碼：http://codereview.stackexchange.com/questions/13258/javascript-a-pathfinding-function-for-tile-based-game-optimisation – Alex

如果「haystack」沒有排序，那麼沒有辦法讓它更快。不知道集合中的元素是如何排序的，因爲你只需要檢查每一件事情就可以發現它們之間的線性關係。

如果您在反覆使用同一個「乾草堆」上使用此功能，您可以對集合進行排序，並使用排序使其更快地找到「針」（查找不同的排序和搜索算法以查找一個適合您的需要最好的，如使用二進制搜索找到了「針」乾草堆被排序之後）

來源

2012-07-02 20:06:26 Caleb

我不知道，如果它的速度更快，但你可以這樣做：

[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-02 20:07:16 laidback

謝謝，可惜這顯著慢。 :( – Alex

我沒有對此做任何測量，但由於額外的操作，這是有意義的。 – laidback

使用for(..;..;..)循環而不是for(..in..)循環進行的最大區別。

（請參見編輯3在問題結束）

來源

2012-07-04 09:22:15 Alex

在我看來，這僅僅是一個字符串搜索，但用數字代替字符爲字符串的組件。因此，Boyer-Moore可能是適用的，特別是如果你的針和乾草堆變大。

來源

2012-07-04 11:19:39

數組中「匹配」數組的Javascript返回位置索引

編輯：

編輯2：

編輯3：

回答

相關問題