# [plt-scheme] efficient set implementation

Chongkai Zhu skrev:
>* Is there any existing efficient set implementation (like RedBlackSet) in Scheme, PLT in particular?
*
The Galore set implementation is reasonably efficient.
However! If all your sets are small the simple minded list based
implementation will probably be faster.
----------------------------------------------------------------------
TIME COMPLEXITIES
----------------------------------------------------------------------
The following table shows the worst case time complexity. The O( ) has
been omitted due to space considerations.
RB-Set RB-Bag Leftist-Heaps List-Set List-Bag
find-min 1 1 1 1 1
delete-min 1 1 1 1 1
get, member? log n log n n n n
insert log n log n log n n n
union n+m n+m log(n+m) n+m n+m
elements n n n 1 n
delete log n log n log n n n
delete-all log n log n log n n n
size n n n n n
bag, list->set n log(n) n log(n)
heap, list->bag n log(n) n log(n)
set, list->heap n
The operations: empty?, empty, singleton, and select are all O(1).
Note that the complexity of union is n+m (just as the AVL trees).
Any insights on improving this is welcome.
Attached is two simple benchmarks. I think they measure the same,
but you better check your self.
Btw - there is also an implementation of integer sets in MzLib:
<http://download.plt-scheme.org/doc/352/html/mzlib/mzlib-Z-H-21.html#node_chap_21>
--
Jens Axel S?gaard
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: benchmark-avl.scm
URL: <http://lists.racket-lang.org/users/archive/attachments/20060904/d38e78d3/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: benchmark-galore2.scm
URL: <http://lists.racket-lang.org/users/archive/attachments/20060904/d38e78d3/attachment-0001.ksh>