处理时间是指数非线性吗？ （VBA集合） [英] Processing time is exponential not linear? (VBA Collections)

问题描述

在下面的代码示例中，如果我将集合的大小从10000更改为20000，我希望处理时间需要两倍的时间。相反，处理时间大约是进行此更改时的4倍。它看起来字典也有这种指数行为，但是数组不行。

In the following code sample, I would expect the processing time to take twice as long if I change the collection's size from 10000 to 20000. Instead, the processing time is approximately 4 times as long when I make this change. It appears Dictionaries also have this kind of exponential behavior, but Arrays do not.

有没有人知道为什么会这样？

Does anyone know why this is?

Sub testing()
Dim i As Long
Dim coll As New Collection
Dim startTime As Single

    For i = 1 To 10000 'change this value to 20000 to see nonlinear increase in processing time
        coll.Add i
    Next i

    startTime = Timer 'start the clock

    For i = 1 To coll.Count
        If coll(i) = 1 Then 'do nothing
        End If
    Next i

    MsgBox "Your final time is " & Round(Timer - startTime, 3)
End Sub

推荐答案

我几乎感觉到一个骗子回答这个问题，因为我是一个自学习者，就像我喜欢去计算机科学课，真理是我的内存分配和检索的力量的知识差。

I almost feel a fraud answering this question, as I'm a self-learner and much as I'd love to have gone to computer science classes, truth is my knowledge of the mechanics of memory allocation and retrieval is poor.

我经常想知道 Collection 项目的检索速度与键和索引，并希望一个受教育的人也能回答这个问题，我也知道。

I often wondered about the difference in speed of retrieval of Collection items by key and index and was hoping a schooled person would answer this question for my own knowledge too.

但是，OP要求我将我的评论转换为一个答案，所以我很高兴。

However, the OP has asked me to convert my comment to an answer so I'm happy to oblige.

我的经验 对象是使用循环在时间上是线性的，即20,000个记录需要两倍的长度10,000，而迭代与对于循环是指数，即20,000条记录需要4倍的长度10,000。

My experience of the Collection object is that iterating with a ForEach loop is linear in time, ie 20,000 records takes twice as long as 10,000, whereas iterating with a For loop is exponential, ie 20,000 records takes 4 times as long as 10,000.

因此，对于大集合， ..

So, for a large collection, this ...

Dim v as Variant 'assuming contents of collection is a primitive data type.
For Each v In someCollection
    'process v in some way
Next

会比这更快...

Dim i as Long
For i = 1 to someCollection.Count
    'process someCollection(i) in some way
Next

这是一种反直觉，因为我在几个地方读到 For Each 循环约。 。

And that's sort of counter-intuitive, as I've read in several places that the For Each loop is approx. 10% slower than the `For' loop.

我完全没有教育的结论是 Collection 对象循环遍历它的成员从第一个找到一个指定的索引，这将解释如何时间以指数级增加的集合变得越大。这将是有意义的，特别是在与数组比较，因为 Collection 对象的结构不是一个订单，而对于一个数组，每个索引是，实际上，一个内存指针。

My entirely uneducated conclusion was that the Collection object loops through its members from the first to find a specified index, which would explain how time increases exponentially the larger the collection becomes. That would kind of make sense, especially in comparison with an array, since the structure of a Collection object isn't predicated on an order whereas for an array, each index is, in effect, a memory pointer.

但是这是怎么回事？ ...

But how about this ? ...

Dim i as Long
For i = 1 to someCollection.Count
    'process someCollection(Cstr(i)) in some way
Next

换句话说，通过键检索成员似乎是与数组类似的速度。我想人们比我必须开发一些形式的真正快速的键/内存指针映射更聪明，所以不需要迭代的集合。正如@bmende所说，它会解释为什么用一个键添加一个项目需要更长的时间比没有（虽然 Dictionary 添加似乎没有体验到这样的程度）。

Time for retrieval becomes linear again. In other words, retrieval of a member by key appears to be at a similar speed to an array. I guess people much cleverer than I must have developed some form of really fast key/memory-pointer map so iterations of the collection is not required. As @bmende notes, it would explain why adding an item with a key takes longer than without (though Dictionary adds don't seem to experience this to such a degree).

如果人们可以原谅我的假定，揭露我处理 Collection 对象的个人规则， p>

If people can excuse my presumptuousness in revealing my personal rules about handling Collection objects, then here they are:

1. 迭代只能使用对于每个循环。


2. 如果没有键，则将索引转换为字符串并使用该字符串（但要注意成员删除，因为索引字符串现在将被删除）。


3. 避免引用


4. 如果一旦填充，集合将不会改变太多，而不是只添加项目，我创建一个类 Item 和 Index 作为两个属性，并添加一个实例类到集合。这样，我仍然可以使用每个循环并检索索引值，如果我需要它。

1. Iterations are only done with For Each loops.
2. If there is no key, then convert the index to a string and use that (but be wary of member removals as the index string will now be out).
3. Avoid referencing a member by its index if at all possible.
4. If, once populated, the Collection isn't going to change much, then, instead of adding just the item, I create a class with Item and Index as two properties and add an instance of this class to the collection. That way I can still use a For Each loop and retrieve the index value if I need it.

b $ b

像这样：

Like so:

Dim member as cMemberItem
Dim i as Long
For Each member in someCollection
    i = member.Index
Next

1. 如果我知道我需要在集合中管理成员的原始数据类型，那么我再次使用一个类。例如，要使Item（3）的值为值+ 1，我必须将值存储在一个临时变量中，删除该项，并在同一位置添加一个包含修改的临时值的新项。

更容易处理的是：

Dim member as cMemberItem
For Each member in someCollections
    member.Item = member.Item + 1
Next

这篇关于处理时间是指数非线性吗？ （VBA集合）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！