如何判断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]

所以看起来时间加倍了，因为我们在列表的大小上加了一个…

Answer 2

处理Prolog或clpfd程序的复杂性的最好方法是避免内部的实际机制，而首先专注于具体的答案或答案集。毕竟，如果这样的分析已经表明一个非常大的O，那么任何进一步的细节都是徒劳的，就像你的程序中的情况一样。

考虑一个包含n个相等数字的列表。在这种情况下，我们将获得n个有效的排列。因此，最坏情况的复杂度至少是O(n!)。这似乎已经够糟糕的了，需要重新考虑你的方法。

在这种情况下，最好的方法是开发一个将该整数列表直接关联到实际列表的约束。如果我的记忆力确实很好的话，这已经在Prolog IV的上下文中实现了。