Fastest way to see if item exists in list

[Lucvdv]

What's the fastest/easiest/best way to determine if a certain item exists
in a list?

(And what's the slowest/dumbest - I suppose that's enumerating the elements
and comparing each in turn in VB code?)

My collection can have up to a few thousand elements (each either a GUID or
an ID card number in "000-0000000-00" format) and an even larger number may
have to be checked, so speed does become a bit of an issue.


The shortest will be something like this, but how is the speed compared to
other methods?

Dim IDList As New Collection
IDList.Add(Nothing, "a")
IDList.Add(Nothing, "b")
IDList.Add(Nothing, "c")

Public Function Exists(ID As String) As Boolean
Try
Dim Dummy As Object = IDList.Item(ID)
Return True
Catch
Return False
End Try
End Function

 

[Cor Ligthert]

Luc

In the way you use it now, I would have a look at the hashtable. Try to
avoid the VisualBasic Collection. It is a complete different collection than
all other Net collections.

hashtable
http://msdn.microsoft.com/library/d...frlrfsystemcollectionshashtableclasstopic.asp

After the scene is of course a lot done in the above collection. Maybe can
you think at the arraylist as well
http://msdn.microsoft.com/library/d...llectionsarraylistclassbinarysearchtopic1.asp

The last method I never used.

However I hope this helps,

Cor

 

[Lucvdv]

Luc

In the way you use it now, I would have a look at the hashtable. Try to
avoid the VisualBasic Collection. It is a complete different collection than
all other Net collections.

Thanks a lot.

The difference is astounding, a hashtable is 1000 times faster than the
method I used in my original post, probably due to the exception that
occurs upon every mismatch more than to the added overhead of putting it in
a function.

I wrote some test code that
- puts 10,000 strings in a VB collection
- looks up 10,000 random strings in it (as I did it in my original post),
- repeats the same with a hashtable and its Contains method.

Result:
- adding 10,000 elements to VB collection: 62 msec
- looking up 10,000 values in VB collection: 18363 msec
- adding 10,000 elements to hashtable: 0 msec
- looking up 10,000 values in hashtable: 15 msec.

The same strings were used for both tests.
The same random sequence was used in the lookup phase (reseeded random
generator to give the same sequence). The "strings" were integer.ToString
with values from 1 to 20,000 for the list and random 10,000 to 29,999 for
the lookup values.

The latter two shouldn't be taken too seriously, the system clock accuracy
is only 15 msec.

 

[Herfried K. Wagner [MVP]]

What's the fastest/easiest/best way to determine if a certain item exists
in a list?

\\\
If MyList.Contains(<object>) Then
...
End If
///

 

[Lucvdv]

\\\
If MyList.Contains(<object>) Then
...
End If
///

I assume you're referring to an ArrayList: it's the simplest, but Cor's
suggestion of using a hashtable delivers lookup results 100 times faster.

Checking for 10,000 items in a list of 10,000 with 50% hits:

VB Collection: 14889.0049 msec
ArrayList: 1484.2135 msec
HashTable: 15.6233 msec

Initializing the list is faster with an ArrayList (as expected).

Code complexity is about the same:

Dim s As String = ...
HashTable.Add(s, Nothing)
versus
ArrayList.Add(s)