Думаю, что каждый программист рано или поздно сталкивается с кодом, который работает «не так, как ты от него ожидаешь». Именно это и подтолкнуло меня к написанию следующей статьи, в которой я пытаюсь понять, почему Except в Linq работает так, как написан, а не так, как я хочу.


Что, по вашему мнению, должен вывести следующий код:

var documentsDir = new DirectoryInfo(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments));

FileInfo[] FirstDirrectoryFiles = documentsDir.GetFiles();

FileInfo[] SecondDirrectoryFiles = documentsDir.GetFiles();

foreach (FileInfo item in FirstDirrectoryFiles.Except(SecondDirrectoryFiles))

{

Console.WriteLine(item.Name);

}

Я вот предположил, что ничего, потому что Except должен вычитать множество (IEnumerable) правого аргумента из множества (IEnumerable) левого аргумента. Однако, вопреки моим ожиданиям я получил:

Вне всякого сомнения — это не похоже на пустое множество. Давайте попробуем разобраться в том, почему так получается (результат в .NET 5 и в .NET 6 — эквивалентен). Чтобы понять, почему так происходит, и что можно с этим сделать обратимся к документации метода Except. Там действительно написано, что этот метод «Находит разность множеств, представленных двумя последовательностями» и имеет две перегрузки:

Except<TSource>(IEnumerable<TSource>, IEnumerable<TSource>)

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

Except<TSource>(IEnumerable<TSource>, IEnumerable<TSource>, IEqualityComparer<TSource>)

Находит разность множеств, представленных двумя последовательностями, используя для сравнения значений указанный компаратор IEqualityComparer<T>.

Обратите внимание на заявление о том, что для сравнения используется компаратор по умолчанию. Чтобы понять, почему наш код сработал именно так, как сработал, нам предстоит разобраться с поведением компаратора по умолчанию. Для этого я предлагаю проследовать на https://github.com/dotnet/runtime/ и проанализировать работу метода Except.

Наша точка входа:

Код на картинке
public static IEnumerable<TSource> Except<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second)
{
            if (first == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.first);
            }

            if (second == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.second);
            }

            return ExceptIterator(first, second, null);
}

Метод проверяет, что получил два объекта с ненулевым указателем и передает аргументы в ExceptIterator.

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

Код на картинке
public static IEnumerable<TSource> Except<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource>? comparer)
{
            if (first == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.first);
            }

            if (second == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.second);
            }

            return ExceptIterator(first, second, comparer);
}

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

Собственно код ExceptIterator:

Код на картинке
private static IEnumerable<TSource> ExceptIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource>? comparer)
{
            var set = new HashSet<TSource>(second, comparer);

            foreach (TSource element in first)
            {
                if (set.Add(element))
                {
                    yield return element;
                }
            }
}

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

Конструктор множества принимает интерфейс компаратора, который используется для сравнения элементов множества:  

Конкретно в нашем случае компаратор равен null, поэтому проваливаемся в свойство Default обобщенного класса EqualityComparer.

Код на картинке
public HashSet(IEqualityComparer<T>? comparer)
{
            if (comparer is not null && comparer != EqualityComparer<T>.Default) // first check for null to avoid forcing default comparer instantiation unnecessarily
            {
                _comparer = comparer;
            }

            // Special-case EqualityComparer<string>.Default, StringComparer.Ordinal, and StringComparer.OrdinalIgnoreCase.
            // We use a non-randomized comparer for improved perf, falling back to a randomized comparer if the
            // hash buckets become unbalanced.
            if (typeof(T) == typeof(string))
            {
                IEqualityComparer<string>? stringComparer = NonRandomizedStringEqualityComparer.GetStringComparer(_comparer);
                if (stringComparer is not null)
                {
                    _comparer = (IEqualityComparer<T>?)stringComparer;
                }
            }
}

Тут, на мой скромный взгляд, все очевидно:

