3 ms·
Regarding 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 origina
by dllthomas 12y ago
Regarding 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.
- taeric 12y agoI'm not sure how the periodic snapshot would "come out ahead" with the mutation free version. Seems the best you could claim is it wouldn't be as far behind as one might think. Unless periodic equals every change. In which case I would expect they could be equal. (That is, the extra work required to make it "mutation free" is extra work. Unless all of the extra work is required, it is hard to see how that version would "come out ahead.") And this is why I particularly asked about the DLX algorithm. It is specifically made for rapid backtracking. Reading briefly [1] shows that it was even made parallel to speed it up. ("made it parallel" is a gross simplification of course.) Is a very interesting read on methods to make a heavily mutation based algorithm parallel. [1] http://did.mat.uni-bayreuth.de/wassermann/allsolutions.ps.gz http://did.mat.uni-bayreuth.de/wassermann/allsolutions.ps.gz
- dllthomas 12y ago'I'm not sure how the periodic snapshot would "come out ahead" with the mutation free version.' A snapshot of freely mutated memory is a O(N) copy. A snapshot of a immutable tree is a single O(1) pointer copy (you just need to save the root). Doing a full copy every change would be tremendously costly (substantially more than the penalty for walking the tree on that change, and probably overwhelming the overhead ofr walking the tree on reads). Doing a full copy every hojillion steps would of course amortize to cheap (and probably the overhead from walking a tree for reads and writes would overwhelm it). Anything real will of course fall somewhere between. As I said, constants are tremendously context dependent. Note that this (of course) doesn't speed up the mutation free version - but if you have the constraint of wanting regular (or otherwise cheap) snapshots then using the mutation-free version can be the cheapest way of doing that. I don't know the details of the DLX algorithm, or adaptations to it, well enough to say much about it in particular off the top of my head. I'd love to dig into it at some point, but I've unfortunately got higher priorities presently.
- taeric 12y agoThis is assuming a very naive snapshot of a mutated memory block. I would assume that if you were doing something that needed snapshots of each instant of the program, you would come up with a much more sane algorithm for getting that done. It would probably use many of the same tricks as the immutable structures. Which is why I would assume they would be equal. (That is, I realize that immutable structures don't do a full copy on every "change." Depending on the structure and the change, they don't even do a copy at all.) Consider, we basically just described how git works, no?
- dllthomas 12y agoWell, certainly nothing stops you from using the immutable version and calling it mutable (it just happens to do no mutation!). But my point is that it's a nontrivial modification compared to other approaches to enabling snapshotting, and it's a good tool to have in your belt for that kind of situation. Particularly interesting, genuinely "persistent" data structures (as used by Okasaki in Purely Functional Data Structures - which is a fantastic read and tons of fun) can give amortized worst-case bounds even in the presence of a malicious consumer of the data structure picking which operations to run against which historical versions of the object.