Как найти предметы в суперсете, которые не находятся в подмножестве

Question

Я знаю, что есть «НЕ» на подъеме благодаря LINQ, которая требует коллекции, чтобы не против, но я беспокоюсь о Big OH Performance, что является самым быстрым алгоритмом для этого?

Answer 1

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

Это даст вам O (N²) в среднем.

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

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

public static IEnumerable<T> Exclude<T>
    (this IEnumerable<T> source, IEnumerable<T> items)
{
    foreach (T t in source)
        if (!items.Contains(t))
            yield return t;
}

---

Неужели, используйте Enumerable.Except Метод расширения:

Создает разницу в двух последовательностях.

Answer 2

Если вы можете итерации над наборами по порядку, вы можете гарантировать поведение O (n) (а не «обычно O (n), но, возможно, O (N²) в худшем случае», который имеет хэшсет), итерация через них оба в Lockstep.

Например:

//loop boilerplate
if(itemA < itemB) {
    itemA = a.next();
    continue;
}
if(itemA > itemB) {
    itemB = b.next();
    continue;
}
a.remove(itemA);

Вам нужно будет добавить проверку границ и другую паттерскую таблицу.

Answer 3

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