Код на картинке
public abstract partial class EqualityComparer<T> : IEqualityComparer, IEqualityComparer<T>
{
        // To minimize generic instantiation overhead of creating the comparer per type, we keep the generic portion of the code as small
        // as possible and define most of the creation logic in a non-generic class.
        public static EqualityComparer<T> Default { [Intrinsic] get; } = (EqualityComparer<T>)ComparerHelpers.CreateDefaultEqualityComparer(typeof(T));
}

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

Давайте же посмотрим на то, как происходит процесс создания компаратора по умолчанию:

Код на картинке
internal static object CreateDefaultEqualityComparer(Type type)
{
            Debug.Assert(type != null && type is RuntimeType);

            object? result = null;
            var runtimeType = (RuntimeType)type;

            if (type == typeof(byte))
            {
                // Specialize for byte so Array.IndexOf is faster.
                result = new ByteEqualityComparer();
            }
            else if (type == typeof(string))
            {
                // Specialize for string, as EqualityComparer<string>.Default is on the startup path
                result = new GenericEqualityComparer<string>();
            }
            else if (type.IsAssignableTo(typeof(IEquatable<>).MakeGenericType(type)))
            {
                // If T implements IEquatable<T> return a GenericEqualityComparer<T>
                result = CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericEqualityComparer<string>), runtimeType);
            }
            else if (type.IsGenericType)
            {
                // Nullable does not implement IEquatable<T?> directly because that would add an extra interface call per comparison.
                // Instead, it relies on EqualityComparer<T?>.Default to specialize for nullables and do the lifted comparisons if T implements IEquatable.
                if (type.GetGenericTypeDefinition() == typeof(Nullable<>))
                {
                    result = TryCreateNullableEqualityComparer(runtimeType);
                }
            }
            else if (type.IsEnum)
            {
                // The equality comparer for enums is specialized to avoid boxing.
                result = TryCreateEnumEqualityComparer(runtimeType);
            }

            return result ?? CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ObjectEqualityComparer<object>), runtimeType);
}

Пойдем по порядку:

1.       Если тип аргумента byte, то возвращается компаратор специально для этого типа (ByteEqualityComparer)

2.       Если это строка, то возвращается GenericEqualityComparer<string>();

3.       Если тип реализует IEquatable, то на основе GenericEqualityComparer<string> возвращается GenericEqualityComparer для типа аргумента (даже не спрашивайте);

4.       Если аргумент является универсальным типом (обобщением) и если этот универсальный тип Nullable<>,  то на основе NullableEqualityComparer<int>  создается NullableEqualityComparer для типа аргумента;

5.       Если аргумент – перечисление, то на основе EnumEqualityComparer<> создается EnumEqualityComparer;

6.       Во всех остальных случаях на основе ObjectEqualityComparer<object> создается ObjectEqualityComparer.

С помощью такого нехитрого кода (хотел было переписать через string builder, но, думаю, тут можно забить :D) попробуем понять, какой же из перечисленных случаев – наш:

Код на картинке
var documentsDir = new DirectoryInfo(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments));
FileInfo[] result1 = documentsDir.GetFiles();
FileInfo[] result2 = documentsDir.GetFiles();

Type type = result1[0].GetType();
Console.Write(
    $"type == typeof(byte): {type == typeof(byte)}\n" +
    $"type == typeof(string): {type == typeof(string)}\n" +
    $"type.IsAssignableTo(typeof(IEquatable<>).MakeGenericType(type)): {type.IsAssignableTo(typeof(IEquatable<>).MakeGenericType(type))}\n" +
    $"type.IsGenericType: {type.IsGenericType}\n" +
    $"type.IsEnum: {type.IsEnum}\n\n");

Что и следовало ожидать:

 Это значит, что теперь наш путь лежит в ObjectEqualityComparer. Вот, собственно, и он:

