Ordered dictionaries compared

[Dan Stromberg]

On Thu, May 23, 2013 at 9:41 AM, duncan smith <buzzard at invalid.invalid>wrote:

>
> RBT is quicker than Treap for insertion with randomized data, but slower
> with ordered data. Randomized data will tend to minimize the number of tree
> rotations needed to keep the RBT balanced, whilst the Treap will be
> performing rotations to maintain the heap property in an already reasonably
> well balanced tree. With ordered data the RBT will have to work harder to
> keep the tree balanced, whilst the Treap will be able to maintain the heap
> property with fewer rotations.
>
> No surprise that find() is generally quicker for RBTs, they tend to be
> better balanced.
>
> Deletion is a bit more confusing. I suppose deletion from a better
> balanced tree will tend to be quicker, but deletion from a treap
> constructed from ordered data is (for some reason) quickest of all.
>
> All these operations require a call to find(), and that is generally going
> to be quicker for RBTs. Treaps tend to require fewer subsequent rotations,
> but they have variable worth (in terms of rebalancing).
>
> Looks like RBTs are better than treaps if they are being populated with
> randomly ordered data, but not if they are being populated with ordered
> data. RBTs are better for use cases that are heavy on finds.
>
> Both types of tree appear to be better balanced (on the basis of the find
> results) if populated from ordered data. Treaps appear to perform better on
> insertion, find and deletion when populated from ordered data.
>

Strange.  I was comparing randomized data (95% get, 50-50 get and set, 95%
set) when I found that treaps were quite a bit faster than red black trees.

The code I used is here:
http://stromberg.dnsalias.org/svn/python-tree-and-heap-comparison/trunk/

See also
https://en.wikipedia.org/wiki/Binary_search_tree#Performance_comparisons ,
which found that treaps were faster on average the red black trees.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20130523/42d5f821/attachment.html>