5 ms·
The conclusion contains an interesting question: Will the ultimate search for asymptotically fastest programs typically lead to fast or slow programs for a
by qsort 5y ago
The conclusion contains an interesting question:
Will the ultimate search for asymptotically fastest programs typically lead to fast or slow programs for arguments of practical size? Levin search, matrix multiplication and the algorithm Mp∗ seem to support the latter, but this might be due to our inability to do better.
Asymptotic complexity analysis is kind of broken, there's more of a tradeoff in using different algorithms than "\Theta(n) is better than \Theta(n \log n)" would indicate.
I wonder if a better framework exists, but that's probably several open research topics bundled in a single question.
- deleted 5y ago[deleted]
- tlb 5y agoYes, it offends my aesthetic sense when the asymptotically fastest algorithms for simple problems are complex monsters. It didn't used to be like that: early fast algorithms (like heapsort and FFT) are only very slightly more complex than the naive ones.
- anon_tor_12345 5y agolol cooley-tukey FFT is anything but simple when you actually have to implement it.
- Greek0 5y agoCooley-Tukey Fast Fourier Transform can be complex to implement, if you want to optimize it. A basic version is surprisingly simple, I implemented it for fun in Python a couple of years ago: def fft(x): N = len(x) if N == 1: return x assert N % 2 == 0 E = fft(x[::2]) O = fft(x[1::2]) X = [None] * N for k in range(N // 2): tf = np.exp(-2j * np.pi * k / N) X[k] = E[k] + tf * O[k] X[k + N//2] = E[k] - tf * O[k] return X The Wikipedia article describing it is surprisingly decent: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algor...
- klyrs 5y agoComputer science was a new branch of mathematics 100 years ago. Folks discovered the easy, low-lying algorithms. I don't know about you, but I've rediscovered quite old results that are named so-and-so's algorithm or what's-their-face's theorem; because they were the obviously efficient ways of solving those problems. Supposing P=NP, one would expect the polytime algorithm to be brain-meltingly complex. Same goes for, say, a n^2log(n) matrix multiplication algorithm. Simplification is a really good strategy for optimizing algorithms. But sometimes, doing less work requires doing a bit of thinking upfront, or carefully cleaning up behind yourself (but not cleaning too eagerly).
- asimpletune 5y agoI really don’t understand why this is being downvoted. Beyond trivial algorithms, as mentioned in the parent, fast algorithms come from deep knowledge of the problem, leading to highly tailored data structures, and thus very complicated algorithms. I’m not sure why this is controversial? Also citing aesthetic sensibility is fine, but it’s also fine to update or recalibrate one’s aesthetic intuition.
- shmageggy 5y agoFTA: > This work could be viewed as another O() warning showing how important factors and even subdominant additive terms are.
- Strilanc 5y agoI remember showing a coworker a complexity analysis I did, where I'd written "0.002 n lg n + 3n". I was surprised when they asked "why did you put the insignificant one first?" but then realized... that's exactly right! Even for universe sized problems, 3n is more than 0.002 n lg n. Basically, as soon as you care enough about constant factors to actually compute them, some of your habits from doing asymptotic analysis can be actively harmful.