第 120 题：为什么for循环嵌套顺序会影响性能？

[jeromehan]

var t1 = new Date().getTime()
for (let i = 0; i < 100; i++) {
  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 10000; k++) {
    }
  }
}
var t2 = new Date().getTime()
console.log('first time', t2 - t1)

for (let i = 0; i < 10000; i++) {
  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 100; k++) {

    }
  }
}
var t3 = new Date().getTime()
console.log('two time', t3 - t2)  

[iNuanfeng]

为什么

[jeoy]

循环次数少的放在外层，减少内层变量的操作(初始化，比较，自增等)次数吧。

[ToSaySomething]

应该是第一个时间少一点，比如，按照每次循环判断来说 （初始化 自增次数类似）

1、i会循环100次，判断i<100 100次 j会循环100 * 1000次，判断j<100 100 * 1000次 k会循环100 * 1000 * 10000次，判断k<100 100 * 1000 * 10000次

2、i会循环10000次，判断i<100 10000次 j会循环10000 * 1000次，判断j<100 10000 * 1000次 k会循环100 * 1000 * 10000次， 判断k<100 100 * 1000 * 10000次

虽然判断k<100的次数都是一样的 但是前面两种判断就不一样了，由此可以看见时间长短。

[EnergySUD]

两个循环的次数的是一样的，但是 j 与 k 的初始化次数是不一样的

• 第一个循环的 j 的初始化次数是 100 次，k 的初始化次数是 10w 次
• 第二个循环的 j 的初始化次数是 1w 次， k 的初始化次数是 1000w 次

所以相同循环次数，外层越大，越影响性能

[GpingFeng]

我尝试了一下只有一层不嵌套的情况，得到的结果似乎不似预期，我认为性能应该是跟执行的次数有关，但是执行相同的次数，没有嵌套的反而是相对时间比较多的

[littleLane]

这里说说我个人的理解：对于这个例子，接下来我们利用三个例子来推算

注意：以下输出结果在不同机型和配置下可能存在差异，但是大小关系是不会变的

首先我们单独来比较最内层的循环，也就是循环 10000 次和 100 次的时长

  var t1 = new Date().getTime()
  for (let k = 0; k < 10000; k++) {
  }

  var t2 = new Date().getTime()
  console.log('first time', t2 - t1)

  for (let k = 0; k < 100; k++) {
  }
  var t3 = new Date().getTime()
  console.log('two time', t3 - t2)

输出： first time 0 two time 0

单独循环 10000 和 100 的时间是相差无几的，基本可以看成一个等量关系。那么差异肯定是在外层嵌套的两个循环了。

我们再来看看另外一个例子：两层嵌套遍历，外层循环次数是 1000，里层循环次数一个是 10000，另一个是 100

  var t1 = new Date().getTime()

  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 10000; k++) {
    }
  }

  var t2 = new Date().getTime()
  console.log('first time', t2 - t1)

  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 100; k++) {
    }
  }

  var t3 = new Date().getTime()
  console.log('two time', t3 - t2)

输出： first time 5 two time 1

差异就出来了，明显看到循环差异在 2-4 ms，可以看到当外层循环的次数一样是，循环的时长取决于里层循环，里层循环次数越多，执行时间越长。

我们再来看看这样一个例子：两层嵌套循环，里层的循环次数都是 1000，外层循环次数一个是 10000，一个是 1000

  var t1 = new Date().getTime()

  for (let j = 0; j < 10000; j++) {
    for (let k = 0; k < 1000; k++) {
    }
  }

  var t2 = new Date().getTime()
  console.log('first time', t2 - t1)

  for (let j = 0; j < 100; j++) {
    for (let k = 0; k < 1000; k++) {
    }
  }

  var t3 = new Date().getTime()
  console.log('two time', t3 - t2)

输出： first time 5 two time 1

差异就出来了，明显看到循环差异在 2-4 ms，可以看到当内层循环的次数一样是，循环的时长取决于外层循环，外层循环次数越多，执行时间越长。

====== 以上结论都可以根据算法的时间复杂度计算规则得到 =====================================

[huhao666]

