Заполните большой список объектов с деталями из другого списка

Question

У меня большой запрос к базе данных, который возвращает около 100k записей в список в памяти.Мне нужно связать список связанных сотрудников с каждой записью (также около 100k записей), но я изо всех сил пытаюсь получить полезную производительность.

foreach (var detail in reportData.Details)
{
    detail.Employees = employees
      .Where(x => x.AccountingDocumentItemId == detail.AccountingDocumentItemId)
      .Select(x => x.Employee)
      .ToList();

    detail.Employee = String.Join(", ", detail.Employees);
}

Приведенный выше код занимает 8 минут для завершения.Я сузил проблему скорости до первой строки в for loop, где он находит соответствующих сотрудников.Если я опускаю ToList(), это супер быстро, но следующая строка немедленно вызывает проблемы, при которых String.Join вызывает выполнение Where.

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

Answer 1

Ваш текущий код имеет O(n ** 2) сложность времени ( вложенных циклов ), и, таким образом, у вас есть 1e5 * 1e5 ~ 1e10 ( 10 миллиардов ) операций, выполнение которых занимает 8 минут,

Давайте извлечем словарь , чтобы иметь O(n) сложность времени (только ~1e5 операции):

var dict = reportData
  .Details
  .GroupBy(item => item.AccountingDocumentItemId,
           item => item.Employee)
  .ToDictionary(chunk => chunk.Key, 
                chunk => chunk.ToList());

foreach (var detail in reportData.Details) {
  detail.Employees = dict.TryGetValue(detail.AccountingDocumentItemId, out var list) 
    ? list.ToList()        // copy of the list 
    : new List<MyClass>(); // put the right type instead of MyType

  detail.Employee = String.Join(", ", detail.Employees);
}