FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

JavaScript专题之学underscore在数组中查找指定元素 · Issue #37 · mqyqingfeng/Blog · GitHub

  1. mqyqingfeng
  2. Blog

Repository navigation

JavaScript专题之学underscore在数组中查找指定元素 #37

Open
Open
JavaScript专题之学underscore在数组中查找指定元素#37
Labels
专题系列

Description

mqyqingfeng
opened on Jul 26, 2017

前言

在开发中，我们经常会遇到在数组中查找指定元素的需求，可能大家觉得这个需求过于简单，然而如何优雅的去实现一个 findIndex 和 findLastIndex、indexOf 和 lastIndexOf 方法却是很少人去思考的。本文就带着大家一起参考着 underscore 去实现这些方法。

在实现前，先看看 ES6 的 findIndex 方法，让大家了解 findIndex 的使用方法。

findIndex

ES6 对数组新增了 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 - 1; 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

createIndexFinder

然而问题在于，findIndex 和 findLastIndex 其实有很多重复的部分，如何精简冗余的内容呢？这便是我们要学习的地方，日后面试问到此类问题，也是加分的选项。

underscore 的思路就是利用传参的不同，返回不同的函数。这个自然是简单，但是如何根据参数的不同，在同一个循环中，实现正序和倒序遍历呢？

让我们直接模仿 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);

sortedIndex

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(func, context) {
       if (context === void 0) return func;
       return function() {
           return func.apply(context, arguments);
      };
}

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

fromIndex

但是即使是数组的 indexOf 方法也可以多传递一个参数 fromIndex，从 MDN 中看到 fromIndex 的讲究可有点多：

设定开始查找的位置。如果该索引值大于或等于数组长度，意味着不会在数组里查找，返回 -1。如果参数中提供的索引值是一个负值，则将其作为数组末尾的一个抵消，即 -1 表示从最后一个元素开始查找，-2 表示从倒数第二个元素开始查找 ，以此类推。 注意：如果参数中提供的索引值是一个负值，仍然从前向后查询数组。如果抵消后的索引值仍小于 0，则整个数组都将会被查询。其默认值为 0。

再看看 lastIndexOf 的 fromIndex：

从此位置开始逆向查找。默认为数组的长度减 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 函数了，但是 underscore 在此基础上还做了两点优化。

第一个优化是支持查找 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 第三个参数不传开始搜索的下标值，而是一个布尔值 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 并不支持。

Activity

  1. mqyqingfeng
    added
    专题系列
    on Jul 26, 2017

  2. FrontToEnd commented on Jul 26, 2017

    FrontToEnd
    on Jul 26, 2017

    厉害了 大神

  3. mqyqingfeng commented on Jul 28, 2017

    mqyqingfeng
    on Jul 28, 2017
    OwnerAuthor

    @FrontToEnd []~(￣▽￣)~*

  4. xiaobinwu commented on Nov 5, 2017

    xiaobinwu
    on Nov 5, 2017

    方法都好妙

  5. HowardTangOvO commented on Nov 7, 2017

    HowardTangOvO
    on Nov 7, 2017

    🤒 之前看过loadsh的源码解读,感觉实现的方式都是差不多的~

  6. mqyqingfeng commented on Nov 8, 2017

    mqyqingfeng
    on Nov 8, 2017
    OwnerAuthor

    @HowardTangHw 确实如此，毕竟两者“本是同根生”~

  7. bailinlin commented on Nov 14, 2017

    bailinlin
    on Nov 14, 2017

    好了，看了你的专题，我要开始读源码了

  8. 0x8f701 commented on Dec 5, 2017

    0x8f701
    on Dec 5, 2017
    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;
}

    这里i的初始笔误了么

  9. mqyqingfeng commented on Dec 6, 2017

    mqyqingfeng
    on Dec 6, 2017
    OwnerAuthor

    @GopherJ 这是一个倒序循环，所以 i 是从 length 开始，i 的值依此递减

  10. 0x8f701 commented on Dec 7, 2017

    0x8f701
    on Dec 7, 2017

    @mqyqingfeng 是我糊涂了么233?还是没懂，有 arr[arr.length] 这个项么？

  11. mqyqingfeng commented on Dec 8, 2017

    mqyqingfeng
    on Dec 8, 2017
    OwnerAuthor

    @GopherJ 哈哈，尴尬了😂 感谢指出~

  12. 0x8f701 commented on Dec 8, 2017

    0x8f701
    on Dec 8, 2017

    @mqyqingfeng 哈哈我就说肯定笔误了。感谢分享啊！写的非常不错，有些地方我估计还得来来回回看几次，期待新的文章！

  13. dowinweb commented on Dec 15, 2017

    dowinweb
    on Dec 15, 2017

    楼主能不能解释下为什么参数中经常会写context，而实际并未传入呀，基本上都是undefined

  14. mqyqingfeng commented on Dec 15, 2017

    mqyqingfeng
    on Dec 15, 2017
    OwnerAuthor

    @dowinweb 像 ES5 的 map、reduce、forEach、find 等等函数，第二个参数都是 context，这是需要开发者写的时候传入的，这其实还算是个蛮常见的场景，举个例子：

    function Greet() {
  this.prefix = 'Hello'
  this.friends = ['dowinweb', 'kevin']
}

