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番目の方法でパフォーマンスが向上する可能性がありますか?

編集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 ページを更新しました。

4

4 に答える 4

2

「干し草の山」がソートされていない場合、それを高速化する方法はありません。コレクション内の要素がどのように順序付けられているかがわからない場合、それぞれをチェックするだけでよいため、本質的に直線的なものを見つけることができます。

この関数を同じ「干し草の山」で何度も使用している場合は、コレクションを並べ替え、並べ替えを使用して「針」をすばやく見つけることができます (さまざまな並べ替えと検索アルゴリズムを調べて、自分に合ったものを見つけます)。干し草の山がソートされた後にバイナリ検索を使用して「針」を見つけるなど、最善を尽くす必要があります。)

于 2012-07-02T20:06:26.073 に答える
0

for(..;..;..)ループではなくループを使用するfor(..in..)と、最大の違いが生じました。

（質問の最後にある編集3を参照してください）

于 2012-07-04T09:22:15.203 に答える
0

私にはこれは単なる部分文字列検索のようですが、文字列の構成要素である文字の代わりに数字が使用されています。そのため、特に針や干し草の山が大きくなる場合は、Boyer-Mooreを適用できます。

于 2012-07-04T11:19:39.437 に答える
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 に答える