Here'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).
An interesting data structure with search time O(sqrt n)
11–20 of 76 posts
Re: An interesting data structure with search time O(sqrt n)
#12Isn't O(log(n)) equivalent to O(sqrt(n))?
Re: An interesting data structure with search time O(sqrt n)
#13Per 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 heap and insert the new element instead. Then propagate upwards (i.e. extract top of next heap and insert top of previous heap, etc). Worst case is O(n^(1/3) + log(n^(2/3)) * n^(1/3)) = O(log(n) * n^(1/3)).
Deletion of an element. Find the heap with the element (i.e. element between maximum of previous heap and this heap). Remove the element from it. Extract top of next heap and insert it into this one. Then continue propagating upwards. So this is O(n^(1/3) + n^(2/3) + log(n^(2/3)) * n^(1/3)) = O(n^(2/3)).
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)?
Edit: Using the suggestion of splitting up according to 1+3+5+..+(2n-1) = n^2 we'd get:
Search: O(sqrt(n) + sqrt(n)) = O(sqrt(n))
Insert: O(sqrt(n) + log(sqrt(n)) * sqrt(n)) = O(log(n) * sqrt(n)
Delete: O(sqrt(n) + sqrt(n) + log(sqrt(n)) * sqrt(n)) = O(log(n) * sqrt(n))
Re: An interesting data structure with search time O(sqrt n)
#14Isn't O(log(n)) equivalent to O(sqrt(n))?
No.
Just as (e^n) grows faster (in the limit) than any polynomial of n, such as n^2 or n^100; likewise, log(n) grows slower than any polynomial of n, such as sqrt(n) = n^(1/2), or even n^(1/100).
They are both practically pretty slow-growing, though. It may well be that for practical sizes, constant factors matter more than the asymptotic difference on present computers.
Re: An interesting data structure with search time O(sqrt n)
#15I'm not sure I'm able to visualize this correctly. Let's say we have an array of strings containing the top 20 movies from Rotten Tomatoes: The Wizard of Oz The Third Man Citizen Kane All About Eve Das Cabinet des Dr. Caligari. (The Cabinet of Dr. Caligari) Modern Times A Hard Day's Night The Godfather E.T. The Extra-Terrestrial Metropolis It Happened One Night Singin' in the Rain Laura The Adventures of Robin Hood I…
It will look like regular plain array of 20 elements (with pointers to your strings). In these 20 elements first one will be the smallest one (use strcmp or similar). Next 4 elements will contain next 4 smallest strings, next 9 next 9 smallest, and then 6 last ones. 1 + 4 + 9 + 6 = 20.
In each of sub-heaps (1, 4, 9, 6) elements will be organized in max-heap. Meaning for each element i, x[i] > x[2* i+1] && x[i] > x[2 * i+2].
Re: An interesting data structure with search time O(sqrt n)
#16Isn't O(log(n)) equivalent to O(sqrt(n))?
No, because sqrt(n)/log(n) is not bounded by a constant as n approaches infinity. Consider: in base 10, if log(n)=10, then sqrt(n) is 5 digits; if log(n)=100, then sqrt(n) is 50 digits; if log(n)=1000, then sqrt(n) is 500 digits; etc.
Re: An interesting data structure with search time O(sqrt n)
#17I don't understand this bit:
> 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,
Just because the maximums of the heaps are increasing order doesn't mean that the minimum is at the front. It means the first element is smaller than the biggest element of the next four.
Consider, for example:
1 4 3 2 0
Re: An interesting data structure with search time O(sqrt n)
#18Even just that question: "Why?" and the corresponding answer are worth a read.
Agreed. I love that this came from noticing a "gap" and coming up with something to fill the hole. I wish I thought like this more often!
"Find a gap and fill it, I always say! My great-grand-uncle is the one who came up with disposible ketchup packets. Me, I found a data structure with O(sqrt) search time. Sure it doesn't have all the doohickeys of a Red-Black Tree, it's not as quick on the insert as a radix - but at the end of the day it gets the job done. And to some people, that's all that matters..."
Re: An interesting data structure with search time O(sqrt n)
#19I'm not sure I'm able to visualize this correctly. Let's say we have an array of strings containing the top 20 movies from Rotten Tomatoes: The Wizard of Oz The Third Man Citizen Kane All About Eve Das Cabinet des Dr. Caligari. (The Cabinet of Dr. Caligari) Modern Times A Hard Day's Night The Godfather E.T. The Extra-Terrestrial Metropolis It Happened One Night Singin' in the Rain Laura The Adventures of Robin Hood I…
From my understanding it would be roughly:
https://gist.github.com/bpicolo/32a7fc775ce1810c88a0
Re: An interesting data structure with search time O(sqrt n)
#20This is a very interesting discussion, but I'd like to ask a question about this in particular: > The short of it is, arrays are king. No two ways about it - following pointers is a losing strategy when there's an alternative. Why is following pointers a losing strategy? If you have a contiguous array (a vector), then the pre-fetcher can do its magic and give you a psuedo-cache level. (I may be wrong about this assum…
The prefetcher works only if it can predict what you're going to access next. Chasing pointers means essentially jumping to random addresses in a given memory region. That's pretty much the worst situation from a caching point of view, what the prefetcher loves is linear traversal. Of course things become more complicated when you start having larger amounts of data, and you want to skip over most of it, but still ke…
In theory, an advanced prefetcher can detect that you are stepping through an array of pointers, dereferencing each of them, and start prefecting.
Even that would have its problems, though. Typically, every one of these dereferences brings in a new cache line. Unless the data that the pointers point to fills an integral number of cache lines, you are bringing data into the cache that you will not need.