On Mar 16, 2020, at 10:39, Barry <ba...@barrys-emacs.org> wrote: > > >>> On 16 Mar 2020, at 14:43, Ben Rudiak-Gould <benrud...@gmail.com> wrote: >>> >>> On Mon, Mar 16, 2020 at 12:57 AM Andrew Barnert <abarn...@yahoo.com> wrote: >>> Even if the extra indirection overhead turns out not to be an issue, just >>> from the added complexity (to every possible implementation) it seems like >>> it would be a bad idea to make that a requirement. >> >> The only change needed to support O(1) copy is making modified copies >> of nodes instead of mutating them in place. The algorithms are >> otherwise the same. > > So when I insert into the copy how do you avoid all the nodes being modified?
You copy the node being inserted and all logN nodes on the path from there back to the root. Which doesn’t affect the algorithmic complexity, since insert is already amortized log N anyway. In practice this deep copy-on-write can be substantially more expensive, but depending on your usage patterns there are also cases where it can be a lot cheaper. (Most extremely, imagine you make a ton of unnecessary copies and never mutate any of them; obviously the CoW wins…) I don’t know why blist chose to go one way and Sorted Containers the other, but knowing the authors involved, I suspect they both thought about it and had good arguments for it with benchmarks and everything, so I don’t think it’s worth trying to re-argue from first principles without someone looking first. At any rate, I still stand by the point that nobody is going to expect O(1) copies for sorteddict when list, dict, etc. don’t do it. _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/ER7I4FKQ3G2MFGAIOWAGWQBAQ6ZA6JN6/ Code of Conduct: http://python.org/psf/codeofconduct/