有没有大佬讲讲for循环嵌套循环相同循环次数，外层越大，越影响性能的原理是什么，比如V8引擎编译机智？或者什么因素的影响，挺好奇的

[michaelChe956]

坐等大佬

[gto999]

第二循环 变量 实例化(次数) 初始化(次数) 　比较(次数) 　　自增(次数) i 　1 　　　　　　　1 　　　　1000 　　　　1000 j 1000 　　　　1000 　　　1000 * 100 　　1000 * 100 k 1000 * 100 　1000 * 100 1000 * 100 * 10　1000 * 100 * 10 第一循环

变量 | 实例化(次数) | 初始化(次数) | 比较(次数) | 自增(次数) 　i 　| 　　　1　　 | 　　　1　　 | 　　10　　|　 10 　j 　| 　　　10 　　|　　 10　　 | 10 * 100　 | 10 * 100 　k　 | 10 * 100　　 | 10 * 100　　 | 10 * 100 * 1000 | 10 * 100 * 1000

主要差别是外层两个变量初始化，比较，自增次数全部减少

[EnergySUD]

我尝试了一下只有一层不嵌套的情况，得到的结果似乎不似预期，我认为性能应该是跟执行的次数有关，但是执行相同的次数，没有嵌套的反而是相对时间比较多的

你可以减少次数测试一下，当单循环次数过大，在相同循环次数的情况下，单循环性能比多循环次数差。可能是一个内存空间存放不了过大的数值，再调用一个内存空间。

[wilesen]

有趣的是在火狐下两次时间差不太多

[HeyShinner]

这里说说我个人的理解：对于这个例子，接下来我们利用三个例子来推算

注意：以下输出结果在不同机型和配置下可能存在差异，但是大小关系是不会变的

首先我们单独来比较最内层的循环，也就是循环 10000 次和 100 次的时长

  var t1 = new Date().getTime()
  for (let k = 0; k < 10000; k++) {
  }

  var t2 = new Date().getTime()
  console.log('first time', t2 - t1)

  for (let k = 0; k < 100; k++) {
  }
  var t3 = new Date().getTime()
  console.log('two time', t3 - t2)

输出： first time 0 two time 0

单独循环 10000 和 100 的时间是相差无几的，基本可以看成一个等量关系。那么差异肯定是在外层嵌套的两个循环了。

我们再来看看另外一个例子：两层嵌套遍历，外层循环次数是 1000，里层循环次数一个是 10000，另一个是 100

  var t1 = new Date().getTime()

  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 10000; k++) {
    }
  }

  var t2 = new Date().getTime()
  console.log('first time', t2 - t1)

  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 100; k++) {
    }
  }

  var t3 = new Date().getTime()
  console.log('two time', t3 - t2)

输出： first time 5 two time 1

差异就出来了，明显看到循环差异在 2-4 ms，可以看到当外层循环的次数一样是，循环的时长取决于里层循环，里层循环次数越多，执行时间越长。

我们再来看看这样一个例子：两层嵌套循环，里层的循环次数都是 1000，外层循环次数一个是 10000，一个是 1000

  var t1 = new Date().getTime()

  for (let j = 0; j < 10000; j++) {
    for (let k = 0; k < 1000; k++) {
    }
  }

  var t2 = new Date().getTime()
  console.log('first time', t2 - t1)

  for (let j = 0; j < 100; j++) {
    for (let k = 0; k < 1000; k++) {
    }
  }

  var t3 = new Date().getTime()
  console.log('two time', t3 - t2)

输出： first time 5 two time 1

差异就出来了，明显看到循环差异在 2-4 ms，可以看到当内层循环的次数一样是，循环的时长取决于外层循环，外层循环次数越多，执行时间越长。

====== 以上结论都可以根据算法的时间复杂度计算规则得到 =====================================

但是我觉得按照这个说法好像不能很好地解释题目三层嵌套的情况

[triplewoodsaid]

