Сохраняет ли метод C # Distinct () исходный порядок последовательности? - PullRequest
70 голосов
/ 19 января 2011

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

Джон Скит и другие предложили использовать следующие

list = list.Distinct().ToList();

удаление дубликатов из списка C #

Удалить дубликаты из списка в C #

Гарантируется ли, что порядок уникальных элементов будет таким же, как и раньше? Если да, пожалуйста, дайте ссылку, подтверждающую это, поскольку я не смог найти ничего в документации.

Ответы [ 6 ]

62 голосов
/ 19 января 2011

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

Возможно, вы захотите прочитать мой блог о реализации Edulinq функции Distinct () .

Обратите внимание, что даже если бы это было гарантировано для LINQ to Objects (что лично мне кажется должно быть), это ничего бы не значило для других поставщиков LINQ, таких как LINQ to SQL.

Уровень гарантий, предоставляемых в LINQ to Objects, иногда немного противоречив, IMO. Некоторые оптимизации задокументированы, другие нет. Черт, некоторая документация не совсем понятна неправильно .

25 голосов
/ 19 января 2011

Да, в порядке первого появления в исходном списке. гарантировано для .Net Framework 3.5

Я провел небольшое исследование с помощью Reflector.После дизассемблирования System.Core.dll, Version = 3.5.0.0, вы можете увидеть, что Distinct () является методом расширения, который выглядит следующим образом:

public static class Emunmerable
{
    public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source)
    {
        if (source == null)
            throw new ArgumentNullException("source");

        return DistinctIterator<TSource>(source, null);
    }
}

Итак, интересным является DistinctIterator, который реализует IEnumerable иIEnumerator.Вот упрощенная (с удалением goto и lables) реализация этого IEnumerator:

private sealed class DistinctIterator<TSource> : IEnumerable<TSource>, IEnumerable, IEnumerator<TSource>, IEnumerator, IDisposable
{
    private bool _enumeratingStarted;
    private IEnumerator<TSource> _sourceListEnumerator;
    public IEnumerable<TSource> _source;
    private HashSet<TSource> _hashSet;    
    private TSource _current;

    private bool MoveNext()
    {
        if (!_enumeratingStarted)
        {
            _sourceListEnumerator = _source.GetEnumerator();
            _hashSet = new HashSet<TSource>();
            _enumeratingStarted = true;
        }

        while(_sourceListEnumerator.MoveNext())
        {
            TSource element = _sourceListEnumerator.Current;

             if (!_hashSet.Add(element))
                 continue;

             _current = element;
             return true;
        }

        return false;
    }

    void IEnumerator.Reset()
    {
        throw new NotSupportedException();
    }

    TSource IEnumerator<TSource>.Current
    {
        get { return _current; }
    }

    object IEnumerator.Current
    {        
        get { return _current; }
    }
}

Как вы можете видеть - перечисление идет в порядке, указанном в источнике enumerable (список, по которому мы называем Distinct).Hashset используется только для определения, вернули ли мы уже такой элемент или нет.Если нет, мы его возвращаем, иначе - продолжаем перечисление по источнику.

Таким образом, гарантируется, что Distinct () будет возвращать элементы точно в том же порядке , которые предоставляются коллекцией, к которой был применен Distinct.

11 голосов
/ 19 января 2011

Согласно документации последовательность неупорядочена.

4 голосов
/ 24 ноября 2017

Да , Enumerable.Distinct сохраняет порядок. Предполагая, что метод является ленивым «дает различные значения, как только они видны», это следует автоматически. Подумай об этом.

Источник .NET Reference подтверждает. Он возвращает подпоследовательность, первый элемент в каждом классе эквивалентности.

foreach (TSource element in source)
    if (set.Add(element)) yield return element;

Реализация .NET Core аналогична.

К сожалению, документация для Enumerable.Distinct запуталась в этом вопросе:

Последовательность результатов неупорядочена.

Я могу только представить, что они означают "последовательность результатов не отсортирована". Вы могли бы реализовать Distinct, предварительно отсортировав и сравнив каждый элемент с предыдущим, но это не будет ленивым, как определено выше.

1 голос
/ 24 марта 2017

По умолчанию при использовании оператора Distinct linq используется метод Equals, но вы можете использовать свой собственный объект IEqualityComparer<T>, чтобы указать, когда два объекта равны, с помощью пользовательской логики, реализующей метод GetHashCode и Equals.Помните, что:

