Raphael Collet wrote:
Russ Abbott wrote:
In reply to code that I wrote that looked though a list of values and
failed if two of them were equal (==), Raph suggested the code
below--which is better than my original nested double loop.
In class today, Brian Smith proposed the following clever hack.
proc {AllDistinct Xs}
thread
try {MakeRecord test Xs _}
catch _ then fail end
end
end
It uses the fact that MakeRecord will fail if the field names it gets
have a repeated value. It suspends until all values are instantiated.
So the point is not really to make a record but to use MakeRecord's
check on the list of fields to detect duplicates. The only reason to
wrap it all in a try-catch is to get rid of the diagnostics that are
printed in the Oz emulator buffer window otherwise.
Indeed, it will work. It is semantically sound. But as you said, it
waits until all variables in Xs are determined. This may generate a
huge amount of search for nothing. Mine concurrently checks all
constraints that constitute the AllDistinct constraint.
Another alternative is to use a port:
declare
proc {AllDistinct Xs}
Values P={NewPort Values}
in
for X in Xs do thread {Wait X} {Send P X} end end
thread
{FoldL Values fun {$ CurValues V}
{Member V CurValues false}
V|CurValues
end nil _}
end
end
The advantage is that this approach only needs a linear number of threads.
Certainly, Member takes linear time but you can use a dictionary as an
accumulator.
Luis
PS: We have used ports for implementing DomReachability( a constraint
that combines the notions of domination and reachability
(http://www.info.ucl.ac.be/~luque/PADL06/paper.pdf)). Please have a look
at http://www.info.ucl.ac.be/~luque/papers/CLEI2005.pdf for details
about the current implementation. Using this approach, we were able to
solve cases like the one in
http://www2.info.ucl.ac.be/~luque/PADL06/DPcase.ps where we were able to
find 14 disjoint paths in a graph of 165 nodes failing less than 100 times.
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