从数学的角度分析，已知for循环执行顺序，1:执行变量（仅执行一次）2:执行条件 3:执行代码块区域 4:最后执行++，当执行到第三步时，发现有一个for循环，程序会先执行完内部所有循环 ，之后返回到外部循环。设单次循环执行步骤2和步骤4的时间为T0,内层循环执行代码块区域的时间为T1,内层循环执行的次数为M ，中间层循环执行的次数为N，外层循环执行的次数为X，那么内层循环执行的总次数为MNX,中间层为MX,外层为X，所以循环的总次数为MNX+NX+X,总时间T是执行循环步骤的总时间加上执行代码区域的总时间，即T=(MNX+NX+X)T0+MNXT1，这里代码不变时，T0和T1不变， 总次数MNX不变，（NX+X）越小，所耗费的时间也会越少。

[GONDON]

两个循环的次数的是一样的，但是 j 与 k 的初始化次数是不一样的

• 第一个循环的 j 的初始化次数是 100 次，k 的初始化次数是 10w 次
• 第二个循环的 j 的初始化次数是 1w 次， k 的初始化次数是 1000w 次

所以相同循环次数，外层越大，越影响性能

var a = 0;
var b = 0;
var t1 = new Date().getTime()
for (let i = 0; i < 10; i++) {
a++
  for (let j = 0; j < 20; j++) {
a++
    for (let k = 0; k < 30; k++) {
a++
    }
  }
}
var t2 = new Date().getTime()
console.log('first time', t2 - t1)

for (let i = 0; i < 30; i++) {
b++
  for (let j = 0; j < 20; j++) {
b++
    for (let k = 0; k < 10; k++) {
b++
    }
  }
}
var t3 = new Date().getTime()
console.log('two time', t3 - t2)  

console.log(a) //6210
console.log(b) //6630

你说的两个循环的次数的是一样的，可是我打印出来的a,b的数值是不一样的，这是为什么呢？

[EnergySUD]

两个循环的次数的是一样的，但是 j 与 k 的初始化次数是不一样的

• 第一个循环的 j 的初始化次数是 100 次，k 的初始化次数是 10w 次
• 第二个循环的 j 的初始化次数是 1w 次， k 的初始化次数是 1000w 次

所以相同循环次数，外层越大，越影响性能

var a = 0;
var b = 0;
var t1 = new Date().getTime()
for (let i = 0; i < 10; i++) {
a++
  for (let j = 0; j < 20; j++) {
a++
    for (let k = 0; k < 30; k++) {
a++
    }
  }
}
var t2 = new Date().getTime()
console.log('first time', t2 - t1)

for (let i = 0; i < 30; i++) {
b++
  for (let j = 0; j < 20; j++) {
b++
    for (let k = 0; k < 10; k++) {
b++
    }
  }
}
var t3 = new Date().getTime()
console.log('two time', t3 - t2)  

console.log(a) //6210
console.log(b) //6630

你说的两个循环的次数的是一样的，可是我打印出来的a,b的数值是不一样的，这是为什么呢？

因为你这累加不对：

• 第一个循环 10 + 200 + 6000
• 第二个循环 30 + 600 + 6000

前两个累加去掉才一样，是 6000

[630268501]

(一)var a = 1000100100 = 100 + 1001000 + 100100010000; (二)var b = 1010010000 = 10000+100001000+100001000100; a<b 但大头100001000100不变

[LqqJohnny]

两个循环的次数的是一样的，但是 j 与 k 的初始化次数是不一样的

• 第一个循环的 j 的初始化次数是 100 次，k 的初始化次数是 10w 次
• 第二个循环的 j 的初始化次数是 1w 次， k 的初始化次数是 1000w 次

所以相同循环次数，外层越大，越影响性能

应该不是吧， let是每次循环都会声明一个新的 i 、j 、 K ,所以

1.   i : 100       j:  100*1000       k : 100 * 1000 * 10000
2.   i: 10000    j:10000 * 1000   k: 10000 * 1000 *100

[LqqJohnny]

有趣的是在火狐下两次时间差不太多

有趣的还有 ， 为什么你的5000+ms 我这只有 几百呀 ， 哈哈

[EnergySUD]

两个循环的次数的是一样的，但是 j 与 k 的初始化次数是不一样的

• 第一个循环的 j 的初始化次数是 100 次，k 的初始化次数是 10w 次
• 第二个循环的 j 的初始化次数是 1w 次， k 的初始化次数是 1000w 次

所以相同循环次数，外层越大，越影响性能

