That's a terrible implementation of persistent data structures in Python. The author seems to have missed the point altogether. What an update operation on a persistent data structure should do is to return the new value to the client; it's up to the client to decide which versions to hold onto, allowing the rest to be garbage-collected. Also, what makes these work in practice is precisely that they don't do an O(n) copy of the data structure for every update! Instead they copy only O(log n) tree nodes.
How would you implement a Persistent Stack in Python to copy only O(log n) tree nodes (unless you're referring to the BST implementation by the person)? I tried to look for implementations online but there doesn't seem to be much available.
In the best case, I would probably implement persistence to store the difference between versions. But I figured in this case, the simpler approach would be better as an introduction to the idea.
If you have any recommendations, I would love to feature them/improve this piece.
There's a whole literature on this topic. Chris Okasaki published a book about it back in 1996, but there have been advances since then. Probably the simplest approach -- which is still not very simple -- is functional red/black trees. These are similar to the familiar imperative ones, except that they rebalance by creating new nodes. My own implementation for Common Lisp (https://github.com/slburson/fset) uses an older data structure called weight-balanced binary trees. But it was Phil Bagwell's invention of the Hash Array-Mapped Trie in about 2005 that really got people excited; it's an exceedingly clever design that is used in Clojure and, IIRC, Scala. But even that has been improved on; the latest I'm aware of is something called CHAMP, but I forget the author's name. Anyway, search for "Bagwell HAMT" and you'll find stuff.
That's a terrible implementation of persistent data structures in Python. The author seems to have missed the point altogether. What an update operation on a persistent data structure should do is to return the new value to the client; it's up to the client to decide which versions to hold onto, allowing the rest to be garbage-collected. Also, what makes these work in practice is precisely that they don't do an O(n) copy of the data structure for every update! Instead they copy only O(log n) tree nodes.
I hope you can find a better example.
Thank you for the input. Few questions-
How would you implement a Persistent Stack in Python to copy only O(log n) tree nodes (unless you're referring to the BST implementation by the person)? I tried to look for implementations online but there doesn't seem to be much available.
In the best case, I would probably implement persistence to store the difference between versions. But I figured in this case, the simpler approach would be better as an introduction to the idea.
If you have any recommendations, I would love to feature them/improve this piece.
Always appreciate your inputs
There's a whole literature on this topic. Chris Okasaki published a book about it back in 1996, but there have been advances since then. Probably the simplest approach -- which is still not very simple -- is functional red/black trees. These are similar to the familiar imperative ones, except that they rebalance by creating new nodes. My own implementation for Common Lisp (https://github.com/slburson/fset) uses an older data structure called weight-balanced binary trees. But it was Phil Bagwell's invention of the Hash Array-Mapped Trie in about 2005 that really got people excited; it's an exceedingly clever design that is used in Clojure and, IIRC, Scala. But even that has been improved on; the latest I'm aware of is something called CHAMP, but I forget the author's name. Anyway, search for "Bagwell HAMT" and you'll find stuff.