Как получить совпадения между коллекциями разных типов?

Question

Я думаю, что это займет O(A x B) время для выполнения.

(где A - размер коллекции A, а B - размер коллекции B)

Я прав?

IEnumerable<A> GetMatches(IEnumerable<A> collectionA, IEnumerable<B> collectionB)
{
    foreach (A a in collectionA)
        foreach (B b in collectionB)
            if (a.Value == b.Value)
                yield return a;
}

Есть либолее быстрый способ выполнить этот запрос?(может быть, используя LINQ?)

Answer 1

К сожалению,

Enumerable.Intersect не сработает, поскольку вы сравниваете два разных типа (A и B).

Для получения вызова Intersect, который будет работать, потребуется отдельная обработка.

Вы можете сделать это поэтапно:

IEnumerable<A> GetMatches(IEnumerable<A> collectionA, IEnumerable<B> collectionB)
     where A : ISomeConstraintWithValueProperty
     where B : ISomeOtherConstraintWithSameValueProperty
{
    // Get distinct values in A
    var values = new HashSet<TypeOfValue>(collectionB.Select(b => b.Value));

    return collectionA.Where(a => values.Contains(a.Value));
}

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

Если вы хотите уникальные совпадения (возвращается только одно), вы можете изменить последнюю строку на:

return collectionA.Where(a => values.Contains(a.Value)).Distinct();

Answer 2

Вы можете попробовать следующий алгоритм пересечения, который имеет сложность O (m + n), если ваши данные отсортированы, или O (nlogn) в противном случае, без использования дополнительной памяти:

    private static IEnumerable<A> Intersect(A[] alist, B[] blist)
    {
        Array.Sort(alist);
        Array.Sort(blist);

        for (int i = 0, j = 0; i < alist.Length && j < blist.Length;)
        {
            if (alist[i].Value == blist[j].Value)
            {
                yield return alist[i];
                i++;
                j++;
            }
            else
            {
                if (alist[i].Value < blist[j].Value)
                {
                    i++;
                }
                else
                {
                    j++;
                }
            }
        }
    }