[From nobody Tue Jan 17 23:17:41 2012
Message-ID: <44FCC06D.5010401@ir.iit.edu>
Date: Mon, 04 Sep 2006 20:10:21 -0400
From: Jefferson Heard <heard@ir.iit.edu>
User-Agent: Thunderbird 1.5.0.5 (X11/20060812)
MIME-Version: 1.0
To: Hans Oesterholt-Dijkema <hdnews@gawab.com>
Subject: Re: [plt-scheme] efficient set implementation
References: <000701c6d030$e5efe670$5ae8619b@DrMathematica>	<1157382448.4970.0.camel@localhost.localdomain>
	<44FC5779.20902@gawab.com> <44FC70C4.7030702@ir.iit.edu>
	<44FC8A80.1010304@gawab.com>
In-Reply-To: <44FC8A80.1010304@gawab.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Hans Oesterholt-Dijkema wrote:
>
>> 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.
> I understand. However, I needed something that could handle shared 
> parallel access on the same datastructure and, if I remember well, 
> galore implements it's structures in a functional way, i.e., each 
> thread will eventually have it's own copy.
>
> --Hans
>
>>
>> -- Jeff
>>
>>
>
>
Yes, that's exactly the point of Galore -- which is exactly what I 
said.  I checked on Galore's documentation, though, and it uses 
Red/Black trees for its implementation of sets by default, so you will 
have an O(n) union time for elements of the set.  This suffices in 99 
cases out of 100, so you should probably pick galore.  If you are doing 
thousands of set-unions over sets of thousands of elements, I'd suggest 
you look at translating Ralf Hinze's excellent pure-functional 
implementation of binomial heaps to Scheme. 

http://www.dcs.gla.ac.uk/jfp/online/jfpvol9-1/hinze/BinomialHeap.lhs

-- Jeff

]