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

81–90 of 95 posts

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

#81

Post by justin66 »

KirinDave wrote: post #68
rntz wrote: post #42

Earlier quoted context omitted.

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

Yes that is it. And it's really a variation on radix sort as well. They're all in the same general family. I can't believe I got down voted for this thread. What does it take? I guess I should just post it.

Given how few of those posting tonight appeared to understand the import of what Joshua Bloch wrote, I wouldn't take it personally. I'm slightly shocked by it, but I wouldn't take it personally...

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

#82

Post by KirinDave »

justin66 wrote: post #81
KirinDave wrote: post #68

Earlier quoted context omitted.

Yes that is it. And it's really a variation on radix sort as well. They're all in the same general family. I can't believe I got down voted for this thread. What does it take? I guess I should just post it.

Given how few of those posting tonight appeared to understand the import of what Joshua Bloch wrote, I wouldn't take it personally. I'm slightly shocked by it, but I wouldn't take it personally...

I did post it, I even said provocatively, "O(n) general sort" in the title. Sadly the point gods were not kind.

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

#83

Post by KyeRussell »

nxc18 wrote: post #62
chrispickels wrote: post #50

Earlier quoted context omitted.

google facebook microsoft amazon baidu

All of those places will pay just as much for (as well as hire far more of) enterprise Java/Go/HTML/JS code monkeys There's nothing wrong with that, but picking 5 companies with their hands in damn-near anything is disingenuous.

So it's less about getting paid for your work and more about a dick measuring contest with your coworkers.

I think that's your issue.

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

#84

Post by majewsky »

throwaway91111 wrote: post #51
admax88q wrote: post #48

Earlier quoted context omitted.

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.

"sufficiently smart tooling" has got to be one of the best jokes in programming. On one hand, it is true that the tooling is possible. On the other hand, it remains an open problem.

http://wiki.c2.com/?SufficientlySmartCompiler

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

#85

Post by bitcoinmoney »

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 companies and typical salary ranges for junior dev or senior developer experience.

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

#86

Post by serhei »

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

The next boom will be in whatever _isn't_ being hyped right now.

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

#87

Post by kzisme »

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…

If you don't mind me asking how did you get into Systems Programming? (Or how would you recommend someone getting into it?)

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

#88

Post by kazinator »

rntz wrote: post #52
pishpash wrote: post #45

Earlier quoted context omitted.

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

Yes, that's why I said: "but then I have to think about rounding error. Ugh." Because integer division rounds. (Or truncates, if you prefer.)

Rouding error can be taken care of:

https://news.ycombinator.com/item?id=14908117

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

#89

Post by kazinator »

CamperBob2 wrote: post #54

Programmer: "The bug is in the choice of data type. Use unsigned ints to index arrays." Computer scientist: "The bug is in the language. Signed integer overflow behavior should have been defined in such a way as to guarantee correct functionality in cases such as this." Me: "Use int64s for this sort of thing. It's still broken, but I'll be retired or dead before anyone notices." Engineer: "The bug is in the documenta…

Mathematician: "I conjecture that a solution exists."

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

#90

Post by kazinator »

ScottBurson wrote: post #8

The bug isn't in your algorithm; the bug is in your language, which doesn't provide arbitrary-precision integer arithmetic by default.

Still, the formula low + (high - low)/2 keeps the integers smaller (assuming everything is positive). That is to say, it can work with larger values before requiring bignums compared to (low + high) / 2. On the other hand, it is more operations.
Post reply on HN