what is faster array/collections?

[jagguy]

What is faster collections or arrays? I have an array of objects which I use and need to search through the objects quickly using for loops.

I could have also used a collection but for speed purposes what is known to be faster. I dont use an array datatype

[Atheist]

Most collections in .NET uses arrays internally, so I doubt you'll see any speed difference in the lookup.
There are however collections that internally uses linked lists, these collections will be slower than arrays or collections using arrays for looking up a value.

[ntg]

If you know before hand the type of the objects, I think that arrays are faster for direct access (e.g. access to element 10 for example). If you can sort the array and the element you need to find can be pinpointed by its index, you should go for this solution. If, on the other hand, you can sort your objects but you cannot pinpoint them by an integer index, you should use the SortedList(Of...) class.

In any event, if speed is critical I always time both candidate solutions using the StopWatch class (I think that this is now part of .Net 3.5). To do that, I implement both candidate solutions and jog them through a few thousand iterations to see how they perform.

[jmcilhinney]

The best solution depends on what data you're storing, how you're storing it and how you're searching it. There are all sorts of different collections, each best for a particular purpose. If you tell us what you're storing, how you're storing it and how you're retrieving the data, then we can probably advise on the best course of action. The situation will almost always tell you what data structure to use.

[jagguy]

Is there a benchtest of different for datatypes i can see?

I am storing an array of objects with about 15 properties and 6 methods. SOme properties have images stored.
I search through them using for loops to match certain boolean properties as i find having flags makes for quicker searching for items.

Say I am storing 20 enemy objects from a game so I cant see a use for key pair collection as each enemy is the same.

[jmcilhinney]

You could create your own strongly-typed collection by inheriting System.Collections.ObjectModel.Collection(Of T). That provides all the standard collection functionality. You could then extend the class. As a very simple example, here's a collection class that gives you immediate access to the items that have a flag set and those that have it not set:

Public Class Thing
 
    Private _flag As Boolean
 
    Public Property Flag() As Boolean
        Get
            Return Me._flag
        End Get
        Set(ByVal value As Boolean)
            If Me._flag <> value Then
                Me._flag = value
                Me.OnFlagChanged(EventArgs.Empty)
            End If
        End Set
    End Property
 
    Public Sub New()
        Me.New(False)
    End Sub
 
    Public Sub New(ByVal flag As Boolean)
        Me._flag = flag
    End Sub
 
    Public Event FlagChanged As EventHandler
 
    Protected Overridable Sub OnFlagChanged(ByVal e As EventArgs)
        RaiseEvent FlagChanged(Me, e)
    End Sub
 
End Class
 
 
Public Class ThingCollection
    Inherits System.Collections.ObjectModel.Collection(Of Thing)
 
    Private _flaggedItems As New List(Of Thing)
    Private _unflaggedItems As New List(Of Thing)
 
    Public ReadOnly Property FlaggedItems() As Thing()
        Get
            Return Me._flaggedItems.ToArray()
        End Get
    End Property
 
    Public ReadOnly Property UnflaggedItems() As Thing()
        Get
            Return Me._unflaggedItems.ToArray()
        End Get
    End Property
 
    Protected Overrides Sub ClearItems()
        Me._flaggedItems.Clear()
        Me._unflaggedItems.Clear()
 
        For Each item As Thing In Me.Items
            RemoveHandler item.FlagChanged, AddressOf HandleFlagChanged
        Next
 
        MyBase.ClearItems()
    End Sub
 
    Protected Overrides Sub InsertItem(ByVal index As Integer, ByVal item As Thing)
        Me.ProcessNewItem(item)
        MyBase.InsertItem(index, item)
    End Sub
 
    Protected Overrides Sub RemoveItem(ByVal index As Integer)
        Me.ProcessRemovedItem(Me.Items(index))
        MyBase.RemoveItem(index)
    End Sub
 
    Protected Overrides Sub SetItem(ByVal index As Integer, ByVal item As Thing)
        Me.ProcessRemovedItem(Me.Items(index))
        Me.ProcessNewItem(item)
        MyBase.SetItem(index, item)
    End Sub
 
    Private Sub HandleFlagChanged(ByVal sender As Object, ByVal e As EventArgs)
        Dim item As Thing = DirectCast(sender, Thing)
 
        If item.Flag Then
            Me._unflaggedItems.Remove(item)
            Me._flaggedItems.Add(item)
        Else
            Me._flaggedItems.Remove(item)
            Me._unflaggedItems.Add(item)
        End If
    End Sub
 
    Private Sub ProcessNewItem(ByVal item As Thing)
        If item.Flag Then
            Me._flaggedItems.Add(item)
        Else
            Me._unflaggedItems.Add(item)
        End If
 
        AddHandler item.FlagChanged, AddressOf HandleFlagChanged
    End Sub
 
    Private Sub ProcessRemovedItem(ByVal item As Thing)
        If item.Flag Then
            Me._flaggedItems.Remove(item)
        Else
            Me._unflaggedItems.Remove(item)
        End If
 
        RemoveHandler item.FlagChanged, AddressOf HandleFlagChanged
    End Sub
 
