I am trying to see if lisp can efficiently retrieve a value (a list)
based upon doing a lookup between a min (first element of list) and max
value (2nd element of list). I have tried the following:
(defparameter itx '(
(1000 1025 101 101 101 101)
(1025 1050 104 104 104 104)
(1050 1075 106 106 106 106)
(1075 1100 109 109 109 109)
))
;; (rc 1060)
(defun rc (income)
(find income itx
:key #'car))
(defun rc2 (income)
(find income itx
:test #' rate-calc))
(defun rate-calc (income)
(and (>= income min) (< income max)))
e.g.
CL-USER 2 > (rc 1000)
(1000 1025 101 101 101 101)
CL-USER 3 > (rc 1050)
(1050 1075 106 106 106 106)
CL-USER 4 > (rc 1012) ;wrong answer!
NIL
i want (rc 1012) to return (1000 1025 101 101 101 101) because 1012 is
between 1000 and 1025;
likewise (rc 1051) should return (1050 1075 106 106 106 106)
Is there a way how this can be accomplished using a combination of key
and test keywords?
Also this is doing list searching. Is it possible to store this in a
hash table and some how to a lookup
on a key changing equality operators?
·········@yahoo.com writes:
| I am trying to see if lisp can efficiently retrieve a value (a list)
| based upon doing a lookup between a min (first element of list) and max
| value (2nd element of list). I have tried the following:
|
| (defparameter itx '(
| (1000 1025 101 101 101 101)
| (1025 1050 104 104 104 104)
| (1050 1075 106 106 106 106)
| (1075 1100 109 109 109 109)
| ))
|
| ;; (rc 1060)
|
| (defun rc (income)
| (find income itx
| :key #'car))
|
| (defun rc2 (income)
| (find income itx
| :test #' rate-calc))
The :test function needs to take two parameters: the thing you're
searching for, and the element that might be a match for it.
| (defun rate-calc (income)
| (and (<= income min) (< income max)))
Where did MIN and MAX in this function come from? Did you really run
it in the interpreter? (Also, did you really mean to require that the
income be less than or equal to the minimum of the range?)
It turns out that they need to come from the element you're
testing for matching against:
(defun rate-calc (income element)
(and (<= (first element) income) (< income (second element))))
On 2005-08-18, ·········@yahoo.com <·········@yahoo.com> wrote:
> I am trying to see if lisp can efficiently retrieve a value (a list)
> based upon doing a lookup between a min (first element of list) and max
> value (2nd element of list).
In C++ you'd stick them in a map key'd on the min and use lower_bound() to
do the lookup.
There are several balanced binary search tree packages for lisp. If none
of them provide something similar to lower_bound() then I'm sure you could
easily add it yourself.
I wrote this haskell code which works:
type TaxTableEntry = (Min, Max,
AmtSingle, AmtMarriedFilingJointly,
AmtMarriedFilingSeparately, AmtHeadOfHousehold)
type TaxTable = [TaxTableEntry]
taxTable :: TaxTable
taxTable =
[
(1000,1025,101,101,101,101),
(1025,1050,104,104,104,104),
(1050,1075,106,106,106,106),
(1075,1100,109,109,109,109),
(18800,18850,2466,2109,2466,2314),
(18850,18900,2474,2116,2474,2321),
(18900,18950,2481,2124,2481,2329),
(18950,19000,2489,2131,2489,2336),
(19000,19050,2496,2139,2496,2344),
(19050,19100,2504,2146,2504,2351),
(19100,19150,2511,2154,2511,2359),
(19150,19200,2519,2161,2519,2366)
]
rc Single income =
[s1 | (min,max,s1,_,_,_) <- taxTable, income > min, income <= max]
rc Marriedfilingjointly income =
[s2 | (min,max,_,s2,_,_) <- taxTable, income > min, income <= max]
rc Marriedfilingseparately income =
[s3 | (min,max,_,_,s3,_) <- taxTable, income > min, income <= max]
rc Headofhousehold income =
[s4 | (min,max,_,_,_,s4) <- taxTable, income > min, income <= max]
but how can I do something similar in lisp?
is a prolog version that works:
rc(single,Income,Rate):-
itx(Min,Max,R,_,_,_), Income >= Min, Income < Max, Rate is R.
rc(married_filing_jointly,Income,Rate):-
itx(Min,Max,_,R,_,_), Income >= Min, Income < Max, Rate is R.
rc(married_filing_separately,Income,Rate):-
itx(Min,Max,_,_,R,_), Income >= Min, Income < Max, Rate is R.
rc(head_of_household,Income,Rate):-
itx(Min,Max,_,_,_,R), Income >= Min, Income < Max, Rate is R.
itx(1175,1200,119,119,119,119).
itx(1200,1225,121,121,121,121).
itx(1225,1250,124,124,124,124).
itx(1250,1275,126,126,126,126).
itx(1275,1300,129,129,129,129).
itx(1300,1325,131,131,131,131).
itx(1325,1350,134,134,134,134).
But I want to do it in LISP!
On 2005-08-18, ·········@yahoo.com <·········@yahoo.com> wrote:
> But I want to do it in LISP!
I have a balanced binary search tree package that isn't released yet. I
was holding off until I could get it to be faster than the package at
http://www.cliki.net/TREES. Unlike that package, mine mirrors the hash
interface.
So in my package you'd do this:
CL-USER> (use-package :trees)
T
CL-USER> (defparameter *map* (make-tree))
*MAP*
CL-USER> (setf (gettree 1000 *map*) '(1000 1025 101 101 101 101))
(1000 1025 101 101 101 101)
CL-USER> (setf (gettree 1025 *map*) '(1025 1050 104 104 104 104))
(1025 1050 104 104 104 104)
CL-USER> (gettree 1000 *map*)
(1000 1025 101 101 101 101)
T
CL-USER> (gettree 1012 *map*)
NIL
NIL
CL-USER> (gettree-left 1012 *map*)
(1000 1025 101 101 101 101)
T
CL-USER>
As I indicated earlier, the other tree packages should be easy to modify
to get similar behavior.
Shameless plug! There is a Red Black Tree package in the AI Repository. :)
Cheers
marco
John wrote:
> On 2005-08-18, ·········@yahoo.com <·········@yahoo.com> wrote:
>
>> But I want to do it in LISP!
>
>
> I have a balanced binary search tree package that isn't released yet. I
> was holding off until I could get it to be faster than the package at
> http://www.cliki.net/TREES. Unlike that package, mine mirrors the hash
> interface.
>
> So in my package you'd do this:
>
> CL-USER> (use-package :trees)
> T
> CL-USER> (defparameter *map* (make-tree))
> *MAP*
> CL-USER> (setf (gettree 1000 *map*) '(1000 1025 101 101 101 101))
> (1000 1025 101 101 101 101)
> CL-USER> (setf (gettree 1025 *map*) '(1025 1050 104 104 104 104))
> (1025 1050 104 104 104 104)
> CL-USER> (gettree 1000 *map*)
> (1000 1025 101 101 101 101)
> T
> CL-USER> (gettree 1012 *map*)
> NIL
> NIL
> CL-USER> (gettree-left 1012 *map*)
> (1000 1025 101 101 101 101)
> T
> CL-USER>
>
> As I indicated earlier, the other tree packages should be easy to modify
> to get similar behavior.
(defun rc3 (income)
(find-if (lambda (x) (<= (car x) income (cadr x))) itx))
fails on the max boundary: e.g. (rc3 1025) but
(defun rc3 (income)
(find-if (lambda (x) (and (<= (car x) income) (< income (cadr x))))
itx))
appears to work.
(defun rc2 (income)
(find income itx
:test #' rate-calc))
(defun rate-calc (income element)
(and (<= (first element) income) (< income (second element))))
also works. Just curious in my example, itx has 4 items. If the item
count increases
to say 10000 will the above algorithms' still be efficient? The fact
there is partial ordering
is it feasible to use a BST or some kind of hash-code to imrove
efficienct to keep log(n) access time.
Thanks for the help guys.
·········@yahoo.com writes:
> (defun rc3 (income)
> (find-if (lambda (x) (and (<= (car x) income) (< income (cadr x))))
> itx))
> [...]
> also works. Just curious in my example, itx has 4 items. If the item
> count increases
> to say 10000 will the above algorithms' still be efficient?
What do you think?
> The fact there is partial ordering
> is it feasible to use a BST or some kind of hash-code
Not in a standard hash-table, since CL only handles EQL, EQUAL or
EQUALP hash tables. You'd need to implement your own hash function
that would give the same hash-code for all values between min and max
for all couples (min max) in the hash table...
> to imrove efficienct to keep log(n) access time.
Put the list into a vector, sort it, and use a dichotomy.
If you need to insert new ranges in O(log(n)) instead of O(n), then
put them in some kind of balanced binary tree.
--
"You cannot really appreciate Dilbert unless you read it in the
original Klingon"
Pascal Bourguignon <····@mouse-potato.com> writes:
> Put the list into a vector, sort it, and use a dichotomy.
I've never heard the term `dichotomy' used in this way. I generally
use the term to mean a twofold opposing classification as in `the
dichotomy between good and evil'.
Does it mean `perform a binary search'?
~jrm
Joe Marshall <···@ccs.neu.edu> writes:
> Pascal Bourguignon <····@mouse-potato.com> writes:
>
>> Put the list into a vector, sort it, and use a dichotomy.
>
> I've never heard the term `dichotomy' used in this way. I generally
> use the term to mean a twofold opposing classification as in `the
> dichotomy between good and evil'.
>
> Does it mean `perform a binary search'?
That's the same.
In a binary search, the cut in two phase has be done previously, we
only need to choose the branches.
In a dichotomy we cut in two at the same time we choose the branch.
We can do that efficiently because the data is already sorted.
(defun dichotomy (vector target compare &optional (min 0) (max (length vector)))
"
RETURN: (values found index order)
+-------------------+----------+-------+----------+
| Case | found | index | order |
+-------------------+----------+-------+----------+
| x < a[min] | NIL | 0 | -1 |
| x = a[i] | T | i | 0 |
| a[i] < x < a[i+1] | NIL | i | 1 |
| a[max] < x | NIL | max | 1 |
+-------------------+----------+-------+----------+
"
(let* ((mid (truncate (+ min max) 2)) ; we cut in two now
(order (funcall compare target (aref vector mid))))
(cond ; choosing the branch
((= 0 order) (values t mid order))
((= min mid) (if (and (< 0 mid) (< order 0))
(values nil (1- mid) 1)
(values nil mid order)))
((< order 0) (dichotomy vector target compare min mid))
(t (dichotomy vector target compare mid max)))))
[92]> (defparameter itx #(
(1000 1025 101 101 101 101)
(1025 1035 104 104 104 104) ; <- a hole
(1050 1075 106 106 106 106) ; <-
(1075 1100 109 109 109 109)
))
ITX
[93]> (loop for i from 999 to 1101 by 3
do (print (cons i (multiple-value-list
(dichotomy itx i
(lambda (a b)
(cond ((< a (car b)) -1)
((and (<= (car b) a)
(< a (cadr b))) 0)
(t 1))))))))
(999 NIL 0 -1)
(1002 T 0 0)
(1005 T 0 0)
(1008 T 0 0)
(1011 T 0 0)
(1014 T 0 0)
(1017 T 0 0)
(1020 T 0 0)
(1023 T 0 0)
(1026 T 1 0)
(1029 T 1 0)
(1032 T 1 0)
(1035 NIL 1 1)
(1038 NIL 1 1)
(1041 NIL 1 1)
(1044 NIL 1 1)
(1047 NIL 1 1)
(1050 T 2 0)
(1053 T 2 0)
(1056 T 2 0)
(1059 T 2 0)
(1062 T 2 0)
(1065 T 2 0)
(1068 T 2 0)
(1071 T 2 0)
(1074 T 2 0)
(1077 T 3 0)
(1080 T 3 0)
(1083 T 3 0)
(1086 T 3 0)
(1089 T 3 0)
(1092 T 3 0)
(1095 T 3 0)
(1098 T 3 0)
(1101 NIL 3 1)
NIL
--
"A TRUE Klingon warrior does not comment his code!"
(message (Hello 'Pascal)
(you :wrote :on '(Fri, 19 Aug 2005 01:46:35 +0200))
(
??>> to imrove efficienct to keep log(n) access time.
PB> Put the list into a vector, sort it, and use a dichotomy.
indeed, binary trees and hashtables are often misused -- simple dichotomy
can provide better performace because of less overhead, if no realtime table
updates are required.
PB> If you need to insert new ranges in O(log(n)) instead of O(n), then
PB> put them in some kind of balanced binary tree.
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")
·········@yahoo.com writes:
> Just curious in my example, itx has 4 items. If the item count
> increases to say 10000 will the above algorithms still be
> efficient?
The efficiency won't change, but it is doing a linear search so it
will take about 10000 times longer.
> The fact there is partial ordering is it feasible to use a BST or
> some kind of hash-code to imrove efficienct to keep log(n) access
> time.
A partial ordering? Do the sets overlap? If there are holes, but no
overlaps, you still have a total ordering.
In your example, you have this:
(1000 1025 101 101 101 101)
(1025 1050 104 104 104 104)
(1050 1075 106 106 106 106)
(1075 1100 109 109 109 109)
and this:
(defun rc2 (income)
(find income itx
:test #' rate-calc))
which sure looks a lot like a tax table of some kind.
Since the table is partitioned on boundaries of 25, you could compute
the row directly from the income: (floor (- income 1000) 25)
Probably your table is a bit less regular than that, but it may be
regular enough to do a similar trick.
~jrm
Joe Marshall wrote:
> ·········@yahoo.com writes:
>
> > Just curious in my example, itx has 4 items. If the item count
> > increases to say 10000 will the above algorithms still be
> > efficient?
>
> The efficiency won't change, but it is doing a linear search so it
> will take about 10000 times longer.
>
> > The fact there is partial ordering is it feasible to use a BST or
> > some kind of hash-code to imrove efficienct to keep log(n) access
> > time.
>
> A partial ordering? Do the sets overlap? If there are holes, but no
> overlaps, you still have a total ordering.
>
> In your example, you have this:
>
> (1000 1025 101 101 101 101)
> (1025 1050 104 104 104 104)
> (1050 1075 106 106 106 106)
> (1075 1100 109 109 109 109)
>
>
> and this:
>
> (defun rc2 (income)
> (find income itx
> :test #' rate-calc))
>
> which sure looks a lot like a tax table of some kind.
>
> Since the table is partitioned on boundaries of 25, you could compute
> the row directly from the income: (floor (- income 1000) 25)
>
> Probably your table is a bit less regular than that, but it may be
> regular enough to do a similar trick.
>
> ~jrm
Yes, I am writing income tax (personal and business) and accounting
software--and Lisp seems like a good match for this type of thing. I
first tried doing it in Haskell/SML and then Prolog (SWIPL) but lisp
seems to be the most flexible choice-- although Ocaml with Camlp4
http://martin.jambon.free.fr/camlmix/ seems like a strong contender.
Most real world software does not fit into precise "business rules etc"
its basically a hodge podge of a little bit of everything. Lisp's
Dynamic typing really makes it a pleasure to code and do exploratory
programming in--and it sure blows the socks off of Python in terms of
raw performance. The real power of lisp is its' huge library and the
ability to mold a system and keep it moldable why you are developing
it. My Current development platform is Mac OSX and I have not been very
lucky in getting open source lisps up and running and communicating
with a GUI. I have looked at TCL, WxWidgets, Qt, GTK, XPCE, etc and
tried out a combination of SLIMe clisp, sbcl, mcl, etc. And then I ran
into CAPI which seems promising--but haven't yet fully tested it out.
The quandary I am in is that I am worried about using lisp open source
solutions for large scale software deployment--and am hoping that
commercial lisp versions are better supported with less bugs,etc.
So, I am currently developing with Lispworks (Personal Edition)and am
wondering if this is the best way to go--before purchasing their
enterprise edition. We intend to market our software by allowing users
to download software and then connect to our servers using socket
connections. In the past(1998) I worked with Allegro Lisp but currently
it is expensive and I am not sure if it really does much more than what
Lispworks does. Basically I am looking at the following: Reliable GUI +
socket interface classes for doing efiling (XML based); plus Lispworks
has embedable prolog and foward chaining (CLIPS like) expert system.
Both of which I haven't tried but it is claimed that prolog wise it is
Edinburg compliant (although I do prefer ISO compliance). Our software
will be mostly command line driven and have a very simple GUI. I am
still tinkering with LISA as well as Qi which seem as useful adjuncts
(allows pattern matching) to lisp. Also the Collect library for Lisp
List Comprehensions seems interesting to use.
When the software sells I want to hire lots of Lisp programmers, as
well as investing in the lisp community!
(We pride ourselves in being a non Java shop)
·········@yahoo.com writes:
> Yes, I am writing income tax (personal and business) and accounting
> software--and Lisp seems like a good match for this type of thing.
> When the software sells I want to hire lots of Lisp programmers, as
> well as investing in the lisp community!
> (We pride ourselves in being a non Java shop)
Good luck!
·········@yahoo.com noted:
> (defun rc3 (income)
> (find-if (lambda (x) (<= (car x) income (cadr x))) itx))
>
> fails on the max boundary: e.g. (rc3 1025) but
Common Lisp offers many ways of doing software engineering.
For example, you would like to centralise this bounds
checking code so that you can get this important little
detail right once and for all. The CLOS way is to define a
mix-in class for bands, define the tests as methods on that
class, then use multiple inheritance to deploy the same
tests in all the objects that use bands.
It might go like this:
;;; bands pervade income tax calculations
;;; so we define a band class that we can mix in where needed
(defclass band ()
((inclusive-lower-limit :accessor bot :initarg :bot)
(exclusive-upper-limit :accessor top :initarg :top)))
;;; We have to get the <= and < right
;;; We do so once for all calculations involving bands
(defmethod in-band ((entry band) value)
(and (<= (bot entry) value)
(< value (top entry))))
;;; Some of these tables with bands are long
;;; We will need to do a binary search for efficieny.
;;; And we need to get the <= and < right here too!
(defmethod three-way-split ((entry band) value)
"Say if the band is too high, too low or just right"
(cond ((< value (bot entry)) 'too-high)
((in-band entry value) 'just-right)
((<= (top entry) value) 'too-low)))
;;; four entries in the filing amounts table
(defclass filing-amounts ()
((amt-single :accessor single :initarg :single)
(amt-married-jointly :accessor jointly :initarg :jointly)
(amt-married-separately :accessor separately :initarg :separately)
(amt-head-of-household :accessor head-of-household
:initarg :head-of-household)))
;;; the tax table specifies the filing amounts in bands
(defclass tax-table-entry (band filing-amounts))
;;; ^
;;; |
;;; All our classes that involve bands get the in-band
;;; method by inheritance from the band class so
;;; the boundary cases ought to always come out right by design
;;; Builds a vector of objects
;;; from a list in a format designed for data entry
;;; first comes the class
;;; then a list of initargs
;;; finally all the data
;;;
(defun table-builder (raw-data)
(let ((class (first raw-data))
(args (second raw-data))
(data-entries (cddr raw-data)))
(let ((object-list (loop for entry in data-entries
collect (apply #'make-instance
class
(mapcan #'list
args
entry)))))
(make-array (length object-list)
:initial-contents object-list))))
(defparameter raw-tax-table-data
'(tax-table-entry
(:bot :top :single :jointly :separately :head-of-household)
( 1000 1025 101 101 101 101)
( 1025 1050 104 104 104 104)
( 1050 1075 106 106 106 106)
( 1075 1100 109 109 109 109)
(18800 18850 2466 2109 2466 2314)
(18850 18900 2474 2116 2474 2321)
(18900 18950 2481 2124 2481 2329)
(18950 19000 2489 2131 2489 2336)
(19000 19050 2496 2139 2496 2344)
(19050 19100 2504 2146 2504 2351)
(19100 19150 2511 2154 2511 2359)
(19150 19200 2519 2161 2519 2366)))
(defparameter tax-table (table-builder raw-tax-table-data))
(defun rc (income)
(search-ordered-vector tax-table (criterion-is income)))
(defun search-ordered-vector (vector test)
(labels ((hunt (lower upper)
(if (>= lower upper) nil
(let ((index (floor (+ lower upper) 2)))
(case (funcall test (aref vector index))
(too-high (hunt lower
index))
(too-low (hunt (+ index 1)
upper))
(just-right (values (aref vector index) index)))))))
(hunt 0 (length vector))))
(defun criterion-is (target)
(lambda (object)(three-way-split object target)))
(head-of-household (rc 18913)) => 2329
One of the best features of Common Lisp is that it offers me
ways of making my code banal, with the tricky details tucked
away where I cannot bork them during maintenance. There
ought to be a word for this. Suggestions anyone?
Alan Crowe
Edinburgh
Scotland
Alan Crowe wrote:
> One of the best features of Common Lisp is that it offers me
> ways of making my code banal, with the tricky details tucked
> away where I cannot bork them during maintenance. There
> ought to be a word for this. Suggestions anyone?
Banal Un-Borkability, or BUB. Sounds like a good buzzword...
Manager : "Hey, i heard we need more BUB is our codebase"
Lisper : "MORE BUB!"
drewc
--
Drew Crampsie
drewc at tech dot coop
"Never mind the bollocks -- here's the sexp's tools."
-- Karl A. Krueger on comp.lang.lisp
drewc wrote:
> Alan Crowe wrote:
>
>> One of the best features of Common Lisp is that it offers me
>> ways of making my code banal, with the tricky details tucked
>> away where I cannot bork them during maintenance. There
>> ought to be a word for this. Suggestions anyone?
>
>
> Banal Un-Borkability, or BUB. Sounds like a good buzzword...
>
> Manager : "Hey, i heard we need more BUB is our codebase"
^in our codebase"
--
Drew Crampsie
drewc at tech dot coop
"Never mind the bollocks -- here's the sexp's tools."
-- Karl A. Krueger on comp.lang.lisp
> Is there a way how this can be accomplished using a combination of key
> and test keywords?
It's not a LISP question, it's a homework question.
What do you want to do?
In English it could be said like that:
I have a list of lists (rate calculation rules).
I have a number (income).
I want to FIND such a sub-list,
where two first elements define an interval,
that the income number falls into.
Now the same in LISP:
(defun rate-calc (income)
(find-if
(lambda (sub-list)
(and (>= income (first sub-list))
(< income (second sub-list))))
itx))
> Also this is doing list searching. Is it possible to store this in a
> hash table and some how to a lookup
> on a key changing equality operators?
What about efficiency, I wonder whether do you plan to call this
function 10,000,000 times a second, and to have more than 1,000,000
rate-calculation rules.
If so, hash tables won't help, because all speed-efficiency of them are
based on equality-test search. What will help you in this case is
balanced indexed-search tree, like RB or AVL (my favorite :)). Using
them you can do a fast search by inequality predicate.
By the way, I possibly have a lack in my education, but I still don't
understand if hashes really work faster than balanced trees both for
insertion and search.
Revzala Haelmic <··@fck.org> writes:
> By the way, I possibly have a lack in my education, but I still don't
> understand if hashes really work faster than balanced trees both for
> insertion and search.
Yes, they do if there are (nearly) no collisions. If there are
many collisions then in worst case you have a simple list.
In fact balanced trees exists because one want's to get rid of the
worst case of hash tables -- so if you can make sure there are
only very, very few collisions, hash tables are better than
balanced trees but if not trees may be (much) better.
--
Stefan.
Revzala Haelmic <··@fck.org> writes:
> By the way, I possibly have a lack in my education, but I still don't
> understand if hashes really work faster than balanced trees both for
> insertion and search.
Hash tables are great if you:
1. know what size to make them
2. can write an appropriate hash function for your keys
3. don't need keys to be in a particular order at any given time
If your table will hold 5 items at one point and 5000000 at another and
always needs to take up the least amount of memory then many hash table
implementations will be unsuitable.
If you can't write a good hash function for your key then you will get
lots of collisions -- also making the hash table unsuitable.
If you need your keys to be ordered at any given time so that you can
iterate over all or a portion of them or so that you can find upper or
lower bounds then a hash table will be unsuitable.
However, it turns out you don't always need the items listed above so hash
tables turn out to be useful for most problems.
Unfortunately, for problems not suited for hash tables people sometimes
mistakenly believe they need a balanced tree. Balanced trees are most
useful when you need a total ordering with frequent insertions and
deletions. If you just want your items sorted, for example, but never add
and delete items once you have it setup then a sorted vector will be much
faster.
John <········@mailinator.com> wrote:
+---------------
| Unfortunately, for problems not suited for hash tables people sometimes
| mistakenly believe they need a balanced tree. Balanced trees are most
| useful when you need a total ordering with frequent insertions and
| deletions. If you just want your items sorted, for example, but never add
| and delete items once you have it setup then a sorted vector will be much
| faster.
+---------------
One should also consider AVL trees (a.k.a. HB[1]), red/black trees,
2-3 trees [order 3 B-tree], and other kinds of trees which permit
limited height or splay imbalance in exchange for better performance
than balanced binary trees. The following contains a summary of some
of the variations:
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic19/
Also see:
http://www.cliki.net/TREES
http://www.cliki.net/spatial-trees
http://www.cliki.net/Red-Black-trees
http://www.toad.net/~menkejg/nary-tree
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> One should also consider AVL trees (a.k.a. HB[1]), red/black trees,
> 2-3 trees [order 3 B-tree], and other kinds of trees which permit
> limited height or splay imbalance in exchange for better performance
> than balanced binary trees.
Red-black trees are closely related to 2-3-4 trees, but they are not
the same as AVL trees.
Paul