Как я могу сказать, какова вычислительная сложность программы clpfd? - PullRequest
Новая
       37

Как я могу сказать, какова вычислительная сложность программы clpfd?

0 голосов
/ 04 марта 2019

Например, скажем, у меня есть эта программа (проверена только на swi-прологе): 

:- 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, очевидно, использует атрибуты, чтобы подключиться к объединению?Я не знаю достаточно об атрибутах, чтобы понять, что это означает для сложности программ, которые я пишу.Где-нибудь я мог бы это узнать?

1 Ответ

0 голосов
/ 06 марта 2019

Пример эксперимента: 

:- 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]

Таким образом, время увеличивается, когда мы добавляем единицу к размеру списка ...

...