Как эффективно сравнить два отсортированных больших списка в C#?

Question

У меня есть два общих списка с 20 000 и 30 000 объектов в каждом списке.

class Employee 
{ 
    string name; 
    double salary; 
} 

List<Employee> newEmployeeList = List<Employee>() {....} // contains 20,000 objects 
List<Employee> oldEmployeeList = List<Employee>() {....} // contains 30,000 objects 

Списки также могут быть отсортированы по названию, если это улучшает скорость.

Я хочу сравнить эти два списка, чтобы узнать

1. сотрудников, чьи имена и зарплаты соответствующие
2. сотрудников, чьи имя не совпадает, но не зарплаты

Какой самый быстрый способ для сравнения такие большие списки данных с вышеуказанными условиями?

Answer 1

Я бы выбрал оба newEmployeeList и oldEmployeeList списки по name - O(n*log(n)). А затем вы можете использовать линейный алгоритм для поиска совпадений. Таким образом, сумма будет равна O(n+n*log(n)), если оба списка примерно одинакового размера. Это должно быть быстрее, чем O(n^2) Алгоритм «грубой силы».

Answer 2

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

Но mantioned других, вы должны измерить его против ваших требований проекта, а производительность часто имеет тенденцию быть субъективным вещи.

Answer 3

Вы можете создать словарь с помощью

var lookupDictionary = list1.ToDictionary(x=>x.name); 

Это даст вам близко к O (1) поиск и близкий к О (п) поведение, если вы отрываясь значения из цикла по сравнению с другими список.

(я здесь при условии, что ToDictionary О (п), будет иметь смысл с прямой передней реализации, но я не проверял, чтобы это было так)

Это сделало бы для очень прямо вперед алгоритм, и я думаю, что переход ниже O (n) с двумя несортированными списками довольно сложно.

Answer 4

Я бы рекомендовал, чтобы два списка хранились в Dictionary<string, Employee> на основе имени для начала, затем вы можете перебирать ключи в одном и искать, существуют ли они, а зарплаты совпадают в другом. Это также сэкономит затраты на их сортировку позже или добавит их в более эффективную структуру.

Это в значительной степени O (n) - линейный, чтобы строить оба словаря, линейные, чтобы проходить через ключи и искать в другом. Поскольку O (п + т + п) сводится к O (N)

Но, если вы должны использовать List<T> для хранения списков по другим причинам, вы можете также использовать метод Join() LINQ, и создать новый список с полем Match, в котором указывается, были ли они совпадением или несоответствием ...

 var results = newEmpList.Join(
      oldEmpList, 
      n => n.Name, 
      o => o.Name, 
      (n, o) => new 
       { 
        Name = n.Name, 
        Salary = n.Salary, 
        Match = o.Salary == n.Salary 
       }); 

Вы можете фильтровать это с помощью пункта Where() для Match или !Match.

Answer 5

Обновление: Я предполагаю (по заголовку вашего вопроса), что 2 списка уже отсортированы. Возможно, они хранятся в базе данных с кластеризованным индексом или что-то в этом роде. Поэтому этот ответ основывается на этом предположении.

Вот реализация, которая имеет сложность O(n), а также очень быстра, и это тоже довольно просто.
Я считаю, что это вариант Merge Algorithm.

Вот идея:

1. Start перечисляя оба списка
2. сравнить 2 текущие элементы.
3. Если они совпадают, то добавьте результаты.
   Если первый элемент «меньше», продвигайте первый список.
   Если второй элемент «меньше», продвигайте второй список.

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

var comparer = StringComparer.OrdinalIgnoreCase; 
var namesAndSalaries = new List<Tuple<Employee, Employee>>(); 
var namesOnly = new List<Tuple<Employee, Employee>>(); 

// Create 2 iterators; one for old, one for new: 
using (IEnumerator<Employee> A = oldEmployeeList.GetEnumerator()) { 
    using (IEnumerator<Employee> B = newEmployeeList.GetEnumerator()) { 
     // Start enumerating both: 
     if (A.MoveNext() && B.MoveNext()) { 
      while (true) { 
       int compared = comparer.Compare(A.Current.name, B.Current.name); 
       if (compared == 0) { 
        // Names match 
        if (A.Current.salary == B.Current.salary) { 
         namesAndSalaries.Add(Tuple.Create(A.Current, B.Current)); 
        } else { 
         namesOnly.Add(Tuple.Create(A.Current, B.Current)); 
        } 
        if (!A.MoveNext() || !B.MoveNext()) break; 
       } else if (compared == -1) { 
        // Keep searching A 
        if (!A.MoveNext()) break; 
       } else { 
        // Keep searching B 
        if (!B.MoveNext()) break; 
       } 

      } 
     } 
    } 
}