End Class

To get the flagged items you simply get the FlaggedItems property and to get the unflagged items you simply get the UnflaggedItems property. This is called "encapsulation" and is one of the basic tenets of OOP.

Just note that in this case a new array object is created each time you get a property value. This does have implications, so be aware.

[jagguy]

ok thanks i will look at it.

THis will be quicker than just searching through each element in the collection or just searching through an array of objects?

So i need to search through the array of flagged items. NOw speed is an issue because i may sometime in the future have a lot of items. Also one property is an array already.

[jmcilhinney]

The whole point here is that there is no searching to be done. If you want the items whose Flag property is True you simply get the FlaggedItems property. Done. It doesn't matter how many items you've got. If you have more properties that you might want to categorise items by then you simply create more properties like those.

Now, in this case I've created two properties that correspond to Flag property values of True and False. This is OK for Booleans because they can only have two values. For other types you couldn't do that. For instance, you couldn't add a String() property to your collection for every possible value that a String property of your items might have. In that case you could maintain a Dictionary internally. The keys would be the item property values and the values would be Lists of items whose properties have that value. To "search" you would then simply test for the existence of a key and, if it existed, get the corresponding List and convert it to an array.

Also, instead of asking over and over "will this be faster" maybe you should conduct some of your own testing to see how performance compares and whether it's worth even worrying about the difference if it's only a few milliseconds. This is the sort of thing developers do.

[jagguy]

i am not getting it right,sorry to be a pain.

I thought i am adding an object to class ThingCollection which which have the flag set to true.
They way i have done it there is no way i can get what specific element was added other than just a whole lot of true value.

Dim a(10) As Thing
Dim b As New ThingCollection
Dim i As Integer
Dim val As Boolean
For i = 0 To 9
a(i) = New Thing
If i >= 6 Then
a(i).Flag = True

b.Insert(b.Count, a(i))
End If
Next

For i = 0 To b.Count - 1
val = b.FlaggedItems(i).Flag
MsgBox(val)
Next

[jmcilhinney]

The point of my example was to show that you could get all the items from the ThingCollection whose Flag property was set to True, or to False, without having to do any "searching". First up, let's try changing the Thing class to make it more obvious which one is which. Change the Thing class definition to this:

Public Class Thing

    Private _flag As Boolean
    Private _name As String

    Public Property Flag() As Boolean
        Get
            Return Me._flag
        End Get
        Set(ByVal value As Boolean)
            If Me._flag <> value Then
                Me._flag = value
                Me.OnFlagChanged(EventArgs.Empty)
            End If
        End Set
    End Property

    Public ReadOnly Property Name() As String
        Get
            Return Me._name
        End Get
    End Property

    Public Sub New(ByVal name As String, ByVal flag As Boolean)
        Me._name = name
        Me._flag = flag
    End Sub

    Public Event FlagChanged As EventHandler

    Protected Overridable Sub OnFlagChanged(ByVal e As EventArgs)
        RaiseEvent FlagChanged(Me, e)
    End Sub