Greet.prototype.sayHello = function(){
  var self = this;
  var res = this.friends.map(function(item){
        return self.prefix + ' ' +  item
  })
  return res
}

var greet = new Greet();
console.log(greet.sayHello()) // [ "Hello dowinweb", "Hello kevin" ]

    一般 map 里的函数，如果要使用外部 this 的值，需要通过 var self = this 这种形式。

    其实我们可以写的更加优雅，就是利用 context 这个参数：

    function Greet() {
  this.prefix = 'Hello'
  this.friends = ['dowinweb', 'kevin']
}

Greet.prototype.sayHello = function(){
  var res = this.friends.map(function(item){
        return this.prefix + ' ' +  item
  }, this)
  return res
}

var greet = new Greet();
console.log(greet.sayHello())  //  // [ "Hello dowinweb", "Hello kevin" ]

    这个算是一个小技巧吧~

  15. dowinweb commented on Dec 18, 2017

    dowinweb
    on Dec 18, 2017

    @mqyqingfeng 嗯嗯，学习了，谢谢

  16. 6 remaining items

  17. iiicon commented on Jan 23, 2018

    iiicon
    on Jan 23, 2018
    function cb(fn, context) {
    return function(obj) {
        return fn ? fn.call(context, obj) : obj;
    }
}

    传入一个函数，返回另一个函数，这属于函数柯里化吗？
    平时写的时候总是抽象不到这个层面。

  18. zjp6049 commented on Jan 24, 2018

    zjp6049
    on Jan 24, 2018

    @iiicon 所以我也感觉写的so nb，脑洞太大

  19. mqyqingfeng commented on Jan 24, 2018

    mqyqingfeng
    on Jan 24, 2018
    OwnerAuthor

    @iiicon 函数柯里化是指将一个 n 元函数转化为 n 个一元函数，我觉得这个例子叫做高阶函数更好些，高阶函数就是传入一个函数，返回一个函数。

    说起来这篇文章并没有讲到这样的例子呀~

    关于平时写的时候抽象不到这个层次的问题，实际上，这种方法很多时候是"被迫"要去做的，你比如说函数防抖：

    document.getElementById('test').onmouseover = fn

    每当 mouseover 的时候，就会去执行 fn 函数，如果我们要做防抖，我们可以直接在 fn 函数内部去做，但这样就会跟 fn 的代码连在一起，如果我们要给多个函数都做防抖，岂不是每次都要写一遍，所以我们才会单独抽离写一个 debounce 函数：

    var debounceFn = debounce(fn);
