Использование \==/2 или dif/2

Если я хочу убедиться, что две переменные не соответствуют одному и тому же термину, каков предпочтительный способ сделать это?

Допустим, мне нужно найти ориентированные ребра в графе, а у узла не может быть ребра:

node(a, x, y). node(b, z, x). node(c, y, y).

(ребра здесь a -> c, b -> a, но не c -> c)

Следующие работы:

edge(A, B) :- node(A, _, X), node(B, X, _), A \== B.

Это тоже работает [swi-prolog]:

edge(A, B) :- dif(A, B), node(A, _, X), node(B, X, _).

Это не работает, по-видимому (потому что ни A, ни B еще не созданы?):

edge(A, B) :- A \== B, node(A, _, X), node(B, X, _).

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

Источник

3 ответа

Решение

Только для элегантности и дидактических целей, dif/2 явно предпочтительнее здесь, а также в подавляющем большинстве других случаев, так как, как вы уже заметили, "может произойти много ненужных объединений", а также потому, что dif/2 это чистый и красиво декларативный предикат, который можно использовать во всех направлениях и в любом месте тела предложения, не меняя смысла программы, в отличие от (\==)/2, dif/2 также является автозагрузочным предикатом в SWI-Prolog, что означает, что вам не нужно явно импортировать какую-либо библиотеку, чтобы использовать его, и dif/2 доступно как любой встроенный предикат.

Если вы используете dif/2 Вы можете гораздо проще рассуждать о своем коде. Например, в вашем случае вы начинаете с:

ребро (A, B):- узел (A, _, X), узел (B, X, _), dif (A, B).

а потом, как вы знаете, что dif/2 это абсолютно чистый предикат, вы знаете, что вы также можете написать это как:

край (A, B):- диф (A, B), узел (A, _, X), узел (B, X, _).

Далее, так как вы знаете, что dif/2 всегда завершается, вы знаете, что это изменение может максимально улучшить свойства завершения вашей программы.

Как и все ограничения, dif/2 предназначен для использования. Я настоятельно рекомендую это вместо нечистых предикатов, которые не являются коммутативными.

Если вы беспокоитесь о производительности, вот небольшое сравнение, просто сравнение dif/2 против не декларативного (\==)/2 в случае использования, где два предиката могут использоваться взаимозаменяемо:

? - N = 1_000_000, время ((между (1,N,_),dif(a,b),false)).
% 11 000 005 выводов, 0,352 ЦП за 0,353 секунды (100% ЦП, 31281029 губ)
? - N = 1_000_000, время ((между (1,N,_),a\==b,false)).
%@ % 3 000 001 вывод, 0,107 ЦП за 0,107 секунды (99% ЦП, 28167437 губ)

Таким образом, иногда есть преимущества в производительности при использовании (\==)/2, Однако при использовании такого низкоуровневого предиката есть и гораздо более серьезные недостатки: его сложнее понять, он более подвержен ошибкам и не декларативен.

Поэтому я рекомендую просто использовать dif/2 чтобы выразить, что два термина разные.

Источник

Запросы мета-интерпретируются, и накладные расходы могут перевесить различия dif(X,Y) а также X\==Y, Вы должны сравнить эти два предиката:

t1:-
    1000=I,
    time(t1(I)).


t1(I):-
    dif(X,Y), 
    between(1,I,X), 
    between(1,I,Y), 
    false.

t2:-
    1000=I,
    time(t2(I)).


t2(I):-
    between(1,I,X), 
    between(1,I,Y), 
    X\==Y,
    false.

На B-Prolog я получил следующие результаты:

| ?- cl(t)
Compiling::t.pl
compiled in 0 milliseconds
loading::t.out

yes
| ?- t1
CPU time 0.14 seconds.
no
| ?- t2
CPU time 0.078 seconds.
no
| ?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false )).
CPU time 0.234 seconds.
no
| ?- 1000=I,time(( between(1,I,X), between(1,I,Y), X \== Y, false )).
CPU time 0.218 seconds.
Источник

Прежде всего, dif/2 а также (\==)/2 означают одно и то же, когда оба аргумента основаны, то есть переменная свободна. Так что, если вы можете гарантировать, что аргументы будут обоснованы - или, скорее, достаточно конкретизированы, чтобы дальнейшие экземпляры не влияли на результат (\==)/2 - тогда это не имеет значения.

В вашем примере нам нужно знать наверняка, что ответы на node/3 всегда содержать первый аргумент В этом случае (\==)/2 Программа в порядке. В редких случаях это может быть менее эффективным, чем dif/2 версия. Думай о цели edge(X, X),

Во многих ситуациях (\==)/2 или даже (\=)/2 значительно эффективнее С другой стороны, насколько важна эффективность по сравнению с правильностью?

Другой способ увидеть это, это рассмотреть (\==)/2 а также (\=)/2 как приближения с двух сторон: Только если оба согласны, мы можем получить безопасный окончательный результат.

Исторически, dif/2 является одним из старейших встроенных предикатов. Он присутствовал в самой первой системе Пролога, которую иногда называют Прологом 0, чтобы отличить ее от следующей версии, которая часто воспринимается как первый Пролог - Пролог Марселя - Пролог 1. Пролог 1 больше не имел dif/2 и именно в этой форме Пролог приехал в Эдинбург. Также, dif/2 не является частью стандарта ISO (в настоящее время), поскольку требует некоторого механизма, подобного сопрограммному. И многие (довольно старые) системы Prolog не имеют такого механизма. Однако даже в ISO Prolog можно было сделать лучше:

iso_dif(X, Y) :-
   X == Y,
   !,
   fail.
iso_dif(X, Y) :-
   X \= Y,
   !.
iso_dif(X, Y) :-
   throw(error(instantiation_error,iso_dif/2)).

(Вот еще одна, возможно, более эффективная реализация)

Обратите внимание, как проблемные случаи покрываются ошибкой, которая останавливает все вычисления.

Современные системы Prolog, которые поддерживают dif/2 прямо из коробки B, SICStus, SWI, YAP. Он находится в библиотеке IF, Ciao, XSB.

Смотрите также этот ответ.

Чтобы поддержать мое утверждение о накладных расходах, вот тест в разных Прологах на одной машине. В SWI накладные расходы в 10 раз выше, в B нет накладных расходов. Как было отмечено @nfz, числа немного отличаются при компиляции. Так что ваш пробег может отличаться.

SWI 6.3.4-55

?- 1000=I, время (( dif(X,Y), между (1,I,X), между (1,I,Y), ложно)).
% 22,999,020 выводов, 5,162 ЦП за 5,192 секунды (99% ЦП, 4455477 губ)
ложный.
?- 1000=I, время ((между (1,I,X), между (1,I,Y), X \== Y, false)).
% 2 000 001 вывод, 0,511 ЦП за 0,521 секунды (98% ЦП, 3912566 Губ)
ложный.

B 7,8

|?- 1000=I, время (( dif(X,Y), между (1,I,X), между (1,I,Y), ложно)).
Время процессора 0,364 секунды.
нет
|?- 1000=I, время ((между (1,I,X), между (1,I,Y), X \ == Y, false)).   
Время процессора 0,356 секунды.
нет

ПЕА

?- 1000=I, время (( dif(X,Y), между (1,I,X), между (1,I,Y), ложно)).
% 2,528 ЦП за 2,566 секунды (98% ЦП)
нет?- 1000=I, время ((между (1,I,X), между (1,I,Y), X \ == Y, false)).
% 0,929 ЦП за 0,963 секунды ( 96% ЦП)
нет
Источник
Другие вопросы по тегам