Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CAGGBd_qDRdWQHVm-=qEfK8qKVdMsD8WjuPtDQ3nEaGia55SvrQ@mail.gmail.com>
References: <lennh4$kpm$1@cabale.usenet-fr.net> <CAPTjJmomgZSFj7TanBn8_qXP4ULhCm85abJ5=2PcikXJkrH6GQ@mail.gmail.com> <CAN1F8qU8AJ+Z-Rb4+wGsYWd_bS5aOA3bsjd5NjF46MUvnecSeQ@mail.gmail.com> <mailman.7473.1393598638.18130.python-list@python.org> <XnsA2E95FA1E1EB6duncanbooth@127.0.0.1> <bnvctpF5vanU1@mid.individual.net> <mailman.7920.1394252278.18130.python-list@python.org> <87eh2d3x8h.fsf_-_@elektro.pacujo.net> <CAGGBd_qU3Zp3A4pymnDQfWynWZwFVrdHJpG=U0WZTap4HiymdA@mail.gmail.com> <lffv32$mqo$1@ger.gmane.org> <mailman.8154.1394846042.18130.python-list@python.org> <87mwgoqy4k.fsf@elektro.pacujo.net> <CAGGBd_qDRdWQHVm-=qEfK8qKVdMsD8WjuPtDQ3nEaGia55SvrQ@mail.gmail.com>
From: Daniel Stutzbach <stutzbach@google.com>
Date: Tue, 18 Mar 2014 13:18:40 -0700
Subject: Re: Balanced trees
To: Dan Stromberg <drsalists@gmail.com>
Content-Type: multipart/alternative; boundary=047d7b675bf05ce3be04f4e740d8
Cc: Python List <python-list@python.org>, Marko Rauhamaa <marko@pacujo.net>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.8259.1395173969.18130.python-list@python.org>
Lines: 43
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:68515

--047d7b675bf05ce3be04f4e740d8
Content-Type: text/plain; charset=UTF-8

On Tue, Mar 18, 2014 at 12:26 PM, Dan Stromberg <drsalists@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

--047d7b675bf05ce3be04f4e740d8
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On T=
ue, Mar 18, 2014 at 12:26 PM, Dan Stromberg <span dir=3D"ltr">&lt;<a href=
=3D"mailto:drsalists@gmail.com" target=3D"_blank">drsalists@gmail.com</a>&g=
t;</span> wrote:<br>

<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div class=3D"">In short, blist.sorteddict d=
idn&#39;t do that well, despite being in C.<br></div></blockquote><div><br>=
</div>

<div>blist.blist is written in C, but blist.sorteddict is written in Python=
 on top of blist.blist. =C2=A0It won&#39;t perform as well as a class writt=
en entirely in C that has similar asymptotic properties. =C2=A0If the objec=
ts in the tree are non-trivial (i.e., not a built-in type), the cost of cal=
ling the __lt__ method may be more important than the choice of blist vs. A=
VL tree, but I haven&#39;t tested it.</div>

</div><div><br></div>-- <br>Daniel Stutzbach
</div></div>

--047d7b675bf05ce3be04f4e740d8--