Balanced trees
Daniel Stutzbach
stutzbach at google.com
Tue Mar 18 16:18:40 EDT 2014
On Tue, Mar 18, 2014 at 12:26 PM, Dan Stromberg <drsalists at gmail.com> wrote:
> In short, blist.sorteddict didn't do that well, despite being in C.
>
blist.blist is written in C, but blist.sorteddict is written in Python on
top of blist.blist. It won't perform as well as a class written entirely
in C that has similar asymptotic properties. If the objects in the tree
are non-trivial (i.e., not a built-in type), the cost of calling the __lt__
method may be more important than the choice of blist vs. AVL tree, but I
haven't tested it.
--
Daniel Stutzbach
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20140318/7f955dcb/attachment.html>
More information about the Python-list
mailing list