Нужна помощь в понимании неожиданного поведения с помощью LINQ Join с HashSet <T> - PullRequest
Новая
       12

Нужна помощь в понимании неожиданного поведения с помощью LINQ Join с HashSet <T>

0 голосов
/ 03 января 2019

Я столкнулся с некоторым странным поведением при использовании C # HastSet с методом LINQ Join, которое я не понимаю.Я упростил то, что я делаю, чтобы сосредоточиться на поведении, которое я вижу.

У меня есть следующее: 

 private HashSet<MyClass> _mySet; // module level

 IEnumerable<ISearchKey> searchKeys; // parameter.
 // Partial key searches are allowed.

 private IEqualityComparer<ICoreKey> _coreKeyComparer; // Module level.
 // Compares instances of MyClass and ISearchKey to determine 
 // if they match.

Учитывая, что

  1. Между searchKeys и _mySet существует отношение 1-ко-многим.
  2. MyClass реализует интерфейс IPartialKey и ICoreKey.
  3. ISearchKey наследуется от IPartialKey и ICoreKey.
  4. Экземпляр MyClass и ISearchKey оба переопределяют метод GetHashCode.
  5. Значение хеш-кода MyClass основано на его полном значении ключа, которое включает значения ICoreKey и IPartialKey и другие поля.
  6. Полные ключи, используемые MyClass, не являются уникальными.Два разных экземпляра MyClass могут иметь одинаковый хеш-код.
  7. Значение хеш-кода ISearchKey основано только на его значениях ICoreKey и IPartialKey.т.е. хеш-код ISearchKey может отличаться от хеш-кода для соответствующего экземпляра MyClass.(Примечание: в случае, когда я впервые столкнулся с проблемой, значения IPartialKey ISearchKey соответствуют полному ключу MyClass, поэтому методы GetHashCode возвращают одинаковое значение для ISearchKey и MyClass. Я включил дополнительную сложность, чтобы лучше проиллюстрировать основную логикуо том, что я делаю.)
  8. Метод _coreKeyComparer.GetHashCode возвращает одно и то же значение для соответствующих экземпляров ISearchKey и MyClass, используя только их значения ICoreKey.
  9. Метод _coreKeyComparer.Equals приводит параметры кMyClass и ISearchKey соответственно и возвращает true, если их значения IPartialKey совпадают.(Примечание: _coreKeyComparer был тяжело протестирован и работает правильно.)

Я ожидал, что объединение двух коллекций должно привести к чему-то вроде: 

{searchKey_a, myClass_a1},
{searchKey_a, myClass_a2},
{searchKey_a, myClass_a3},
{searchKey_b, myClass_b1},
{searchKey_b, myClass_b2},
{searchKey_c, myClass_c1},
{searchKey_c, myClass_c2},
{searchKey_c, myClass_c3},
{searchKey_c, myClass_c4},
etc....

т.е. тот же ISearchKeyэкземпляр будет происходить несколько раз, по одному разу для каждого соответствующего экземпляра MyClass, к которому он присоединен.

Но когда я выполняю объединение с searchKeys на _mySet: 

        var matchedPairs = searchKeys
          .Join(
            _mySet,
            searchKey => searchKey,
            myClass => myClass,
            (searchKey, myClass) => new {searchKey, myClass},
            _coreKeyComparer)
            .ToList();

, я получаю только один экземпляр MyClass наэкземпляр searchKeyClass.то есть коллекция matchedPairs выглядит следующим образом: 

    {searchKey_a, myClass_a1},
    {searchKey_b, myClass_b1},
    {searchKey_c, myClass_c1},
etc....

Однако если я переверну объединение, перейдем от _mySet к searchKeys: 

   var matchedPairs = _mySet
          .Join(
            searchKeys,
            myClass => myClass,
            searchKey => searchKey,
            (myClass, searchKey) => new {searchKey, myClass},
            _coreKeyComparer)
            .ToList();

Я получу правильную коллекцию matchedPairs.Все соответствующие записи из _mySet возвращаются вместе с searchKey, с которым они сопоставлены.

Я проверил документацию и изучил несколько примеров и не вижу причин, по которым соединение searchKeys-to-_mySet дает неправильный ответ, а _mySet-to-searchKeys дает правильный / другой ответ.

(Примечание: я также пытался использовать GroupJoin из searchKeys в _myset и сравнивать результаты. То есть каждый экземпляр searchKeyClass нашел не более одного результата из _mySet.)

