www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - RedBlackTree with Array Store

reply %u <wfunction hotmail.com> writes:
Hi,

I've noticed that, just as you can have a heap with an array-backed store, you
can also have a binary search tree with the same store (although structured
differently; see attachment for a bare-bones unsorted binary tree
implementation -- which I have NOT yet tested, but which I can test if it will
be used). The improvement will be in data locality, and while it may seem to
use a bit more space than a link-based tree, I think it's worth it to let the
RedBlackTree class use a custom store, such as any store that has
getLeft/getRight/setLeft/setRight methods, and that uses opaque pointers.

How does this idea sound?
Thank you!
begin 644 arraycontainer.d
M<')I=F%T92!I;7!O<G0 <W1D+F%L9V]R:71H;2`Z(&UA>"P <W=A<#L-"G!R

M3F]D92A4*0T*>PT*"7!U8FQI8R!4('9A;'5E.PT*"7!R:79A=&4 <'1R9&EF



M<FEV871E($)I;F%R>4AE87`A*'!T<F1I9F9?=%M=*2!O<&5N26YD:6-E<SL-


M8V  *&D[('1H:7,N;W!E;DEN9&EC97,I('L 87-S97)T*'1H:7,N:71E;7-;


M96T[('1H:7,N:71E;7,I('L :68 *&ET96TN<V5L9B`^/2`P*2![(&%S<V5R
M="AI=&5M+G-E;&8 /3T :2P (DET96T :6YD97  9&ED(&YO="!P;VEN="!T
M;R!I=&5M+B(I.R!C;W5N="LK.R!]('T-" D)87-S97)T*&-O=6YT(#T]('1H
M:7,N:71E;7,N;&5N9W1H("T =&AI<RYO<&5N26YD:6-E<RYL96YG=& L(")4

M('9O:60 =F%L:61A=&4H:6X 8V]N<W0H3F]D92$H5"DI*B!N;V1E*0T*"7L-
M" D):68 *&YO9&4 (3T ;G5L;"D-" D)>PT*"0D)87-S97)T*"9T:&ES+FET

M(#P ,"!\?"!T:&ES+F=E=$QE9G0H;F]D92DN<&%R96YT(#T](&YO9&4N<V5L

M="AN;V1E*2YP87)E;G0 /3T ;F]D92YS96QF*3L-" D)"6%S<V5R="AN;V1E

M(&YO9&4N<V5L9BD ?"`H=&AI<RYG971087)E;G0H;F]D92DN<FEG:'0 /3T 

M;VYS="A.;V1E(2A4*2DJ(')O;W0H*2![(')E='5R;B!T:&ES+FE2;V]T(#X]

