algorithm - 程序中的模数优化

Question

我看到很多人喜欢在代码中使用:

 while(i<1000000){
       ret+=a[i];
       i++;
       if(ret >= MOD) 
          ret -= MOD;
   }

而不是在最后一步制作 ret%MOD。

这两者之间有什么区别以及它们如何相等？

它是如何优化我们的代码的？

Answer 1

基本上，您不尝试就无法分辨。有两种可能的结果(考虑我在下面的注释):

• 编译器以某种方式优化代码，两种解决方案都使用条件跳转或模运算。这不仅取决于编译器有多“聪明”，还必须考虑目标架构的可用指令集(但说实话，没有模运算会很奇怪)。

• 编译器没有优化代码(很可能是针对非优化调试构建)。

基本区别是 - 如前所述 - 使用 if() 的解决方案将使用一个条件跳转，这 - 同样取决于您的架构 - 可能会减慢您的速度，因为编译器如果不先评估跳转条件，就无法预取下一条指令。

---

进一步说明:

使用模运算或您的 if() 语句实际上不等于(取决于实际值)，仅仅是因为 ret % MOD 将导致以下相同的代码:

while (ret >= MOD)
    ret -= MOD;

假设 a[i] 大于 MOD 并且新的总和大于 MOD 的两倍。在那种情况下，您最终会得到一个大于 MOD 的 ret，使用模数时不会发生这种情况。