Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <519e46c0$0$26690$862e30e2@ngroups.net>
References: <mailman.1989.1369279892.3114.python-list@python.org> <519e46c0$0$26690$862e30e2@ngroups.net>
Date: Thu, 23 May 2013 10:44:53 -0700
Subject: Re: Ordered dictionaries compared
From: Dan Stromberg <drsalists@gmail.com>
To: Python List <python-list@python.org>
Content-Type: multipart/alternative; boundary=20cf3074afe066f32504dd663d7f
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.2024.1369331102.3114.python-list@python.org>
Lines: 96
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:45826

--20cf3074afe066f32504dd663d7f
Content-Type: text/plain; charset=ISO-8859-1

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.

--20cf3074afe066f32504dd663d7f
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><div class=3D"gmail_quote">=
On Thu, May 23, 2013 at 9:41 AM, duncan smith <span dir=3D"ltr">&lt;<a href=
=3D"mailto:buzzard@invalid.invalid" target=3D"_blank">buzzard@invalid.inval=
id</a>&gt;</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0pt 0pt 0pt 0.8ex;border-=
left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
RBT is quicker than Treap for insertion with randomized data, but slower wi=
th ordered data. Randomized data will tend to minimize the number of tree r=
otations needed to keep the RBT balanced, whilst the Treap will be performi=
ng rotations to maintain the heap property in an already reasonably well ba=
lanced 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.<br>

<br>
No surprise that find() is generally quicker for RBTs, they tend to be bett=
er balanced.<br>
<br>
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 o=
rdered data is (for some reason) quickest of all.<br>
<br>
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).<br>
<br>
Looks like RBTs are better than treaps if they are being populated with ran=
domly ordered data, but not if they are being populated with ordered data. =
RBTs are better for use cases that are heavy on finds.<br>
<br>
Both types of tree appear to be better balanced (on the basis of the find r=
esults) if populated from ordered data. Treaps appear to perform better on =
insertion, find and deletion when populated from ordered data.<span class=
=3D""><font color=3D"#888888"><br>
</font></span></blockquote><div>=A0</div><div>Strange.=A0 I was comparing r=
andomized data (95% get, 50-50 get and set, 95% set) when I found that trea=
ps were quite a bit faster than red black trees. <br></div></div><br>The co=
de I used is here: <a href=3D"http://stromberg.dnsalias.org/svn/python-tree=
-and-heap-comparison/trunk/">http://stromberg.dnsalias.org/svn/python-tree-=
and-heap-comparison/trunk/</a><br>
<br></div><div class=3D"gmail_extra">See also <a href=3D"https://en.wikiped=
ia.org/wiki/Binary_search_tree#Performance_comparisons">https://en.wikipedi=
a.org/wiki/Binary_search_tree#Performance_comparisons</a> , which found tha=
t treaps were faster on average the red black trees.<br>
<br><br></div></div>

--20cf3074afe066f32504dd663d7f--