3 ms·
Not absolutely necessary. One could use a persistent data structure, where the copy shares structure with the original. Of course even this has its cost, but it
by lucian1900 14y ago
Not absolutely necessary. One could use a persistent data structure, where the copy shares structure with the original. Of course even this has its cost, but it makes mutable state much, much less necessary.
- DanWaterworth 14y agoIt's also true that what looks like creating a new value may be optimized by the compiler to update in place.
- bunderbunder 14y agoFor simple structures or situations with low performance needs, yes definitely. But the classic example of a data type for which persistent structures have a hard time cutting the mustard is an associative array. With mutability you get hash tables, which I assume need no introduction. With persistent data structures you're generally stuck with some sort of balanced tree that has O(log n) lookup time in the best case, O(log n) insert time (and memory allocations) in the average case, a lot of pointer overhead, and absolutely depressing locality of reference.
- DanWaterworth 14y agoOr a HAMT with O(1) time operations.
- dllthomas 14y ago> absolutely depressing locality of reference. If a hashtable gives you good locality of reference, your hash function isn't working :-P But yes, obviously you're hitting more nodes in the tree typically, so you're paying a larger price for being cache-unfriendly.