Словарь поиска (O (1)) против Linq где - PullRequest
Новая
       14

Словарь поиска (O (1)) против Linq где

6 голосов
/ 16 марта 2010

Что быстрее, и стоит ли жертвовать стандартом 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), и я не вижу, как он может быть лучше этого.

1 Ответ

7 голосов
/ 16 марта 2010

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

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

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

...