4 ms·

Please don't misunderstand my post as an attack on research that has a more theoretical impact. What I'm saying is that if you claim to have found a faster vers

by anaphor 12y ago

Please don't misunderstand my post as an attack on research that has a more theoretical impact. What I'm saying is that if you claim to have found a faster version of some algorithm, then it should actually be true (preferably with working code). I have no problem with people showing a theoretically better version as long as they explain whether or not it's useful in practice. Also I would point out that as computers get faster things that were suboptimal before become feasible and begin to outperform the tricks people used before. A good example would be spellchecking, which had to be done using a wide array of cleverness but now we can just throw tons of computing power at it and get better results.

CHY872 12y ago
I believe the mistake to be yours. Algorithms is a largely theoretical field - when an algorithms researcher comes up with an algorithm with a lower asymptotic bound, that's all he or she is claiming - they're making no statements about its practical utility or the performance of an implementation. An implementation will almost certainly be provided, but that's besides the point. An explanation of why it's useful in practice is again totally besides the point - and really would be taken to be rather insulting by many researchers - the motivations are often largely theoretical. As a case in point, the fibonacci queue noted by OP was motivated by reducing the theoretical worst-case asymptotic complexity of Dijkstra's algorithm, and does that very - no benefit intended at all for normal programmers. If people do not know what big-O means, that's their own problem. The algorithms people do their research, and their papers are published in the context of an informed reader - if someone does not know the definition of big-O and make mistakes based on it, the time wasted by them is probably their own fault. In the case of this article, it seems as though the code originally ran in 200ms. This seems like a very acceptable amount - and one that would be improved more by using an algorithm like A* with decent heuristics than by simply trying to do the same work in less time.

by anaphor 12y ago

CHY872 12y ago

I believe the mistake to be yours. Algorithms is a largely theoretical field - when an algorithms researcher comes up with an algorithm with a lower asymptotic bound, that's all he or she is claiming - they're making no statements about its practical utility or the performance of an implementation. An implementation will almost certainly be provided, but that's besides the point. An explanation of why it's useful in practice is again totally besides the point - and really would be taken to be rather insulting by many researchers - the motivations are often largely theoretical. As a case in point, the fibonacci queue noted by OP was motivated by reducing the theoretical worst-case asymptotic complexity of Dijkstra's algorithm, and does that very - no benefit intended at all for normal programmers. If people do not know what big-O means, that's their own problem. The algorithms people do their research, and their papers are published in the context of an informed reader - if someone does not know the definition of big-O and make mistakes based on it, the time wasted by them is probably their own fault. In the case of this article, it seems as though the code originally ran in 200ms. This seems like a very acceptable amount - and one that would be improved more by using an algorithm like A* with decent heuristics than by simply trying to do the same work in less time.