Пролог: получить максимальное / минимальное значение с помощью возврата?

Question

Я хотел бы знать, если это хорошая идея, чтобы получить максимальное значение (самый старый человек) некоторых фактов с помощью обратного отслеживания, как это:

data(MaxID, MaxName, MaxAge),
\+ (data(ID, Name, Age), ID \= MaxID, MaxAge < Age).

Или наоборот для минимального значения (самый молодой человек):

data(MinID, MinName, MinAge),
\+ (data(ID, Name, Age), ID \= MinID, MinAge > Age).

Эффективно ли это с точки зрения пространственной или временной сложности?

Является ли стиль реализации простым / понятным? Существуют ли "более хорошие" реализации?

Answer 1

Эффективно ли это с точки зрения пространственной или временной сложности?

Ваша реализация - это O(N^2) относительно временной сложности, поскольку для каждого предиката-кандидата все остальные "вызываются" для сравнения. Пространственная сложность O(1).

Существуют ли "более хорошие" реализации?

Да, более хорошие и эффективные реализации существуют. Уже давно SWI-Prolog предлагает библиотеку ( агрегат), прямое улучшение классических встроенных функций setof/bagof/findall:

?- aggregate(max(Age,data(ID,Name,Age)), ID^Name^data(ID,Name,Age), max(_,X)).

Обратите внимание на стиль количественного контроля, выраженный ID^Name^..., Это то же самое, что требуется для setof/3 и bagof/3. Реализация является более эффективной, основанной на невыбираемом назначении.

Последним дополнением можно считать библиотеку ( solution_sequence). Прежде чем копаться в этом последнем, подумайте об использовании библиотеки (агрегата).

редактировать

Основываясь на @false комментарии к вопросу и ответе @boris, я бы попытался обеспечить более "хорошую" (конечно, субъективную оценку) реализацию:

min(P,A) :-
    copy_term(P,Q),
    arg(A,P,V), arg(A,Q,U),
    call(P), \+ ( call(Q), U@<V ).

Теперь вы можете передать свой предикат в качестве первого параметра и указать аргумент P использоваться для сравнения со вторым параметром.

Answer 2

Короткий ответ: нет, на самом деле ничего более "хорошего" не существует, с точки зрения того, чтобы быть всегда правильным, простым в реализации и эффективным одновременно.

Небольшая поправка: достаточно написать

data(MaxID, MaxName, MaxAge),
\+ (data(ID, Name, Age), MaxAge < Age)

(как предложено @false в комментарии к вашему вопросу)

Вы можете увидеть также этот вопрос и ответы. Этот ответ в деталях, когда и почему с помощью setof/3 может быть проблематичным. Это может быть важно для вашего случая использования.

Другой способ сделать это (не упомянутый в очень полезном ответе @CapelliC) - собрать все решения из вашего предиката и отсортировать их, используя ключ. Если вы используете SWI-Prolog или другой Prolog, имеющий версию сортировки с 4 аргументами, которая позволяет вам выбирать сравнение и ключ в термине, вы можете сделать, например:

bagof(data(ID, Name, Age), data(ID, Name, Age), All),
sort(3, @>=, All, [data(Max_ID, Max_Name, Max_Age)|_])

Пока ваш data/3 это просто таблица фактов, это безопасно для использования.

Это, конечно, ломается, если у вас есть эквивалентные, но не равные элементы в списке, как data(10, john, 34) а также data(101, jane, 34), В вопросе и ответе, который я связал, есть примеры, как с этим справиться, но опять же, я действительно не думаю, что это становится "лучше". Это может быть более эффективным. Я настоятельно рекомендую тщательно рассмотреть ваш вариант использования и измерить производительность, если вы считаете, что это может быть "горлышком бутылки".

Рассматривая реализацию библиотеки (агрегата), предложенную @CapelliC, становится очевидным, что она предназначена именно для этого варианта использования: она может найти минимум, максимум, сумму и т. Д. В постоянной памяти и затрагивать каждый факт только один раз и отступает построить весь список, если это необходимо.