GetHashCode не следует использовать тяжелое сравнение с процессором (например, использовать только некоторые очевидные базовые проверки) и использовать его в качестве первого, чтобы указать, что два объекта наверняка различны (если возвращен другой хэш-код) илипотенциально то же самое (тот же хэш-код).В этом последнем случае, когда два объекта имеют одинаковый хэш-код, платформа будет проверять, используя метод Equals, как окончательное решение о равенстве заданных объектов.

После того, как у вас есть классы MyType и MyTypeEqualityComparerКод не гарантирует, что последовательность поддерживает свой порядок:

var cmp = new MyTypeEqualityComparer();
var lst = new List<MyType>();
// add some to lst
var q = lst.Distinct(cmp);

Далее sci library Я реализовал метод расширения, чтобы убедиться, что набор Vector3D поддерживает порядок при использовании определенного метода расширения DistinctKeepOrder:

соответствующий код выглядит следующим образом:

/// <summary>
/// support class for DistinctKeepOrder extension
/// </summary>
public class Vector3DWithOrder
{
    public int Order { get; private set; }
    public Vector3D Vector { get; private set; }
    public Vector3DWithOrder(Vector3D v, int order)
    {
        Vector = v;
        Order = order;
    }
}

public class Vector3DWithOrderEqualityComparer : IEqualityComparer<Vector3DWithOrder>
{
    Vector3DEqualityComparer cmp;

    public Vector3DWithOrderEqualityComparer(Vector3DEqualityComparer _cmp)
    {
        cmp = _cmp;
    }

    public bool Equals(Vector3DWithOrder x, Vector3DWithOrder y)
    {
        return cmp.Equals(x.Vector, y.Vector);
    }

    public int GetHashCode(Vector3DWithOrder obj)
    {
        return cmp.GetHashCode(obj.Vector);
    }
}

Вкратце Vector3DWithOrder инкапсулирует тип и целое число заказа, тогда как Vector3DWithOrderEqualityComparer инкапсулирует оригинальный компаратор типа.

, и этовспомогательный метод для обеспечения порядка

/// <summary>
/// retrieve distinct of given vector set ensuring to maintain given order
/// </summary>        
public static IEnumerable<Vector3D> DistinctKeepOrder(this IEnumerable<Vector3D> vectors, Vector3DEqualityComparer cmp)
{
    var ocmp = new Vector3DWithOrderEqualityComparer(cmp);

    return vectors
        .Select((w, i) => new Vector3DWithOrder(w, i))
        .Distinct(ocmp)
        .OrderBy(w => w.Order)
        .Select(w => w.Vector);
}

Примечание : дальнейшие исследования могут позволить найти более общий (использование интерфейсов) и оптимизированный способ (без инкапсуляции объекта).

0 голосов
/ 02 августа 2018

Это сильно зависит от вашего linq-провайдера.В Linq2Objects вы можете остаться на внутреннем исходном коде для Distinct, что позволяет предположить, что исходный порядок сохранен.

Однако для других поставщиков, которые разрешают, например, какой-то SQL, это неОбязательно, так как ORDER BY -статус обычно приходит после любой агрегации (такой как Distinct).Таким образом, если ваш код такой:

myArray.OrderBy(x => anothercol).GroupBy(x => y.mycol);

, это переводится в нечто похожее на следующее в SQL:

SELECT * FROM mytable GROUP BY mycol ORDER BY anothercol;

Это, очевидно, сначала группирует ваши данные, а затем сортирует.Теперь вы застряли на собственной логике СУБД, как выполнить это.На некоторых СУБД это даже не разрешено.Представьте себе следующие данные:

mycol anothercol
1     2
1     1
1     3
2     1
2     3

при выполнении myArr.OrderBy(x => x.anothercol).GroupBy(x => x.mycol) мы предполагаем следующий результат:

mycol anothercol
1     1
2     1

Но СУБД может агрегировать другой столбец colcol таким образом, чтобы значениеиспользуется первая строка, в результате чего получаются следующие данные:

mycol anothercol
1    2
2    1

, что после заказа приведет к следующему:

mycol anothercol
2    1
1    2

Это похоже на следующее:

SELECT mycol, First(anothercol) from mytable group by mycol order by anothercol;

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

Вы видите, что план выполнения может отличаться в зависимости от того, кто является основным поставщиком.Вот почему нет никаких гарантий по этому поводу в документации.

...