[OT] n-way union

[Jason House]

Georg Wrede Wrote:

> Andrei Alexandrescu wrote:
> > Georg Wrede wrote:
> >> Andrei Alexandrescu wrote:
> >>> This is somewhat OT but I think it's an interesting problem. Consider 
> >>> the following data:
> >>>
> >>> double[][] a =
> >>> [
> >>>     [ 1, 4, 7, 8 ],
> >>>     [ 1, 7 ],
> >>>     [ 1, 7, 8],
> >>>     [ 4 ],
> >>>     [ 7 ],
> >>> ];
> >>>
> >>> We want to compute an n-way union, i.e., efficiently span all 
> >>> elements in all arrays in a, in sorted order. You can assume that 
> >>> each individual array in a is sorted. The output of n-way union 
> >>> should be:
> >>>
> >>> auto witness = [
> >>>     1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8
> >>> ];
> >>> assert(equal(nWayUnion(a), witness[]));
> >>>
> >>> The STL and std.algorithm have set_union that does that for two sets: 
> >>> for example, set_union(a[0], a[1]) outputs [ 1, 1, 4, 7, 7, 8 ]. But 
> >>> n-way unions poses additional challenges. What would be a fast 
> >>> algorithm? (Imagine a could be a very large range of ranges).
> >>>
> >>> Needless to say, nWayUnion is a range :o).
> >>
> >> If we'd know anything about the data, such as, the max value is always 
> >> smaller than the total number of elements in the subarrays, then we'd 
> >> probably more easily invent a decent algorithm.
> >>
> >> But the totally general algorithm has to be more inefficient. And 
> >> constructing (not worst-case, but) tough-case data is trivial. For 
> >> example, take a thousand subarrays, each a thousand elements long, 
> >> containing random uints from the inclusive range 0..uint.max.
> > 
> > You can assume that each array is sorted.
> 
> Err, you didn't comment on my algorithm, at the end. So, either it is 
> worthless to an extent not deserving even a dismissal, or you didn't 
> read the rest of the post.

Don't get offended, he didn't respond to anyone else's algorithm either.