most appropriate data structure

[spandex44]

Hi all,
I am currently writing a completely object oriented graphical application. I have a certain type of object that at some points in the program will not exist at all, but at other points there ay be numerous instances of this object.

I want some sort of data structure to hold all of the objects of this type, so that I can easily perform actions on all of them. I'm thinking something along the lines of a stack or queue (from Java), as I will be adding and taking away from this list of objects frequently.

As my VB is a bit rusty (and never was too great anyway), I wanted to do this with a dynamic array, but this certainly doesnt seem like the best option due to arrays' limitations. Are there any other structures I can use, or a way I can manipulate dynamic arrays to model the behaviour I need?

Thanks a lot!

[David.Poundall]

What do you consider a limitation of the Array aproach?

[brucevde]

Look into the Collection object.

[spandex44]

Ill look into Collections, thanks.

As to the limitations of the array approach:
As far as I know, though I can declare a dynamic array without any initial items, and then redimming it to add more data to it. However, if I want to get get rid of all data, as far as I know I have to keep one item, thereby taking up unwanted space in memory. Also, from my experience, it is hard to efficiently add and remove items from the array (not just fom the end, but from the middle as well) without wasting system resources.

Please correct me if Im wrong, however.

[dglienna]

you can redim array(0)

[spandex44]

you can redim array(0)

Which will leave it with one element, will it not?

[Disiance]

yes, but just replace the '0' with another number.

[dglienna]

I wouldn't worry about single value array memory consumption, but if its that important, than you could look into a collection. I don't know if you can have zero collection objects, as the definition takes up memory.

[brucevde]

The Erase statement will remove a dynamic array from memory, no need to use Redim(0).

How important is speed? A collection adds overhead, both in memory consumption and speed (although neglible). Do you need "Game" type speed, where everything must complete in say 30ms or "User" speed where processing in 1000ms is hardly noticable.

[dglienna]

if you erase it, do you need to use DIM again, or can you use REDIM for it?

[David.Poundall]

I agree on the overjhead bit. I have found in the past that collections were slower by a factor of 4 or 5 to use than arrays. I use them as a last resort or if I need to index an array.

Another factor against using collections is that you cannot hover over them at debug time to get the value associated with the collection. With arrays you can. Thats probably a mute point as spandex is dealing with objects.

My final gripe on collections (now where did I leave that soap box ) is that they are picky about having duplicate key names and a right pain to delete from.

Hmmm - having said all that, given a FIFO or a stack requirement, so long as you don't use keys and you are only using the collection as a container to hold items that you are going to cycle through and process, collections should be the best aproach.

[spandex44]

The Erase statement will remove a dynamic array from memory, no need to use Redim(0).

How important is speed? A collection adds overhead, both in memory consumption and speed (although neglible). Do you need "Game" type speed, where everything must complete in say 30ms or "User" speed where processing in 1000ms is hardly noticable.

I need "game " type speed, that's the onl reason that this is even a consideration. I can tell that this is my first time attempting to do "efficient" programming, as I normally dont pay attention to speed issues.

I'm having troubles understanding, however, how to use an array to act the same as a collection. For instance, how do we go about deleting just one element somewhere in the array and "dynamically" adjusting the size of the array to account for this? Same goes for changing the order of elements...

[David.Poundall]

If I were doing this I would have a 2D array, set to say 100 items.

(0,x) would hold the object, (1,x) would hold status info for the object. You could record status as destroyed, active, needs to be checked etc.

I would then cycle around all of the status array entries and operate on the objects as needed. If you have more than 100 objects on the go then you could extend the array with redim preserve array(0 to 1, 0 to ubound(array)+50) say or you could re-use "Destroyed" locations in the original array.

There is no destroying or rebuilding of arrays, the pointer contol is clean and fast.

[spandex44]

If I were doing this I would have a 2D array, set to say 100 items.

(0,x) would hold the object, (1,x) would hold status info for the object. You could record status as destroyed, active, needs to be checked etc.

