> On Mar 16, 2020, at 00:13, Ben Rudiak-Gould <benrud...@gmail.com> wrote: > > On Sun, Mar 15, 2020 at 9:41 PM Andrew Barnert via Python-ideas > <python-ideas@python.org> wrote: >> Do you really want to require “binary”? > > I don't think so; they never talked about binary trees, only "binary > search tree semantics." It could alternately be called autobalanced > tree semantics or something.
Why not just leave “tree” out of it? All logarithmic search containers are technically equivalent to some kind of tree, but try actually describing a skiplist’s operations in terms of how the equivalent tree is rebalanced. It’s a lot easier to just show that the skiplist’s operations are logarithmic in its own terms. >> Sorted Containers, that implemented the consensus API (largely based on >> blist’s). > > One feature blist has that sortedcontainers seems to lack is O(1) > copies. It would be nice to have that in a standard library. You don’t get O(1) copies for list, or dict, so why would you expect them for sorteddict? People who want data-sharing vectors go grab numpy instead of using the builtin list type. 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. > 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. (By the way, Python already has a similar HAMT implementation, and it may be exposed for user code in 3.9; see PEP 603.) _______________________________________________ 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/5MGCA4GQSHRN3LRAZMMR6OAQLDOK4QNO/ Code of Conduct: http://python.org/psf/codeofconduct/