Код на картинке
public sealed partial class ObjectEqualityComparer<T> : EqualityComparer<T>
{
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public override bool Equals(T? x, T? y)
        {
            if (x != null)
            {
                if (y != null) return x.Equals(y);
                return false;
            }
            if (y != null) return false;
            return true;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public override int GetHashCode([DisallowNull] T obj) => obj?.GetHashCode() ?? 0;

        // Equals method for the comparer itself.
        public override bool Equals([NotNullWhen(true)] object? obj) =>
            obj != null && GetType() == obj.GetType();

        public override int GetHashCode() =>
            GetType().GetHashCode();
}

ObjectEqualityComparer определяет метод Equals для двух объектов следующим образом:

·         Объекты равны, если они оба null (что логично);

·         Объекты не равны, если только один из них null;

·         Если оба объекта не null, то их эквивалентность определяется методом Equals «левого» аргумента.

Если обратиться к документации, то можно увидеть, что у нашего класса FileInfo действительно есть метод Equals с пометкой «Унаследовано от Object». Что же, туда и лежит наш путь! Там в секции «комментарии» мы можем узнать, что:

Если текущий экземпляр является ссылочным типом, Equals(Object) метод проверяет равенство ссылок, а вызов Equals(Object) метода эквивалентен вызову ReferenceEquals метода. Равенство ссылок означает, что сравниваемые объектные переменные ссылаются на один и тот же объект.

На этом, казалось, можно было бы завершить наше путешествие, но давайте на последок придумаем, как заставить Except перестать показывать файлы в директории с моими документами.

Вариант из категории «пока так, потом пофикшу»:

Код на картинке
var documentsDir = new DirectoryInfo(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments));
FileInfo[] result1 = documentsDir.GetFiles();
FileInfo[] result2 = documentsDir.GetFiles();
foreach (FileInfo item in result1
                                 .Select(i => i.FullName)
                                 .Except(result2.Select(i => i.FullName))
                                 .Select(i => new FileInfo(i)))
{
    Console.WriteLine(item.Name);
}

Мы, по сути, вызываем Except для двух IEnumerate<string>, а потом из результата снова собираем IEnumerate<FileInfo>.

В свежем .net6 еще можно воспользоваться ExceptBy:

Код на картинке
var documentsDir = new DirectoryInfo(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments));
FileInfo[] result1 = documentsDir.GetFiles();
FileInfo[] result2 = documentsDir.GetFiles();
foreach (FileInfo item in result1.ExceptBy(result2.Select(i => i.FullName), ks => ks.FullName))
{
    Console.WriteLine(item.Name);
}

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

Следующей идеей, посетившей мою голову, было унаследовать FileInfo и переопределить Equals, но, к сожалению, FileInfo является запечатанным (sealed) классом, а это значит, что он не может быть унаследован, так что этот путь нам отрезан.

Подойдем к вопросу с другой стороны. Вспомним, что Equals имеет перегрузку, принимающую вторым аргументом IEqualityComparer, что позволяет нам создать что-то вроде такого решения:

var documentsDir = new DirectoryInfo(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments));
FileInfo[] result1 = documentsDir.GetFiles();
FileInfo[] result2 = documentsDir.GetFiles();

foreach (FileInfo item in result1.Except(result2, new CustomFileInfoComparer()))
{
    Console.WriteLine(item.Name);
}

public class CustomFileInfoComparer : IEqualityComparer<FileInfo>
{
    bool IEqualityComparer<FileInfo>.Equals(FileInfo? lhv, FileInfo? rhv)
       => lhv?.FullName == rhv?.FullName;
    int IEqualityComparer<FileInfo>.GetHashCode(FileInfo obj) => obj.FullName.GetHashCode();
}

Это решение хорошо подходит в том случае, если дальше по коду вам предстоит еще хотя бы раз сравнивать IEnumerable<FileInfo>.

На этом у меня все, надеюсь, что читатель нашел любопытным мой скромный труд.

Хочется выразить огромную благодарность моей жене за помощь в подготовке данного поста, а также сообществу .NET Talks????

