代码之家 › 专栏 › 技术社区 › Andrew

循环次数相同的O(1)运算算法的性能

time-complexity optimization loops

Andrew · 技术社区 · 7 年前

每当我看到算法优化,我就会看到很多关于减少循环数的讨论。我经常看到多个操作被合并到一个循环中,这个循环最初是单独完成的。

最终,执行相同数量的O(1)过程。只是一个算法将它们分成多个迭代。从可伸缩的角度来看,合并操作真的有性能优势吗?

过于简单的例子。我知道这不是一个很好的例子,因为内部时间复杂度的操作与递增行为相比是低的。 i ,但你明白我的意思。

let tally1 = 0
let tally2 = 0

for (let i = 0; i < 10; i++) {
  tally1 += 1
}

for (let i = 0; i < 10; i++) {
  tally2 += 1
}

// vs

for (let i = 0; i < 10; i++) {
  tally1 += 1
  tally2 += 1
}

2 回复 | 直到 7 年前

Laurenz Albe 7 年前

显然,第二个版本的性能会更好,因为组成循环的所有操作只需执行一次。

因此,虽然在循环内执行的操作不会有好的或坏的结果,但总体执行时间会更短。

这是否相关在很大程度上取决于循环中的操作有多昂贵。如果它们很便宜,那么循环的开销将是显而易见的,并且可能值得优化代码。如果它们很贵的话,可能不值得这么做。

除了性能,代码的清晰性也是一件好事。因此,如果从性能的角度来看这无关紧要,那么您应该选择更适合阅读的代码。

Yves Daoust 7 年前

在非常短的循环中,循环构造本身(增量和终止测试)的开销是“显著的”。编译器可能会执行“循环展开”优化,即复制循环体以避免执行中间测试(在处理终止时要格外小心)。

循环合并可以带来类似的加速。

当循环体更加复杂时,循环开销变得可以忽略不计,并且在合并循环时性能甚至会降低,因为可能会使所需寄存器的数量饱和或降低缓存效率。

对于普通程序来说,这种微观优化往往不值得去做。它们在开发具有一般用途的可重用代码(如BLAS例程)时更为相关。

推荐文章

BlurKid · R中for循环时结果的奇怪差异

8 月前

Costinean Sebastian · 如何优化使用for循环处理大型数组的MATLAB脚本的执行时间?"

8 月前

bigjdawg43 · 迭代多个数据帧中的列并有条件地执行操作

1 年前

Colin · 缩短嵌套文件夹名称

1 年前

xhamsterIT · 循环VBA Microsoft Excel

1 年前

Nico44044 · 使用for循环遍历Django模型字段

1 年前

chanbo chung · 如何在聚合中获得所有可能的组合

1 年前

Himanshu · 无法在逐行二进制搜索中迭代2D数组中的所有行

1 年前

Sonia Acosta · 如何在python for while循环中获取下一个用户输入?[副本]

1 年前

stephr · 循环为多个变量选择最接近另一个日期的日期

1 年前