Thread overview | |||||||||
---|---|---|---|---|---|---|---|---|---|
|
January 14, 2011 RedBlackTree with Array Store | ||||
---|---|---|---|---|
| ||||
Attachments: | 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! |
January 14, 2011 Re: RedBlackTree with Array Store | ||||
---|---|---|---|---|
| ||||
Posted in reply to %u |
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!
|
January 14, 2011 Re: RedBlackTree with Array Store | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Wawryk | > 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. :)
|
January 14, 2011 Re: RedBlackTree with Array Store | ||||
---|---|---|---|---|
| ||||
Posted in reply to %u |
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. :)
|
January 14, 2011 Re: RedBlackTree with Array Store | ||||
---|---|---|---|---|
| ||||
Posted in reply to %u | 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
|
January 15, 2011 Re: RedBlackTree with Array Store | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | > 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?) |
January 15, 2011 Re: RedBlackTree with Array Store | ||||
---|---|---|---|---|
| ||||
Posted in reply to %u | 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
|
Copyright © 1999-2021 by the D Language Foundation