[m-users.] Cartesian product of two sets of things.

[Zoltan Somogyi]

On 2023-10-10 21:02 +11:00 AEDT, "Julien Fischer" <jfischer at opturion.com> wrote:
> A big part of the difference would be that the nondet version sorts
> the elements and (redundantly) attempt to remove duplicates, whereas the
> det version just constructs the elements in reverse order directly.

Another source of difference is that its lowest level operations
are tail recursive, while the lowest level operations in the nondet version
can't be tail recursive, because you can't recover a nondet stack frame
while the values of the variables it contains may be needed to find
another solution.

You should note that even the det version in cproduct.m is not
as fast as it could be, because it adds each new item to the cross product
using a higher order call. Converting the sets to sorted lists and iterating
over the lists directly could replace those higher order calls with simple
unifications, which would make that version even faster.

But there is another question: do you actually want a cartesian product?
What percentage of the objects you are dealing with actually move?
If that percentage is high, then the cartesian product approach is
probably appropriate. If it is low, then another approach is probably
better, because any time spent checking whether two stationary objects
have collided is wasted. (I don't think the Eiffel tower will collide with
the Burj Khalifa anytime soon.) Approaches based on data structures
such as oct-trees, k-d-trees or region trees (rtrees) would let you check
for collisions between (a) just the moved objects and (b) just the objects,
moving and stationary, near the moved object being examined.
This approach has a higher constant factor than the cartesion product
approach due to the need to maintain a tree, but its asymptotic
complexity would be lower, so for large enough data sets, it should be
faster.

The Mercury standard library contains an implementation of one of the
data structures I mentioned above; you may want to check out rtree.m.
I have never used it myself, so I can't vouch for it, but it may be
worth a try.

Zoltan.