[Python-Dev] collections.sortedtree

[Daniel Stutzbach]

On Fri, Mar 28, 2014 at 2:54 PM, Marko Rauhamaa <marko at pacujo.net> wrote:

> The blist implementation, which I have taken a quick glance at,
>
buys cache locality at the price of block copying; I have no data to
> decide if the tradeoff is a good one.
>

There's actually a compile-time parameter so that you can tune the tradeoff
by adjusting how wide each of blist's nodes are. Like most tradeoffs,
whether it's good or bad depends on what you're trying to do.  RedBlack
trees are very similar to a B-tree with a node-width of 4:
http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Analogy_to_B-trees_of_order_4

blist's sorteddict is written in Python on top of the blist type (which is
written in C).  Because of the Python layer, it's slower by a constant
factor compared to pure-C implementations in microbenchmarks.

-- 
Daniel Stutzbach
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20140328/56fe8385/attachment.html>