> 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? Barry > > 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/ _______________________________________________ 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/QG3XO3DR5HLFUIG34T3LXOJCJMIYEE54/ Code of Conduct: http://python.org/psf/codeofconduct/
