5 ms·
How would you implement a fast diff that didn't involve looking at each text value anyways? Would there be a separate store in the structure that tracks changes
by epmatsw 11y ago
How would you implement a fast diff that didn't involve looking at each text value anyways? Would there be a separate store in the structure that tracks changes, or something along those lines?
- amelius 11y agoYou can do this by skipping over shared sub structures, while comparing, for example.
- epmatsw 11y agoI don't see how that is related to immutability. Immutability gives you the ability to verify that it's unchanged in O(1), but it doesn't change your ability to do optimizations like that...
- amelius 11y agoWell, immutable data-structures use "structural sharing", internally. Search for it. For example, this image, [1], shows two data-structures (the green nodes), that internally share many nodes. Now, comparing those two structures can be done efficiently, because the shared parts don't need comparing. [1] http://eclipsesource.com/blogs/wp-content/uploads/2009/12/clojure-trees.png http://eclipsesource.com/blogs/wp-content/uploads/2009/12/cl... (a random image I found on the internet that illustrates my point)
- epmatsw 11y agoWouldn't that be an argument for using an immutability library then? If you can implement a shallow equality that takes shared structures into account, what about non-immutable structures makes them a more efficient option for such a thing?