我怎么知道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显然使用属性挂钩统一？我对属性知之甚少，不知道这对我编写的程序的复杂性意味着什么。有什么地方我能找到吗？

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]

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