JavaScript特定のテーマの学undersscoreは配列の中で指定の要素を探します.


JavaScriptテーマシリーズ第10編は、どのように配列から指定要素を検索するかを説明し、undesocreに従ってfindIndexとfindLastIndex、sortedIndex、indexOfとlastIndexOfを実現します.
前言
開発の中で、私達は常に行列の中で指定の元素の需要を探すことに出会って、みんなはこの需要があまりにも簡単だと感じて、しかしどのように優雅なのは1つのfindIndexとfindLastindex、indexOfとlastIndexOf方法を実現しますか?本論文では、アンダースコアを参考にして、みんなでこれらの方法を実現します.
実現する前に、まずES 6のfindIndex方法を見てみて、findIndexの使い方を理解させます.
findIndex
ES 6は配列に対して、findIndex方法を追加しました.これは配列の中で提供された関数を満たす最初の要素のインデックスを返します.そうでなければ、-1を返します.
例を挙げます
function isBigEnough(element) {
  return element >= 15;
}

[12, 5, 8, 130, 44].findIndex(isBigEnough);  // 3
findIndexは、最初の15より大きい要素の下付きを見つけるため、最後に3を返します.
簡単ではないですか?実は、自分でfindIndexを実現するのも簡単です.
findIndexを実現します
考え方はもちろんはっきりしています.いろいろ見て、要求に合った値を返してください.
function findIndex(array, predicate, context) {
    for (var i = 0; i < array.length; i++) {
        if (predicate.call(context, array[i], i, array)) return i;
    }
    return -1;
}

console.log(findIndex([1, 2, 3, 4], function(item, i, array){
    if (item == 3) return true;
})) // 2
findLastIndex
findIndexは順を追って検索しますが、indexOfには対応するlastIndexOf方法があります.私たちも順序を追って検索したfindLastIndex関数を書きたいです.自然を実現するのも簡単です.サイクルを修正すればいいです.
function findLastIndex(array, predicate, context) {
    var length = array.length;
    for (var i = length; i >= 0; i--) {
        if (predicate.call(context, array[i], i, array)) return i;
    }
    return -1;
}

console.log(findLastIndex([1, 2, 3, 4], function(item, index, array){
    if (item == 1) return true;
})) // 0
createIndex Finder
しかし問題なのは、findIndexとfindLastIndexは実は多くの重複部分があります.どうやって冗長な内容を合理化しますか?これは私たちが勉強したいところです.今後面接でこのような質問をするのも追加の選択肢です.
underscoreの考えは、パラメータの違いを利用して、異なる関数を返します.これはもちろん簡単ですが、どのようにパラメータによって同じサイクルで正順と倒順の遍歴ができますか?
アンダースコアの実現を直接にまねましょう.
function createIndexFinder(dir) {
    return function(array, predicate, context) {

        var length = array.length;
        var index = dir > 0 ? 0 : length - 1;

        for (; index >= 0 && index < length; index += dir) {
            if (predicate.call(context, array[index], index, array)) return index;
        }

        return -1;
    }
}

var findIndex = createIndexFinder(1);
var findLastIndex = createIndexFinder(-1);
sorted Index
findIndexとfindLastIndexの需要は終わったと言えますが、もう一つの新しい需要が来ました.順序の良い配列の中でvalueの対応する位置を見つけて、配列を挿入した後も依然として秩序正しい状態を維持します.
この関数をsortedIndexと命名すると、効果は以下の通りです.
sortedIndex([10, 20, 30], 25); // 2
つまり、もし、25がこの下付きで配列を挿入すると、配列は[10,20,25,30]となり、配列は依然として秩序立っている状態になることに注意する.
これはどうやって実現しますか?
秩序化された配列であるならば、遍歴を必要とせず、大きいものは二分ルックアップ法を使用して、値の位置を確定することができます.一枚書いてみましょう.
//    
function sortedIndex(array, obj) {

    var low = 0, high = array.length;

    while (low < high) {
        var mid = Math.floor((low + high) / 2);
        if (array[mid] < obj) low = mid + 1;
        else high = mid;
    }

    return high;
};

console.log(sortedIndex([10, 20, 30, 40, 50], 35)) // 3
今の方法は使えますが、通用性が足りないです.例えば、このような状況を解決したいです.
// stooges             The Three Stooges
var stooges = [{name: 'stooge1', age: 10}, {name: 'stooge2', age: 30}];

var result = sortedIndex(stooges, {name: 'stooge3', age: 20}, function(stooge){
    return stooge.age
});

console.log(result) // 1
だから、私たちはもう一つのパラメータiteratee関数を加えて、配列の各要素を処理したいです.普通はこの時、this指向の問題にも関連します.だから、私たちはもう一つのcontextを伝えて、thisを指定できます.このような関数はどうやって書きますか?
//    
function cb(fn, context) {
    return function(obj) {
        return fn ? fn.call(context, obj) : obj;
    }
}

