From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00,
	REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4
Path: 
 border1.nntp.dca1.giganews.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!feeder.erje.net!eu.feeder.erje.net!news.ecp.fr!aioe.org!.POSTED!not-for-mail
From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Newsgroups: comp.lang.ada
Subject: Re: B-Tree v Skip-List Insertion Benchmark
Date: Thu, 18 Sep 2014 09:41:58 +0200
Organization: cbb software GmbH
Message-ID: <1x1p8c1ys7ely$.d0rvczpoa0kb$.dlg@40tude.net>
References: <lvdbn4$99j$1@dont-email.me>
Reply-To: mailbox@dmitry-kazakov.de
NNTP-Posting-Host: yj8+JIQUMOEawvIM7K49kA.user.speranza.aioe.org
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
X-Complaints-To: abuse@aioe.org
User-Agent: 40tude_Dialog/2.0.15.1
X-Notice: Filtered by postfilter v. 0.8.2
Xref: number.nntp.dca.giganews.com comp.lang.ada:189040
Date: 2014-09-18T09:41:58+02:00
List-Id: <comp.lang.ada>

On Wed, 17 Sep 2014 18:15:15 -0700, Jeffrey Carter wrote:

> I ran a quick comparison of the insertion times for Kazakov's Generic_B_Tree pkg
> against PragmARC.Skip_List_Unbounded from the PragmAda Reusable Components.
> 
> Both data structures are used for similar purposes, allowing O(log N) look-up
> times. Insertion and deletion are expensive operations on balanced trees due to
> re-balancing, and one reason skip lists were invented was to have fast insertion
> and deletion times compared to balanced trees. I had never actually compared
> times, and Kazakov's recent post comparing DB times got me thinking about it.
> 
> A typical run inserting the same 1,000 items into both structures gives times of
> 
> 1.484 ms for the B tree
> 0.709 ms for the skip list
> 
> (Divide by 1,000 for average per-insertion times.)
> 
> The trade off is similar to using heap sort or quick sort. Both are O(N log N),
> with quick sort usually being faster. Heap sort is always O(N log N), but in
> rare cases, however, quick sort has worst-case performance of O(N**2).
> 
> A skip list is probabilistically balanced, and has a worst-case search time of
> O(N) in very rare circumstances, almost always for small N (< 256).

Thanks for pointing this.

Can skip list made fit into a series fixed-size blocks?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de