document.getElementById('test').onmouseover = debounceFn

    你看赋给 onmouserover 的值必须要是一个函数，所以你写 debounce 函数的时候，不就是要传入一个函数，返回另一个函数吗？

    关于你写的这个 cb 函数，我最一开始以为是 underscore 中的 cb 函数，后来觉得这个有点像 bind 函数的模拟实现：

    fucntion bind(fn, context){
         return function(){
               return fn.apply(context,arguments);
         }
}

    bind 函数其实也是同样的道理，我们只是想将一个函数的 this 指向一个固定的 context，如果我们直接使用 fn.call(context) ，就执行了 fn 函数，其实我们现在还并不想执行这个函数，所以为了不让他立刻执行，就可以返回一个函数，里面”包裹“着执行 fn 函数的代码。

    嗯，说了这么多，还是要多看多思考……

    最后，

    记得早点睡觉哈~ 😀

  20. iiicon commented on Jan 24, 2018

    iiicon
    on Jan 24, 2018

    @mqyqingfeng 我其实是拷贝的你的 sortedIndex 第二版的 iteratee 函数，我感觉和 bind 关系不大，如果不抽象一般就 iteratee(array[mid], fn, context), 我一般就这样

    还有就是在南方这边工作就是要中午睡一大觉，晚上不熬个夜感觉贼浪费，不过你说的很对，得爱惜自己的身体
    古耐~~

  21. mqyqingfeng commented on Jan 25, 2018

    mqyqingfeng
    on Jan 25, 2018
    OwnerAuthor

    @iiicon 哈哈，我竟然没有发现……😂 这个 cb 函数是我当时简写 underscore 的 cb 函数得来的……现在看来，写法上有点莫名其妙，给你造成了困扰，我很抱歉，完整的 cb 函数还要参考 underscore 系列之内部函数 cb 和 optimizeCb

    如果我现在写的话，应该是写成：

    function cb(func, context) {
       if (context === void 0) return func;
       return function() {
           return func.apply(context, arguments);
      };
}

    我还是修改一下吧~

  22. Tan90Qian commented on Apr 17, 2018

    Tan90Qian
    on Apr 17, 2018

    @mqyqingfeng 在具有fromIndex参数的实现版本里，没有考虑传入的参数为NaN的问题，因为typeof NaN为“number”，也会走进if语句的代码体内，导致参数被污染，而原生的indexOf没有这个问题[1,2,3,1].lastIndexOf(1,NaN) //0以及[1,2,3,1].indexOf(1,NaN) // 0，虽然不知道为什么都返回了0。。。

  23. mqyqingfeng commented on Apr 24, 2018

    mqyqingfeng
    on Apr 24, 2018
    OwnerAuthor

    @Tan90Qian 感谢指出~ 确实有这个问题~

    此外，关于 [1,2,3,1].lastIndexOf(1,NaN) 结果为 0，是因为 fromIndex 如果为 NaN , fromIndex 的值相当于被设置为 0，这点在 MDN 的 lastIndexOf 的模拟实现中可以看出：

  24. habc0807 commented on Dec 28, 2018

    habc0807
    on Dec 28, 2018

    最近我在手动实现数组的常用方法，同事推荐看你的这篇文章，受益匪浅。

  25. Dannyzn commented on Sep 29, 2020

    Dannyzn
    on Sep 29, 2020
    indexOf ---->. var index = dir > 0 ? 0 : length - 1;
for (; index >= 0 && index < length; index += dir) 
不管是正序遍历还是逆序遍历都是满足 于这个 循环遍历的条件

  26. Dannyzn commented on Sep 29, 2020

    Dannyzn
    on Sep 29, 2020
    学习笔记分析
