Theory vs Practice: Making algorithms claimed 'optimal', 10x faster.

Posted by HarrySimons on Sunday July 11, 2010 @02:34AM
from the cacm.acm.org dept.

http://cacm.acm.org/magazines/2010/7/95061-youre-doing-it-wrong/fulltext

"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?"

( 2 comments | 32 points | on HN )

Re:Theory vs Practice: Making algorithms claimed 'optimal', ... by RiderOfGiraffes on Sunday July 11, 2010 @04:02AM (#1505192)

I think this is pretty much identical to the subject being discussed here:

http://news.ycombinator.com/item?id=1426211

There's a lot of discussion there already, and it might be worth reading it before commenting here and repeating all the arguments.

ADDED IN EDIT: Having gone and taken my own advice (for a change 8-) I prefer the other article because the diagrams are larger and in-line.

[ Parent | on HN ]

Re:Theory vs Practice: Making algorithms claimed 'optimal', ... by jrockway on Sunday July 11, 2010 @05:55AM (#1505288)

It's the same article by the same author, of course. One is a preprint and the other is from this month's CACM.

[ Parent | on HN ]