Re: Possible Glib BTree substitute
- From: Derek Simkowiak <dereks kd-dev com>
- To: Soeren Sandmann <sandmann daimi au dk>
- cc: gtk-devel-list redhat com, recipient list not shown: ;
- Subject: Re: Possible Glib BTree substitute
- Date: Wed, 1 Mar 2000 15:18:40 -0800 (PST)
See comments below...
> In my opinion, there should be only one O(log n) searching data
> structure in GLib. These are some of the possibilities:
> - Skip lists:
> A simple and, on the average/in the expected sense, very
> fast data structure.
Also, we now have a mostly-complete implementation.
Another advantage to skip lists is that the 'balancing' is
randomized, so there is no particular type, series, or ordering of data
that will produce a slower search time than another.
Finally, as an application developer I find it very convenient to
have all of my data elements wind up in a simple linked list. I find it
easier to visualize the data and what to do with it. But that's just
> It is randomized, which means that it's worst case
> behavoiour is O(n).
"To search a list containing 1000 items, the probability that
search time will be 5 times the average is about 1 in
> - Balanced binary search trees (AVL, red/black, ...)
> Guaranteed O(log n) worst case behaviour. There is already a
> working and bug-free implementation.
Your first comment that there should be only one O(log n)
structure, combined with the fact that the GTree already exists, implies
that you object to considering a skip list (or other tree implementation)
for addition into Glib.
First, I'd like to say that a two child-node based structure is
not always appropriate. It is not as flexible as, say, a BTree that would
let the programmer set the MIN/MAX (where MAX=2*MIN) number of nodes. At
the same time, I would be strongly opposed to *removing* the GTree in
favor of a more flexible structure.
Also, it is likely that the new Gtk+ text widget (probably Havoc's
TkText port) will have some kind of Glib-style Node-based structure on the
backend. If that is going to be shipped with Gtk+, it would make sense to
have that structure made available to other programmers through Glib.
Therefor, I think we should be open to the idea of adding a second
O(log n) search structure.
> The constant hidden in O(log n), while small, is larger than
> that for skip lists (I am not certain as I have not seen
> your skip list implementation).
I would sincerely appreciate it if you could take the time to look
at the code and offer some criticism. I'm not in an environment where I
have local peers to effectively review the code.
] [Thread Prev