Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #5885

Re: Splay trees

Show all headers | View raw

"A. Bolmarcich" <aggedor@earl-grey.cloud9.net> wrote in message 
news:slrnn00jcd.gdp.aggedor@earl-grey.cloud9.net...
> On 2015-09-16, James Harris <james.harris.1@gmail.com> wrote:
>>
>> Naturally, the best rebalancing action would depend on the upcoming
>> access pattern but, without trying it, I would have guessed that 
>> moving
>> a node a step up the tree on each access would be better overall 
>> rather
>> than moving the node all the way up to the root. Anyone care either 
>> to
>> agree or to dispute that?
>>
> Moving a tree node up one level instead of to the root could have
> both performance pluses and minuses.  The results with some simple
> modifications to code that I have for a splay tree is that for random
> values, searching was 13% faster for the single level change, but the
> resulting tree had a 20% greater average node depth.

Thank you very much for the measured figures. When you say you moved up 
one level do you mean that you moved nodes up two levels in the 
hierarchy, i.e. what might be called a zig-zig or zig-zag pair of 
rotations? You will see I referred to a "step" up, meaning two levels of 
the hierarchy. If the node is one level below the root I would just 
leave it unchanged rather than doing a zig step.

> On the plus side, it is likely that fewer instructions were executed
> to restructure the tree.  Moving a tree node to the root can involve
> restructing the tree at many places on the path between the previous
> root and where the node was in the tree.  Moving a tree node up only
> one level involves restructing the tree at only one place.
>
> On the minus side, the resulting tree was more unbalanced.
>
> Splay trees were designed to improve the performance of clustered
> searches, not the random searches that I did.  In the test I did,
> compared to an unbalanced tree, the single level change tree search
> was 68% slower and the resulting tree had a 35% greater average node
> depth.

I was thinking of how the tree behaved over time. I don't know that a 
comparison with an unbalanced tree is a fair one.

If you still have the testing setup in place I wonder if you could 
compare the times taken for a full traversal of the tree. I would expect 
the traditional splay-to-root to be faster than splaying up a step (two 
levels) at a time as nearly all accesses would be to adjacent nodes and 
splaying to root would bring adjacent nodes up too, but it would be 
interesting to see how much difference it made to the time.

James

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-16 19:32 +0100
  Re: Splay trees Melzzzzz <mel@zzzzz.com> - 2015-09-16 20:59 +0200
    Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-17 17:10 +0100
      Re: Splay trees Melzzzzz <mel@zzzzz.com> - 2015-09-18 13:12 +0200
        Re: Splay trees Richard Heathfield <rjh@cpax.org.uk> - 2015-09-18 14:03 +0100
          Re: Splay trees Kaz Kylheku <kaz@kylheku.com> - 2015-09-18 15:32 +0000
            Re: Splay trees Richard Heathfield <rjh@cpax.org.uk> - 2015-09-18 17:30 +0100
          Re: Splay trees Melzzzzz <mel@zzzzz.com> - 2015-09-19 01:10 +0200
  Splay trees Chad <cdalten@gmail.com> - 2015-09-17 21:32 -0700
    Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-18 11:28 +0100
      Re: Splay trees Chad <cdalten@gmail.com> - 2015-09-18 15:59 -0700
  Re: Splay trees "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> - 2015-09-21 13:33 -0500
    Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-22 18:41 +0100
      Re: Splay trees "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> - 2015-09-23 13:03 -0500
        Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-23 19:20 +0100
          Re: Splay trees "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> - 2015-09-23 15:33 -0500
            Re: Splay trees James Harris <james.harris.1@gmail.com> - 2015-09-25 13:29 +0100

csiph-web