4 ms·
I don't think so. I think he is pointing out a really, really important thing that many overlook because of the way we have come to teach computer science. Whe
by mcherm 11y ago
I don't think so. I think he is pointing out a really, really important thing that many overlook because of the way we have come to teach computer science.
When evaluating different algorithms, there are lots of criteria we could use. How often is it correct? How long does it take to run? How difficult is it for people to read? How often does it use the letter "r" which happens to be broken on my keyboard?
Computer science made ENORMOUS strides by picking out a specific criterion (running time on the computers of the time) and finding a way to make it mathematically rigorous (asymptotic performance analysis, Big-O notation, and all of the related mechanisms that we learn in computer science classes). This was TREMENDOUSLY valuable, and by turning the whole power of mathematical analysis loose on the problem it formed the modern field of algorithm analysis and completely transformed how we build computers.
But we need to remember that this is base on one particular simplification of how computers work. It assumes a Von-neuman architecture where execution steps are the key criterion. We have extended this framework to consider things like parallel execution... that was fruitful also. More recently, we've been noticing that our actual machines are no longer dominated by the "steps" in the algorithm, but most often are dominated by memory usage, so we have turned the same formalism onto the use of memory -- but still (in my opinion) lack a rigorous approach for analyzing the combination of steps taken and memory usage.
Even more significant is the fact that there are OTHER things we could trade off. One of those is accuracy. Look at some of the research on probabilistic algorithms: you will find that there are some incredible gains to be made with losses in accuracy that are well within the bounds of what are acceptable for most uses. Yet this isn't covered in an introductory computer science course, so many programmers are not even aware of the option. With so much of traditional algorithm analysis already mapped out by the past several decades of researchers, much of the fertile ground in the near future will, I believe, lie in investigating these other sorts of tradeoffs.
- CHY872 11y agoNo - there are many fruitful formalisations of parallel programming (the CLRS chapter is pretty good) and indeed, of non-von Neumann architectures (check out balancing, comparison networks etc etc). This sort of work is not reliant on von-Neumann - it quantifies the amount of work you need to do. Coincidentally, the algorithm listed parallelises very well; it has a good span. Of course it is useful to avoid galactic algorithms, but the article is totally correct. It would be incorrect to read its conclusion as anything but what it actually says. As a general principle, sure, but it shouldn't be a criticism of this article.