3 ms·

This touches on an interesting topic: how robust implementations of most algorithms go well beyond what you're taught in an algorithms course. There are tons of

This touches on an interesting topic: how robust implementations of most algorithms go well beyond what you're taught in an algorithms course. There are tons of optimizations that matter when dealing with real world data that don't matter for algorithmic complexity. Two links on the subject: Bentley and McIlroy on Engineering a Sort Function: http://cs.fit.edu/~pkc/classes/writing/samples/bentley93engineering.pdf http://cs.fit.edu/~pkc/classes/writing/samples/bentley93engi... Tim Peters' Timsort: https://en.wikipedia.org/wiki/Timsort https://en.wikipedia.org/wiki/Timsort https://mail.python.org/pipermail/python-dev/2002-July/026837.html https://mail.python.org/pipermail/python-dev/2002-July/02683...

wsh91 11y ago
An interesting topic, indeed. Check out this gem from Knuth, "The Dangers of Computer Science Theory": https://books.google.com/books?id=QUgmsMm5LcAC&lpg=PA189&ots=xmjDeT6VGz&dq=%22The%20dangers%20of%20computer-science%20theory%22%20knuth&pg=PA189#v=onepage&q=%22The%20dangers%20of%20computer-science%20theory%22%20knuth&f=false https://books.google.com/books?id=QUgmsMm5LcAC&lpg=PA189&ots... (Sadly, I can't find a free PDF. I've sen this in Selected Papers on the Analysis of Algorithms--you can get a used copy from Amazon for a few dollars.) "Is there any area (outside of numerical analysis) where mathematical theory has actually helped computer programmers?" Ironically enough, he mentions bubblesort's performance as better in theory than practice for the most part. :P
- hyperpape 11y ago
  Nice little speech, and his conclusion is much less inflammatory than your quote suggests (it would be strange if Knuth was really against mathematical theory). Reading his examples, I feel as if time has been kind to mathematical theory. n has gotten a lot larger these days, and random access memory also simplifies some analyses. That's not always true, and the gap he identifies is still real, but maybe it's not always as important as it was.
  - wsh91 11y ago
    I wasn't trying to suggest he was inflammatory! I think you'll find the paper as a whole is of that tone. :)

wsh91 11y ago

An interesting topic, indeed. Check out this gem from Knuth, "The Dangers of Computer Science Theory": https://books.google.com/books?id=QUgmsMm5LcAC&lpg=PA189&ots=xmjDeT6VGz&dq=%22The%20dangers%20of%20computer-science%20theory%22%20knuth&pg=PA189#v=onepage&q=%22The%20dangers%20of%20computer-science%20theory%22%20knuth&f=false https://books.google.com/books?id=QUgmsMm5LcAC&lpg=PA189&ots... (Sadly, I can't find a free PDF. I've sen this in Selected Papers on the Analysis of Algorithms--you can get a used copy from Amazon for a few dollars.) "Is there any area (outside of numerical analysis) where mathematical theory has actually helped computer programmers?" Ironically enough, he mentions bubblesort's performance as better in theory than practice for the most part. :P

hyperpape 11y ago
Nice little speech, and his conclusion is much less inflammatory than your quote suggests (it would be strange if Knuth was really against mathematical theory). Reading his examples, I feel as if time has been kind to mathematical theory. n has gotten a lot larger these days, and random access memory also simplifies some analyses. That's not always true, and the gap he identifies is still real, but maybe it's not always as important as it was.
- wsh91 11y ago
  I wasn't trying to suggest he was inflammatory! I think you'll find the paper as a whole is of that tone. :)