prolog - 如何判断 clpfd 程序的计算复杂度是多少？

Question

例如，假设我有这个程序(仅在 swi-prolog 中测试过):

:- use_module(library(clpfd)).
:- use_module(library(lists)).

% Sorted has the same elements as List and is also sorted
clpfd_sort(List, Sorted) :-
  same_length(List, Sorted),
  chain(Sorted, #=<),
  permutation(List, Sorted).

我在哪里可以找到关于 clpfd 如何工作的足够信息来了解这是否是一个有效的解决方案？问这样一个简单的解决方案可能是贪婪的 n lg(n)但据我所知，它是 10^n .

我查看了诸如 this 之类的来源他们都很好地解释了 clpfd 的魔力但他们都没有充分解释它是如何实现的，让我了解哪些程序会运行得很快，哪些会运行得很慢。 clpfd 显然使用属性 Hook 统一？我对属性的了解不够，无法知道这对我编写的程序的复杂性意味着什么。有什么地方可以查到吗？

Answer 1

示例实验:

:- use_module(library(clpfd)).
:- use_module(library(lists)).

call_time(G,T) :-
   statistics(runtime,[T0|_]),
   G,
   statistics(runtime,[T1|_]),
   T is T1 - T0.

% Sorted has the same elements as List and is also sorted
clpfd_sort(List):-
  same_length(List, Sorted),
  chain(Sorted, #=<),
  permutation(List, Sorted).

item_goal(I,clpfd_sort(I)).

n_randoms_times(NumberOfExperiments,Random_Lists,Times) :- 
  numlist(1,NumberOfExperiments,Experiment_Sizes),
  maplist(numlist(1),Experiment_Sizes,ExperimentLists),
  maplist(random_permutation,ExperimentLists,Random_Lists),
  maplist(item_goal,Random_Lists,Goals),
  maplist(call_time,Goals,Times).

测试:

?- n_randoms_times(15,R,T),write(T).
[0,0,0,1,1,1,2,5,4,3,16,34,43,115,246]

因此，当我们向列表的大小添加一个时，时间看起来会增加一倍......