C# Удаление дубликатов из списка, содержащего список

Question

Скажем, у нас есть список «А студенты» и список «B студентов». Затем мы добавляем оба списка в более общий список, называемый «студенты». Затем кто-то решает усложнить жизнь, добавив дублированный список «A Students» в общий список «учеников». Какой самый эффективный способ удалить один из дубликатов списков «А студенты»? Обратите внимание, что есть два пользовательских класса.

Общий список студентов в коде называется lstStudents. Это список, из которого я хотел бы удалить любые дубликаты.

(я пытался придумать более удачный пример, но это лучшее, что я мог бы сделать прямо сейчас.)

Я не использовать LINQ, но она доступна. ПодробнееLinq доступен.

Вот мои классы:

public class Student 
{ 
    public Student(string _name, int _age, Exam _lastExam) 
    { 
     name = _name; 
     age = _age; 
     lastExam = _lastExam; 
    } 

    public string name { get; set; } 
    public int age { get; set; } 
    public Exam lastExam { get; set; } 
} 

public class Exam 
{ 
    public Exam(int _correct, int _possible) 
    { 
     correct = _correct; 
     possible = _possible; 
    } 

    public int correct { get; set; } 
    public int possible { get; set; } 
} 

А вот код, чтобы создать беспорядок:

List<List<Student>> lstStudents = new List<List<Student>>(); 
List<Student> lstAStudents = new List<Student>(); 
List<Student> lstDuplicateAStudents = new List<Student>(); 
List<Student> lstBStudents = new List<Student>(); 

// Create a list of some A students 
lstAStudents.Add(new Student("Alex", 14, new Exam(98,100))); 
lstAStudents.Add(new Student("Kim", 13, new Exam(96, 100))); 
lstAStudents.Add(new Student("Brian", 14, new Exam(92, 100))); 
lstStudents.Add(lstAStudents); 

// Create a duplicate list of A students 
lstDuplicateAStudents.Add(new Student("Alex", 14, new Exam(98, 100))); 
lstDuplicateAStudents.Add(new Student("Kim", 13, new Exam(96, 100))); 
lstDuplicateAStudents.Add(new Student("Brian", 14, new Exam(92, 100))); 
lstStudents.Add(lstDuplicateAStudents); 

// Create a list of some B students 
lstBStudents.Add(new Student("John", 13, new Exam(88, 100))); 
lstBStudents.Add(new Student("Jenny", 13, new Exam(80, 100))); 
lstBStudents.Add(new Student("Jamie", 15, new Exam(81, 100))); 
lstStudents.Add(lstBStudents); 

Answer 1

Вы можете использовать IEquatable<T> как для Student и Exam:

public class Student: IEquatable<Student> 
{ 
    ... 

    public bool Equals(Student other) 
    { 
     return name == other.name && age == other.age 
        && lastExam.Equals(other.lastExam); 
    } 

    public override bool Equals(object obj) 
    { 
     Student student = obj as Student; 
     return Equals(student); 
    } 

    public override int GetHashCode() 
    { 
     return name.GetHashCode()^
      age.GetHashCode()^lastExam.GetHashCode(); 
    } 
} 

Для Exam:

public class Exam: IEquatable<Exam> 
{ 
    ... 

    public bool Equals(Exam exam) 
    { 
     return exam.correct == correct && exam.possible == possible; 
    } 

    public override bool Equals(object obj) 
    { 
     Exam exam = obj as Exam; 
     return Equals(exam); 
    } 

    public override int GetHashCode() 
    { 
     return correct.GetHashCode()^possible.GetHashCode(); 
    } 
} 

Затем построить обычай IQualityComparer<T> для List<Student>:

public class StudentListComparer : IEqualityComparer<List<Student>> 
{ 
    public bool Equals(List<Student> x, List<Student> y) 
    { 
     return x.OrderBy(a => a.name) 
       .SequenceEqual(y.OrderBy(b => b.name)); 
    } 

    public int GetHashCode(List<Student> obj) 
    { 
     return obj.Aggregate(0, (current, t) => current^t.GetHashCode()); 
    } 
} 

Тогда вам можно Distinct, чтобы получить результат:

Answer 2

Возможно, вы можете провести набор, который будет аккумулировать уникальные списки:

var set = new HashSet<List<Student>>(new CustomComparer()); 
foreach (List<List<Student>> list in source) 
{ 
    if (set.Contains(list)) 
    continue; 
    set.Add(list) 
} 


public class CustomComparer : IEqualityComparer<List<Student>> 
{ 
    public bool Equals(List<Student> one, List<Student> two) 
    { 
    if (one.Count != two.Count) return false; 

    // simplest possible code to compare two lists 
    // warning: runs in O(N*logN) for each compare 
    return one.OrderBy(s=>s).SequenceEqual(two.OrderBy(s=>s)); 
    } 

    public int GetHashCodeList<Student> item) 
    { 
    int ret = -1; 
    foreach (var s in item) 
     ret ^= s.GetHashCode(); 
    return ret; 
    } 
} 

Основная проблема с этим решением - это код, который используется для сравнения двух списков < >. Являются ли списки, содержащие одинаковые элементы в разном порядке, равными? Если да, нам нужно либо изменить порядок, предварительно отсортировав каждый список (чтобы сэкономить время на сравнение), либо отсортировать каждый раз копию каждого списка, что потребует дополнительного времени. Поэтому, я думаю, главный вопрос в том, насколько велики ваши списки. Для значений ниже 1000 учеников/100 списков проблем с производительностью не должно быть заметно.

Другая проблема - реализация GetHashCode - это O (N), и мы не можем кэшировать рассчитанное значение, поскольку List является структурой структуры. Чтобы обойти это, я бы предложил ввести класс StudentList, который будет иметь сопоставитель (на данный момент мы должны указать его извне) и получить хэш-код с кешированием.

Кроме того, существует лучшая реализация generic collection equivalence comparer.