What NET collection provides the fastest search

Question

I have 60k items that need to be checked against a 20k lookup list  Is there a collection object  like List  HashTable  that provides an exceptionly fast Contains   method  Or will I have to write my own  In otherwords  is the default Contains   method just scan each item or does it use a better search algorithm   foreach  Record item in LargeCollection        if  LookupCollection Contains item Key                   Do something           Note  The lookup list is already sorted

User · Accepted Answer

In the most general case  consider System Collections Generic HashSet as your default  Contains  workhorse data structure  because it takes constant time to evaluate Contains    The actual answer to  What is the fastest searchable collection  depends on your specific data size  ordered-ness  cost-of-hashing  and search frequency

User · Answer

If you don t need ordering  try HashSet lt Record gt   new to  Net 3 5   If you do  use a List lt Record gt  and call BinarySearch

User · Answer

Keep both lists x and y in sorted order   If x   y  do your action  if x  lt  y  advance x  if y  lt  x  advance y until either list is empty   The run time of this intersection is proportional to min  size  x   size  y    Don t run a  Contains    loop  this is proportional to x   y which is much worse

User · Answer

If you re using  Net 3 5  you can make cleaner code using   foreach  Record item in LookupCollection Intersect LargeCollection         dostuff     I don t have  Net 3 5 here and so this is untested   It relies on an extension method   Not that LookupCollection Intersect LargeCollection  is probably not the same as LargeCollection Intersect LookupCollection      the latter is probably much slower   This assumes LookupCollection is a HashSet

User · Answer

If you aren t worried about squeaking every single last bit of performance the suggestion to use a HashSet or binary search is solid   Your datasets just aren t large enough that this is going to be a problem 99  of the time   But if this just one of thousands of times you are going to do this and performance is critical  and proven to be unacceptable using HashSet binary search   you could certainly write your own algorithm that walked the sorted lists doing comparisons as you went   Each list would be walked at most once and in the pathological cases wouldn t be bad  once you went this route you d probably find that the comparison  assuming it s a string or other non-integral value  would be the real expense and that optimizing that would be the next step

User · Answer

Have you considered List BinarySearch item    You said that your large collection is already sorted so this seems like the perfect opportunity   A hash would definitely be the fastest  but this brings about its own problems and requires a lot more overhead for storage

User · Answer

You should read this blog that speed tested several different types of collections and methods for each using both single and multi-threaded techniques   According to the results  a BinarySearch on a List and SortedList were the top performers constantly running neck-in-neck when looking up something as a  value    When using a collection that allows for  keys   the Dictionary  ConcurrentDictionary  Hashset  and HashTables performed the best overall

User · Answer

If it s possible to sort your items then there is a much faster way to do this then doing key lookups into a hashtable or b-tree  Though if you re items aren t sortable you can t really put them into a b-tree anyway    Anyway  if sortable sort both lists then it s just a matter of walking the lookup list in order   Walk lookup list    While items in check list  lt   lookup list item      if check list item   lookup list item do something    Move to next lookup list item

[c#] What .NET collection provides the fastest search

Examples related to c#

Examples related to .net

Examples related to search

Examples related to collections