Array数组的indexOf、includes vs for-loop性能比较

发表于 | 更新于: | 分类于 |
字数统计: 682 | 阅读时长 ≈ 3

Array数组的indexOf、includes vs for-loop性能比较

最近遇到一道算法题，然后有些人会使用 includes、indexOf 去判断是否存在另一个数。这让我不禁思考，这和 for loop有什么区别，能减少时间复杂度吗？我一开始也不是很清楚，但我可以找文档，找标准。我的第一判断是 includes 完全和 for loop没有区别的，只是es6 标准规范提供的语法糖，而 indexOf 还是有一定效率的。带着疑惑，查看 MDN 和 ecma-262

includes

includes 是 ES6 新增语法，返回 布尔值。最容易拿 indexOf 来比较， indexOf 不能判断 NaN, 而且不够语义，返回的是 匹配值的位置 或 -1。 includes 内部实现是这样的：

  1. Let O be ? ToObject(this value).
  2. Let len be ? ToLength(? Get(O, “length”)).
  3. If len is 0, return false.
  4. Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step produces the value 0.)
  5. If n ≥ 0, then
    1. Let k be n.
  6. Else n < 0,
    1. Let k be len + n.
    2. If k < 0, let k be 0.
  7. Repeat, while k < len
    1. Let elementK be the result of ? Get(O, ! ToString(k)).
    2. If SameValueZero(searchElement, elementK) is true, return true.
    3. Increase k by 1.
  8. Return false.

其中的 SameValueZero 内部实现是这样的：

  1. If Type(x) is different from Type(y), return false.
  2. If Type(x) is Number, then
    1. If x is NaN and y is NaN, return true.
    2. If x is +0 and y is -0, return true.
    3. If x is -0 and y is +0, return true.
    4. If x is the same Number value as y, return true.
  3. Return false.
  4. Return SameValueNonNumber(x, y).

从上面可以看出 includes 内部是使用 while 循环，并不能够降低时间复杂度。它能判断出 NaN 以及 +0等于-0。

所以，返回值的语义化和 NaN的判断就是 includes 的场景。

indexOf

好，includes 用来提升效率的幻想破灭了，那 indexOf 呢，规范是这么写的：

  1. Let O be ? ToObject(this value).
  2. Let len be ? ToLength(? Get(O, “length”)).
  3. If len is 0, return -1.
  4. Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step produces the value 0.)
  5. If n ≥ len, return -1.
  6. If n ≥ 0, then
    1. If n is -0, let k be +0; else let k be n.
  7. Else n < 0,
    1. Let k be len + n.
    2. If k < 0, let k be 0.
  8. Repeat, while k < len
    1. Let kPresent be ? HasProperty(O, ! ToString(k)).
    2. If kPresent is true, then
      1. Let elementK be ? Get(O, ! ToString(k)).
      2. Let same be the result of performing Strict Equality Comparison searchElement === elementK.
      3. If same is true, return k.
    3. Increase k by 1.
  9. Return -1.

Array的 indexOf 也使用了 while 循环，并使用 === 全等比较。（注： 与 String.prototype.indexOf 并不同）

indexOf 使用场景是需要知道 匹配值的位置。

结论

这是一个性能测试比较

我的测试结果

so? 如果单纯只是想比较，简单的才是最快的。 includes与indexOf效率相当，而for Loop最快，因为没有其他的前置判断和浏览器对它的优化。

0%