Menu
▾
▴
#10 N-ary Tree
I propose that the tree implementation at
http://web.uvic.ca/~erempel/tcl/tree/tree.html
be included in the tcllib as well (or possibly
replace) the tree lib (struct::tree) currently in
tcllib.
To make life easier for this transition, I am willing
to write a "struct::tree" interface to the N-ary tree
library. I may be sticking my foot in my mouth here
since I have not actually tried this yet, but I
could "look into it".
Comments on this new tree? Suggestions or criticisms
are welcome.
Logged In: YES
user_id=304001
Well, I "looked into it" and have come up with a
struct::tree that conforms to the tree.test in tcllib. This
new struct::tree builds its trees using the ::Tree library
at http://web.uvic.ca/~erempel/tcl/tree/tree.html, and is
included with it.
Due to the nested calls to ::Tree and the API conversion,
this struct::tree is slower than the TCLLib one, however,
doing the same work directly with the ::Tree should be
similar in performance if not faster.
This does show the flexibility of the ::Tree package, which
was the motivating concept for the API. A universal
building block for heirachical structures.
After going through this exercise, I am fairly confident
that the struct::tree could not be used to impliment the
API of the ::Tree package.
Logged In: YES
user_id=304001
Problems with the struct::tree Package.
First off, I acknowlegde that given enough code, I can make
the struct::tree do everything, but at what programming
cost.
Things that can not easily be done with struct::tree.
1. Once the root of a tree is created, it can not be
changed. I could take all of the data out of the root node,
and place it into another node and place new data into the
root node, thus effectively changing the root, but it would
be much more consistent to be able to move the root node
around, just like all the other nodes in a tree can be
moved.
2. A node can not be removed from one tree and added to
another tree. Once again, I could move all of the data,
rather than the node itself, but that really defeats the
purpose of trees and nodes.
3. Binary trees can not be efficiently created. Actually,
no N-way trees where N is fixed can be created. The basic
problem is that children are referenced by an index number.
I could use 0 for a left node, and 1 for a right node. This
sounds great, but if I remove the left node (index 0) the
node at index 1 automatically shifts into the 0 position.
In order to keep the right child in the right position, I
must keep a place holder in the index 0 position. To keep
the representation consistent, these sentinal nodes are
required everywhere, for a total of N+1 where N is the
number of real data nodes in the tree. This wastes a
tremendous amount of data space, not to mention processing
power to manipulate. Even if this were not an issue, if a
tree was built using this technique, and I see no other way
to use the struct::tree to impliment a binary tree, then
the routines sich a depth, isleaf and walk all need to be
overloaded to accomodate for these sentinal nodes.
Logged In: YES
user_id=304001
Some performance enhancements in the Tree package have
resulted it the ::struct::tree API wrapper to outperform the
tcllib ::struct::tree package. I no longer see any reason to
remain with the existing tcllib ::struct::tree package.
As always, I'm open to feedback, comments or requests.
Logged In: YES
user_id=75003
Raising the priority of the item because its inclusion in the
upcoming release was proposed in the Tcllib-devel mailing list.
Supporting or contrarian statements should be made on the
referenced mailing list for public discussion.
Logged In: YES
user_id=75003
Looking into this I can't find the code which was used to
benchmark the submitted tree code (*), nor can I find a
benchmark app which works through the struct::tcl wrapper.
This means that with the current state of things am unable to
verify that the new codebase together with a struct::tcl
wrapper is indeed faster than the struct:tree we have.
(*) The results of that one are shown in tree.html, at the very
end. So I believe that a benchmark app does exist. However it
doesn't seem to be part of the download.
Logged In: YES
user_id=304001
There is no timing file provided with the struct::tree library, so
I could not perform a detailed timing analysis with the
struct::treee, or my API replacement.
The tree.time file that I use to provide the timings on the
tree.html page are really only provided to show timing
comparisons between the different ::Tree implimentations.
Since the release of TCL 8.4, the struct::tree library is much
faster due to the enhanced list handling in TCL 8.4. The ::Tree
library uses a mix of arrays and lists, and did not benefit
nearly as much from the release of TCL 8.4. The end result is
that for the same API (::struct::tree) the ::struct::tree library is
approx 40% faster running the tree.test file that is provided
with tcllib 1.3. That was the extent of my time comparison,
however, it is not obvious which routines are slower since
timings are not provided for each routine in ::struct::tree. It
may be that the slow test run is a result of only one or two
routines that exibit poor performance. Without a struct::tree
timing script, I can't be sure.
Does the tcllib development team have a stuct::tree timing
script? If so, could I get my hands on it.
I'll look into this a little more closely, but as it stands now,
the struct::tree is about 40% faster than the ::Tree using the
struct::tree API converter. I don't think that this difference
would exist for any given application written to the native APIs
of each package.
Logged In: YES
user_id=75003
Ah, I see. I thought that you had a timing script for the various
API commands. Ok. Thanks for the detailed response. I was
basically at a loss how and where the claims came from and
wanted to verify things.
The information about the speed-up in Tcl 8.4 actually implies
that while performance is something we can use to compare
the two it is of less significance for choosing between them
than I thought. Simply because the tcl core itself has much to
say in that too. IOW this is even more about "taste" (i.e.
liking an API).
In a few minutes a will post a longer mail to tcllib-devel in the
same vein I did for the indexing stuff. Hopefully I get more
response to that than for the indexing.
Logged In: YES
user_id=304001
There is no timing file provided with the struct::tree library, so
I could not perform a detailed timing analysis with the
struct::treee, or my API replacement.
The tree.time file that I use to provide the timings on the
tree.html page are really only provided to show timing
comparisons between the different ::Tree implimentations.
Since the release of TCL 8.4, the struct::tree library is much
faster due to the enhanced list handling in TCL 8.4. The ::Tree
library uses a mix of arrays and lists, and did not benefit
nearly as much from the release of TCL 8.4. The end result is
that for the same API (::struct::tree) the ::struct::tree library is
approx 40% faster running the tree.test file that is provided
with tcllib 1.3. That was the extent of my time comparison,
however, it is not obvious which routines are slower since
timings are not provided for each routine in ::struct::tree. It
may be that the slow test run is a result of only one or two
routines that exibit poor performance. Without a struct::tree
timing script, I can't be sure.
Does the tcllib development team have a stuct::tree timing
script? If so, could I get my hands on it.
I'll look into this a little more closely, but as it stands now,
the struct::tree is about 40% faster than the ::Tree using the
struct::tree API converter. I don't think that this difference
would exist for any given application written to the native APIs
of each package.
Logged In: YES
user_id=304001
There is no timing file provided with the struct::tree library, so
I could not perform a detailed timing analysis with the
struct::treee, or my API replacement.
The tree.time file that I use to provide the timings on the
tree.html page are really only provided to show timing
comparisons between the different ::Tree implimentations.
Since the release of TCL 8.4, the struct::tree library is much
faster due to the enhanced list handling in TCL 8.4. The ::Tree
library uses a mix of arrays and lists, and did not benefit
nearly as much from the release of TCL 8.4. The end result is
that for the same API (::struct::tree) the ::struct::tree library is
approx 40% faster running the tree.test file that is provided
with tcllib 1.3. That was the extent of my time comparison,
however, it is not obvious which routines are slower since
timings are not provided for each routine in ::struct::tree. It
may be that the slow test run is a result of only one or two
routines that exibit poor performance. Without a struct::tree
timing script, I can't be sure.
Does the tcllib development team have a stuct::tree timing
script? If so, could I get my hands on it.
I'll look into this a little more closely, but as it stands now,
the struct::tree is about 40% faster than the ::Tree using the
struct::tree API converter. I don't think that this difference
would exist for any given application written to the native APIs
of each package.
Logged In: YES
user_id=75003
After long discussion on tcllib-devel, see mailing list archive I
made the decision to leave this out of the 1.4 release.
This has to (or can) be revisited when a major version change
of tcllib comes up.