应该不是吧， let是每次循环都会声明一个新的 i 、j 、 K ,所以

1.   i : 100       j:  100*1000       k : 100 * 1000 * 10000
2.   i: 10000    j:10000 * 1000   k: 10000 * 1000 *100

每一次for循环只会初始化一次而已。后面的循环是不会初始化。

[jeromehan]

可以参考这本书

[EnergySUD]

可以参考这本书

按照你的示例，结果却是相反的。

[LqqJohnny]

两个循环的次数的是一样的，但是 j 与 k 的初始化次数是不一样的

• 第一个循环的 j 的初始化次数是 100 次，k 的初始化次数是 10w 次
• 第二个循环的 j 的初始化次数是 1w 次， k 的初始化次数是 1000w 次

所以相同循环次数，外层越大，越影响性能

应该不是吧， let是每次循环都会声明一个新的 i 、j 、 K ,所以

1.   i : 100       j:  100*1000       k : 100 * 1000 * 10000
2.   i: 10000    j:10000 * 1000   k: 10000 * 1000 *100

每一次for循环只会初始化一次而已。后面的循环是不会初始化。

我在网上看到的文章都是这样说的，let 每一轮都是一个新声明的变量的，你看看这里 还有这里

[jeromehan]

可以参考这本书

按照你的示例，结果却是相反的。

预测，不能保证百分之百，就像天气预报似的,刷新一次，会有不同的结果。

[EnergySUD]

两个循环的次数的是一样的，但是 j 与 k 的初始化次数是不一样的

• 第一个循环的 j 的初始化次数是 100 次，k 的初始化次数是 10w 次
• 第二个循环的 j 的初始化次数是 1w 次， k 的初始化次数是 1000w 次

所以相同循环次数，外层越大，越影响性能

应该不是吧， let是每次循环都会声明一个新的 i 、j 、 K ,所以

1.   i : 100       j:  100*1000       k : 100 * 1000 * 10000
2.   i: 10000    j:10000 * 1000   k: 10000 * 1000 *100

每一次for循环只会初始化一次而已。后面的循环是不会初始化。

我在网上看到的文章都是这样说的，let 每一轮都是一个新声明的变量的，你看看这里 还有这里

噢噢，let 每次循环都会初始化，var 是每个for循环只初始化一次

[JingchaoZhao]

我测试了一下 使用var和let的区别，为什么var比let性能差那么多呀？有大佬知道吗？

[abshawn]

内循环多的话，在跳出内部循环的之前，会动态记录和调整转移指，这部分工作需要消耗一定的时间，第二个 内循环跳出的次数多，导致耗时较多。

[lingnan-bulu]

初始化值是正解啊

[Bjkb]

这... 难道是我的chrome比较新？为什么得到的答案完全不一样

[woody8280]

for循环中使用let，js引擎会为每一次循环初始化一个独立作用域和变量。 所以，第一种情况： i 初始化次数：100，j 初始化次数：100 * 1000，k 初始化次数：100 * 1000 * 10000 第二种情况： i 初始化次数：10000，j 初始化次数：10000 * 1000，k 初始化次数：10000 * 1000 * 100 通过比较可得 第二种情况，需要初始化的次数较多，所以耗时较长。

[lpf123lpf]

我测试了很多次，发现每次的结果都不尽相同。但是当循环次数到达亿级的时候试了很多次输出的结果没有嵌套的比嵌套的使用时间更长。有大佬知道为什么吗？

[MissNanLan]

学习了，for的嵌套顺序不同，原来是因为每个值初始化的次数不一样，学习了

[yft]

同问为什么 var 和 let 时间差这么多，一直以为 var 用在循环里面会比较好，哪位大佬来解惑🐰🐰🐰

var t1 = new Date().getTime()
for (var i = 0; i < 100; i++) {
  for (var j = 0; j < 1000; j++) {
    for (var k = 0; k < 10000; k++) {
    }
  }
}
var t2 = new Date().getTime()
console.log('first time', t2 - t1)
// first time 1884

var t1 = new Date().getTime()
for (let i = 0; i < 100; i++) {
  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 10000; k++) {
    }
  }
}
var t2 = new Date().getTime()
console.log('first time', t2 - t1)
// first time 470