End Class

So now each Thing has a name, to help distinguish it from all the other things. Now try executing this code:

Dim things As New ThingCollection

For index As Integer = 0 To 9
    things.Add(New Thing("Thing " & index, index Mod 2 = 0))
Next

For Each something As Thing In things.FlaggedItems
    MessageBox.Show(something.Name, "Divisable By 2")
Next

For Each something As Thing In things.UnflaggedItems
    MessageBox.Show(something.Name, "Not Divisable By 2")
Next

Hopefully that proves to you that the FlaggedItems property gets you all the Thing objects in the collection whose Flag property is set to True without your having to do any "searching". There's no need to loop through the collection because all the flagged items are immediately available via that property. Likewise the Thing objects in the collection whose Flag property is set to False are immediately available via the UnflaggedItems property.

Now, to show what all the event code in the Thing and ThingCollection classes is for, try executing this code:

Dim things As New ThingCollection

For index As Integer = 0 To 9
    things.Add(New Thing("Thing " & index, index Mod 2 = 0))
Next

For Each something As Thing In things.FlaggedItems
    MessageBox.Show(something.Name, "Divisable By 2")
Next

For Each something As Thing In things.UnflaggedItems
    MessageBox.Show(something.Name, "Not Divisable By 2")
Next

For index As Integer = 0 To things.Count - 1
    things(index).Flag = (index Mod 3 = 0)
Next

For Each something As Thing In things.FlaggedItems
    MessageBox.Show(something.Name, "Divisable By 3")
Next

For Each something As Thing In things.UnflaggedItems
    MessageBox.Show(something.Name, "Not Divisable By 3")
Next

So you see, the FlaggedItems and UnflaggedItems properties have been automatically updated to reflect the changes made to the Flag properties of the items in the collection.

[jagguy]

ok i see what you are saying. It works but i am unclear how some of it works.

It is really how the objects are being added in the first place .
For index As Integer = 0 To 9
things.Add(New Thing("Thing " & index, index Mod 2 = 0))
Next

NOw the add method you can use as it is a method of collections but if i comment out this method i dont see why the things fails as how is this connected when adding new items?

Protected Overrides Sub InsertItem(ByVal index As Integer, ByVal item As Thing)
'Me.ProcessNewItem(item)
'MyBase.InsertItem(index, item)

End Sub

[jmcilhinney]

How much have you read about the Collection(Of T) class?

[jagguy]

i am new to extending a class so it is taking time to understand.

http://msdn.microsoft.com/en-us/library/ms132404.aspx
http://msdn.microsoft.com/en-us/library/ms132397.aspx

[jmcilhinney]

Just as long as you've read it and tried to understand, I'm happy. Try first, ask questions later is my own philosophy and what I expect from others.

The Collection(Of T) class is SPECIFICALLY intended to be used as a base class for your own strongly-typed collections. You can inherit it and all you have to do is provide a value for the generic type parameter and, with no code at all, you've created a collection type that will work for your item type only.

What it also provides is the facility to extend the class to provide extra functionality. That's what we're doing here. When you call the Add method to add an item or the Insert method to insert an item, in both cases the InsertItem method is called internally. The base implementation of this method simply inserts the specified item at the specified index. If you called Add then the index will simply be one greater than the previous highest index.

Now, if you want to perform some custom processing when an item is added, which we do, you are supposed to override the InsertItem method, which we do. When you do that you MUST call the base method. Remember that it's the base method that actually inserts the new item, so if you don't call it the item won't get inserted. That's why you cannot comment out this line:

MyBase.InsertItem(index, item)

As for the other line, that's our custom processing. The whole point of overriding the InsertItem is so we can do some custom processing so if we're not going to do any processing why would we override the method? Our custom processing is adding a handler for the new item's FlagChanged event. This allows us to detect when the value of the Flag property changes for any and all items. When that happens we move the item from the _flaggedItems to the _unflaggedItems or vice versa, whichever is appropriate. This is exactly the point of this whole exercise. We maintain these lists as changes are made, therefore there's no need to go searching if and when we need to get all the flagged or unflagged items. They are already categorised by Flag, courtesy of this custom processing.

