Paul Rubin wrote:
João Valverde <backu...@netcabo.pt> writes:
Could you clarify what you mean by immutable? As in... not mutable? As
in without supporting insertions and deletions?
Correct.
That's has the same performance as using binary search on a sorted
list. What's the point of using a tree for that?
The idea is you can accomplish the equivalent of insertion or deletion
by allocating a new root, along with the path down to the place you
want to insert, i.e. O(log n) operations. So instead of mutating an
existing tree, you create a new tree that shares most of its structure
with the old tree, and switch over to using the new tree. This
trivially lets you maintain snapshots of old versions of the tree,
implement an "undo" operation, have a background thread do a complex
operation on a snapshot while the foreground thread does any number of
update-and-replace operations, etc.
Interesting, thanks. The concept is not difficult to understand but I'm
not sure it would be preferable. A copy operation should have the same
cost as a "snapshot", undo is kind of redundant and multithreading...
don't see a compelling use that would justify it. Also the interface is
a mapping so it'd be rather nice to emulate dict's.
Have you considered how the syntax would work in Python by the way? This:
new_tree = old_tree.insert(object)
Just looks wrong. The interface should support non functional idioms too.
--
http://mail.python.org/mailman/listinfo/python-list
