[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>