Самый эффективный способ удаления дубликатов из списка

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

List<int> myList = new List<int>(Enumerable.Range(0, 10000));

// adding a few duplicates here
myList.Add(1); 
myList.Add(2);
myList.Add(3);

Я нашел 3 подхода для решения этой проблемы:

List<int> result1 = new HashSet<int>(myList).ToList(); //3700 ticks
List<int> result2 = myList.Distinct().ToList(); //4700 ticks
List<int> result3 = myList.GroupBy(x => x).Select(grp => grp.First()).ToList(); //18800 ticks
//referring to pinturic comment:
List<int> result4 = new SortedSet<int>(myList).ToList(); //18000 ticks

В большинстве ответов здесь, в SO, подход Отличный показан как "правильный", но HashSet всегда быстрее!

Мой вопрос: есть ли что-нибудь, о чем я должен знать, когда я использую подход HashSet и есть ли еще более эффективный способ?

Ответы

Ответ 1

Существует большая разница между этими двумя подходами:

List<int> Result1 = new HashSet<int>(myList).ToList(); //3700 ticks
List<int> Result2 = myList.Distinct().ToList(); //4700 ticks

Первый может (возможно,) изменить порядок элементов возвращаемых элементов List<>: Result1 не будет в том же порядке, что и myList. Второй сохраняет исходный порядок.

Вероятно, нет более быстрого способа, чем первый.

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

(третий похож на второй, только медленнее)

Просто из любопытства, Distinct():

// Reference source http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,712
public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source) {
    if (source == null) throw Error.ArgumentNull("source");
    return DistinctIterator<TSource>(source, null);
}

// Reference source http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,722
static IEnumerable<TSource> DistinctIterator<TSource>(IEnumerable<TSource> source, IEqualityComparer<TSource> comparer) {
    Set<TSource> set = new Set<TSource>(comparer);
    foreach (TSource element in source)
        if (set.Add(element)) yield return element;
}

Итак, в конце Distinct() просто используется внутренняя реализация HashSet<> (называемая Set<>) для проверки уникальности элементов.

Для полноты я добавлю ссылку на вопрос Не сохраняет ли метод С# Distinct() первоначальный порядок последовательности?