Dictionary Lookup (O(1)) vs Linq where

Question

What is faster and should I sacrifice the Linq standard to achieve speed (assuming Dictionary lookup is truly faster)? So let me elaborate:

I have the following:

List<Product> products = GetProductList();

I have a need to search for a product based on some attribute, for example, the serial number. I could first create a dictionary, and then populate it as follow:

Dictionary<string, Product> dict = new Dictionary<string, Product>();
foreach(Product p in products)
{
    dict.Add(p.serial, p);
}

When it's time to find a product, take advantage of O(1) offered by the Dictionary look-up:

string some_serial = ...;
try { Product p = dict[some_serial]; } catch(KeyNotFoundException) { }

Alternatively, using Linq:

Product p = products.Where(p => p.serial.Equals(some_serial)).FirstOrDefault();

The drawback with the Dict approach is of course this requires more space in memory, more code to write, less elegant, etc (though most of this is debatable). Assume that's non-factor. Should I take the first approach?

To conclude, I would like to confirm if the complexity of the Linq approach above is indeed O(n) and I don't see how it can be better than that.

Answer 1

Assuming you are starting with an enumeration of objects and are only doing this once ...

It will be faster to do the Where method as opposed to adding to a Dictionary<TKey,TValue> and then looking it back up. The reason why is that the dictionary method is not O(1). In this scenario you are adding items to the dictionary and then looking it up. The adding part is O(N) which is just as expensive as the Where method with additional memory overhead.

Another minor point to be aware of is that Dictionary<TKey,TValue> is not truly O(1). It instead approaches O(1) but can degrade to lesser performance in certain circumstances (lots of clashing keys for instance).