On Wed, Aug 01, 2007 at 01:42:52PM -0700, Dan Weston wrote:
Andy Gimblett wrote:
cartesian :: Ord a => S.Set a -> S.Set (a,a) cartesian x = S.fromList [(i,j) | i <- xs, j <- xs] where xs = S.toList x
Your list comprehension always generates a sorted list, so changing S.fromList to its "unsafe" version (but guarateed by you) S.fromDistinctAscList should get you back to O(n).
That'll do it: with that change, my program runs eight times faster; according to the profiler, it's gone from spending ~85% of its time in cartesian to ~0%. :-) I don't see why my list comprehension always generates a sorted list, however: toList generates a sorted list? It doesn't claim to in the docs. Do I perhaps need to use toAscList instead? I happen to have put my data into the Set in order in this example, so maybe I just lucked out? Or am I missing something?
Of course the order of the generators was key (i before j).
Lucky me. :-) Thanks! -Andy -- Andy Gimblett Computer Science Department University of Wales Swansea http://www.cs.swan.ac.uk/~csandy/