M:6, 8V]N<W0H3F]D92$H5"DI*B!G971087)E;G0H8V]N<W0H3F]D92$H5"DI
M*B!N;V1E*2!I;B![('1H:7,N=F%L:61A=&4H;F]D92D[('T ;W5T("AP*2![
M('1H:7,N=F%L:61A=&4H<"D[('T 8F]D>2![(')E='5R;B!N;V1E+G!A<F5N

M"7!U8FQI8R!C;VYS="A.;V1E(2A4*2DJ(&=E=$QE9G0H8V]N<W0H3F]D92$H
M5"DI*B!N;V1E*2!I;B![('1H:7,N=F%L:61A=&4H;F]D92D[('T ;W5T("AP
M*2![('1H:7,N=F%L:61A=&4H<"D[('T 8F]D>2![(')E='5R;B!N;V1E+FQE

M<'5B;&EC(&-O;G-T*$YO9&4A*%0I*2H 9V5T4FEG:'0H8V]N<W0H3F]D92$H
M5"DI*B!N;V1E*2!I;B![('1H:7,N=F%L:61A=&4H;F]D92D[('T ;W5T("AP
M*2![('1H:7,N=F%L:61A=&4H<"D[('T 8F]D>2![(')E='5R;B!N;V1E+G)I
M9VAT(#X
M" T*"7!U8FQI8R!V;VED('-E=$QE9G0H8V]N<W0H3F]D92$H5"DI*B!N;V1E

M92`A/2!N=6QL*3L =&AI<RYV86QI9&%T92AN;V1E*3L =&AI<RYV86QI9&%T
M92AL969T*3L ?0T*"6)O9'D >R!T:&ES+FET96US6VYO9&4N<V5L9ETN;&5F
M="`](&QE9G0 (3T ;G5L;"`_(&QE9G0N<V5L9B`Z("TQ.R!I9B`H;&5F="`A
M/2!N=6QL*2![('1H:7,N:71E;7-;;&5F="YS96QF72YP87)E;G0 /2!N;V1E

M92$H5"DI*B!N;V1E+"!I;B!C;VYS="A.;V1E(2A4*2DJ(')I9VAT*0T*"6EN
M('L 87-S97)T*&YO9&4 (3T ;G5L;"D[('1H:7,N=F%L:61A=&4H;F]D92D[

M;F]D92YS96QF72YR:6=H="`](')I9VAT("$](&YU;&P /R!R:6=H="YS96QF
M(#H +3$[(&EF("AR:6=H="`A/2!N=6QL*2![('1H:7,N:71E;7-;<FEG:'0N
M<V5L9ETN<&%R96YT(#T ;F]D92YS96QF.R!]('T-" T*"7!U8FQI8R!C;VYS


M=&5M<RYL96YG=&  *R`Q*3L-" D)875T;R!I(#T =&AI<RYO<&5N26YD:6-E
M<RYF<F]N=#L-" D)=&AI<RYI=&5M<UMI72`]($YO9&4A*%0I*%0N:6YI="P 

M;G0H*3L-" D):68 *'1H:7,N:5)O;W0 /"`P*2![('1H:7,N:5)O;W0 /2!I



M('!R979,96X /2!T:&ES+FET96US+FQE;F=T:#L-" D)"71H:7,N:71E;7,N
M;&5N9W1H(#T ;6%X*&-A<&%C:71Y+"`R("H =&AI<RYI=&5M<RYL96YG=& I
M.PT*"0D)875T;R!I;F1I8V5S(#T ;F5W('!T<F1I9F9?=%MT:&ES+FET96US

M;W!E;DEN9&EC97,N96UP='DI('L :6YD:6-E<UMI*RM=(#T =&AI<RYO<&5N
M26YD:6-E<RYF<F]N=#L =&AI<RYO<&5N26YD:6-E<RYR96UO=F5&<F]N=" I

M9W1H*2![(&EN9&EC97-;:2LK72`](&H[('T-" D)"71H:7,N;W!E;DEN9&EC
M97,N86-Q=6ER92AI;F1I8V5S+"!I*3L-" D)?0T*"7T-" T*"7!U8FQI8R!V
M;VED(&9R965.;V1E*&-O;G-T*$YO9&4A*%0I*2H ;F]D92D-" EI;B![('1H


M;V1E+G-E;&9=.PT*"0D)=&AI<RYF<F5E3F]D92AT:&ES+F=E=$QE9G0H<$UY
M3F]D92DI.PT*"0D)<$UY3F]D92YL969T(#T
M;V1E*'1H:7,N9V5T4FEG:'0H<$UY3F]D92DI.PT*"0D)<$UY3F]D92YR:6=H
M="`]("TQ.PT*"0D):68 *'!->4YO9&4N<&%R96YT(#X
M=&5M<UMP37E.;V1E+G!A<F5N=%TN;&5F="`]/2!P37E.;V1E+G-E;&8I('L 

M9B`H<$UY3F]D92YP87)E;G0 /CT ,"`F)B!T:&ES+FET96US6W!->4YO9&4N
M<&%R96YT72YR:6=H="`]/2!P37E.;V1E+G-E;&8I('L =&AI<RYI=&5M<UMP
M37E.;V1E+G!A<F5N=%TN<FEG:'0 /2`M,3L ?0T*"0D)<$UY3F]D92YP87)E
M;G0 /2`M,3L-" D)"71H:7,N;W!E;DEN9&EC97,N:6YS97)T*'!->4YO9&4N

M;V]T(#T]('!->4YO9&4N<V5L9BD >R!T:&ES+FE2;V]T(#T +3$[('T-" D)
M?0T*"7T-" T*"7!R:79A=&4 =F]I9"!S=V%P4VQO='-.;TYO=&EF>4AE87`H
M<'1R9&EF9E]T(&DL('!T<F1I9F9?="!J*0T*"7L-" D)87-S97)T*&D /CT 
M,"`F)B!J(#X
M;7-;:ETI.PT*"0ES=V%P*'1H:7,N:71E;7-;:5TN<V5L9BP =&AI<RYI=&5M
M<UMJ72YS96QF*3L-" D):68 *'1H:7,N:71E;7-;:5TN;&5F="`^/2`P*2![
M('1H:7,N:71E;7-;=&AI<RYI=&5M<UMI72YL969T72YP87)E;G0 /2!J.R!]


M:&ES+FET96US6VI=+FQE9G0 /CT ,"D >R!T:&ES+FET96US6W1H:7,N:71E
M;7-;:ETN;&5F=%TN<&%R96YT(#T :3L ?0T*"0EI9B`H=&AI<RYI=&5M<UMJ
M72YR:6=H="`^/2`P*2![('1H:7,N:71E;7-;=&AI<RYI=&5M<UMJ72YR:6=H
M=%TN<&%R96YT(#T :3L ?0T*"0EI9B`H=&AI<RYI4F]O="`]/2!I*2![('1H

M>R!T:&ES+FE2;V]T(#T :3L ?0T*"7T-" T*"7!U8FQI8R!V;VED('1R:6TH
M*0T*"7L-" D)<VEZ95]T(&QE;E9A;&ED(#T =&AI<RYI=&5M<RYL96YG=& [

M" D)>PT*"0D):68 *'1H:7,N;W!E;DEN9&EC97,N96UP='DI('L 8G)E86L[

M;R!O<&5N26YD97  /2!T:&ES+F]P96Y);F1I8V5S+F9R;VYT.PT*"0D)"71H
M:7,N;W!E;DEN9&EC97,N<F5M;W9E1G)O;G0H*3L-" D)"0ET:&ES+G-W87!3
M;&]T<TYO3F]T:69Y2&5A<"AI+"!O<&5N26YD97 I.PT*"0D)"71H:7,N;W!E

M;&5N9W1H(#T

M"0EI;G0 <F5S=6QT(#T ,#L-" D)875T;R!S=&%C:R`](&YE=R!.;V1E(2A4




M;F=T:"`M/2`Q.PT*"0D)"69O<B`H875T;R!T96UP(#T =&AI<RYG9712:6=H
M="AN;V1E*3L =&5M<"`A/2!N=6QL.R!T96UP(#T =&AI<RYG971,969T*'1E


M="`](&1G*&YO9&4I.PT*"0D)"6EF("AR97-U;'0I('L 8G)E86L[('T-" D)
M"7T-" D)?0T*"0ER971U<FX <F5S=6QT.PT*"7T-"GT-" T*86QI87, 07)R
M87E":6YA<GE4<F5E(2AI;G0I($EN=%1R964[("\O2G5S="!F;W( =&5S=&EN
!9P``
`
end
Jan 13 2011
next sibling parent reply Steven Wawryk <stevenw acres.com.au> writes:
I haven't looked at your code, but I came across the idea of a vector 
map in C++ (based on a std::vector of std::pairs) with some performance 
advantages over std::map if there aren't a lot of insertions and 
deletions.  The idea is a good one.  Whether it's best as a custom store 
for RedBlackTree or as a separate container I don't know.

The "unsorted binary tree" you mention doesn't sound right.  Such a 
container would need to be kept sorted.

On 14/01/11 15:55, %u wrote:

 Hi,

 I've noticed that, just as you can have a heap with an array-backed store, you
 can also have a binary search tree with the same store (although structured
 differently; see attachment for a bare-bones unsorted binary tree
 implementation -- which I have NOT yet tested, but which I can test if it will
 be used). The improvement will be in data locality, and while it may seem to
 use a bit more space than a link-based tree, I think it's worth it to let the
 RedBlackTree class use a custom store, such as any store that has
 getLeft/getRight/setLeft/setRight methods, and that uses opaque pointers.

 How does this idea sound?
 Thank you!
Jan 13 2011
parent reply %u <wfunction hotmail.com> writes:
 The "unsorted binary tree" you mention doesn't sound right.  Such a


container would need to be kept sorted.

It would, IF it was implemented the same way as a heap. But it's not. Take a
look
at my implementation if you get the chance; every node has four members in
addition to the value, which are the indices of the (1) node (self-pointer), (2)
parent, (3) left child, and (4) right child. There's no direct mapping between
the
place of a node in the tree and its place in the array, so there's no need to
keep
anything sorted.

Hopefully that made sense... let me know if it doesn't. :)
Jan 13 2011
parent Steven Wawryk <stevenw acres.com.au> writes:
I see.  It's not what I meant when I described the vector map.  That has 
no pointers/indices stored in it.  The position in the tree is implied 
by the index.

On 14/01/11 18:21, %u wrote:

 The "unsorted binary tree" you mention doesn't sound right.  Such a


 container would need to be kept sorted.

 It would, IF it was implemented the same way as a heap. But it's not. Take a
look
 at my implementation if you get the chance; every node has four members in
 addition to the value, which are the indices of the (1) node (self-pointer),
(2)
 parent, (3) left child, and (4) right child. There's no direct mapping between
the
 place of a node in the tree and its place in the array, so there's no need to
keep
 anything sorted.

 Hopefully that made sense... let me know if it doesn't. :)
Jan 14 2011
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 14 Jan 2011 00:25:17 -0500, %u <wfunction hotmail.com> wrote:


 Hi,

 I've noticed that, just as you can have a heap with an array-backed  
 store, you
 can also have a binary search tree with the same store (although  
 structured
 differently; see attachment for a bare-bones unsorted binary tree
 implementation -- which I have NOT yet tested, but which I can test if  
 it will
 be used). The improvement will be in data locality, and while it may  
 seem to
 use a bit more space than a link-based tree, I think it's worth it to  
 let the
 RedBlackTree class use a custom store, such as any store that has
 getLeft/getRight/setLeft/setRight methods, and that uses opaque pointers.

 How does this idea sound?
 Thank you!


Didn't look at your code exactly, but from reading this discussion, what  
you have implemented is basically a memory pool ;)  Yes it's possible, and  
dcollections does this.  in our discussions on bringing dcollections' red  
black tree to std.container, I asked if my custom allocator that uses an  
array for storage should be ported or not, and we decided to defer custom  
allocation until later.  I fully expect that a custom allocation scheme  
will be introduced at some point in std.container.

-Steve
Jan 14 2011
parent reply %u <wfunction hotmail.com> writes:
 Didn't look at your code exactly, but from reading this discussion, what you


have implemented is basically a memory pool ;)

Huh, interesting... I didn't think about it that way, but in a way, that's true.
:) I just thought of it as some tree representation that did not use pointers.



 Yes it's possible, and dcollections does this.  in our discussions on bringing


dcollections' red black tree to std.container, I asked if my custom allocator
that
uses an array for storage should be ported or not, and we decided to defer
custom
allocation until later.  I fully expect that a custom allocation scheme will be
introduced at some point in std.container.

Oh cool! So long as it's on the (probably very long!) to-do list, that's great.
Thanks for letting me know. :]

(By the way, if I happen to find enough time to modify the current version to
allow for a custom allocator, would that be potentially of any use?)
Jan 14 2011
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 14 Jan 2011 20:57:18 -0500, %u <wfunction hotmail.com> wrote:


 Didn't look at your code exactly, but from reading this discussion,  
 what you


 have implemented is basically a memory pool ;)

 Huh, interesting... I didn't think about it that way, but in a way,  
 that's true.
 :) I just thought of it as some tree representation that did not use  
 pointers.



 Yes it's possible, and dcollections does this.  in our discussions on  
 bringing


 dcollections' red black tree to std.container, I asked if my custom  
 allocator that
 uses an array for storage should be ported or not, and we decided to  
 defer custom
 allocation until later.  I fully expect that a custom allocation scheme  
 will be
 introduced at some point in std.container.

 Oh cool! So long as it's on the (probably very long!) to-do list, that's  
 great.
 Thanks for letting me know. :]

 (By the way, if I happen to find enough time to modify the current  
 version to
 allow for a custom allocator, would that be potentially of any use?)


Sure, in fact you could currently use dcollections to test it, since it  
allows for custom allocators ;)

-Steve
Jan 15 2011