[mercury-users] Set performance

[Richard A. O'Keefe]

Thomas Conway wrote:

	It turns out that the union inside the foldl (ie the inner loop) results
	in O(n^2) behaviour (The list that we're folding over is of similar size
	to the sets). I found that I could change this to O(n log n) by constructing
	a list of new sets in the inner loop, and then unioning the list of sets
	in a pairwise fashion. eg:
		[A, B, C, D, E, F] ->
		[A \/ B, C \/ D, E \/ F] -> ....
	
I note that ordsetes:union/2 in the Quintus library does something
rather similar:
	union([A,B,C,D,E,F,G,H]) =
	((A \/ B) \/ (C \/ D)) \/ ((E \/ F) \/ (G \/ H))

In fact, it's pretty much the same structure as sort/2.

It is _definitely_ a good idea.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------