Сложность предикатов ISO Пролог

Question

Есть ли гарантии для верхних границ сложности времени стандартных предикатов Пролога?

Например: точно ли это sort(+List, ?SortedList) выполняется за время O(nlog(n)) (n - длина List) в любой стандартной системе Prolog?

Answer 1

Д -р: нет и нет.

Давайте начнем с sort/2 который в идеале потребовал бы n ld (n) сравнений. Хорошо, но сколько времени занимает одно сравнение? Давайте попробуем это:

tails(Es0, [Es0|Ess]) :-
   Es0 = [_|Es],
   tails(Es, Ess).
tails([],[[]]).

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

| ?- between(12,15,I), N is 2^I, length(L,N),maplist(=(a),L),
     tails(L,LT), call_time(sort(LT,LTs), Tms).

На SICStus 4.3.1 и SWI 7.1.28

I = 12, N = 4096,   Tms_SICS =   680,  Tms_SWI =   3332
I = 13, N = 8192,   Tms_SICS =  2800,  Tms_SWI =  14597
I = 14, N = 16384,  Tms_SICS = 11300,  Tms_SWI =  63656
I = 15, N = 32768,  Tms_SICS = 45680,  Tms_SWI = 315302

Дублируя размер, мы можем легко оценить, каким будет время выполнения. Если он также дублируется, он является линейным, а если он увеличивается в четыре раза, то он квадратичен. Очевидно, что оба имеют как минимум квадратичное время выполнения.

Описать точное время выполнения абстрактным способом возможно, но очень трудно убедиться, что все в порядке. В любом случае, практически невозможно назначить конкретное обещание в стандартном документе. Кроме того, очень трудно подтвердить такие претензии.

Лучшей абстрактной мерой может быть число выводов, часто их легко наблюдать. Смотрите наибольшее целое число или факторы. Но опять же, это только абстрактная мера - поэтому что-то оторвано, абстрактно. Вполне может быть, что ключевые функции тоже были оторваны.

Как правило, ядро ​​стандарта ISO/IEC 13211-1:1995 не требует каких-либо гарантий на сложности во время выполнения, которые явно выходят за рамки. В примечании прямо упоминается, что также ограничения ресурса выходят за рамки:

1 Область применения

....

ПРИМЕЧАНИЕ. - Эта часть ISO / IEC 13211 не определяет:

а) размер или сложность текста Пролога, который будет превышать
емкость любой конкретной системы обработки данных или языка
процессор, или действия, которые необходимо предпринять, когда соответствующий
превышены лимиты;
...

Всегда помните, что технический стандарт является предварительным условием, чтобы гарантировать, что система подходит для какой-либо цели. Это не достаточное условие. Посмотрите пример в разделе Цель в этом ответе для несколько экстремального примера.