On 06/04/2023 09:55, Panagiotis Stamatopoulos wrote: > Hello All, > > Is there any possibility for the same program to be more efficient > when it uses ic:alldifferent/1 than its counterpart that exploits > ic_global:alldifferent/1? It seems quite strange to me and I wonder > if I am doing something wrong. Yes, this is possible, and even quite common. The reason is that there is a trade-off between the potential strength of propagation, and the effort with which this can be achieved. For example, the stronger algorithm of ic_global:alldifferent/1 can detect failures before any variables are instantiated, e.g. ?- length(Xs,3), Xs#::1..3, ic_global:alldifferent(Xs), max(Xs)#=2. No (0.00s cpu) which the simple ic:alldifferent/1 implementation misses: ?- length(Xs,3), Xs#::1..3, ic:alldifferent(Xs), max(Xs)#=2. Xs = [_762{[1,2]},_776{[1,2]},_790{[1,2]}] There are 4 delayed goals. Yes (0.00s cpu) To be able to achieve this, ic_global:alldifferent/1 * wakes up on every variable domain reduction * runs an algorithms with a complexity of at least O(N*log(N)) whereby ic:alldifferent/1 * only wakes up when a variable is instantiated * costs only O(N) time Better propagation may lead to a smaller search tree and therefore has the potential for exponential speed-up. But if the extra propagation does not lead to enough search space reduction, the effort is wasted and an overall slowdown can result. This phenomenon is not specific to alldifferent, but to all global constraints where propagation algorithms of different strength and complexity exist. An additional remark: in some cases, it could even be advantageous to call both versions together via [ic,ic_global]:alldifferent(Xs) You then get full strength propagation from ic_global, and potentially quicker discovery of simple failures from the ic version. -- JoachimReceived on Fri Apr 07 2023 - 10:19:16 CEST
This archive was generated by hypermail 2.3.0 : Wed Sep 25 2024 - 15:13:21 CEST