[jagguy]

I know in OO theory that if you inherit classes you can override certain methods and write your own as well as you functionality of inherited class.

What confused was that
1) I couldnt see that add method uses insert as well.
2)The mybase.insert does the inserting and you have added an extra method to it Me.ProcessNewItem(item) for extra functionality. You cant actually change the functionality of this method because you need mybase but you can extend what it does.


What I still have trouble understanding.

1)you have added an event for something which i would use a method for. Events to me has meant clicking on a button or catering for dynamic controls which have no events. It looks like you have created a new event which is to be overriden anyway so following the logic is a bit 'back and forth'. I would not have bothered with using the THing class to keep track of a list of thing items values.

I would have had the flag property as a method which would deal with the creation of the new list there. For a beginner this is easier to follow than making an event and overriding it with another event handler.

[jmcilhinney]

You are confused. I'm not overriding any event. It's not possible to override an event. What I have done is declare and event in the Thing class and then handle that event in the ThingCollection class. What are events for? They are to enable other objects to be notified when something happens. What is this event for? It's to notify the ThingCollection whenever the Flag property of a Thing object changes.

You seem to be completely missing the point here. The whole point of this exercise is for the ThingCollection to be able to keep all the Thing objects it contains continually categorised by the value of their Flag properties. How is the ThingCollection supposed to do that if it doesn't get notified when a Thing object's Flag property changes? Let's say you get a Thing object and pass it into a method and, in that method, you change it's Flag property value. How else is the ThingCollection supposed to know that it needs to recategorise that Thing object if there's no event raised to notify it of the change. I'm not sure what you're suggesting as an alternative but, while it may be easier to understand, it simply won't work. This is an opportunity to learn how to use events. I suggest you take it.

[jagguy]

As a test
I declare the event like this....

Public Event FlagChanged(ByVal Value As Boolean)

Raise the event when the flag is changed, which is done in the Flag property....

Public Property Flag() As Boolean
Get
Return Me._flag
End Get
Set(ByVal value As Boolean)
If Me._flag <> value Then
Me._flag = value
RaiseEvent FlagChanged(value)
End If
End Set
End Property

....then i handle the event with a routine like this....

AddHandler aa.FlagChanged, AddressOf FlagChanged

Private Sub FlagChanged(ByVal sender As Object, ByVal e As EventArgs)
MsgBox("_name")
End Sub

[jmcilhinney]

What you've done there is basically no different to what I did except that you've broken several conventions. That and your code won't compile, of course.

First up, you've declared your FlagChanged event as having a single parameter of type Boolean, then you try to handle it with a method that has two parameters of type Object and EventArgs. That's simply not going to work. While they don't have to be, all events SHOULD be handled by methods that have two parameters of type Object and EventArgs (or some type that inherits EventArgs). As such, all events should be declared like this:

Public Event SomeEvent As EventHandler

or like this:

Public Event SomeEvent As EventHandler(Of SomeTypeThatInheritsEventArgs)

which is exactly what I did in my code.

Secondly, while it doesn't have to be, it is convention to NOT raise an event directly in a property setter. It is convention to declare a method for each event whose sole purpose it is to raise that event. Whenever you want to raise the event, like in the property setter, you simply call that method. The method is declared Protected Overridable to enable derived classes to override the method and provide custom behaviour on that event. This is exactly how we create derived controls and provide custom painting behaviour by overriding the OnPaint method, which raises the Paint event. Again, that's exactly what I did in my code. When the Flag property is set the OnFlagChanged method is called and the FlagChanged event is raised.

[jagguy]

ok i see .
I dont need the boolean parameter because i get access to the whole object via sender and then cast, and place the raise event in an overridable method

[jmcilhinney]

If you really did need to pass data to the event handlers then that's what the 'e' parameter is for. You declare your event with one of the existing derived EventArgs types or, if a suitable one doesn't exist, declare your own. You then bundle the data into an instance of that type and pass as the second argument when you call RaiseEvent, so it then becomes the second argument for each event handler.

