Re: [OT] n-way union

[Andrei Alexandrescu]

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.

Andrei