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

Nearly All Binary Searches and Mergesorts Are Broken (2006)

research.googleblog.com

Post reply on HN
Print view View original

41–50 of 95 posts

Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)

#41

Post by flor1s »

booleandilemma wrote: post #25
sillysaurus3 wrote: post #4

I wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit. It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could i…

The current hotness is AI/machine learning/deep learning. Maybe after that it will be something like "quantum programming"? Just my guess. http://www.newsweek.com/2017/04/21/quantum-computing-ibm-580...

It seems like in that field you can use some of your knowledge of system programming. Overflow and underflow happens a lot with the big data volumes you face. Another systems programming topic discussed in most big data courses is floating point accuracy.

Understanding floating point arithmetic is even more important than over/underflow of integers in dynamic languages such as Python (see e.g. https://www.python.org/dev/peps/pep-0237/).

Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)

#42

Post by rntz »

KirinDave wrote: post #39
rntz wrote: post #36

Earlier quoted context omitted.

The O(n log n) bound only holds for comparison-based sorts. It's not a matter of time; it's an assumption/precondition of the proof.

Right, but a generalization of discrimination-based sorts didn't exist until earlier this decade. So it was a reasonable statement to misinterpret or relegate to "say you have a 30m character string you wanted to sort as quickly as possible" interview questions. I certainly didn't realize how generalized discrimination-based sorts were. Many people I've talked to outside of the Haskell community don't know at all. I'…

Huh, is this the stuff you're talking about:

    http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf
    http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011c.pdf
    https://www.youtube.com/watch?v=sz9ZlZIRDAg
    https://hackage.haskell.org/package/discrimination
I didn't know about this until I read your reply and googled; I thought you were just obliquely referring to radix sort or something like that.

Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)

#44

Post by sova »

dsacco wrote: post #17
sillysaurus3 wrote: post #4

I wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit. It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could i…

It's still worth a lot to be good at systems programming. Outside of the HN bubble there are plenty of companies willing to pay extremely well for people who can do systems programming, particularly under high performance constraints.

Name 5 please

Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)

#45

Post by pishpash »

rntz wrote: post #40
tzs wrote: post #30

> int mid = low + ((high - low) / 2); That may fix things in the case of searching a sorted array, but binary search can be used more generally than that. I think that fix might not work for some of the more general applications of binary search. For instance, suppose f(n) is an increasing function from the signed integers to the signed integers, with f(a) 0, and you want to find an n in (a,b), if such n exists, such…

I'm tempted to suggest (low / 2) + (high / 2) but then I have to think about rounding error. Ugh. I guess you could write a bunch of nested `if`s to handle the parity errors, assuming you know how your language rounds when dividing negative numbers. (I wouldn't be surprised if C leaves that "implementation-defined".) If you're really searching an arbitrary range, maybe just use bigints. Then at least you can stop wor…

That won't get you the middle, these are integer divisions.

Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)

#48

Post by admax88q »

sillysaurus3 wrote: post #4

I wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit. It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could i…

The problem is these sorts of things are trivia. They are things that sufficiently smart tooling should handle for us so people can spend time building higher level constructs and less time worrying about individual bits.

A smart compiler should have caught (a + b) / 2 and fixed it to be correct, there's no way the overflow situation is what the programmer wanted.

Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)

#49

Post by [deleted] »

throwaway91111 wrote: post #26
albinofrenchy wrote: post #10

Earlier quoted context omitted.

Simply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.

If "this bug" is the ability to sort >2^30 elements on a 64-bit machine, this bug IS addressed by changing the index type. Of course sorting 2^63 elements would require the different calculation.

[deleted]

Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)

#50

Post by chrispickels »

sova wrote: post #44
dsacco wrote: post #17

Earlier quoted context omitted.

It's still worth a lot to be good at systems programming. Outside of the HN bubble there are plenty of companies willing to pay extremely well for people who can do systems programming, particularly under high performance constraints.

Name 5 please

google facebook microsoft amazon baidu
Post reply on HN