*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: > > advantages: > 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 me... > disadvantages: > 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 1,000,000,000,000,000,000." (http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/niemann/s_skl.htm) > - Balanced binary search trees (AVL, red/black, ...) > > advantages: > 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. > disadvantages: > 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. Thank You, Derek Simkowiak dereks@kd-dev.com

**References**:**Re: Possible Glib BTree substitute***From:*Soeren Sandmann

[Date Prev][Date Next] [Thread Prev][Thread Next] [Thread Index] [Date Index] [Author Index]