Либо я не понимаю, какПредполагается, что метод Join работает, или Join работает с HashSet иначе, чем с List или другим типом коллекции.

Если первое, мне нужно разъяснение, чтобы я не допустил ошибок при использовании Join в будущем.

Если второе, то это другое поведение - ошибка .Net, или этоправильное поведение с HashSet?

Предполагая, что поведение правильное, я был бы очень признателен, если бы кто-то объяснил основную логику этого (неожиданного) поведения Join / HashSet.

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

1 Ответ

0 голосов
/ 03 января 2019

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

Предполагая поведениеправильно, я был бы очень признателен, если бы кто-то объяснил основную логику этого (неожиданного) поведения Join / HashSet.

Поскольку я не знаю, что такое непредвиденное поведение, я не могу сказать, почему это происходит.Однако я могу точно сказать, что делает Join, и, возможно, это поможет.

Join принимает следующее:

  • «Внешняя» коллекция - получательJoin.
  • «Внутренняя» коллекция - первый аргумент метода расширения
  • Два экстрактора ключей, которые извлекают ключ из внешней и внутренней коллекций
  • Проекция, которая берет член внутренней и внешней коллекций, ключи которых совпадают, и выдает результат для этого соответствия
  • Операция сравнения, которая сравнивает два ключа на равенство.

Воткак работает Join(Это логически , что происходит; фактические детали реализации несколько оптимизированы.)

Сначала мы перебираем «внутреннюю» коллекцию, ровно один раз.

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

Таким образом, теперь у нас есть поиск от TKey до IEnumerable<TInner>.

Во-вторых, мы перебираем «внешнюю» коллекцию ровно один раз.

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

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

То есть Join ведет себя так же, как эта реализация псевдокода: 

static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult>
  (IEnumerable<TOuter> outer, 
  IEnumerable<TInner> inner, 
  Func<TOuter, TKey> outerKeySelector, 
  Func<TInner, TKey> innerKeySelector, 
  Func<TOuter, TInner, TResult> resultSelector, 
  IEqualityComparer<TKey> comparer) 
{
  var lookup = new SomeMultiDictionary<TKey, TInner>(comparer);
  foreach(TInner innerItem in inner)
  {
    TKey innerKey = innerKeySelector(innerItem);
    lookup.Add(innerItem, innerKey);
  }
  foreach (TOuter outerItem in outer) 
  {
    TKey outerKey = outerKeySelector(outerItem);
    foreach(TInner innerItem in lookup[outerKey])
    {
      TResult result = resultSelector(outerItem, innerItem);
      yield return result;
    }
  }
}

Некоторые предложения:

  • Замените все ваши GetHashCode реализации, чтобы они возвращались 0 и запустите все свои тесты.Они должны пройти! Всегда допустимо возвращать ноль с GetHashCode. Это почти наверняка разрушит вашу производительность , но не должно нарушить вашу правильность .Если вы находитесь в ситуации, когда вам требуется конкретное ненулевое значение GetHashCode, то у вас есть ошибка.
  • Проверьте правильность сравнения ключей.Он должен подчиняться трем правилам равенства: (1) рефлексивность: вещь всегда равна себе, (2) симметрия: равенство A и B должно совпадать с B и A, (3) транзитивность: если A равно B и B равно C, тогда A должно равняться C.Если эти правила не соблюдаются, то Join может вести себя странно.

  • Замените ваш Join на SelectMany и Where.То есть:

    from o in outer join i in inner on getOuterKey(o) equals getInnerKey(i) select getResult(o, i)

можно переписать как 

from o in outer
from i in inner
where keyEquality(getOuterKey(o), getInnerKey(i))
select getResult(o, i)

Этот запрос на медленнее , чем соединениеверсия, но она логически точно такая же.Опять же, запустите ваши тесты.Вы получаете тот же результат?Если нет, у вас есть ошибка где-то в вашей логике .

Опять же, я не могу особо подчеркнуть, что ваше отношение к «Соединению, вероятно, нарушено, если дана хеш-таблица», является тем, что удерживаетВы вернулись от поиска вашей ошибки.Регистрация не нарушена.Этот код не изменился за десятилетие, он очень прост, и это было правильно, когда мы написали его в первый раз.Гораздо более вероятно, что ваша сложная и загадочная логика сравнения ключей где-то нарушена.

...