Как сделать вложенный цикл более эффективным?
У меня есть следующий код, который я хотел бы ускорить:
foreach (var workflow in closedWorkflows)
{
var w = relatedWorkflows.FirstOrDefault(r => r.Fingerprint != workflow.Fingerprint && r.TradeDate == workflow.TradeDate);
if (w != null)
{
relatedWorkflows.Add(workflow);
}
}
relatedWorkflows и closedWorkflows — список объектов одного типа.
Я думал о создании поиска или словаря с анонимным классом или кортежем для Fingerprint и TradeDate, но одна проверка предназначена для равенства, а другая — для неравенства.
Было бы хорошим подходом создать поиск на TradeDate, а затем создать поиск на Fingerprint для каждого списка поиска TradeDate?
Обновлено:
ОГРОМНОЕ спасибо @Дмитрию Быченко.
В моем тесте разница 41486 мс против 26мс!!!
Ответы 1
Основная проблема с производительностью связана с
var w = relatedWorkflows.FirstOrDefault(...)
мы сканируем relatedWorkflows снова и снова, поэтому у нас есть O(closedWorkflows.Count * relatedWorkflows.Count) временная сложность.
Мы можем избавиться от relatedWorkflows.Count с помощью коллекций на основе хэшей (словарей и хешсетов), например
var dict = workflow
.GroupBy(item => item.TradeDate, item => item.FingerPrint)
.ToDictionary(group => group.Key, group => group.ToHashSet());
foreach (var workflow in closedWorkflows) {
// If we have a date, but NOT print we add it into relatedWorkflows
if (dict.TryGetValue(workflow.TradeDate, out var prints) &&
prints.Add(workflow.Fingerprint)) {
relatedWorkflows.Add(workflow);
}
}
Вместо prints.Add(workflow.Fingerprint) я бы предпочел !prints.Contains(workflow.Fingerprint), чтобы избежать изменения структуры поиска и для более четкой семантики.
@Theodor Zoulias: Обратите внимание, что исходный код мы модифицируем relatedWorkflows -relatedWorkflows.Add(workflow); поэтому при следующем сканировании должна использоваться измененная коллекция; это основная причина, по которой я поставил Add, а не Contains.
При использовании FirstOrDefault проверка будет последовательной, поэтому поиск, очевидно, будет быстрее. Кстати, насколько велики ваши коллекции, и вы замечаете задержки.