javascript - javascriptで範囲をマッピングして一致させる

Question

JavaScriptで配列を使用して範囲をマップするのに最も効果的なものは何ですか？

私はこれを持っています：

var def = [70,200,1000];

そして、可能な数の配列は、次のように言います。

var n = [23,45,74,120,240,800,1204,2000];

さて、どうすればからnの値と一致する最も近い値を抽出できますdefか？

上記の例では、を取得し[74,240,800]ます。私は自分自身を明確にしたいと思います...

Answer 1

これが試してみます。繰り返してdef1n回だけ：

var nIndex = 0,
    nlen = n.length,
    prev,
    next;

for(var i = 0, ilen = def.length; i < ilen && nIndex < nlen; i++) {
    var current = def[i];

    while (n[nIndex] < current && nIndex < nlen - 1) nIndex++;

    next = n[nIndex];
    prev = nIndex == 0 ? next : n[nIndex - 1];

    result[i] = current - prev < next - current ? prev : next;
}
// values in def are larger than the greatest value in n
while (result.length < def.length) result.push(n[nlen-1]);

フィドル

Answer 2

http://jsfiddle.net/8bY2M/

var def = [70,200,1000];
var n = [23,45,74,120,240,800,1204,2000];

var result = [];

for (var i = 0; i < def.length; i++){
    var val = def[i];
    for (var j = 0; j < n.length; j++){
        var nVal = n[j];                
        if (nVal > val){
            var closest = n[j-1] == undefined ? nVal : 
                nVal - val > val - n[j-1] ? n[j-1] : nVal;

            result.push(closest);
            break;
        }    
    }
}

console.log(result); // outputs: [74, 240, 800] 

これは、2つの一致が発生した場合に、より大きな値に対応することに注意してください。（つまり、70と一致させようとしていて、nに66と74が含まれている場合、これは74と一致します）

Answer 3

他の解決策は非常に単純ですが、効率を求めている場合は、最初のリストを事前に並べ替えてから（まだ並べ替えられていない場合）、バイナリ検索を実行するのが最善の策です。これが私の解決策です：

var def = [70,200,1000];
var n = [23,45,74,120,240,800,1204,2000];

var findClosest = function(n, def) {
    var i, result = [];

    n = n.sort(function(a, b) { return a - b; }); //numeric sort


    var closestN = (function(val) {
        return (function search(r) {
            var mid = r.low + (0 | ((r.high - r.low) / 2));

            if(n[mid] === val) { 
                return n[mid];
            }

            if((r.high - r.low) === 1) {
                return n[r[(Math.abs(n[r.low] - val) > Math.abs(n[r.high] - val)) ? "high" : "low"]];
            }

            r[(val < n[mid]) ? "high" : "low"] = mid;

            return search(r);
        }({low : 0, high: (n.length - 1)})); 
    });

    for (i=0; i<def.length; i++) {
        result.push(closestN(def[i]));    
    }

    return result;
};

//The result can be obtained with findClosest(n, def)

覚えておいてください、それはあまり読みにくいです（バイナリ検索アルゴリズムに精通していない場合）。パフォーマンスが重要ではない単純なソリューションを探している場合、線形検索はより保守しやすいコードになります。ただし、このソリューションは、線形探索のようにO（n ^ 2）時間ではなく、O（n log（n））時間で実行されます。

ここで実際の動作を確認できます。

http://jsfiddle.net/naYu6/

「同点」の場合（リスト内の2つの値が問題の値から等距離にある場合、2つのうち低い方が選択されることに注意してください）。