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=-1.9 required=5.0 tests=BAYES_00
	autolearn=unavailable autolearn_force=no version=3.4.4
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Simon Wright <simon@pushface.org>
Newsgroups: comp.lang.ada
Subject: Re: meaningfully/compellingly "advertising" Ada on StackOverflow
Date: Fri, 18 May 2018 12:10:47 +0100
Organization: A noiseless patient Spider
Message-ID: <lyzi0xgqx4.fsf@pushface.org>
References: <6420bab2-0aef-4d36-b978-525e4de45e7e@googlegroups.com>
	<aed23075-1271-4e2c-b5f2-8da705e1a73e@googlegroups.com>
	<a86dc533-a8f5-4d1c-9b4c-11d7963c6d15@googlegroups.com>
	<pdkrvk$n53$1@franka.jacob-sparre.dk>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: h2725194.stratoserver.net;
 posting-host="0e28988de108da281e5475d3050bb8e9";
	logging-data="26881"; mail-complaints-to="abuse@eternal-september.org";
	posting-account="U2FsdGVkX18MUH2sd8XFcJUQ5g5ong7NHj59Dh8dKTk="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (darwin)
Cancel-Lock: sha1:iucbnMhNDXgjuUnarth2z9QceDc=
	sha1:onyLsqfxsyff9ZnuJgnry657A9w=
Xref: reader02.eternal-september.org comp.lang.ada:52426
Date: 2018-05-18T12:10:47+01:00
List-Id: <comp.lang.ada>

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "John Perry" <john.perry@usm.edu> wrote in message 
> news:a86dc533-a8f5-4d1c-9b4c-11d7963c6d15@googlegroups.com...
>> On Wednesday, May 16, 2018 at 9:46:32 PM UTC-5, John Perry wrote:
>>>> It's quite a simple program: adding and removing ~10^6 nodes to a
>>>> tree, and testing if the tree has a value.
>>>
>> Argh. I knew as I was typing that that the description wasn't quite
>>right, but I didn't think to correct it. It adds (10^6/3) nodes,
>>attempts to delete (10^6)/3, and tests for a value in the tree
>>(10^6)/3 times. Still, it's relatively simple.
>
> Did you try implementing that with the Tree container as opposed to
> using a raw nodes? Probably not quite as fast, but much less work to
> write/read/maintain (since the container does the storage management
> and provides most of the algorithms).

I think this would be quite problematic.

https://en.wikipedia.org/wiki/Treap :

   "The treap was first described by Raimund Seidel and Cecilia
   R. Aragon in 1989;[1][2] its name is a portmanteau of tree and
   heap. It is a Cartesian tree in which each key is given a (randomly
   chosen) numeric priority. As with any binary search tree, the inorder
   traversal order of the nodes is the same as the sorted order of the
   keys. The structure of the tree is determined by the requirement that
   it be heap-ordered: that is, the priority number for any non-leaf
   node must be greater than or equal to the priority of its
   children. Thus, as with Cartesian trees more generally, the root node
   is the maximum-priority node, and its left and right subtrees are
   formed in the same manner from the subsequences of the sorted order
   to the left and right of that node."

So there's rebalancing on insertion/removal; _lots_ of tree
manipulation.