在VBA中使用循环的两种方式的时间复杂度有什么区别？ [英] What is the difference between the time complexity of these two ways of using loops in VBA?

问题描述

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

说，我们有这两个代码。
第一个：

 对于每个单元格在rng1 
 collectionOfValues.Add（cell.Value）
下一个
 
对于每个单元格在rng2 
 collectionOfAddresses.Add（cell.Address）
下一个
 
对于i = 1 To collectionOfAddresses.Count 
范围（collectionOfAddresses.Item（i））= collectionOfValues.Item（i）
下一个i 
  

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

这是第二个代码，这样做是一样的：

 对于i = 1到rng1.Rows.Count 
对于j = 1到rng1.Columns.Count 
 rng2.Cells（i，j）= rng1.Cells（i，j）
下一步j 
 Next i 
  

所以问题是 - 在两个案件？我的意思是，很明显，第二种情况是O（n ^ 2）（为了使我们更容易地假定范围是平方的）。

第一个怎么样？是为每个人考虑一个嵌套循环？如果是的话，这意味着第一个代码的时间是O（n ^ 2）+ O（n ^ 2）+ O（n ^ 2） = 3 * O（n ^ 2），这与第二个代码时间相同？

一般来说，这两个代码与第一个

非常感谢您提前收集。

解决方案

实际上，你的第一个例子是 O（n ^ 4）！

这可能听起来很奇怪，但这是因为>索引到VBA集合具有线性，而不是常数复杂性。 VBA Collection本质上具有列表的性能特征 - 通过索引获得元素N 需要与N成比例的时间。为了迭代整个事物通过索引花费时间成比例到N ^ 2。 （我切换你的案例来区分N，数据结构中的元素数量，从n，单元格方块的单元格数，所以这里N = n ^ 2。）

这就是为什么VBA有For ...每个符号迭代集合的一个原因。当您使用For ...每个，VBA在幕后使用迭代器，因此遍历整个集合是O（N）不是O（N ^ 2）。

所以，切换回你的n，你的前两个循环正在使用For ...每个超过一个范围与n ^ 2个单元格，所以它们是每个O（n ^ 2）。你的第三个循环是使用For ...下一个包含n ^ 2个元素的集合，所以是O（n ^ 4）。

我其实不知道确定你的最后一个循环，因为我不知道一个范围的细胞属性的工作原理 - 这可能会有一些额外的隐藏的复杂性。但是我认为单元格将具有一个数组的性能特征，所以O（1）通过索引进行随机访问，这将使最后一个循环O（n ^ 2）。

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

必须有一个Shlemiel画家的
在某处的算法。每当
的东西似乎应该有
的线性表现，但似乎
有n平方的表现，寻找
隐藏的Shlemiels。他们通常被你的图书馆隐藏
。

（在构建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就不会循环通过范围来复制单元格内容。）

I got a theoretical question, will appreciate if you advise me here.

Say, we have these two pieces of code. First one:

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

Here we add addresses from one range to a certain collection, and values from another range to a second collection, and then fill cells on these addresses with the values.

Here is the second code, which makes the same:

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

So, the question is - what is the time of execution in both cases? I mean, it's clear that the second case is O(n^2) (to make it easier we assume the range is square).

What about the first one? Is For Each considered a nested loop?

And if so, does it mean that the time of the first code is O(n^2) + O(n^2) + O(n^2) = 3*O(n^2) which makes pretty the same as the second code time?

In general, do these two codes differ apart from the fact that the first one takes additional memory when creating collections?

Thanks a lot in advance.

解决方案

Actually, your first example is O(n^4)!

That might sound surprising, but this is because indexing into a VBA Collection has linear, not constant, complexity. The VBA Collection essentially has the performance characteristics of a list - to get element N by index takes a time proportional to N. To iterate the whole thing by index takes a time proportional to N^2. (I switched cases on you to distinguish N, the number of elements in the data structure, from your n, the number of cells on the side of a square block of cells. So here N = n^2.)

That is one reason why VBA has the For...Each notation for iterating Collections. When you use For...Each, VBA uses an iterator behind the scenes so walking through the entire Collection is O(N) not O(N^2).

So, switching back to your n, your first two loops are using For...Each over a Range with n^2 cells, so they are each O(n^2). Your third loop is using For...Next over a Collection with n^2 elements, so that is O(n^4).

I actually don't know for sure about your last loop because I don't know exactly how the Cells property of a Range works - there could be some extra hidden complexity there. But I think Cells will have the performance characteristics of an array, so O(1) for random access by index, and that would make the last loop O(n^2).

This is a good example of what Joel Spolsky called "Shlemiel the painter's algorithm":

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.

(See this article from way before stackoverflow was founded: http://www.joelonsoftware.com/articles/fog0000000319.html)

More about VBA performance can be found at Doug Jenkins's webstie:

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/

(I will also second what cyberkiwi said about not looping through Ranges just to copy cell contents if this were a "real" program and not just a learning excercise.)

这篇关于在VBA中使用循环的两种方式的时间复杂度有什么区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！