Как работает метод except в linq

У меня есть классы:

class SomeClass
{
   public string Name{get;set;}
   public int SomeInt{get;set;}
}


class SomeComparison: IEqualityComparer<SomeClass>
{
     public bool Equals(SomeClass s, SomeClass d)
     {
         return s.Name == d.Name;
     }

     public int GetHashCode(SomeClass a)
     {
         return (a.Name.GetHashCode() * 251);
     }
}

У меня также есть два больших List<SomeClass>, называемых list1 и list2

прежде чем я использовал:

 var q = (from a in list1
         from b in list2
         where a.Name != b.Name
         select a).ToList();

и это заняло около 1 минуты. Теперь у меня есть:

var q =  list1.Except(list2,new SomeComparison()).ToList();

и это занимает менее 1 секунды!

Я хотел бы понять, что делает метод Except. Создает ли метод хэш-таблицу каждого списка, а затем выполняет одно и то же сравнение? Если я буду выполнять много этих сравнений, я должен создать Hashtable вместо этого?

ИЗМЕНИТЬ

Теперь вместо списков у меня есть два HashSet<SomeClass>, называемый hashSet1 и hashSet2

когда я это сделаю:

   var q = (from a in hashSet1
           form b in hashSet2
           where a.Name != b.Name
           select a).ToList();

который все еще занимает много времени... Что я делаю неправильно?

Ответ 1

Ваша догадка близка - метод расширения Linq to Objects Except использует внутреннюю часть HashSet<T> для второй переданной последовательности, что позволяет ей искать элементы в O (1), итерации по первой последовательности для фильтрации из которых заключены во второй последовательности, следовательно, общее усилие равно O (n + m), где n и m - длина входных последовательностей - это лучшее, что вы можете надеяться сделать, так как вы должны смотреть на каждый элемент хотя бы один раз.

Для обзора того, как это может быть реализовано, я рекомендую серию Jon Skeet EduLinq, здесь часть ее реализации Except и ссылку на полная глава:

private static IEnumerable<TSource> ExceptImpl<TSource>(
    IEnumerable<TSource> first,
    IEnumerable<TSource> second,
    IEqualityComparer<TSource> comparer)
{
    HashSet<TSource> bannedElements = new HashSet<TSource>(second, comparer);
    foreach (TSource item in first)
    {
        if (bannedElements.Add(item))
        {
            yield return item;
        }
    }
}

Ваша первая реализация, с другой стороны, будет сравнивать каждый элемент в первом списке с каждым элементом во втором списке - он выполняет cross product. Для этого потребуются операции nm, поэтому он будет работать в O (nm) - когда n и m станут большими, это становится слишком медленным. (Также это решение неверно, так как оно создает повторяющиеся элементы).

Ответ 2

Два примера кода не дают одинаковых результатов.

Ваш старый код создает Декартовы продукты из двух списков.

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

С "большими" списками это займет много времени.

Ответ 3

from a in list1 from b in list2 создает элементы list1.Count * list2.Count и не совпадает с list1.Except(list2)!

Если list1 имеет элементы { a, b, c, d } и list2 элементы { a, b, c }, тогда ваш первый запрос даст следующие пары:

(a,a), (a,b), (a,c),  
(b,a), (b,b), (b,c),  
(c,a), (c,b), (c,c),  
(d,a), (d,b), (d,c)

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

(a,a), (a,b), (a,c),  
(b,a), (b,b), (b,c),  
(c,a), (c,b), (c,c),  
(d,a), (d,b), (d,c)

И поскольку вы выбираете только первый элемент из пар, вы получите

{ a, a, b, b, c, c, d, d, d }

Второй запрос даст { a, b, c, d } минус { a, b, c }, i.e { d }.

Если в Exclude не была использована хеш-таблица, тогда будет создан вложенный цикл с O(m*n). С хэш-таблицей запрос приблизительно выполняется с O(n) (пренебрегая стоимостью для заполнения хеш-таблицы).

Ответ 4

Так я об этом думаю.

IEnumerable<T> Except<T>(IEnumerable<T> a,IEnumerable<T> b)
{
    return a.Where(x => !b.Contains(x)).Distinct();
}

Ответ 5

Мне кажется, это было бы более эффективно

private static IEnumerable<TSource> ExceptImpl<TSource>(
    IEnumerable<TSource> first,
    IEnumerable<TSource> second,
    IEqualityComparer<TSource> comparer)
{
    HashSet<TSource> bannedElements = new HashSet<TSource>(second, comparer);
    foreach (TSource item in first)
    {
        if (!bannedElements.Contains(item))
        {
            yield return item;
        }
    }
}

Содержит O (1)

Добавить, если граф меньше емкости внутреннего массива, этот метод является операцией O (1). Если объект HashSet должен быть изменен, этот метод станет операцией O (n), где n - Count.