I would then cycle around all of the status array entries and operate on the objects as needed. If you have more than 100 objects on the go then you could extend the array with redim preserve array(0 to 1, 0 to ubound(array)+50) say or you could re-use "Destroyed" locations in the original array.

There is no destroying or rebuilding of arrays, the pointer contol is clean and fast.

THat's an interesting approach, thanks. I'll give something like that a go.

[plenderj]

2 comments.

1) Redim without the Preserve keyword will clear the contents of the array
2) Erase will delete the array

[VBAhack]

You can use the memory managment API's for stacks and queues. Here is a simple example

Private Declare Sub CopyMemoryPut Lib "kernel32" Alias "RtlMoveMemory" (ByVal Destination As Long, Source As Any, ByVal Length As Long)
Private Declare Sub CopyMemoryRead Lib "kernel32" Alias "RtlMoveMemory" (Destination As Any, ByVal Source As Long, ByVal Length As Long)

Private Type Node
    Data As Long
    Next As Long
End Type

Dim cNode as Node, i as long, pCurrent as long
pCurrent = HeapAlloc(hHeap, 0, 8) 
For i = 1 To 10
   cNode.Data = i
   cNode.Next = HeapAlloc(hHeap, 8, 8) 
   CopyMemoryPut pCurrent, cNode, 8
   pCurrent = cNode.Next
Next i

[MartinLiss]

The Erase statement will remove a dynamic array from memory, no need to use Redim(0).

How important is speed? A collection adds overhead, both in memory consumption and speed (although neglible). Do you need "Game" type speed, where everything must complete in say 30ms or "User" speed where processing in 1000ms is hardly noticable.

Some times a collection is a lot faster than an array.

Option Explicit
Private Declare Function GetTickCount Lib "kernel32" () As Long
 
Private Sub Form_Load()
    ' Place this code in any Sub or Function
    Dim lngStart As Long
    Dim lngFinish As Long
    Dim lngCounter As Long
    
    ' Record the start "time"
    lngStart = GetTickCount()
    
    ' About 60ms on my PC
'    Dim MyCollection As New Collection
'    For lngCounter = 1 To 100000
'        MyCollection.Add lngCounter
'    Next
    
    ' About 5200ms on my PC
    Dim MyArray() As Long
    For lngCounter = 1 To 100000
        ReDim MyArray(lngCounter)
        MyArray(lngCounter) = lngCounter
    Next
    
    
    ' Record the finish "time"
    lngFinish = GetTickCount()
    
    ' Display the difference
    MsgBox CStr(lngFinish - lngStart)
End Sub

[MartinLiss]

BTW, this takes 15ms but there's probably a lot of wasted space.

Dim MyArray(100000) As Long
    For lngCounter = 1 To 100000
        'ReDim MyArray(lngCounter)
        MyArray(lngCounter) = lngCounter
    Next

[VBAhack]

Some times a collection is a lot faster than an array.

In your example yes, but my experience with collections is that they are extremely slow when you include reading and deleting items. Also, executing the redim preserve statement on every iteration is what really slows down the array example. Arrays are extremely fast.

BTW, this takes 15ms but there's probably a lot of wasted space.

visual basic code:------ Dim MyArray(100000) As Long
For lngCounter = 1 To 100000
'ReDim MyArray(lngCounter)
MyArray(lngCounter) = lngCounter
Next

Right you are on both counts!. But, the following executes in the same abount of time (10-20 ms) AND and memory can easily be de-allocated item by item.

hHeap = GetProcessHeap()
    pCurrent = HeapAlloc(hHeap, 0, 8)
    For i = 1 To 10000
        cNode.Data = i
        cNode.Next = HeapAlloc(hHeap, 8, 8)
        CopyMemoryPut pCurrent, cNode, 8
        pCurrent = cNode.Next
    Next i

[VBAhack]

Ooops, off by a factor of 10. The API example I just posted takes about 150ms (10x the array example). Thus, if you want raw speed, arrays can't be beat. But if you want an elegant C-like data structure, the memory API's seem like a good choice.

VBAhack

[VBAhack]

