On Thu, Aug 02, 2007 at 04:15:35PM +1200, ok wrote:
On the other hand, I've usually found that it pays to avoid explicitly constructing things like Cartesian products. Could that be the case here?
Quite possibly, though for my purposes I don't _think_ it's worth routing around it. I'm using it in a naive (and intentionally so) algorithm to search for "local top elements" in a partial order. That is, we require that the PO satisfies the property: for all a,b,c in PO . a <= b and a <= c => exists d in PO . b <= d and c <= d where a is a "local bottom element" for b and c, and d is the corresponding "local top element". Given a PO, for every such a, I want the set of corresponding d's. If any such set is empty, a big red "NO" lights up elsewhere in the program. My algorithm is the simplest thing I could think of that works: represent the PO as a Set of (a,a), then simply search its cartesian product, a Set of ((a,a),(a,a)), for elements of the right shape. It works, in only a few lines of code, and really looks a lot like the definition given above. It also seems to be fast enough for reasonably sized examples - for a PO with ~40 elements it's instantaneous. That's at the bottom end of "realistic" for my application, and I need to check it for ~100 elements (which is more like my reality), but I think it ought to be fine/usable. If, with real data, it turns out to be too slow then yes, I'll ditch this naive method and look at graph algorithms, which is of course the Smart thing to do. However, it's beautiful (to me) code right now, which strongly reflects the definition of the problem, so I'd be happy not to. :-) Cheers, -Andy -- Andy Gimblett Computer Science Department University of Wales Swansea http://www.cs.swan.ac.uk/~csandy/