3 ms·
I can see two legitimate cases for writing very short, very dense code. 1: Implement an algorithm in a very concise and straightforward, even if not very effic
by nine_k 12y ago
I can see two legitimate cases for writing very short, very dense code.
1: Implement an algorithm in a very concise and straightforward, even if not very efficient, way. An example is the classic quicksort in Haskell, which most literally implements the idea of the algorithm:
qsort [] = []
qsort (p:xs) = qsort [ y | y <- xs, y < p ] ++ [p] ++
qsort [ y | y <- xs, y >= p ]
2: Implement an algorithm in a super-efficient, while non-obvious, way. An example is the inverse square root calculation made by famous by John Carmack (http://www.codemaestro.com/reviews/9 http://www.codemaestro.com/reviews/9).
The linked hashtable implementation, to my mind, is neither very elegant nor fiendishly clever, nor even reasonably correct.
- taeric 12y agoThere is something funny about stating that most "literally" implements the idea of the algorithm, when the main "idea" of the algorithm is to be quick. :) Also, even in examples of super efficient ways, be wary. The inverse square root you are referring to is actually slower than what many CPUs can do with a single instruction nowdays. Also, I think you are missing out on the main reason this code was written. Essentially a puzzle to see if it can be done.
- foota 12y agoJust because it's one instruction doesn't make it faster
- to3m 12y agoIn the case of a reciprocal square root estimate it probably is, particularly compared to the code given. A fast reciprocal square root estimate function usually takes less than 5 cycles - and is less than 1/4096th out, so the accuracy is better too.