Re: "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! ]