Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #45826

Re: Ordered dictionaries compared

Show all headers | View raw

[Multipart message — attachments visible in raw view] - view raw

On Thu, May 23, 2013 at 9:41 AM, duncan smith <buzzard@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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Ordered dictionaries compared Dan Stromberg <drsalists@gmail.com> - 2013-05-22 20:31 -0700
  Re: Ordered dictionaries compared duncan smith <buzzard@invalid.invalid> - 2013-05-23 17:41 +0100
    Re: Ordered dictionaries compared Dan Stromberg <drsalists@gmail.com> - 2013-05-23 10:44 -0700
      Re: Ordered dictionaries compared duncan smith <buzzard@invalid.invalid> - 2013-05-24 00:57 +0100

csiph-web