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. That said, it's possible that blist does something that's faster but more complicated. I haven't looked. > > pyrsistent has O(1) copying and is maintained but it's terribly slow and > > the interface is nonstandard (Haskellish instead of Pythonic). > > It’s also neither sorted nor mutable, which means it’s pretty far from what > you’re looking for here. The distinction between mutability and immutability is an illusion. You can convert a blist-style data structure into a pyrsistent-style data structure with a wrapper that takes an O(1) copy of its internal blist object, mutates it, wraps it, and returns it. You can convert a pyrsistent-style data structure into a blist-style data structure with a wrapper that maintains an internal pyrsistent object and overwrites it with the modified copy after each operation. The complexity of the operations is unaffected and the underlying implementations can be identical. The key to this equivalence is the O(1) copying of the mutable version. Pyrsistent could switch to a blist backend but not to a sortedcontainers backend unless sortedcontainers added that operation. You're right that blist and pyrsistent don't have the same functionality as they stand. Pyrsistent's PMap and PSet are sorted but don't allow duplicates. The equivalent (modulo interface translation) of blist.sortedlist would be pyrsistent.PMultiSet. _______________________________________________ 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/FYK4IJKS5ZGVMKFDFNYVQLDM4N6RLP4D/ Code of Conduct: http://python.org/psf/codeofconduct/
