Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An interesting data structure with search time O(sqrt n)

forum.dlang.org

Post reply on HN
Print view View original

21–30 of 76 posts

Re: An interesting data structure with search time O(sqrt n)

#21

Post by jcdavis »

rntz wrote: post #17

I 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 th…

Minimum is only at the front of the entire structure, not each heap. Thats because the first element is a heap of size 1. From what I understand, the correct layout would be something like

  0 4 2 3 1
Max heap of size 1 containing the smallest element, then a maxheap of size 4 containing the next 4 smallest, etc

Re: An interesting data structure with search time O(sqrt n)

#22

Post by mmozeiko »

bpicolo wrote: post #19
biot wrote: post #9

I'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

I won't be array of arrays. It will be just one array.

Re: An interesting data structure with search time O(sqrt n)

#23

Post by bpicolo »

mmozeiko wrote: post #22
bpicolo wrote: post #19

Earlier quoted context omitted.

From my understanding it would be roughly: https://gist.github.com/bpicolo/32a7fc775ce1810c88a0

I won't be array of arrays. It will be just one array.

  we decompose an array of size 35 into: an array of size 1 followed by arrays of sizes 4, 9, 16, 5
Then again, maybe he means `mentally decompose` in terms of pretending they're separate arrays? I interpreted it as `visualize this data structure`.

Re: An interesting data structure with search time O(sqrt n)

#24

Post by lobster_johnson »

davidhariri wrote: post #10

From what I understand, this is how Medium organizes the fast retrieval and editing of their rich text. You might want to read this for more information: https://medium.com/medium-eng/why-contenteditable-is-terribl... I may have missed something, though :-|

That doesn't sound like it at all. Medium's document model is a list of paragraphs, and that (according to your link) is it.

Re: An interesting data structure with search time O(sqrt n)

#25

Post by btilly »

gamesbrainiac wrote: post #3

This 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…

In addition to the unexpected high costs of following pointers, the cost of searching an array is often less than you'd expect thanks to branch prediction.

What is that? Well CPUs actually process a statement in several steps, and try to process several statements at a time. But what if you have an if? The solution is to guess which way it will turn out, then begin on the expected branch before it is done evaluating the if. If the if turns out as expected, this goes faster. If not, the partially done work is thrown out, and the other branch is run. This is a substantial speedup when branches are predicted correctly.

When you search through an array you often get into a situation where most of the time the if turns out the same way. "Is this bigger than my max? No. Is this bigger than my max? No...." As a result branch prediction makes this execute surprisingly quickly.

Re: An interesting data structure with search time O(sqrt n)

#28

Post by teraflop »

herewhere wrote: post #26

if 4 log2(N) So, in Big-O term, this only trying to optimize only small dataset (4 <= N <= 16).

Big-O is only strictly meaningful in terms of asymptotic behavior; as soon as you start talking about specific values of N, you have to care about constant factors.

In this case, the constant factors will probably be quite different because the goal is to make better use of CPU cache.

Re: An interesting data structure with search time O(sqrt n)

#29

Post by DannyBee »

drfuchs wrote: post #16
chias wrote: post #12

Isn'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.

Errr, what? natural log grows slower than sqrt(n)

http://www.wolframalpha.com/input/?i=sqrt%281e55%29+%3E+log%...

Re: An interesting data structure with search time O(sqrt n)

#30

Post by eloff »

Someone wrote: post #20
tux3 wrote: post #6

Earlier quoted context omitted.

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.

There are costs to this, because you may dereference things that are not valid pointers either. The kernel used to have software prefetch code for linked list traversal. On each access it would prefetch the subsequent access. Which sounds like a huge win. However, in practice the most common list size was just a few elements and there was a huge penalty for fetching the final, invalid null pointer. They ended up taking out the prefetching recently (and I think they saw a small speedup as a result!) Now maybe someone could invent a hardware prefetcher that does this in a way that's a net gain, but the fact that Intel hasn't done it yet suggests that it maybe it doesn't help much or that the situation isn't all that common.
Post reply on HN