From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-yw0-f173.google.com ([209.85.161.173]) by ur; Mon Dec 12 01:38:42 EST 2016 Received: by mail-yw0-f173.google.com with SMTP id r204so57882165ywb.0 for <9front@9front.org>; Sun, 11 Dec 2016 22:38:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=fAwpNVBpzGrde9hQsJ/6M9yoNeh8ng7hruu8cj1CMxM=; b=xyUSmrVzNjBhrhrB528g3iWVdNSQ2BAkPMgG1I+VJZ75yTAfiQlvCcqVcKDPdhsuhI TzZDUw/IXpTuojC78m6U90L0N43KJgeh0aUq3BHUPCO7dP+6igqu8gJpncXaRwolAx4C AJqHXXxl8k6ZfxTNGuOUZsukF+3Os7ell1RTLoqsmhHhql8EN52mrMfAIVGdKSA/sv2K p7bsHaOIGU5hWfnxdda+nTRaUsPo+uUzhzMu6kul26NB5RhkxtQkb3cZIITAN6C/I7T8 9f1eN8w4ZOl5t0E5FM9b/N1unjuF4HMKCRXn4eJqORhe1/LVtnK1NZ/yPbA6X5it/JGe WVog== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=fAwpNVBpzGrde9hQsJ/6M9yoNeh8ng7hruu8cj1CMxM=; b=VZERjYrcF3uKxtDrQOT4e7pZYQ1/kW1KPtdzxwIXbmso0F3Zx59BqLTWhIJP4tFsrv p3lk1wQoENMqe9JE4fQuiso1g+KN0DdRHVKq0KrCvuFpSxc6NJ0xbFU97NbKKgSO34EV IhplUureDHrG/t6fK3AiC8iz3BSVLt62N0GWu28EZmi9VfZB7R7wS0jKpfuXh9X3gR19 CzRZuyEy809S+usHPd/X+rIc3CgnujcpN13B8UHMLms3PIZ8khLT2Nna+/vLyGIDb9Oj sATH0Uy4JgD7ZhSy83KlLjJjsy4jvIjDL90s4DldBxz9aTNj7vPuJ0AjzaTYAczkA1R0 UdkA== X-Gm-Message-State: AKaTC03ZyhJ3OvMhpRq/sSPic6ZekqjGDVwgRedzMTXV35vPXCaugj0qhLMGdxX36BTg8FvJINXi8SIrTxxdPA== X-Received: by 10.13.202.196 with SMTP id m187mr85288558ywd.11.1481524719886; Sun, 11 Dec 2016 22:38:39 -0800 (PST) MIME-Version: 1.0 Received: by 10.37.209.208 with HTTP; Sun, 11 Dec 2016 22:38:39 -0800 (PST) In-Reply-To: References: From: Mehmet Erol Sanliturk Date: Sun, 11 Dec 2016 22:38:39 -0800 Message-ID: Subject: Re: [9front] New Balanced Search Tree Implementation To: 9front@9front.org Content-Type: multipart/alternative; boundary=001a114e6f1ea7acd60543705a50 List-ID: <9front.9front.org> List-Help: X-Glyph: ➈ X-Bullshit: table lifecycle package --001a114e6f1ea7acd60543705a50 Content-Type: text/plain; charset=UTF-8 On Sun, Dec 11, 2016 at 10:30 PM, Benjamin Purcell wrote: > I have written a binary search tree C library for Plan 9. It contains > implementations of both left leaning red-black trees and AVL trees. > In short, you create an AVL tree with > > Bsttree *t = bstcreate(AVL, cmp); > > and an LLRB tree with > > Bsttree *t = bstcreate(LLRB, cmp); > > Cmp is a comparison function. All other implementation details are > hidden from the user. > > I intend to replace libavl with this library for the following reasons > (details can be found below): > > 1. You get a choice of BST with a single API. > 2. The AVL implementation is much faster. > 3. The AVL implementation is smaller and less complicated. > 4. The API is easier to use. > > Item 1. is self-explanatory. > > Item 2. > Measurements of the new AVL implementation against the old one shows > that on average: > Insertion is 21.9% faster. > Deletion is 23.9% faster. > Lookup is 14.95% faster. > 10 trials were conducted on random keys. Sequential keys show similar > results. > > Item 3. > As for code size, the new AVL implementation plus walk code -- which > is shared with the LLRB tree -- comes to 362 source lines of idiomatic > C. The old AVL implementation 436 lines. The old implementation also > contains more functions, and calls many of them unnecessarily. > Despite the fact that it has more functions, the individual functions > themselves are more complicated. > > Item 4. > The AVL implementation's api has the following signatures expressed as > abstract types: > > Avl *(*)(Avltree*, Avl*); > Avl *(*)(Avltree*, Avl*, int); > Avl *(*)(Avlwalk*); > Avltree *(*)(int(*)(Avl*, Avl*)); > Avlwalk *(*)(Avltree*); > void (*)(Avltree*, Avl*, Avl**); > void (*)(Avlwalk*); > > Duplicate signatures have been removed in the above. The new bst > implementation has the following de-duped signatures: > > Bst *(*)(Bsttree*); > Bsttree *(*)(int, int(*cmp)(Bst*, Bst*)); > Channel *(*)(Bsttree*, Bst*, Bst*, int); > > but maintains the same functionality. Which API would you rather use? > > The code can be found at the following locations: > > /n/contrib/spew/libbst > https://bitbucket.org/spewspews/libbst > https://github.com/spewspews/libbst > > A full man page is include and various tests are included in src/tests > including measurements of AVL vs. LLRB, and the new AVL implementation > against the old. > > If there are no objections I would like to remove libavl and add > libbst instead. Libavl has no usages in the source tree. If anyone tries > to compile a libavl program then tough. There will be a better > implementation available and we can always keep it available in > contrib or extra. > > Spew > There is no license information file in https://github.com/spewspews/libbst means , it can not be used in any way or manner . Thank you very much . Mehmet Erol Sanliturk --001a114e6f1ea7acd60543705a50 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable


On Sun, Dec 11, 2016 at 10:30 PM, Benjamin Purcell &l= t;benjapurcell@= gmail.com> wrote:
I have written a binary search tree C library for Plan 9.=C2=A0 = It contains
implementations of both left leaning red-black trees and AVL trees.
In short, you create an AVL tree with

Bsttree *t =3D bstcreate(AVL, cmp);

and an LLRB tree with

Bsttree *t =3D bstcreate(LLRB, cmp);

Cmp is a comparison function.=C2=A0 All other implementation details are hidden from the user.

I intend to replace libavl with this library for the following reasons
(details can be found below):

1. You get a choice of BST with a single API.
2. The AVL implementation is much faster.
3. The AVL implementation is smaller and less complicated.
4. The API is easier to use.

Item 1. is self-explanatory.

Item 2.
Measurements of the new AVL implementation against the old one shows
that on average:
Insertion is 21.9% faster.
Deletion is 23.9% faster.
Lookup is 14.95% faster.
10 trials were conducted on random keys.=C2=A0 Sequential keys show similar=
results.

Item 3.
As for code size, the new AVL implementation plus walk code -- which
is shared with the LLRB tree -- comes to 362 source lines of idiomatic
C. The old AVL implementation 436 lines.=C2=A0 The old implementation also<= br> contains more functions, and calls many of them unnecessarily.
Despite the fact that it has more functions, the individual functions
themselves are more complicated.

Item 4.
The AVL implementation's api has the following signatures expressed as<= br> abstract types:

Avl *(*)(Avltree*, Avl*);
Avl *(*)(Avltree*, Avl*, int);
Avl *(*)(Avlwalk*);
Avltree *(*)(int(*)(Avl*, Avl*));
Avlwalk *(*)(Avltree*);
void (*)(Avltree*, Avl*, Avl**);
void (*)(Avlwalk*);

Duplicate signatures have been removed in the above.=C2=A0 The new bst
implementation has the following de-duped signatures:

Bst *(*)(Bsttree*);
Bsttree *(*)(int, int(*cmp)(Bst*, Bst*));
Channel *(*)(Bsttree*, Bst*, Bst*, int);

but maintains the same functionality.=C2=A0 Which API would you rather use?=

The code can be found at the following locations:

/n/contrib/spew/libbst
https://bitbucket.org/spewspews/libbst
https://github.com/spewspews/libbst

A full man page is include and various tests are included in src/tests
including measurements of AVL vs. LLRB, and the new AVL implementation
against the old.

If there are no objections I would like to remove libavl and add
libbst instead.=C2=A0 Libavl has no usages in the source tree.=C2=A0 If any= one tries
to compile a libavl program then tough.=C2=A0 There will be a better
implementation available and we can always keep it available in
contrib or extra.

Spew




There i= s no license information file in

https://github.com/spewsp= ews/libbst


means , it = can not be used in any way=C2=A0 or manner .



Thank you very much .


Mehmet Erol Sanliturk





--001a114e6f1ea7acd60543705a50--