js数组循环的时间复杂度

      const a = []
      for (i = 0; i < 100000; i++) {
        a.push({ id: i, name: 'xx' + i })
      }

      const b = []
      for (let i = 0; i < 100; i++) {
        b.push({ id: i, name: 'yy' + i })
      }

      // 最慢的循环:n^2,最好把map放到外面用变量接收
      const c = a.filter(n => b.map(m => m.id).includes(n.id))
      // console.log(c)

      // 三种方法:
      // 第一种:2个forEach
      console.time('打印d')
      const d = []
      b.forEach(n => {
        a.forEach(m => {
          if (n.id === m.id) d.push(n)
        })
      })
      console.log(d)
      console.timeEnd('打印d')

      // 把长的数据放在外面更快
      console.time('打印d1')
      const d1 = []
      a.forEach(n => {
        b.forEach(m => {
          if (n.id === m.id) d1.push(m)
        })
      })
      console.log(d1)
      console.timeEnd('打印d1')

      // 第二种:filter(ES5) + includes(ES7)
      console.time('打印e')
      const ids = a.map(m => m.id)
      const e = b.filter(n => ids.includes(n.id))
      console.log(e)
      console.timeEnd('打印e')

      // 第三种:创建obj(兼容性好)
      console.time('打印f')
      let obj = {}
      b.forEach(n => (obj[n.id] = n.name))
      console.log(obj)
      const f = a.filter(n => {
        n.name = obj[n.id]
        return obj[n.id]
      })
      console.log(f)
      console.timeEnd('打印f')

结果:

js数组循环的时间复杂度

 

总结:

  1、不要在filter中写map,这种的时间复杂度是 n^2,最慢

  2、通过两个forEach来遍历时,时间复杂度为 n*2。把长的数据放在外面速度更快

  3、filter + includes的方法除了兼容性问题,运行很快

  4、通过创建一个obj的形式,时间复杂度为n,没有兼容性问题

 

上一篇:三种遍历的方法(map和forEach的区别)


下一篇:sql动态拼接<if>标签嵌套<foreach>判空、if失效等问题