Fastest way to find an item in a list?

I have an unsorted list of strings. I can place these items in an array, List, SortedList, whatever.

I need to find the fastest way of looking up a string in this list. Am I better off dumping the list into an array, sorting it, then implementing binary search? Or does the framework provide a way to do this?

Thanks

P.S. Using VS2008 against .NET 2.0

Answers


If your goal is just to make it very fast to find the strings in a collection, put them into a HashSet.

HashSet.Contains is an O(1) method, and strings have a good hash algorithm by default, so it will be difficult to make a faster routine than this.


Edit:

Since you're using .NET 2, I would just do Dictionary<string,string> and use the same string for key and value. Dictinoary<TKey,TValue>.Contains is also O(1), and will be much faster than any list-based searching you attempt.


If you will only have to find one object, one time, just start at the beginning and look at each one until you find it. If you will have to repeat this Find operation multiple times against the same list, to find different items, then sort it keep the sorted list and do a binary search...


I'm not sure whether this will be of any use to you, but this would be a fairly simple way of doing it, not sure on the exact "speed" of it though.

List<string> collection = new List<string>();

collection.Sort();

foreach(string value in collection)
{
   if(value == "stringToLookFor")
   {
       return value;
   }
{

Need Your Help

Determine if an HTML element's content overflows

javascript html css

Can I use JavaScript to check (irrespective of scrollbars) if an HTML element has overflowed its content? For example, a long div with small, fixed size, the overflow property set to visible, and no

CGContext line drawing: CGContextFillPath not working?

iphone quartz-2d cgcontext

Anyone have any idea why CGContextFillPath won't work in the code snippet below? I'm using the following code to draw to a UIImageView. It's stroking the path correctly, but ignoring CGContextFillP...