JS 快速生成自然数数组引发的思考

本是古典何须时尚 2022-04-27 17:10 404阅读 0赞

# 起因 #

昨天在一个技术交流群里，有个群友问了个问题，就是如何快速生成自然数数组。群友各抒己见，总共提出了大概以下几种方法：

const n = 10000;
    
    // 方法一
    let i = 0;
    new Array(n).fill(i++);
    
    // 方法二
    Array.from({ length: n }, (v, i) => i);
    
    // 方法三
    [...Array(n).keys();
     
    // lodash
     _.times(n);
    复制代码

# 探寻 #

好奇之下，我对各种方法的运行效率进行了基准测试，测试代码如下：

import Benchmark from 'benchmark';
    import _ from 'lodash';
    
    const suite = new Benchmark.Suite();
    
    suite
      .add('new Array', () => {
        let i = 0;
        new Array(10000).fill(i++);
      })
      .add('array.from', () => {
        Array.from({ length: 10000 }, (_, i) => i);
      })
      .add('keys', () => {
        [...Array(10000).keys()]
      })
      .add('lodash.times', () => {
        _.times(10000);
      })
      // add listeners
      .on('cycle', function (event) {
        console.log(String(event.target));
      })
      .on('complete', function () {
        console.log('Fastest is ' + this.filter('fastest').map('name'));
      })
      // run async
      .run({ async: true });
    复制代码

测试结果如下：

new Array x 56,299 ops/sec ±2.47% (84 runs sampled)
    array.from x 1,302 ops/sec ±0.53% (91 runs sampled)
    keys x 2,891 ops/sec ±0.39% (87 runs sampled)
    lodash.times x 60,763 ops/sec ±1.08% (80 runs sampled)
    Fastest is lodash.times
    复制代码

其中的 `ops/sec` 是每秒运行次数，如 `56,299 ops/sec ±2.47%` 就是每秒运行 56299 次，误差在 `±2.47%` 之内。

# 结论 #

从基准测试的结果来看,`lodash.times` 最快，看源码是通过 `new Array` 和 `while` 循环实现的。方法一的 `fill` 和 `lodash.times` 的速度差不多。

其实 `fill/keys/from` 等等在底层都是用遍历来实现的，所以说运行速度就看遍历了几次， `lodash.times` 和 `fill` 都只遍历了一次。

方法三先运行 `Array(n).keys()` 得到一个 `Itreator`，然后用展开操作符展开成数组，实际上是遍历了两次。

至于 `Array.form`，看 [MDN 上的 Polyfill][MDN _ Polyfill] 实现，也是通过 `new Array` 和 `while` 循环实现的，但是每次循环都要执行一个回调函数，所以会慢一些。实际测试大概在 `7,237 ops/sec`，比 chrome 原生实现的要快一些，不知道 chrome 原生是怎么实现的，为什么这么慢。

[MDN _ Polyfill]: https://link.juejin.im?target=https%3A%2F%2Fdeveloper.mozilla.org%2Fzh-CN%2Fdocs%2FWeb%2FJavaScript%2FReference%2FGlobal_Objects%2FArray%2Ffrom%23Polyfill