I’ve been thinking a lot recently about how you find the th smallest element in the disjoint union of several data structures.
Multi-quickselect on data structures with fast
Yesterday I came up with an algorithm similar to quickselect for the version of this problem where you have multiple sorted arrays.
But this algorithm also works on any other data structure which supports the
rank method in time.
On a collection of data structures with a total of elements, the modified quickselect algorithm involves iterations. In each iteration, the rank of a random element is computed in every data structure.
So the total time taken is (time to calculate rank in every data structure) * (log of total number of elements).
|$$ m$$ sorted arrays of average length $$ n$$||$$ \log(m \cdot n) \cdot m \cdot \log(n)$$|
|$$ m$$ sorted arrays of total length $$ t$$||$$ \log(t) \cdot m \cdot \log(\frac tm)$$|
|Two sorted arrays, of lengths $$ a$$ and $$ b$$||$$ \log(a + b)^2$$|
|$$ m$$ order statistic trees of average size $$ n$$||$$ \log(m \cdot n) \cdot m \cdot \log(n)$$|
|$$ \log(n)$$ sorted arrays of sizes $$ [1, 2, 4, ...n]$$||$$ \log(n)^3$$|
(See 1 for more details on the exponentially shrinking arrays.)
For data structures with
rank, I think this is optimal.
Allowing data structures without fast
How about if some of your data structures are unsorted?
This algorithm needs to be modified, because there’s no particular guarantee that any data structure gets smaller on a particular iteration. This is okay in cases where
rank is cheap enough that the asymptotic complexity isn’t affected by having a data structure which stays at its original size for most of the runtime of the algorithm. But on an unsorted array,
rank takes and a key part of the argument for the good runtime of quickselect is that the unordered array usually gets smaller every time you call
This issue is why my attempt at an optimal algorithm for selection on an OST and an unsorted array was so complex.
Obviously there’s not going to be a sublinear time solution to this problem. So we might as well take linear time to add all our unsorted structures together into an unsorted array, in linear time. So we only need to consider the problem where we have a single unsorted array.
When I have a collection of data structures such that
rank takes time and
select takes time , I can run my
double_quickselect_v2 algorithm on an unordered array of length and that collection, with query time . For example, this algorithm can deal with a sorted array of size and an unsorted array of size in overall .
What an optimal solution might look like
I bet we can generalize my alleged optimal algorithm for selection on an OST and an unsorted array.
I have a bunch of data structures and want to find the th smallest item in their union. How long will it take me?
|Unsorted array of size $$ n$$||Median of medians||Worst case $$ O(n)$$|
|Sorted array of size $$ n$$||Binary search||Worst case $$ O(\log(n))$$|
|Order statistic tree||its native `find` implementation||Worst case $$ O(\log(n))$$|
|A bunch of unsorted data structures, of total size $$ O(n)$$||Stick it all in an array then call median of medians||Worst case $$ O(\log(n))$$|
|$$ m$$ data structures which support
||Multi sorted array quickselect||Average case $$ O(m \cdot \log(n) \cdot \log(m \cdot n))$$|
|$$ m$$ data structures which support
||"Non-optimal solution" as described above||Average case $$ O(\log(u) \cdot m \cdot \log(n) +\\ m \cdot \log(n) \cdot \log(m \cdot n))$$|
I suspect that I can improve upon most of the algorithms listed there that I invented myself; I’ll keep this table updated.
If you know a faster algorithm for one of these problems, please let me know!
There are a total of elements in those arrays. The inner loop will happen times.
Each iteration will need to do a binary search within its array. On the first iteration the time taken will be . Further iterations obviously won’t be slower than that. So we can bound above this runtime by .
We can also give a proof sketch for bounding it below. Suppose that all our arrays have roughly the same distribution, so that on the th iteration, every array has a size of only its original size.