From: Simon Wright <simon@pushface.org>
Subject: Re: meaningfully/compellingly "advertising" Ada on StackOverflow
Date: Fri, 18 May 2018 12:10:47 +0100
Date: 2018-05-18T12:10:47+01:00 [thread overview]
Message-ID: <lyzi0xgqx4.fsf@pushface.org> (raw)
In-Reply-To: pdkrvk$n53$1@franka.jacob-sparre.dk
"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.
next prev parent reply other threads:[~2018-05-18 11:10 UTC|newest]
Thread overview: 28+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-05-16 14:27 meaningfully/compellingly “advertising” Ada on StackOverflow Dan'l Miller
2018-05-16 14:35 ` Lucretia
2018-05-16 15:06 ` Dan'l Miller
2018-05-16 22:48 ` Mehdi Saada
2018-05-17 2:46 ` John Perry
2018-05-17 2:49 ` John Perry
2018-05-17 21:25 ` meaningfully/compellingly "advertising" " Randy Brukardt
2018-05-17 23:27 ` Luke A. Guest
2018-05-18 1:22 ` Paul Rubin
2018-05-18 2:28 ` Dan'l Miller
2018-05-18 2:59 ` Lucretia
2018-05-18 2:57 ` Lucretia
2018-05-18 4:25 ` John Perry
2018-05-18 4:38 ` Paul Rubin
2018-05-18 15:39 ` John Perry
2018-05-18 15:48 ` John Perry
2018-05-18 20:49 ` Randy Brukardt
2018-05-18 20:47 ` Randy Brukardt
2018-05-18 4:37 ` Paul Rubin
2018-05-18 10:44 ` Lucretia
2018-05-20 7:54 ` Paul Rubin
2018-05-18 11:17 ` Ben Bacarisse
2018-05-18 20:42 ` Randy Brukardt
2018-05-18 4:22 ` John Perry
2018-05-18 20:52 ` Randy Brukardt
2018-05-18 11:10 ` Simon Wright [this message]
2018-05-18 15:43 ` meaningfully/compellingly “advertising” " John Perry
2018-05-18 16:40 ` Dan'l Miller
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox