[deleted]
An interesting data structure with search time O(sqrt n)
51–60 of 76 posts
Re: An interesting data structure with search time O(sqrt n)
#52Here's a related paper (on HN last month) which tries to find the arrangement of elements in an array which minimizes search time, measuring wall-clock time rather than theoretical complexity: http://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf . (Spoiler alert: it's not sorted order with binary search, and the answer has a lot to do with the cache).
Interesting. One layout they did not consider is the bit-reversal permutation[1] of the sorted array. Searching is straightforward: to find element i, you reverse the bits of i -- so then, you can just binary search. This layout is similar to Eytzinger, so it should perform at least as well, and it may have some advantages.
Re: An interesting data structure with search time O(sqrt n)
#53Earlier quoted context omitted.
Errr, what? natural log grows slower than sqrt(n) http://www.wolframalpha.com/input/?i=sqrt%281e55%29+%3E+log%...
I think that's the point he is making as well. Except it might be confusing that he is using numbers for log(n) and number of digits for srqt(n).
Exactly; it shows just how wildly faster sqrt(n) grows than log(n).
Re: An interesting data structure with search time O(sqrt n)
#54Per the last posts: Number of heaps: O(n^(1/3)). Maximum elements per heap O(n^(2/3)). Lookup of an element. Find the heap with the element (i.e. element between maximum of previous heap and this heap). Perform linear search in heap. Worst cast complexity O(n^(1/3) + n^(2/3)) = O(n^(2/3)). Insertion of an element. Find the last heap those maximum element is still larger than the element. Extract top element of the he…
Deletion can't be done efficiently, as pointed out by Timon Gehr: >> Deletion leaves a hole in one heap, which should be filled by the minimum element of the next heap, etc. The minimum cannot be extracted efficiently from a max-heap.
Indeed. If the smallest element is deleted, then we are removing the singleton element of the first heap. We need to find the second-smallest element, which will be in the next heap after it, but it could be any of the leaves. That means we need to traverse O(heapsize) elements.
And since we started with the smallest element, this will cascade through each of the heaps, in order to keep them all (but the last) at full size. All together, that's O(N).
Re: An interesting data structure with search time O(sqrt n)
#55Is it immediately obvious this can be constructed in O(n) time? The author just gleans over it but I'm still not able to figure it out.
Re: An interesting data structure with search time O(sqrt n)
#56Per the last posts: Number of heaps: O(n^(1/3)). Maximum elements per heap O(n^(2/3)). Lookup of an element. Find the heap with the element (i.e. element between maximum of previous heap and this heap). Perform linear search in heap. Worst cast complexity O(n^(1/3) + n^(2/3)) = O(n^(2/3)). Insertion of an element. Find the last heap those maximum element is still larger than the element. Extract top element of the he…
Deletion can't be done efficiently, as pointed out by Timon Gehr: >> Deletion leaves a hole in one heap, which should be filled by the minimum element of the next heap, etc. The minimum cannot be extracted efficiently from a max-heap.
Never used one, but how about a min-max heap instead?
Re: An interesting data structure with search time O(sqrt n)
#57Per the last posts: Number of heaps: O(n^(1/3)). Maximum elements per heap O(n^(2/3)). Lookup of an element. Find the heap with the element (i.e. element between maximum of previous heap and this heap). Perform linear search in heap. Worst cast complexity O(n^(1/3) + n^(2/3)) = O(n^(2/3)). Insertion of an element. Find the last heap those maximum element is still larger than the element. Extract top element of the he…
> Building the structure. Why is this O(n)? If you have already segregated the array into segments for the separate heaps, heapifying them would be O(n). How can the segmentation be done in O(n)?
Using 1 + 3 + 5 ... = n^2, wouldn't the largest segment hold roughly sqrt(n) elements. So O(sort(n)) heapify for sqrt(n) heaps, or O(sqrt(n) * sqrt(n)) = O(n).
Re: An interesting data structure with search time O(sqrt n)
#58Earlier quoted context omitted.
I'm not really sure what amortization you're talking about here. BSTs are O(n) lookup, and the pathological case is quite easy to achieve: add elements to it in sorted order. There are other trees that have O(lg n) lookup. Red-black trees are the canonical example.
BSTs can have O(lg n) lookups. A Red-black tree is such an example. It is a self-balancing BST, so a red-black tree is a BST itself.
And BSTs can have O(n) lookup. The only property of a BST is that you know something about the value of the children compared to the parent. This means that a sorted linked list is a BST.
Re: An interesting data structure with search time O(sqrt n)
#59Earlier quoted context omitted.
BSTs can have O(lg n) lookups. A Red-black tree is such an example. It is a self-balancing BST, so a red-black tree is a BST itself.
And BSTs can have O(n) lookup. The only property of a BST is that you know something about the value of the children compared to the parent. This means that a sorted linked list is a BST.
Sure, but abcdabcd987 was evidently not suggesting using a completely general BST. That there exists a BST with the mentioned properties is sufficient to validate the claim made; that there exists a BST which does not is irrelevant.
Re: An interesting data structure with search time O(sqrt n)
#60Another thing that works is a length-sqrt(n) list of length-sqrt(n) sorted lists with internal gaps, like with Python's SortedContainers[1].
Something like this with a contiguous allocation would probably require quite a lot of empty space - 100% reserve for each subarray by necessity[2] and 50% for the array as a whole, so 200% overhead at worst and probably 90% overhead on average. Alternatively you can heap allocate each subarray at the expense of slower operations, but resulting in a more typical 100% worst-case overhead.
So you'd store like this
|----------HEADER---------| |-----------------------BUCKETS------------------------|
idx
(0, 3) (2, 2) (1, 4) (_, _) [1, 3, 7, _] [14, 15, 16, 19] [9, 12, _, _] [_, _, _, _]
length
So to search for a value, you do a binary search over the header to find the wanted bucket and then over the bucket to find the value. That's O(log n).
Insertion is O(sqrt n) since you need to find the bucket and then do a normal insertion into it. You might need to reallocate the whole thing (remember to increase bucket size!) but that's amortized out.
Deletion is even easier since you don't have to deal with overflow (although you might want to move empty buckets to the end or merge adjacent ones, maybe). O(sqrt n).
Creating the structure is trivially O(n log n), since it's sorted.
Converting to a sorted list is just compacting the buckets.
You also get access by index at O(sqrt n) speed since you just need to traverse the counts in the header. Not perfect, but close.
For a cache-efficient design it's pretty neat. Binary searches are fast, after all.
[1]: http://www.grantjenks.com/docs/sortedcontainers/implementati...
[2]: When you split an overfull subarray, each new subarray will be half full.