---

var t2 = new Date().getTime()
for (var i = 0; i < 10000; i++) {
  for (var j = 0; j < 1000; j++) {
    for (var k = 0; k < 100; k++) {

    }
  }
}
var t3 = new Date().getTime()
console.log('two time', t3 - t2)  
// two time 1939

var t2 = new Date().getTime()
for (let i = 0; i < 10000; i++) {
  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 100; k++) {

    }
  }
}
var t3 = new Date().getTime()
console.log('two time', t3 - t2)
// two time 358

[hbbaly]

限定条件， 变量初始化，赋值都为1次

console.time('first1')
let i = 0, j = 0, k = 0
for (; i< 100; i++) {
  for (; j< 1000; j++) {
    for (; k< 10000; k++) {
    }
  }
}
console.time('first')
let i = 0, j = 0, k = 0
for (; i< 100; i++) {
  for (; j< 1000; j++) {
    for (; k< 10000; k++) {
    }
  }
}
console.timeEnd('first')

i 自增： 100， 比较 100， 赋值 1， 初始化 1 j自增： 100*1000， 比较 100*1000， 赋值 1， 初始化 1 k 自增： 100*1000*10000， 比较: 100*1000*10000， 赋值 1， 初始化 1

console.time('second')
let a = 0, b = 0, c = 0
for (; a< 10000; a++) {
  for (; b< 1000; b++) {
    for (; c< 100; c++) {
    }
  }
}
console.timeEnd('second')

a自增： 10000， 比较 10000， 赋值 1， 初始化 1 b自增： 1000*10000， 比较: 1000*10000， 赋值 1， 初始化 1 c自增： 100*1000*10000， 比较 :100*1000*10000， 赋值 1， 初始化 1

上面可以看出， 第一种 i，j 自增和初始化明显小雨第二种， 随着循环次数增加，相差也就更多

[libin1991]

复杂度成指数增长，太可怕了

[bra1nworld]

查找栈中数据的位置所需要时间不同，最外层数值越大，所花的时间越多

[yygmind]

var t1 = new Date().getTime()
for (let i = 0; i < 100; i++) {
  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 10000; k++) {
    }
  }
}
var t2 = new Date().getTime()
console.log('first time', t2 - t1)

for (let i = 0; i < 10000; i++) {
  for (let j = 0; j < 1000; j++) {
    for (let k = 0; k < 100; k++) {

    }
  }
}
var t3 = new Date().getTime()
console.log('two time', t3 - t2)

[bbrucechen]

我的想法是： 每一层循环的时间差不多，但是第一种只需要100次的进入下一层，而第二种需要10000次的进入下一层 ，在进入每一层的时间不等的情况下，整体循环就是第一种快于第二种

[whosesmile]

猜的: 脚本执行对每个for循环都要重新新建一个词法环境(块级作用域): 第一个例子中最频繁的操作是在栈顶创建然后销毁，也就类似于原地前进一步后退一步； 第二个例子中最频繁的操作是从栈顶倒数三次，相当于前进三步再后退三步；

尽管总步数是一致的，词法环境创建的次数也一致，但是每一个词法环境是要维系外层调用关系的(闭包)，这导致第二个例子中关系链路更长，分配内存/内部引用重建销毁的成本更高。

可以想象一下，如果让你走同样的步数，要求每走一步都要记住脚印的位置，第一个方案相当于走一步报告一次，而第二个方案相当于走三步报告一次。

[James-Lam]

综上，循环次数少的循环置于外层可以达到优化性能的效果

[gitwillsky]

CPU 干同样一件事情，流水线越长越难优化

[prophetw]

从汇编执行的指令周期角度考虑

假设一次 for 循环指令数 1.自增 2.比较 3.跳转 实际对应不同的cpu周期，简化下，一次for循环就算3个指令周期吧 越往外层执行的指令就越多

那 i=1 j=10 k=100

• 最里层需要执行的指令周期 1x10x100x3
• 中间层 1x10x3
• 最外层 1x3

粗略合计 3033次指令执行

那 i=100 j=10 k=1

• 最里层需要执行的指令周期 i j k 100x10x1x3
• 中间层 i j 100x10x3
• 最外层 i 100x3

