Преобразование IEnumerable в словарь для производительности?

Question

Недавно в моей фирме появилась новая тенденция, когда мы меняем IEnumerable на словарь с помощью простого преобразования LINQ следующим образом:

enumerable.ToDictionary(x=>x);

В основном мы делаем это, когда операция над коллекцией является Contains / Access, и, очевидно, словарь имеет лучшую производительность в таких случаях.

Но я понимаю, что преобразование Enumerable в словарь имеет свою стоимость, и мне интересно, в какой момент он начинает работать безубыточно (если это так), т.е. производительность IEnumerable Contains / Access is равно ToDictionary + доступ / содержит.

Хорошо, я мог бы добавить, что нет доступа к базе данных, который может быть создан перечислимым из запроса к базе данных, и это тоже, и перечисляемое может быть отредактировано и после этого тоже.

Также было бы интересно узнать, как тип данных ключа влияет на производительность?

Обычно поиск может быть 2-5 раз, но иногда может быть и один. Но я видел такие вещи, как Для перечисляемого:

 var element=Enumerable.SingleorDefault(x=>x.Id);
 //do something if element is null or return

для словаря:

 if(dictionary.ContainsKey(x))
 //do something if false else  return

Это уже давно меня беспокоит.

Answer 1

Производительность словаря по сравнению с IEnumerable

A Dictionary при правильном использовании всегда быстрее читать из (за исключением случаев, когда набор данных очень мал, например, 10 элементов). При его создании могут быть накладные расходы.

Учитывая m как количество поисков, выполненных для одного и того же объекта (они приблизительны):

• Производительность IEnumerable (созданного из чистого списка): O (mn)
  • Это потому, что вам нужно каждый раз смотреть на все предметы (по сути m * O(n)).
• Производительность Dictionary: O(n) + O(1m) или O(m + n)
  • Это потому, что вам нужно сначала вставить элементы (O(n)).

В целом можно видеть, что Dictionary выигрывает, когда m > 1, и IEnumerable выигрывает, когда m = 1 или m = 0.

В общем, вы должны:

• Используйте Dictionary при выполнении поиска более одного раза для одного и того же набора данных.
• Используйте IEnumerable при поиске.
• Используйте IEnumerable, когда набор данных может быть слишком большим, чтобы поместиться в память.
  • Имейте в виду, что таблица SQL может использоваться как Dictionary, так что вы можете использовать ее для компенсации нагрузки на память.

Дополнительные соображения

Dictionary s использует GetHashCode() для организации своего внутреннего состояния. Производительность Dictionary тесно связана с хеш-кодом двумя способами.

• Плохо выполняет GetHashCode() - накладные расходы при каждом добавлении, поиске или удалении элемента.
• Низкокачественные хеш-коды - в результате словарь не будет иметь O(1) производительность поиска.

Большинство встроенных типов .Net (особенно типов значений) имеют очень хорошие алгоритмы хеширования. Однако с типами, подобными списку (например, строка), GetHashCode() имеет O(n) производительность - потому что он должен выполнять итерацию по всей строке. Таким образом, производительность вашего словаря действительно может быть видна как (где M - это большой показатель эффективности GetHashCode()): O(1) + M.

Answer 2

Это зависит ....

Как долго IEnumerable?

Вызывает ли доступ к IEnumerable доступ к базе данных?

Как часто он используется?

Лучше всего было бы поэкспериментировать и составить профиль.

Answer 3

Если вы выполняете поиск элементов в своей коллекции по какому-либо ключу - определенно, словарь будет быстрее, потому что это коллекция, основанная на хешах, и поиск будет быстрее во времени, в противном случае, если вы не выполняете поиск по коллекции, конверсия не нужна, потому что время конверсии может быть больше, чем вы, один или два поиска в коллекции,

Answer 4

Я добавлю, что вы не сказали нам, что происходит каждый раз, когда вы «перематываете» свой IEnumerable<>.Это непосредственно поддержано сбором данных?(например List<>) или он рассчитан "на лету"?Если это первое и для небольших коллекций, перечисление их для поиска нужного элемента происходит быстрее (словарь для 3/4 элементов бесполезен. Если вы хотите, я могу создать какой-то эталонный тест, чтобы найти точку разрыва).Если это второе, то вы должны подумать, является ли "кэширование" IEnumerable<> в коллекции хорошей идеей.Если это так, то вы можете выбрать между List<> или Dictionary<>, и мы вернемся к пункту 1. Является ли IEnumerable маленьким или большим?И есть третья проблема: если коллекция не поддерживается, но слишком велика для памяти, то, очевидно, вы не можете поместить ее в Dictionary<>.Тогда, возможно, пришло время заставить SQL работать на вас: -)

Я добавлю, что «сбои» имеют свою стоимость: в List<>, если вы попытаетесь найти элемент, который не существует,стоимость составляет O(n), тогда как в Dictionary<> стоимость по-прежнему составляет O(1).

Answer 5

ИМХО: вам нужно измерить это в вашей среде с репрезентативными данными. В таких случаях я просто пишу быстрое консольное приложение, которое измеряет время выполнения кода. Я полагаю, что для лучшего измерения вам нужно выполнить один и тот же код несколько раз.

ADD:

Это также зависит от приложения, которое вы разрабатываете. Обычно вы получаете больше за счет оптимизации других мест (избегая обходов сети, кэширования и т. Д.) За это время и усилия.