function createIndexOf(dir) {
  return function(array, item, idx) {
    var length = array.length;

    var i = 0;
 
    // [0,1,1,2,4]
    // idx 正数  0, 1, 2, 3, 4
    // idx 负数  -5,-4,-3,-2,-1
    
    // idx 的格式判断
    // dir > 0 ===>  我们需要的是 i
    // dir < 0 ===>  我们需要的是 length
    // 和下面的for 循环 成为 一一对应的 关系

    //   dir > 0  从前向后查找  length 此时是数组的长度(需要遍历的次数)
    //  i 是指 从数组 array[i] 开始遍历 
    //  在 dir > 0  ===>  idx >= 0  i = idx
    //  在 dir > 0  ===>  idx <  0  i = Math.max(length + idx, 0)

    //   dir < 0  从后向前查找     i 此时是初始值  
    //  length  是指这当前数组可遍历的次数(长度) 
    //  dir < 0  ===> idx >= 0   length  Math.min(idx + 1, length)
    //  dir < 0  ===> idx < 0    length  idx + length + 1;
    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;
      }
    }

    // dir 1 和 -1 => 正向查找 he 逆向查找 

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

    return -1;
  }
}

  27. lqPrototype commented on Dec 8, 2020

    lqPrototype
    on Dec 8, 2020

    字符串的indexOf 有很大的学问，楼主可以看看。

  28. yinju123 commented on Apr 24, 2021

    yinju123
    on Apr 24, 2021

    可能是我技术的问题，我感觉稍微有点乱。typeof idx == "number这个步骤只对后面的for循环有用吧，我觉得可以把它跟for循环写在一起。然后我有个问题sortedIndex && idx && length其中的 idx是什么意思，而且还是else if判断的，那么传入idx时，sortedIndex是无效的

    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;

  29. dsphoebe commented on Jan 13, 2022

    dsphoebe
    on Jan 13, 2022

    @yinju123 https://github.com/jashkenas/underscore/blob/58df1085cdb05cb0888719c5fe5493948604ab69/test/arrays.js#L351-L353 underscore 的测试案例里面可以看出来，idx 是在非数字的情况下，才会触发 sortedIndex 的执行。

  30. zlh-GitHub commented on Jan 19, 2023

    zlh-GitHub
    on Jan 19, 2023

    感觉把idx 改为 fromIndex， length 改为 end 会比较好理解，然后逆向查找的判断里面 end 的计算可以不用再 +1，相当于计算查找范围的最后的位置，这样在 for 循环里的三元运算中的 end 也不用再减了，最后把 i < end - 1 改为 i <= end 就行

    const createIndexOfFinder = dir => {
  return (arr, item, fromIndex) => {
    let end = arr.length;
    let i = 0;
    if (typeof fromIndex === 'number') {
      if (dir > 0) { // 正向查找
        ......
      } else { // 逆向查找
        end = fromIndex >= 0 ? Math.min(fromIndex, end) : fromIndex + end;
      }
    }
    for (i = dir > 0 ? i : end; i >= 0 && i <= end; i += dir) {
      ......
    }
    return -1;
  }
}

  31. bobo-only-cv commented on Mar 19, 2023

    bobo-only-cv
    on Mar 19, 2023

    针对于lastIndexOf，关于NaN的查找哪里有点bug
    根据‘’其绝对值大于数组长度，则方法返回 -1，即数组不会被查找。‘’
    这句话
    console.log(lastIndexOf([NaN,1,2],NaN,-5)) 应该返回-1的；
    实际调用文中的方法会返回0
    原因是因为slice去截取的时候length作为负数也是会从数组末尾向前的偏移

    可以增加一条判断
    if (typeof idx == "number") { if (dir > 0) { i = idx >= 0 ? idx : Math.max(length + idx, 0); } else { //此处可以增加一条判断 if(Math.abs(idx)>length) return -1; length = idx >= 0 ? Math.min(idx + 1, length) : idx + length + 1; } }

    不知道说的对不对

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    专题系列

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      Back | FazBrowse Home | New Git URL