[jagguy]

I understand how to raise my own events so thankyou for this.

I am not so clear about the 'e' parameter. You said you pass data via the e parameter but how do you do that, as it doesnt seem to allow you to assign it to anything.
The msdn example was a bit much to understand but it looks like you need to declare you own class and create you own eventargs and somehow use this.

ok i looked on google and msdn and didnt really understand e parameter well.
If you have a website i can read about it that is a bit simpler to understand than msdn as you have helped me enough so far.

[jmcilhinney]

The 'e' parameter must be type EventArgs or some type derived from EventArgs. If you don't need to pass any data then you simply use EventArgs and, when you raise the event, you pass EventArgs.Empty. If you need to pass some data then you use some type that inherits EventArgs and adds properties to contain the data. This type could be one of the existing derived EventArgs types in the Framework or it might be one of your own creation.

Consider the situation where you have a property that you want to be notified of changes to, but you also want to be notified before the property changes so that you can cancel the change if the proposed value isn't valid. I've done exactly this myself for a class that had a Key property that was required to be unique within a collection. If the client code tried to set the Key to a value that already existed within the collection the change was rejected. Here's how that would look:

Public Class Thing
 
    Private _key As String
 
 
    Public Property Key() As String
        Get
            Return Me._key
        End Get
        Set(ByVal value As String)
            If Me._key <> value Then
                'Pass the proposed value to the KeyChanging event.
                Dim e As New KeyChangingEventArgs(value)
 
                'Notify client code that the property value is changing.
                Me.OnKeyChanging(e)
 
                If Not e.Cancel Then
                    'The change was not cancelled so commit it.
                    Me._key = value
 
                    'Notify client code that the property value changed.
                    Me.OnKeyChanged(EventArgs.Empty)
                End If
            End If
        End Set
    End Property
 
 
    Public Event KeyChanging As EventHandler(Of KeyChangingEventArgs)
    Public Event KeyChanged As EventHandler
 
 
    Protected Overridable Sub OnKeyChanging(ByVal e As KeyChangingEventArgs)
        RaiseEvent KeyChanging(Me, e)
    End Sub
 
    Protected Overridable Sub OnKeyChanged(ByVal e As EventArgs)
        RaiseEvent KeyChanged(Me, e)
    End Sub
 
End Class

Notice how the two events are declared. KeyChanged is just declared as an EventHandler so it passes an EventArgs object to its handlers, which is the default. The KeyChanging event needs to pass data to its handlers so it is declared as a generic EventHandler, with the generic type argument being KeyChangingEventArgs, so it will pass an object of that type to its handlers.

Note the way the events are raised. The methods that raise the events look almost exactly the same, except that the type of the object passed to the second parameter of the event handlers is different. Now look at how those methods are called in the property setter. KeyChanging is called BEFORE the property value is actually changed. A KeyChangingEventArgs object is created that contains the data required by the event handlers, i.e. the value that the property is changing to. Now, in this case the KeyChangingEventArgs inherits the CancelEventArgs class, so it is able to receive data in the event handlers too. Specifically, the client code can set its Cancel property to True. In that case the event is cancelled, which is interpreted as the new property value being discarded without being committed, so the property value never changes. Now, if the property never changes then the KeyChanged event is never raised, but if the KeyChanging event is not cancelled and the property value does change, then the KeyChanged is raised. The KeyChanged event handlers don't require any data so EventArgs.Empty is passed when the event is raised.

As I said, I've used this exact pattern in a collection class that needed to ensure that each item had a unique key. The event handler for the KeyChanging event would look like this:

Private Sub something_KeyChanging(ByVal sender As Object, _
                                  ByVal e As KeyChangingEventArgs)
    Dim proposedValue As String = e.ProposedValue
 
    For Each item As Thing In Me.Items
        If item.Key = proposedValue Then
            'The proposed key already exists.
            e.Cancel = True
            Exit For
        End If
    Next
End Sub

[jagguy]

thanks, i have been busy but i will look at it soon