Re: [OT] n-way union

[Georg Wrede]

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.