"Hi. I'm A Set, Implemented As {BST | AVL | Splay | Red-Black}."

On Sep 3, 3:58 pm, Ulrich Eckhardt <eckha...@satorlaser.com> wrote:
> Le Chaud Lapin wrote:
> > 1. Do what STL did: Pick one, ignore the rest, and get on with it.
> > 2. Create compile-time framework to choose among implementations
> > according to anticipated use.
> > 3. Create run-time framework to choose among implementations,
> > according to anticipated use.
> BTW: I'm not actually sure what you mean with version 2, do you mean you
> determine the best type during build (i.e. via a test that runs first and
> then sets a macro for the real build) or that you hard-code it manually?

Hard-code it manually. In most cases, the engineer can probably guess
order of elements. Like a few months ago, I needed to process 55.6GB
of data, and I knew in advance that elements would be coming off the
disk in order. Using AVL implementation, I got processing time down to
1 hour, 24 minutes.

I cannot remember what time was for Red-Black.

Examples:

1. std::set<int> foo; // Likely that red-black is implementation
2. myset<int, SchemeAVL> foo; // Force use of AVL implemntation.
3. myset<int> foo; foo.go(SchemeRedBlack); foo.insert(3)...etc.

Lance Diduck in his post showed link of something similar to 2.

At this point, I am inclined to punt and just pick AVL or Red Black as
STL [P.J. Plauger] did.

-Le Chaud Lapin-


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

>At this point, I am inclined to punt and just pick AVL or Red Black as
>STL [P.J. Plauger] did.

I dont think BST or splay are legal as they will fail on the
complexity guarantees whereas AVL, Red-Black and quite a few others
do not (weight balanced, generalised height balanced etc). The
guarantee a limited depth that is O(log N).

Have you considered scapegoat trees? The nice thing is each node has
no additional per-node overhead but there is a per-containter
overhead. See
http://en.wikipedia.org/wiki/Scapegoat_tree
and read
http://cg.scs.carleton.ca/~morin/tea.../refs/gr93.pdf

Stephen Howe

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]