[OT] n-way union
jason.james.house at gmail.com
Sat May 23 10:01:55 PDT 2009
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, a) 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).
My first thought was to throw everything in a heap map with key=r.front and value=r
That makes each pop operation O(log(# non-empty ranges)) which should be near optimal.
> Needless to say, nWayUnion is a range :o).
> Finally, why would anyone care for something like this?
More information about the Digitalmars-d