Каков самый простой способ достижения O (n) производительности при создании объединения 3 IEnumerables?

Скажите, что a, b, c - все List<t>, и я хочу создать их несортированный союз. Хотя производительность не является суперкритической, они могут иметь по 10 000 записей, поэтому я стараюсь избегать решений O (n ^ 2).

AFAICT документация MSDN не говорит ничего о характеристиках производительности объединения в отношении различных типов.

Мой инстинкт кишки говорит, что если я просто сделаю a.Union(b).Union(c), это займет время O (n ^ 2), но new Hashset<t>(a).Union(b).Union(c) будет O (n).

Есть ли у кого-нибудь документация или показатели, чтобы подтвердить или опровергнуть это предположение?

Ответ 1

Вы должны использовать Enumerable.Union, потому что он так же эффективен, как и подход HashSet. Сложность - O (n + m), потому что:

Enumerable.Union

Когда объект, возвращаемый этим методом, перечислит, Union<TSource>e зачисляет первый и второй в этом порядке и дает каждый элемент, который еще не было получено.

Исходный код здесь.

Иван прав, есть накладные расходы, если вы используете Enumerable.Union с несколькими коллекциями, так как новый набор должен быть создан для каждого прикованного вызова. Поэтому, если вы используете один из этих подходов, он может быть более эффективным (с точки зрения потребления памяти):

Concat + Distinct:

a.Concat(b).Concat(c)...Concat(x).Distinct()

Union + Concat
```
a.Union(b.Concat(c)...Concat(x))
```
HashSet<T> конструктор, который принимает IEnumerable<T> (f.e. с int):
```
new HashSet<int>(a.Concat(b).Concat(c)...Concat(x))
```

Разница между двумя первыми может быть незначительной. Третий подход не использует отложенное выполнение, он создает HashSet<> в памяти. Это хороший и эффективный способ 1. если вам нужен этот тип коллекции или 2. если это окончательная операция по запросу. Но если вам нужно продолжить операции над этим связанным запросом, вы должны выбрать либо Concat + Distinct, либо Union + Concat.

Ответ 2

В то время как @Tim Schmelter прав насчет линейной временной сложности метода Enumerable.Union, привязка нескольких операторов Union имеет скрытые служебные данные, которые каждый оператор Union внутренне создает хэш-набор, который в основном дублирует один из предыдущего оператора (плюс дополнительные элементы), тем самым используя гораздо больше памяти по сравнению с одним подходом HashSet.

Если учесть тот факт, что Union является просто ярлыком для Concat + Distinct, масштабируемое решение LINQ с той же сложностью времени/пространства для HashSet будет:

a.Concat(b).Concat(c)...Concat(x).Distinct()

Ответ 3

Union - O (n).

a.Union(b).Union(c) менее эффективен в большинстве реализаций, чем a.Union(b.Concat(c)), потому что он создает хэш-набор для первой операции объединения, а затем второй для второго, как говорили другие ответы. Оба они также заканчиваются цепочкой объектов IEnumerator<T>, которые увеличивают стоимость по мере добавления дополнительных источников.

a.Union(b).Union(c) более эффективен в .NET Core, потому что вторая операция .Union() создает единый объект со знанием a, b и c, и он создаст один хэш-набор для всего а также избежать цепочки объектов IEnumerator<T>.