vba - 在VBA中这两种使用循环的方式的时间复杂度有什么区别？

Question

我有一个理论问题，如果您在这里给我建议，我将不胜感激。

假设我们有这两段代码。 第一个:

For Each cell In rng1
    collectionOfValues.Add (cell.Value)
Next

For Each cell In rng2
   collectionOfAddresses.Add (cell.Address)
Next

For i = 1 To collectionOfAddresses.Count
   Range(collectionOfAddresses.Item(i)) = collectionOfValues.Item(i)
Next i

在这里，我们将一个范围中的地址添加到某个集合，并将另一个范围中的值添加到第二个集合中，然后用这些值填充这些地址上的单元格。

这是第二个代码，其效果相同:

For i = 1 To rng1.Rows.Count
  For j = 1 To rng1.Columns.Count
       rng2.Cells(i, j) = rng1.Cells(i, j)
  Next j
Next i

那么，问题是 - 这两种情况的执行时间是多少？我的意思是，很明显第二种情况是 O(n^2) (为了更容易我们假设范围是平方的)。

第一个怎么样？ For Each 是否被视为嵌套循环？

如果是这样，是否意味着第一个代码的时间是 O(n^2) + O(n^2) + O(n^2) = 3*O(n^2) 这使得与第二次编码时间相同吗？

一般来说，除了第一个代码在创建集合时需要额外的内存之外，这两个代码是否有所不同？

提前非常感谢。

Answer 1

实际上，你的第一个例子是O(n^4)!

这可能听起来令人惊讶，但这是因为索引到 VBA 集合具有线性复杂性，而不是恒定的复杂性。 VBA Collection 本质上具有列表的性能特征 - 通过索引获取元素 N 所需的时间与 N 成正比。通过索引迭代整个元素所需的时间与 N 成正比到 N^2。 (我对你进行了切换，以区分 N(数据结构中的元素数量)和 n(方形单元格一侧的单元数)。所以这里 N = n^2。)

这就是 VBA 使用 For...Each 表示法来迭代集合的原因之一。当您使用 For...Each 时，VBA 在幕后使用迭代器，因此遍历整个 Collection 的时间复杂度为 O(N) 而不是 O(N^2)。

因此，切换回 n，前两个循环在包含 n^2 个单元格的范围内使用 For...Each，因此它们每个都是 O(n^2)。第三个循环是在包含 n^2 个元素的 Collection 上使用 For...Next，因此时间复杂度为 O(n^4)。

我实际上不确定你的最后一个循环，因为我不知道 Range 的 Cells 属性到底是如何工作的 - 那里可能存在一些额外的隐藏复杂性。但我认为 Cells 将具有数组的性能特征，因此通过索引进行随机访问的时间复杂度为 O(1)，这将使最后一个循环的时间复杂度为 O(n^2)。

这是 Joel Spolsky 所说的“画家 Shlemiel 算法”的一个很好的例子:

There must be a Shlemiel the Painter's Algorithm in there somewhere. Whenever something seems like it should have linear performance but it seems to have n-squared performance, look for hidden Shlemiels. They are often hidden by your libraries.

(参见 stackoverflow 成立之前的这篇文章: http://www.joelonsoftware.com/articles/fog0000000319.html )

有关 VBA 性能的更多信息，请访问 Doug Jenkins 的网站:

http://newtonexcelbach.wordpress.com/2010/03/07/the-speed-of-loops/

http://newtonexcelbach.wordpress.com/2010/01/15/good-practice-best-practice-or-just-practice/

(如果这是一个“真正的”程序而不仅仅是一个学习练习，我也会赞同cyberkiwi所说的不要循环遍历范围只是为了复制单元格内容。)