[plt-scheme] efficient set implementation

From: Jefferson Heard (heard at duvel.ir.iit.edu)
Date: Mon Sep 4 14:30:28 EDT 2006

Hans Oesterholt-Dijkema wrote:
> I don't know which one is more efficiënt. I've got an implementation
> that is thread safe, based on an AVL implementation.
>
> http://planet.plt-scheme.org/300/#datastructs.plt
>
> --Hans
>
>
> Sam Tobin-Hochstadt schreef:
>> On Mon, 2006-09-04 at 08:46 -0600, Chongkai Zhu wrote:
>>  
>>> Hi all,
>>>
>>> Is there any existing efficient set implementation (like 
>>> RedBlackSet) in Scheme, PLT in particular?
>>>     
>>
>> See galore.plt in PLaneT. 
>> http://planet.plt-scheme.org/#galore.plt
>>
>> sam th
>>
>> _________________________________________________
>>   For list-related administrative tasks:
>>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>
>>
>>   
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
AVL trees only support the set-union operation in O(n) time.  I haven't 
checked galore for it yet, but I'd suspect that the author uses 
something more efficient to represent sets, such as a binomial heap.  I 
know for my purposes, galore's amazingly fast and its bonus of 
referential transparency just plain rocks.  I love not having to make 
copies of a data structure to make sure I have a clean copy.

-- Jeff


Posted on the users mailing list.