VS 2015 [RESOLVED] Optimization with Lists-VBForums
Results 1 to 7 of 7

Thread: [RESOLVED] Optimization with Lists

  1. #1

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    228

    Resolved [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:
    1. Private Function ListContains(x As Int32, y As Int32) As Boolean
    2.         If ListOfBlock.Contains(New Block(x, y)) Then
    3.             Return True
    4.         End If
    5.         Return False
    6.     End Function
    7.  
    8.     Private Function Cycle1(x As Int32, y As Int32) As Boolean
    9.         For i As Int32 = 0 To ListOfBlock.Count - 1 Step 1
    10.             If ListOfBlock(i).Equals(New Block(x, y)) Then
    11.                 Return True
    12.             End If
    13.         Next
    14.         Return False
    15.     End Function
    16.  
    17.     Private Function Cycle2(x As Int32, y As Int32) As Boolean
    18.         For i As Int32 = 0 To ListOfBlock.Count - 1 Step 1
    19.             If ListOfBlock(i).X = x And ListOfBlock(i).Y = y Then
    20.                 Return True
    21.             End If
    22.         Next
    23.         Return False
    24.     End Function

  2. #2
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    39,428

    Re: Optimization with Lists

    Quote Originally Posted by NinjaNic View Post
    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. #3

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    228

    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. #4
    .NUT jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    97,091

    Re: Optimization with Lists

    Quote Originally Posted by NinjaNic View Post
    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.
    Why is my data not saved to my database? | MSDN Data Walkthroughs
    VBForums Database Development FAQ
    My CodeBank Submissions: VB | C#
    My Blog: Data Among Multiple Forms (3 parts)
    Beginner Tutorials: VB | C# | SQL

  5. #5
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Pointless Forest 38.517,-92.023
    Posts
    8,940

    Re: Optimization with Lists

    Quote Originally Posted by NinjaNic View Post
    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)
                    ListOfBlock.Add(blk)
                Next
            Next
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein
    "They who can give up essential liberty to obtain a little temporary safety, deserve neither liberty nor safety." Benjamin Franklin
    "It is not all that I know that is the problem, it is all I think I do that is."

  6. #6
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    39,428

    Re: Optimization with Lists

    Quote Originally Posted by NinjaNic View Post
    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. #7

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    228

    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!

Tags for this Thread

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


Click Here to Expand Forum to Full Width

Survey posted by VBForums.