Словарь Lookup (O (1)) vs Linq, где

Question

Что происходит быстрее, и я должен пожертвовать стандартом Linq для достижения скорости (при условии, что поиск словаря действительно быстрее)? Итак, позвольте мне уточнить:

я следующее:

List<Product> products = GetProductList(); 

У меня есть необходимость поиска продукта на основе некоторого атрибута, например, серийный номер. Я мог бы сначала создать словарь, а затем заполнить его следующим образом:

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

Когда пришло время, чтобы найти продукт, воспользоваться O (1), предлагаемые словарного поиска:

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

в качестве альтернативы, с помощью Linq:

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

Недостатка подхода Dict, конечно, это требует больше места в памяти, больше коды писать, менее элегантно, и т.д. (хотя большинство это спорно). Предположим, что это нефактор. Должен ли я принять первый подход?

В заключение я хотел бы подтвердить, действительно ли сложность подхода Linq выше O (n), и я не вижу, как это может быть лучше.

Answer 1

Предполагая, что вы начинаете с перечислением объектов и только делает это один раз ...

Это будет быстрее сделать метод Where в отличие от добавления к Dictionary<TKey,TValue>, а затем ищет его обратно. Причина в том, что метод словаря не O (1). В этом случае вы добавляете элементы в словарь, а затем просматриваете его. Добавочной частью является O (N), которая столь же дорога, как и метод Where с дополнительными дополнительными ресурсами памяти.

Еще одна небольшая точка, о которой следует помнить, заключается в том, что Dictionary<TKey,TValue> не является действительно O (1). Вместо этого он приближается к O (1), но при определенных обстоятельствах может деградировать до меньшей производительности (например, много столкновений ключей).