function sortedIndex(array, obj, iteratee, context) {

    iteratee = cb(iteratee, context)

    var low = 0, high = array.length;
    while (low < high) {
        var mid = Math.floor((low + high) / 2);
        if (iteratee(array[mid]) < iteratee(obj)) low = mid + 1;
        else high = mid;
    }
    return high;
};
indexOf
sortedIndexも完成しました.今はindexOfとlastIndexOf関数を書いてみます.findIndexとFindLastIndexの方式を勉強します.
//    
function createIndexOfFinder(dir) {
    return function(array, item){
        var length = array.length;
        var index = dir > 0 ? 0 : length - 1;
        for (; index >= 0 && index < length; index += dir) {
            if (array[index] === item) return index;
        }
        return -1;
    }
}

var indexOf = createIndexOfFinder(1);
var lastIndexOf = createIndexOfFinder(-1);

var result = indexOf([1, 2, 3, 4, 5], 2);

console.log(result) // 1
from Index
しかし、配列のindexOf方法であっても、一つのパラメータfrom Indexを多く伝達することができます.MDNからfrom Indexのこだわりを見ると、ちょっと多いかもしれません.
検索開始位置を設定します.インデックス値が配列長以上である場合、配列内で検索されないことを意味し、-1を返します.パラメータに提供されるインデックス値が負の値である場合は、配列の最後の要素から検索を開始することを表します.-2は、下から2番目の要素から検索を開始することを表します.これに類推します.注意:パラメータから供給されるインデックス値が負の値である場合は、依然として前から後ろへ照会する配列です.相殺されたインデックス値がまだ0以下の場合、配列全体が照会されます.そのデフォルトは0です.
lastIndexOfのfrom Indexを見てみます.
この位置から逆方向に検索します.デフォルトでは、配列の長さを1に減らすということです.つまり、配列全体が検索されます.この値が配列の長さ以上の場合、配列全体が検索されます.負の値であれば、配列の端から前へのオフセットと見なします.この値が負であっても、配列は後から前へ検索されます.この値が負の場合、その絶対値が配列長より大きい場合、方法は-1を返します.つまり配列は検索されません.
こんなに多くの規則に従って、私達は第二版を書いてみます.
//    
function createIndexOfFinder(dir) {

    return function(array, item, idx){
        var length = array.length;
        var i = 0;

        if (typeof idx == "number") {
            if (dir > 0) {
                i = idx >= 0 ? idx : Math.max(length + idx, 0);
            }
            else {
                length = idx >= 0 ? Math.min(idx + 1, length) : idx + length + 1;
            }
        }

        for (idx = dir > 0 ? i : length - 1; idx >= 0 && idx < length; idx += dir) {
            if (array[idx] === item) return idx;
        }
        return -1;
    }
}

var indexOf = createIndexOfFinder(1);
var lastIndexOf = createIndexOfFinder(-1);
最適化
これまでは原生のindexOf関数に近いですが、undersscoreはこの基礎の上に2点の最適化をしました.
最初の最適化はNaNの検索をサポートすることである.
NaNは全部NaNに等しくないので、原生のindexOfはNaNの下标を探し出すことができません.
[1, NaN].indexOf(NaN) // -1
この機能はどうやって実現しますか?
配列の中から条件に合った値の下付きを見つけるということですか?最初に書いたfindIndexではないですか?
書いてみましょう.
//    
function createIndexOfFinder(dir, predicate) {

    return function(array, item, idx){

        if () { ... }

        //         NaN
        if (item !== item) {
            //                isNaN        
            idx = predicate(array.slice(i, length), isNaN)
            return idx >= 0 ? idx + i: -1;
        }

        for () { ... }
    }
}

var indexOf = createIndexOfFinder(1, findIndex);
var lastIndexOf = createIndexOfFinder(-1, findLastIndex);
第二の最適化は,秩序化した配列のより速い二分割ルックアップをサポートすることである.
indexOfの3番目のパラメータが検索を開始するアンダースケール値ではなく、ブール値trueであると考えられています.配列は順序の良い配列であると考えられています.このときは、より速い二分割法で検索されます.このときは、私たちが書いたsortedIndex関数を利用することができます.
ここで直接最終のソースコードを渡します.
//    
function createIndexOfFinder(dir, predicate, sortedIndex) {

    return function(array, item, idx){
        var length = array.length;
        var i = 0;

        if (typeof idx == "number") {
            if (dir > 0) {
                i = idx >= 0 ? idx : Math.max(length + idx, 0);
            }
            else {
                length = idx >= 0 ? Math.min(idx + 1, length) : idx + length + 1;
            }
        }
        else if (sortedIndex && idx && length) {
            idx = sortedIndex(array, item);
            //                   ,            
            return array[idx] === item ? idx : -1;
        }

        //       NaN
        if (item !== item) {
            idx = predicate(array.slice(i, length), isNaN)
            return idx >= 0 ? idx + i: -1;
        }

        for (idx = dir > 0 ? i : length - 1; idx >= 0 && idx < length; idx += dir) {
            if (array[idx] === item) return idx;
        }
        return -1;
    }
}

var indexOf = createIndexOfFinder(1, findIndex, sortedIndex);
var lastIndexOf = createIndexOfFinder(-1, findLastIndex);
注目すべきことは、underscoreの実装において、indexOfだけが順序配列をサポートして二分割ルックアップを使用しており、lastIndexOfはサポートされていません.