[RESOLVED] Optimization with Lists

[NinjaNic]

Hi!

So, I've been experimenting with lists of custom classes and trying to find the most efficient way to find if a specific object is in the list. I made 3 functions that run differently to find out which one was the most efficient. ListOfBlock contained 10,200 items. (I ran 5 trials of 10k times each.) I expected the first function to be the fastest but in fact it was not.

ListContains ran at about 1515 times per second.
Cycle1 ran at about 926 times per second.
Cycle2 ran at about 3333 times per second, the fastest by far. I was surprised because this function cycled through every item in the list.

Can someone explain to me why this method is faster than using List.Contains? Does List.Contains also cycle through every item in the list, only we don't see it?

Thanks,
~Nic

Private Function ListContains(x As Int32, y As Int32) As Boolean
        If ListOfBlock.Contains(New Block(x, y)) Then
            Return True
        End If
        Return False
    End Function
 
    Private Function Cycle1(x As Int32, y As Int32) As Boolean
        For i As Int32 = 0 To ListOfBlock.Count - 1 Step 1
            If ListOfBlock(i).Equals(New Block(x, y)) Then
                Return True
            End If
        Next
        Return False
    End Function
 
    Private Function Cycle2(x As Int32, y As Int32) As Boolean
        For i As Int32 = 0 To ListOfBlock.Count - 1 Step 1
            If ListOfBlock(i).X = x And ListOfBlock(i).Y = y Then
                Return True
            End If
        Next
        Return False
    End Function

[si_the_geek]

Does List.Contains also cycle through every item in the list, only we don't see it?

Of course, how could it know if the requested item is there without checking each one?

Can someone explain to me why this method is faster than using List.Contains?

Cycle2 is more efficient than both of the others because you aren't creating a new Block object, which takes a bit of time (the fact that Cycle1 creates it inside the loop is why that was the slowest - storing it in a variable before the loop should get it roughly equal to ListContains).

You can make Cycle2 a bit faster by changing And to AndAlso (that way the .Y will only be checked if the .X is the same).

If you know in advance that the list will be sorted, using a Binary Search is likely to be much faster.

[NinjaNic]

Of course, how could it know if the requested item is there without checking each one?

Then I don't understand the advantage of List.Contains at all. If it still cycles through every item in the list and checks to make sure that all the properties are equal, is there any real use except that it's a little shorter to write?

[jmcilhinney]

If it still cycles through every item in the list and checks to make sure that all the properties are equal, is there any real use except that it's a little shorter to write?

That's not what List.Contains does. It simply tests whether each item is Equal to the specified object. For reference types, that means whether they refer to the same object. That means that Contains will return False if the List contains an item whose property values all match but is not the same object. For value types, Equals tests value equality.

[dbasnett]

Then I don't understand the advantage of List.Contains at all. If it still cycles through every item in the list and checks to make sure that all the properties are equal, is there any real use except that it's a little shorter to write?

Another approach is to move equality checks, = and <> operators, into the Block Class. This has the advantage of centralizing the check, but will not be as fast for iterating lists.

Here is what I mean,

Class Block
    Public X As Integer
    Public Y As Integer

    Public Sub New(x As Integer, y As Integer)
        Me.X = x
        Me.Y = y
    End Sub

    Public Shared Operator =(blockL As Block, blockR As Block) As Boolean
        If blockL.X = blockR.X AndAlso blockL.Y = blockR.Y Then
            Return True
        Else
            Return False
        End If
    End Operator

    Public Shared Operator <>(blockL As Block, blockR As Block) As Boolean
        Return Not blockL = blockR
    End Operator

End Class

This gives you the ability to write code like this

        Dim foo As New Block(3, 7)
        Dim bar As New Block(3, 7)

        If foo = bar Then
            Stop
        End If

The other advantage is what happens when there is a new variable that has to be considered for equality. You need only change the = operator to reflect the change.

Here is your list lookup using the = operator.

        Dim look4 As New Block(110, 109)

        Dim b As Block
        Dim fnd As Boolean = False
        For Each b In ListOfBlock
            If b = look4 Then
                fnd = True
                Exit For 'b will contain the equal item if found
            End If
        Next

I populated ListOfBlock like this to test

        Dim ListOfBlock As New List(Of Block)
        For x As Integer = 1 To 110
            For y As Integer = 1 To 110
                Dim blk As New Block(x, y)
                ListOfBlock.Add(blk)
            Next
        Next

[si_the_geek]

is there any real use except that it's a little shorter to write?

Shorter code is a very good thing most of the time (it takes less time to write/test, it is easier to maintain, etc), and as nearly all code runs much faster than it needs to, any minor speed loss is usually totally ignorable.

If you have a situation where you want to do something a bit different to the defaults provided then you need to put in the time to do it (eg: if you want a MessageBox to play video, it is probably best to create a new MessageBox), and similar applies if you want more speed (the default behaviours are designed to work properly in all cases, not be the fastest for a specific case). As dbasnett showed, you can often modify behaviours indirectly, in a way that is easier to re-use in other parts of your project.

However, if speed actually is an issue (it usually isn't, so I recommend checking) then trying to optimise a particular item (such as List.Contains) is rarely the best option - you can usually get far bigger speed gains by changing the algorithm based on the actual situation (eg: a Binary Search is massively fast, but is only valid if the data is sorted).

[NinjaNic]

@jmc: Okay thanks. I didn't write it in the first post, but I did override Equals in the 'block' class.

@dbasnett:

Another approach is to move equality checks, = and <> operators, into the Block Class. This has the advantage of centralizing the check, but will not be as fast for iterating lists.

Thank you very much for this. This is the first time I learned that that's possible. Most of my code looked similar except for .Equals instead of =.

@si_the_geek: Thanks for your insight. Speed wasn't an issue, but I was curious to see how fast this could run while changing around some things.

Thanks to all for the help!