On 30-Nov-2015 23:13, Andrei Alexandrescu wrote:
Okasaki's book is a continued inspiration of data structures and
algorithms.
I was thinking along the following lines: typical collections are
searchable in linear time. Then we have highly structured collections
that feature logarithmic search time. But there seems to be nothing in
between. So I was thinking, what would be a data structure that allows
O(sqrt n) search times?
After a little tinkering, here's what I came up with.
Start with a simple array of data. Then mentally decompose that array
into a concatenation of smaller arrays: first has size 1, second has
size 4, third has size 9, then 16, 25, 36, ... Generally the size of
these imaginary subarrays grows quadratically. And they're adjacent to
each other. The last array may be incomplete.
Example: we decompose an array of size 35 into: an array of size 1
followed by arrays of sizes 4, 9, 16, 5 (last being an incomplete
fragment of an array of size 25).
Now each of these arrays we organize as a max heap. Moreover, we arrange
data such that the maximums of these heaps are in INCREASING order. That
means the smallest element of the entire (initial) array is at the first
position, then followed by the next 4 smallest organized in a max heap,
followed by the next 9 smallest organized in a max heap, ... etc. There
are a total of O(sqrt n) heaps, and each has O(sqrt n) elements.
That's the layout! Now, to search we look at one heap at a time.
Whenever the maximum element (first element in the subarray) is smaller
than the searched value, we skip over that entire heap and go to the
next one. In the worst case we'll skip O(sqrt n) heaps. When the max
value in a heap is less than the searched element, we found the heap and
we run a linear search among O(sqrt n) elements.
Reminds me of Van Emde Boas layout which is however fractal in nature:
sqrt(N) pieces each having sqrt(N) element are subdivided again into
sqrt(sqrt(N)) pieces and so on.
Not sure if you have seen, but see also cache-oblivious data-structures:
http://erikdemaine.org/papers/BRICS2002/paper.pdf
--
Dmitry Olshansky
