[OT] n-way union
Don
nospam at nospam.com
Tue May 26 07:11:30 PDT 2009
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.
More information about the Digitalmars-d
mailing list