粗略合计 6300次指令执行 显然外层越大，执行的指令越多，所以需要的时间就越长

c语言

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int test1(){
   clock_t begin,end;
   begin = clock();
   for(int i=0;i<100;i++){
      for(int j=0;j<1000;j++){
         for(int k=0;k<10000;k++){
         }
      }
   }
    // end time
    end = clock();
    double cost = (double)(end - begin)/CLOCKS_PER_SEC;
    printf("the running time is %lf secs\n", cost);
}
int main (){
   test1();
   return 1;
}

上面的 test1 c 对应的汇编

    117e:	c7 45 dc 00 00 00 00 	movl   $0x0,-0x24(%rbp) i=0
    1185:	eb 2d                	jmp    11b4 <test1+0x4b>
    1187:	c7 45 e0 00 00 00 00 	movl   $0x0,-0x20(%rbp) j=0
    118e:	eb 17                	jmp    11a7 <test1+0x3e>
    1190:	c7 45 e4 00 00 00 00 	movl   $0x0,-0x1c(%rbp) k=0
    1197:	eb 04                	jmp    119d <test1+0x34>
    1199:	83 45 e4 01          	addl   $0x1,-0x1c(%rbp) k++
    119d:	83 7d e4 63          	cmpl   $0x63,-0x1c(%rbp) k-99
    11a1:	7e f6                	jle    1199 <test1+0x30> k-99<=0 跳 1199 
    11a3:	83 45 e0 01          	addl   $0x1,-0x20(%rbp)  j++
    11a7:	81 7d e0 e7 03 00 00 	cmpl   $0x3e7,-0x20(%rbp) j-999
    11ae:	7e e0                	jle    1190 <test1+0x27> j-999<=0 跳 1190
    11b0:	83 45 dc 01          	addl   $0x1,-0x24(%rbp)  i++
    11b4:	81 7d dc 0f 27 00 00 	cmpl   $0x270f,-0x24(%rbp) i-9999
    11bb:	7e ca                	jle    1187 <test1+0x1e> i-9999<=0 条 1187

c语言中，也确实

gcc -g 未经优化的调试代码 所以速度如下 the running time is 1.674982 secs i=10000 j=1000 k=100 the running time is 1.427300 secs i=100 j=1000 k=10000 the running time is 1.429261 secs 一层 i=1000000000

[huhao666]

您好，我是胡豪，您的邮件我已收到，我会尽快给您回复的~

[ToSaySomething]

你好，邮件已收到，我现在未上线，一会儿回复你。

[Bosaidonio]

` // 答案： 应该是循环次数不同。

// A例子
for (let i = 0; i < 1; i++) {
  for (let j = 0; i < 2; i++) {
  }
}
// 循环次数为： 3次

// B例子
for (let i = 0; i < 2; i++) {
  for (let j = 0; i < 3; i++) {
  }
}
// 循环次数为: 8次

// A例子的循环次数并不是： 1 * 2
// B例子的循环次数也不是： 2 * 3
// 可以发现一个规律：
//  1 + (1 * 2) = 3
//  2 + (2 * 3) = 8
// 由此可得：双层循环嵌套的次数 = (第一层循环次数 * 第二层循环次数) + 第一层循环次数 

// 三层循环同理
// C例子
for (let i = 0; i < 1; i++) {
  // 可以将内层的两个循环看做是外层循环的内循环
  for (let j = 0; j < 2; j++) {
    for (let k = 0; k < 3; k++) {
    }
  }
}
// D例子
for (let i = 0; i < 3; i++) {
  for (let j = 0; j < 2; j++) {
    for (let k = 0; k < 1; k++) {
    }
  }
}

// 公式： 总次数 = ( 第一层循环次数 * ((第二层循环次数 * 第三层循环次数) + 第二层循环次数) ) + 第一层循环次数
// 由此可得：
// C例子次数为： 1 * ((2 * 3) + 2) + 1  = 9
// D例子次数为： 3 * ((2 * 1) + 2) + 3  = 15
// 个人理解，不对还请纠正一下下。

`

[Lingdeqing]

没有这么复杂吧，就最内层次数是一样的