What is the simplest way to achieve O(n) performance when creating the union of 3 IEnumerables?

user_457392 0
Viewed 3966

Say a, b, c are all List<t> and I want to create an unsorted union of them. Although performance isn't super-critical, they might have 10,000 entries in each so I'm keen to avoid O(n^2) solutions.

AFAICT the MSDN documentation doesn't say anything about the performance characteristics of union as far as the different types are concerned.

My gut instinct says that if I just do a.Union(b).Union(c), this will take O(n^2) time, but new Hashset<t>(a).Union(b).Union(c) would be O(n).

Does anyone have any documentation or metrics to confirm or deny this assumption?

linq c#
4 Answers

As with everything, this has been changing with .NET Core and now just .NET. With Framework, it was most efficient (by about 20%) to use a chain of Concat operations embedded within a Union:

a.Union(b.Concat(c).Concat(d)...Concat(x))

However, sometime in .NET Core, this changed and now a chained Union is now more efficient (by as much as 75%):

a.Union(b).Union(c).Union(d)...Union(x)

As with everything, it is important to monitor your critical sections and test.

user_1270540
Related