我可以有一个更快的嵌套循环来降低算法的复杂性吗？

Question

伙计们，我有一个新手问题。

假设我有以下简单的嵌套循环，其中 m 和 n 不一定相同，但确实是 大数字 ：

x = 0;

for (i=0; i<m; i++)
{
   for (j=0; j<n; j++)
   {
      delta = CalculateDelta(i,j);
      x = x + j + i + delta;
   }
}

现在我有了这个：

x = 0;

for (i=0; i<m; i++)
{
   for (j=0; j<n; j++)
   {
      delta = CalculateDelta(i,j);
      x = x + j + i + delta;

      j++;

      delta = CalculateDelta(i,j);
      x = x + j + i + delta;
   }
}

规则：我需要遍历循环的所有元素，因为这个delta计算。

我的问题是：

1) 第二种算法比第一种算法快，还是一样？我有这个疑问，因为对我来说，第一个算法的复杂度为 O(m * n)，第二个算法的复杂度为 O(m * n/2)。还是不必降低复杂性使其更快？

2) 如果没有 Parallel. For 之类的东西，有没有其他方法可以使它更快？

3) 如果我使用 Parallel. For，它真的会更快吗，因为我可能需要对 x 变量进行同步锁定？

谢谢！

Answer 1

在一个 post 中提出三个问题正在挑战 "too broad" 的极限。但就你而言，问题相当简单，所以……

1) Does the second algorithm is faster then the first one, or is it the same? I have this doubt because for me the first algorithm have a complexity of O(m * n) and the second one is O(m * n/2). Or does lower complexity not necessary makes it faster?

复杂度忽略了像 1/2 这样的系数。所以 O(m * n) 和 O(m * n/2) 之间没有区别。后者应该已经缩减为O(m * n)，这显然与前者相同

而第二个并不是真正的 O(m * n/2)，因为您并没有真正删除工作。您只是部分展开了循环。这些无意义的转换是我们首先忽略大 O 符号中系数的原因之一。在不真正改变实际计算工作的情况下 fiddle 使用系数太容易了。

2) Is there any other way to make this faster without something like a Parallel.For?

这绝对是一个太宽泛的问题。 "Any other way"？大概。但是你没有提供足够的上下文。

我在您 post 编辑的代码中看到的唯一明显的潜在改进是您正在重复计算 j + i，而您可以观察到整个计算的那个部分增加了1 每次迭代，因此您可以保留一个单独的递增变量，而不是每次添加 i 和 j。但是 a) 尚不清楚做出这种改变是否会加速任何事情（是否会，将在很大程度上取决于 CPU 自己的优化逻辑中的细节），并且 b）如果这样做可靠，则有可能一个好的优化 JIT 编译器会为您转换代码。

但除此之外，CalculateDelta() 方法在这里完全未知。它可能是编译器为您内联的简单在线程序，也可能是一些主导整个循环的巨大计算。

我们无法告诉您是否有 "any other way" 可以加快循环速度。就此而言，您所做的更改是否使循环更快还不清楚。也许有，也许没有。

3) If I make usage of a Parallel.For, would it really make it faster since I would probably need to do a syncronization lock on the x variable?

这至少取决于 CalculateDelta() 在做什么。如果它足够昂贵，那么 x 上的同步可能无关紧要。更大的问题是 x 的每个计算都取决于前一个。并行计算是不可能的，因为它本质上是一个串行计算。

你可以做的是并行计算所有增量，因为它们不依赖于x（至少，它们不在代码中你 posted)。总和的另一个元素是常量（i + j 已知 m 和 n），所以最后它只是增量和那个常量的总和。同样，这是否值得做在某种程度上取决于 CalculateDelta() 的成本。该方法的成本越低，您就越不可能通过并行执行看到任何改进。

Answer 2

第一个 for() 会将您转到第二个 for() 第二个 for() 将循环到 jn) 和第二个 mn/2

Answer 3

一个有利的转换是使用双算术级数公式提取i和j项的贡献的算术和。这节省了相当多的工作，将那部分计算的复杂度从 O(m*n) 降低到 O(1)。

x = 0;

for (i=0; i<m; i++)
{
   for (j=0; j<n; j++)
   {
      delta = CalculateDelta(i,j);
      x = x + j + i + delta;
   }
}

可以变成

x = n * m * (n + m - 2) / 2;

for (i=0; i<m; i++)
{
   for (j=0; j<n; j++)
   {
      x += CalculateDelta(i,j);
   }
}

进一步优化完全取决于CalculateDelta做了什么，你没有透露。如果它有副作用，那就是个问题。但如果它是一个纯函数（其结果仅取决于输入 i 和 j），那么它也很有可能可以直接计算。

Answer 4

绝对不是，因为时间复杂度大概是由CalculateDelta()被调用的次数决定的，你是否内联调用并不重要，在单个循环或任意数量的嵌套循环，调用 m*n 次。

现在你有一个错误（这就是我决定在@Peter-Duniho 完成后添加答案的原因这么全面）

如果 n 是奇数，则说明您执行的迭代次数超出预期 - 几乎肯定会得到错误的答案或使您的程序崩溃...

我可以有一个更快的嵌套循环来降低算法的复杂性吗？

Can I have a faster nested loop just lowering the algorithm complexity?

.net

c#

time-complexity

code-complexity

computation-theory