excel - 处理时间是指数非线性的？ (VBA 集合)

Question

在下面的代码示例中，如果我将集合的大小从 10000 更改为 20000，我预计处理时间会增加一倍。相反，当我进行此更改时，处理时间大约是原来的 4 倍。似乎字典也有这种指数行为，但数组没有。

谁知道这是为什么？

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

Answer 1

我几乎觉得回答这个问题是在骗人，因为我是一个自学者，而且我很想上计算机科学课，但事实是我对内存分配和检索机制的了解很差。

我经常想知道 Collection 的检索速度有何不同？ key 的项目和 index并希望受过教育的人也能根据我自己的知识回答这个问题。

但是，OP 要求我将我的评论转换为答案，所以我很乐意帮忙。

我对 Collection 的体验对象是用 ForEach 迭代循环在时间上是线性的，即 20,000 条记录花费的时间是 10,000 条记录的两倍，而使用 For 进行迭代循环是指数级的，即 20,000 条记录花费的时间是 10,000 条记录的 4 倍。

所以，对于大型集合，这...

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循环是大约。比“For”循环慢 10%。

我完全没有受过教育的结论是 Collection object 从第一个成员开始循环以找到指定的索引，这可以解释时间如何随着集合的增加呈指数增长。这是有道理的，尤其是与数组相比，因为 Collection 的结构对象不基于顺序，而对于数组，每个索引实际上是一个内存指针。

但是这个怎么样？ ...

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

检索时间再次变为线性。换句话说，通过键检索成员的速度似乎与数组相似。我猜比我聪明得多的人一定已经开发出某种形式的真正快速的键/内存指针映射，因此不需要集合的迭代。正如@bmende 指出的那样，它可以解释为什么添加带有 key 的项目比没有 key 需要更长的时间(尽管 Dictionary 添加似乎并没有达到这种程度)。

如果人们可以原谅我透露我处理个人规则的冒昧Collection对象，那么它们就在这里:

1. 迭代只用 For Each 完成循环。
2. 如果没有键，则将索引转换为字符串并使用它(但要小心成员删除，因为索引字符串现在将被删除)。
3. 尽可能避免通过索引引用成员。
4. 如果填充后，Collection不会有太大变化，那么，我不是只添加项目，而是使用 Item 创建一个类和 Index作为两个属性并将此类的实例添加到集合中。这样我仍然可以使用 For Each循环并在需要时检索索引值。

像这样:

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

1. 如果我知道我需要操纵集合中成员的原始数据类型，那么我再次使用类。例如，要使 Item(3) 的值为 value + 1，我必须将该值存储在一个临时变量中，删除该项目，然后在同一位置添加一个包含修改后的临时值的新项目。如果更改每个成员的值，这可能会变成噩梦。

而更容易处理的是:

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