I remember doing performance comparisions long ago and just had to do it again to confince myself. Yep, the Collection is very slow at retrieving/removing objects. See code example comparing Collection, Linked-List based on memory API, and array. The array is, of course, the hands down winner, but the example isn't exactly fair because you can't delete array items one by one. Just for kicks I commented out the Collection remove line and there wasn't much difference.

VBAhack

Option Explicit
 
Private Declare Function HeapAlloc Lib "kernel32" (ByVal hHeap As Long, ByVal dwFlags As Long, ByVal dwBytes As Long) As Long
Private Declare Function GetProcessHeap Lib "kernel32" () As Long
Private Declare Function GetTickCount Lib "kernel32" () As Long
Private Declare Sub CopyMemoryPut Lib "kernel32" Alias "RtlMoveMemory" (ByVal Destination As Long, Source As Any, ByVal Length As Long)
Private Declare Sub CopyMemoryRead Lib "kernel32" Alias "RtlMoveMemory" (Destination As Any, ByVal Source As Long, ByVal Length As Long)
Private Declare Function HeapFree Lib "kernel32" (ByVal hHeap As Long, ByVal dwFlags As Long, lpMem As Any) As Long
 
Private Type Node
    Data As Long
    Next As Long
End Type
 
Private Sub Form_Load()
    ' Place this code in any Sub or Function
    Dim lngStart As Long, lngFinish As Long, lngCounter As Long, lngItems As Long, lngData As Long
    Dim lngCnt1 As Long, lngCnt2 As Long, lngCnt3 As Long, lngCnt4 As Long, lngCnt5 As Long
    Dim cNode As Node, i As Long, pCurrent As Long, hHeap As Long, pStart As Long
    lngItems = 30000
    lngStart = GetTickCount() ' Record the start time
    
    ' Collection (fast to create, but slow to retrieve/delete)
    Dim MyCollection As New Collection
    For lngCounter = 1 To lngItems
        MyCollection.Add lngCounter
    Next
    lngCnt1 = GetTickCount()
    For lngCounter = lngItems To 1 Step -1
        lngData = MyCollection.Item(lngCounter)
        MyCollection.Remove (lngCounter)
    Next
    lngCnt2 = GetTickCount()
    
    ' Memory API linked-list
    hHeap = GetProcessHeap()
    pStart = HeapAlloc(hHeap, 0, 8)
    pCurrent = pStart
    For lngCounter = 1 To lngItems
        cNode.Data = lngCounter
        cNode.Next = HeapAlloc(hHeap, 8, 8)
        CopyMemoryPut pCurrent, cNode, 8
        pCurrent = cNode.Next
    Next
    lngCnt3 = GetTickCount()
    pCurrent = pStart
    For lngCounter = 1 To lngItems
        CopyMemoryRead cNode, pCurrent, 8
        HeapFree GetProcessHeap(), 0, pCurrent
        pCurrent = cNode.Next
        lngData = cNode.Data
    Next
    lngCnt4 = GetTickCount()
    
    ' Array
    ReDim MyArray(lngItems) As Long
    For lngCounter = 1 To lngItems
        MyArray(lngCounter) = lngCounter
    Next
    lngCnt5 = GetTickCount()
    For lngCounter = 1 To lngItems
        lngData = MyArray(lngCounter)
    Next
    Erase MyArray
    lngFinish = GetTickCount() ' Record the finish "time"
    
    ' Display the difference
    ' 30000 item Collection: Create = 50  Create, Touch & Remove = 24144
    ' 30000 item API l-list: Create = 40  Create, Touch & Remove = 60
    ' 30000 item      Array: Create = 10  Create, Touch & Remove = 10
    Debug.Print lngItems & " item Collection: Create = " & lngCnt1 - lngStart & _
    "  Create, Touch & Remove = " & lngCnt2 - lngStart
    
    Debug.Print lngItems & " item API l-list: Create = " & lngCnt3 - lngCnt2 & _
    "  Create, Touch & Remove = " & lngCnt4 - lngCnt2
    
    Debug.Print lngItems & " item      Array: Create = " & lngCnt5 - lngCnt4 & _
    "  Create, Touch & Remove = " & lngFinish - lngCnt4
End Sub