Andrei Alexandrescu wrote:
Don wrote:
Andrei Alexandrescu wrote:
I think you can't do better. Complexity is O(n) at a minimum because
you need to go through each element. The heap-based algorithm has O(n
log m). What you could improve on is the log m factor (m = the number
of sets).
Depending on what "going through each element" means. Certainly, if
you need to move them, you can't beat O(n) moves, but you can
definitely get O(m*m) < < O(n) comparisons in the best case I
described. And that would also be the number of splicing operations.
Oh, I see. So yes, comparisons can be reduced. So how exactly do you
think that can be done? By binary searching the upper bound of the head
to find a long run of identical elements?
That was my original thought, but it's easy to come up with cases that
would perform really badly -- so that you do a binary search for every
two elements.
Which was why I suggested repeated doubling of the stride distance, I
think you can prove that's never worse than a linear search of every
element.
Although, if it was worth doing, I'd imagine that implementations of STL
set_union would already be doing it.
Anyway, it's a really interesting problem.
