3 ms·
For a fun mutable algorithm to test this with, I'd be interested in seeing an implementation of Knuth's Dancing Links. For that matter, I'm curious on any perf
by taeric 12y ago
For a fun mutable algorithm to test this with, I'd be interested in seeing an implementation of Knuth's Dancing Links.
For that matter, I'm curious on any performance comparisons between algorithms such as the DLX and any "FP" equivalent. This already exist?
- jerf 12y agoSticking to traditional computer science (i.e., ignoring constants, caching, and other details, and just sticking to Big-O analysis), it is easy to show, or indeed easy to simply see that any mutable algorithm can be represented in a purely functional way by creating a balanced tree that represents memory and can be written to and read from by index. All reading and writing operations that treat the tree as simply an expanse of RAM are O(log n), vs. O(1) of direct RAM access. Therefore, pure functional programs can simulate any impure algorithm with a slowdown no worse than a log n factor. Again, let me emphasize this is a worst-case analysis. Many common algorithms are equivalent regardless, and that's part of the reason tel specifically names Union/Find as such an algorithm, as it's actually somewhat rare to encounter one where there isn't a Big-O equivalent algorithm that is pure. Pure functional algorithms often require some modestly clever amortization to get there, but that's perfectly valid both in theory and in practice (many beloved "imperative" structures have amortized complexities, too, including such basics as a hash table). In practice pure functional can sometimes come with larger constants; whether they hit you in practice depends on your use case and, often, sensitivity to garbage collection pauses. In light of all that, I think it would be fair to say that your question is somewhat ill-defined. You can really only compare particular algorithms against each other, because there's no trivial equivalence between "imperative" and "pure functional" algorithms. Plus, the barrier between the two in practice is quite fungible... especially in a garbage-collected imperative language nothing stops you from using a "functional" algorithm, and every practical "functional" language will give you a way of running "imperative" algorithms directly. (Yes, even Haskell. But tel is building up to that. I won't give it away yet. Stay tuned.)
- taeric 12y agoMy question may have been ill defined, but your answer was awesome. :) I have to confess your "easy to show/see" isn't immediately obvious to me yet. However, that is as likely because I haven't tried hard to see as anything else. This post is between other things I'm trying to get done. Poorly already, digging into this is something I fear would not help. I am interested, though, so more pointers and explanations would be greatly appreciated.
- deleted 12y ago[deleted]
- dllthomas 12y agoRegarding the "easy to see": 1) Take your algorithm that involves updates to memory. 2) Split it up so that "memory" is represented by an ADT - in the original imperative setting, it's logically a hash table - O(1) read and write. 3) Replace that ADT with a binary tree. Now you have O(lg(n)) read and write. 4) If the previous algorithm was O(f(n)), it can't do any particular thing more than O(f(n)) times, including memory access. So in the worst case, you've made O(f(n)) things take O(lg(m)) times as long, so the new algorithm must be in O(f(n) * lg(m)).
- taeric 12y agoAh, I think I see what you mean. Seems the constants being ignored could be massive. Are there any comparisons saying how things compare in practice? (Similar to how heapsort is typically not used, even though it has among the better Big O values, right?)
- dllthomas 12y agoRight, this particular approach is most interesting as an easy upper bound. Constants are always highly situation dependent. If you are replacing a single memory lookup with a tree traversal, that's going to be a huge difference. If, for some reason, access to your mutable variables is already an expensive operation, it might not make much difference at all. If you need to take periodic snapshots of your world state, the mutation-free version might come out way ahead sharing portions of the tree that don't need to be copied.