3

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
5
  • 2
    I've noticed this too, but if you run a For Each loop the time is linear. Try Dim v as Variant|For Each v In coll|Next and you'll see what I mean. My uneducated conclusion was that the processor loops through each item to find the index rather than array whose index is, in effect, a memory pointer.
    – Ambie
    Commented Oct 14, 2015 at 7:59
  • Wow, please post as answer so I can check it. This speeds up my code infinitely.
    – bmende
    Commented Oct 14, 2015 at 14:53
  • I found the same behavior as well when referencing an object by key vs by index. The time taken to reference by key seems linear, while referencing by index is exponential. The catch seems to be that adding objects with keys in a collection seems to take significantly longer than leaving the key parameter out, but this process of adding objects with keys to a coll is almost completely linear. So with big collections, I suppose referencing by key could be infinitely faster than referencing by index
    – bmende
    Commented Oct 14, 2015 at 15:49
  • Or you could just use arrays...
    – bmende
    Commented Oct 14, 2015 at 15:56
  • 1
    I've just converted my comment to an answer for you.
    – Ambie
    Commented Oct 15, 2015 at 23:47

1 Answer 1

4

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.

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.

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

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

will be considerably quicker than this ...

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

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.

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

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).

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

  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.

Like so:

Dim member as cMemberItem
Dim i as Long
For Each member in someCollection
    i = member.Index
Next
  1. If I know I'll need to manuipulate primitive data types of members within the collection, then I, again, use a class. For example, to make the value of Item(3) be value + 1, I'd have to store the value in a temp variable, remove the item, and add a new item containing the modified temp value in the same place. This can become nightmarish if changing every member's value.

Whereas an easier handling of that would be:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.