Check out skiplists which are much easier to implement then self
balancing binary trees and have to advantage of implementing rank
operations with logarithmic complexity. I implemented a skiplist library
years ago and was very happy
with the performance. They are comparable to AVL trees in performance
but have the disadvantage that the algorithm is probabilistic. In
reality that shouldn't be a problem.
http://en.wikipedia.org/wiki/Skip_list
Jason Evans has a macro based red-black tree implementation in the
public domain. It's very fast! There's a copyright but no license
http://www.canonware.com/rb/
On 29/05/2013 1:44 PM, Paul Gilmartin wrote:
On Wed, 29 May 2013 12:23:01 +0800, David Crayford wrote:
IMO all of the dictionary routines in the standard runtime are
sub-optimal. It's either RYO, ...
I like that. I can even make the substitutable compare routines
macros instead of functions, so they're (mostly) inline. Assembler
programmers should be proud of me.
This is all kind of obsessive; the table size is about 1000, the
number of searches per execution is about 100. As I said,
linear search works fine.
They could have balanced the silly tree. They could have
allowed macros as the compare facilities.
-- gil
----------------------------------------------------------------------
For IBM-MAIN subscribe / signoff / archive access instructions,
send email to [email protected] with the message: INFO IBM-MAIN
----------------------------------------------------------------------
For IBM-MAIN subscribe / signoff / archive access instructions,
send email to [email protected] with the message: INFO IBM-MAIN
