PHP User Warning: fetch_template() calls should be replaced by the vB_Template class. Template name: bbcode_highlight in ..../includes/functions.php on line 4197
VS 2015 [RESOLVED] Optimization with Lists-VBForums

# Thread: [RESOLVED] Optimization with Lists

1. ## [RESOLVED] Optimization with Lists

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

vb Code:
`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`

2. ## Re: Optimization with Lists

Originally Posted by NinjaNic
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.

3. ## Re: Optimization with Lists

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?

4. ## Re: Optimization with Lists

Originally Posted by NinjaNic
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.

5. ## Re: Optimization with Lists

Originally Posted by NinjaNic
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,

Code:
```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

Code:
```        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.

Code:
```        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

Code:
```        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)
Next
Next```

6. ## Re: Optimization with Lists

Originally Posted by NinjaNic
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).

7. ## Re: Optimization with Lists

@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!

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Featured