Комментарии (25)


  1. Radiosterne
    20.11.2021 17:37
    +38

    Сократил эту статью до двух предложений:

    Почему я ожидал, что A.Except(B) вернёт пустое множество, а вернулись элементы первой коллекции?

    Потому что я не открыл MSDN, не выяснил смысл термина «ссылочный тип», и не знаю, как по умолчанию сравниваются объекты ссылочных типов.


    1. slepmog
      20.11.2021 18:41
      +5

      Причём поддерживается саспенс: с первых строк возникает ощущение, что в результирующую коллекцию попали только некоторые из множества файлов в "Моих документах", а статья посвящена тому, что инстансы FileInfo иногда новые, а иногда кешированные.
      Финальное разочарование от этого усиливается.


    1. AgentFire
      20.11.2021 21:54
      +5

      Я бы чуть по-другому перефомулировал:

      "Потому что FileInfo не умеет в сравнение".

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


  1. Brom95 Автор
    20.11.2021 18:02
    -2

    Я вас услышал, в следующий раз я буду более тщательно выбирать макгаффин для своей истории. Было бы здорово услышать ваше мнение о том, как ещё можно было бы сделать пост лучше и интереснее, чтобы я мог повысить свой навык письма.


    1. dopusteam
      20.11.2021 18:15
      +12

      Вы промахнулись с ответом, под комментарием есть кнопка 'Ответить'

      Чтоб сделать пост лучше и интереснее, нужна интересная тема

      Это статья от человека, который только начал изучать язык и решил поделиться своим открытием, и которая бесполезна для более менее опытных людей


    1. Radiosterne
      20.11.2021 18:27
      +13

      Полагаю, что это ответ мне, поэтому изложу свои мысли здесь.

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

      Смотрите, я полагаю, что этот пост несёт некоторую педагогическую нагрузку, то есть призван обучить людей чему-то. Припоминая известную цитату, людей, по моему мнению, надо обучать ловле рыбы, а не давать им конкретную рыбу.

      Так вот, предположим, что я начинающий .NET-девелопер. Я прочёл эту статью, и теперь знаю, как ExceptIterator сранивает объекты (Вам плюсик, умение читать исходный код фреймворка — полезная вещь).

      Возникают вопросы:

      1) Распространяются ли мои знания на код X.Where(xItem => Y.All(yItem => xItem != yItem)) ?
      2) Правильно ли я понял, что лучший способ получить ответы на мои вопросы — пойти закопаться в код фреймворка?

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

      Поэтому я считаю, что для начинающих разработчиков Ваша статья не полезна, а, наоборот, вредна.

      Для остальных она, полагаю, не несёт новой информации.

      Отдельно по поводу оформления: все картинки нечитаемы при увеличении.


  1. agim-gal
    20.11.2021 19:01

    Было бы более интересно узнать, почему этот метод пересчитывает хеш сравниваемых объектов каждый раз заново и не кеширует внутри себя. Как то раз, я начал кешировать хеш внутри объекта и уменьшил время работы функции с часа до 20 секунд. Не знал эту фишку, думал это очевидно, что во время Except объекты в коллекций изменяться не будут и значит их хеш не будет изменяться, значит его можно сохранить и не считать заново каждый раз.


    1. dopusteam
      20.11.2021 19:06
      -1

      Надолго кэшировать?

      Он не знает про операцию выполняемую, очевидно.

      Хэш принято считать от неизменяемых полей

       Как то раз, я начал кешировать хеш внутри объекта и уменьшил время работы функции с часа до 20 секунд

      Выглядит так, будто Вы костыль впилили вместо нормального решения


  1. lair
    20.11.2021 19:48
    +3

    Очень грустно, что вы не знаете, что для всех действий, предполагающих сравнение объектов (а не примитивов), надо первым делом смотреть на компареры. Делаем хэшсет? Смотрим на компарер. Делаем словарь, где объект в ключе? Смотрим на компарер.


  1. Naf2000
    20.11.2021 20:39
    +1

    Дело не в Except и не в Union. Дело реально в реализации компарера, как и написали выше. Акцент в статье не там.


    1. Brom95 Автор
      21.11.2021 12:31

      Вы все абсолютно правы, я настолько сильно сконцентрировался на конкретном примере, что совершенно забыл упомянуть, что это общее правило, а не частный случай.


  1. Ascar
    21.11.2021 05:34
    -1

                var documentsDir = new DirectoryInfo(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments));
    
                var FirstDirrectoryFiles = documentsDir.GetFiles().Select(a=> a.Name);
    
                var SecondDirrectoryFiles = documentsDir.GetFiles().Select(a => a.Name);
    
                foreach (var item in FirstDirrectoryFiles.Except(SecondDirrectoryFiles))
                    Console.WriteLine(item);


    1. Brom95 Автор
      21.11.2021 08:39
      -2

      Это во-первых: https://docs.microsoft.com/en-us/dotnet/csharp/fundamentals/coding-style/coding-conventions#implicitly-typed-local-variables

      А во-вторых, это буквально тоже самое, что и код в статье


      1. dopusteam
        21.11.2021 09:48

        Не воспринимайте слишком серьёзно рекомендации майков, они сами не всегда их соблюдают.

        На практике явное указание типов, по моему опыту, используется крайне редко


        1. Brom95 Автор
          21.11.2021 09:56
          -1

          Тут за неявным указанием типов спрятали то, что на выходе у нас IEnumerable<string>, а не IEnumerable<FileInfo>. Да и в целом, как по мне, эти рекомендации не про то, что var зло и его не надо использовать, а про то, что он не должен усложнять понимание кода. Это скорее ближе к питоновскому "Явное лучше неявного".


          1. dopusteam
            21.11.2021 10:00
            +1

            Select(file => file.Name)

            Достаточно информативно. Разве что сама переменная названа неправильно, FirstDirrectoryFiles


            1. Brom95 Автор
              21.11.2021 10:21

              Предлагаю сойтись на том, что это вкусовщина, а оригинальный комментарий просто чуть иначе изложил мой код из поста :D


      1. Ascar
        21.11.2021 17:14

        Вас сильно удивит результат "того же самого" кода.


        1. Brom95 Автор
          21.11.2021 17:26

          var documentsDir = new DirectoryInfo(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments));
          FileInfo[] result1 = documentsDir.GetFiles();
          FileInfo[] result2 = documentsDir.GetFiles();
          foreach (FileInfo item in result1
                                           .Select(i => i.FullName)
                                           .Except(result2.Select(i => i.FullName))
                                           .Select(i => new FileInfo(i)))
          {
              Console.WriteLine(item.Name);
          }

          Вот вам код из статьи. Ваш отличается лишь тем, что вы вынесли Select чуть выше по коду. Быть может вы просто не заметили его из-за того, что он спрятан в спойлере почти в конце поста.


          1. Ascar
            21.11.2021 17:34
            -1

            Сравните не с этим кодом, а с тем что постили в самом начале статьи.


            1. Brom95 Автор
              21.11.2021 17:39

              Так статья и посвящена тому, почему тот вариант не работает, а в конце приведены три рабочих варианта.


              1. Ascar
                21.11.2021 17:47
                -1

                Я подправил ваш код так как бы вы хотели, как бы он работал. Дальше читать статью смысла не было. Если вы сами поняли свою ошибку, то стоило вообще удалить эту статью, так как она бессмысленна и строится из-за изначального непонимания как сравниваются элементы.


                1. alexalok
                  25.11.2021 20:21

                  Автор и без вас в статье показал работающий вариант своего кода. Всё-таки перед комментированием статьи следует хотя бы вскользь ее прочитать.


              1. Ascar
                21.11.2021 17:52
                -1

                Я вот предположил, что ничего, потому что Except должен вычитать множество (IEnumerable) правого аргумента из множества (IEnumerable) левого аргумента. Однако, вопреки моим ожиданиям я получил:

                Видимо, только вы один предположили это.


  1. ImmortalCAT
    22.11.2021 08:17

    all my friends are toxic (c) BoyWithUke - Toxic