5 ms·

Advances in algorithms are a fundamental starting point, but I think it's a common mistake to conflate the efficiency of an algorithm in the abstract sense to h

Advances in algorithms are a fundamental starting point, but I think it's a common mistake to conflate the efficiency of an algorithm in the abstract sense to how those benefits are manifested in the applied sense. While true, all things held equal a new algorithm will advance the field, providing "gains" as you said, but it's false to assume that algorithms are more important than understand computer architecture, full stop. A simple example is dijkstra's algorithm vs bellman ford. Sure, in the abstract sense, the greed algorithm wins. However, it would be wrong to assume that dijkstra's algorithm is faster than bellman ford, because it's not. That's because dijkastra's algorithm doesn't parallelize as well, where as bellman ford parallelizes very well (and by "well" I mean it exploits the architecture - in a sense has "mechanical sympathy"). You end up creating very exotic data structures that are good for caching and stealing work from unused threads. There are many other examples, check out matrix matrix multiplication if your interested. I'm not making the argument that one is more important than the other, but I think it's a bit reductive to say algorithm only matter because there are so many examples of where computer architecture matters more (and vice versa). Another way to say what I mean is that ultimately reality matters. > The likes of Karp, Valiant, Cook, Blum, Vazirani, Papdimitriou, Micali, Goldwasser, Goldreich, Shamir, Rivest and etc.? I doubt these people know the inner workings of computers, but they have revolutionized our view of what it means to compute. Um, why would you think that they don't understand the inner workings of computers? Is that just your intuition or is that based on some practical knowledge? I'm not saying I know the answer (I haven't quizzed them), but since we're guessing here I'm going to say that they probably know a lot about the inner workings of computer - and there's no harm in us mortals trying to do the same. They probably don't know like specific things about how intel's branch prediction works or anything like that, but as a general concept, the inner workings of computers is pretty fundamental stuff and is very helpful to know, along with algorithms.

gravypod 10y ago
>common mistake to conflate the efficiency of an algorithm in the abstract sense to how those benefits are manifested in the applied sense > While true, all things held equal a new algorithm will advance the field, providing "gains" as you said > but it's false to assume that algorithms are more important than understand computer architecture, full stop I wish there were two like buttons. I have nothing to add that you haven't said better then I could have.
vram22 10y ago
>> The likes of Karp, Valiant, Cook, Blum, Vazirani, Papdimitriou, Micali, Goldwasser, Goldreich, Shamir, Rivest and etc.? I doubt these people know the inner workings of computers, but they have revolutionized our view of what it means to compute. >Um, why would you think that they don't understand the inner workings of computers? Yes, great point. I know of at least one person who seems to straddle both those worlds - Jon Bentley: https://en.wikipedia.org/wiki/Jon_Bentley_(computer_scientist) https://en.wikipedia.org/wiki/Jon_Bentley_(computer_scientis... He wrote Programming Pearls, More Programming Pearls, and Writing Efficient Programs. I own copies of either two or all three of those, and have read good amounts of the first two, and pretty close to the whole of the third (some years ago), which is out of print. A fantastic book (the first two are too). And the point here is that in the Efficient programs book, he goes into a lot of detail on performance improvement at the lower levels too, not just at the level of algorithms, though he covers that some too. And he has also invented algorithms (e.g. the Bentley–Ottmann algorithm). So he is an example that one can do/be both high-level and low-level. And of course, many more people do that, at a lower level of accomplishment (but still non-trivial), such as working with low-level languages (C, assembly) and doing perf tuning, as well as creating or improving algorithms and data structures for their work, high-level software design/architecture, etc.
Ar-Curunir 10y ago
Studying algorithms is independent from solving that problem practically; we know plenty of problems having an optimal solution that is impractical, and a "less-efficient" algorithm that is much more practical. This doesn't make the study of algorithms any less important. Thankfully, the initial study of algorithms (basic stuff like greedy and dynamic algorithms, etc) usually doesn't cover impractical algorithms, which makes it appropriate for new students. From my interactions with some of the names I mentioned, as well as from my (short) experience in the TCS community, I do not think it likely that many theoretical computer scientists remember what they learned in computer architecture class. I agree that it is useful to learn it; I was pushing back in the idea that learning architecture at the expense of the rest of computer science is a good idea.
Ar-Curunir 10y ago
Studying algorithms is independent from solving that problem practically; we know plenty of problems having an optimal solution that is impractical, and a "less-efficient" algorithm that is much more practical. This doesn't make the study of algorithms any less important. Thankfully, the initial study of algorithms (basic stuff like greedy and dynamic algorithms, etc) usually doesn't cover impractical algorithms, which makes it appropriate for new students. From my interactions with some of the names I mentioned, as well as from my (short) experience in the TCS community, I do not think it likely that many theoretical computer scientists remember what they learned in computer architecture class. I agree that it is useful to learn it; I was pushing back in the idea that learning architecture at the expense of the rest of computer science is a good thing.

gravypod 10y ago

>common mistake to conflate the efficiency of an algorithm in the abstract sense to how those benefits are manifested in the applied sense > While true, all things held equal a new algorithm will advance the field, providing "gains" as you said > but it's false to assume that algorithms are more important than understand computer architecture, full stop I wish there were two like buttons. I have nothing to add that you haven't said better then I could have.

vram22 10y ago

>> The likes of Karp, Valiant, Cook, Blum, Vazirani, Papdimitriou, Micali, Goldwasser, Goldreich, Shamir, Rivest and etc.? I doubt these people know the inner workings of computers, but they have revolutionized our view of what it means to compute. >Um, why would you think that they don't understand the inner workings of computers? Yes, great point. I know of at least one person who seems to straddle both those worlds - Jon Bentley: https://en.wikipedia.org/wiki/Jon_Bentley_(computer_scientist) https://en.wikipedia.org/wiki/Jon_Bentley_(computer_scientis... He wrote Programming Pearls, More Programming Pearls, and Writing Efficient Programs. I own copies of either two or all three of those, and have read good amounts of the first two, and pretty close to the whole of the third (some years ago), which is out of print. A fantastic book (the first two are too). And the point here is that in the Efficient programs book, he goes into a lot of detail on performance improvement at the lower levels too, not just at the level of algorithms, though he covers that some too. And he has also invented algorithms (e.g. the Bentley–Ottmann algorithm). So he is an example that one can do/be both high-level and low-level. And of course, many more people do that, at a lower level of accomplishment (but still non-trivial), such as working with low-level languages (C, assembly) and doing perf tuning, as well as creating or improving algorithms and data structures for their work, high-level software design/architecture, etc.

Ar-Curunir 10y ago

Studying algorithms is independent from solving that problem practically; we know plenty of problems having an optimal solution that is impractical, and a "less-efficient" algorithm that is much more practical. This doesn't make the study of algorithms any less important. Thankfully, the initial study of algorithms (basic stuff like greedy and dynamic algorithms, etc) usually doesn't cover impractical algorithms, which makes it appropriate for new students. From my interactions with some of the names I mentioned, as well as from my (short) experience in the TCS community, I do not think it likely that many theoretical computer scientists remember what they learned in computer architecture class. I agree that it is useful to learn it; I was pushing back in the idea that learning architecture at the expense of the rest of computer science is a good idea.

Ar-Curunir 10y ago