Knuth Got It Wrong or "You're doing it wrong"

[jdarling]

I found this article more than just very interesting, I found it mind numbingly simple and once I thought about it, very obvious. Truth is, I'm as guilty of not thinking about page faults and access times when I develop my trie's as anyone out there. Time to go back and pay a bit more attention to my basic implementations. A few minor tweaks could speed up your seek times x10!



Would you believe me if I claimed that an algorithm that has been on the books as "optimal" for 46 years, which has been analyzed in excruciating detail by geniuses like Knuth and taught in all computer science courses in the world, can be optimized to run 10 times faster?

http://queue.acm.org/detail.cfm?id=1814327


- Jeremy

[User137]

Forgot the link to the article? ;)

[Traveler]

This (http://queue.acm.org/detail.cfm?id=1814327) might be the one

[pstudio]

Interesting read.

I enjoy reading Poul-Hennings Danish blog though I don't always agree with him. Right now he's receiving a lot of critic for attacking the CS world and claiming that they don't realize how computers actually work.

PH's has a good point about focusing on the VM. Unfortunately he can't write an article without attacking someone/thing he doesn't agree with.

[jdarling]

The link was there, it was just buried in the quote (sorry, I know they don't show up well in some of the schemes here).

I didn't see where he "attacked" anyone directly, and in fact he states several times it isn't his intention to attack the CS or Knuth. He even goes to show the the postulate placed by Knuth is true as long as you leave out the Page Faulting.

Guess its all in how you choose to read his writings. Any way you want to read them, the basic premise is correct, if you forget to calculate access times you are missing a MAJOR part of searching :)