17

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、ライブラリ内にあるため、このような単純なケースで使用することを意図したものではないことを示しています（ただし、私が探しているように見える正確な機能を備えています）。

4

3 に答える 3

7

まず第一に、dif/2そして(\==)/2両方の引数が根拠のある場合、つまり変数がない場合も同じことを意味します。したがって、引数が根拠のあるものになること、またはそれ以上のインスタンス化が結果に影響を与えないように十分にインスタンス化されることを保証できれば(\==)/2、違いはありません。

node/3あなたの例では、の答えには常に最初の引数が含まれていることを確認する必要があります。その場合、(\==)/2プログラムは問題ありません。まれに、dif/2バージョンよりも効率が悪い場合があります。目標を考えてくださいedge(X, X)。

多くの場合、(\==)/2または(\=)/2ははるかに効率的です。一方、正確性と比較した場合、効率はどれほど重要ですか？

これを確認するもう1つの方法は、2つの側面からの概算として検討(\==)/2する(\=)/2ことです。両方が同意した場合にのみ、安全な最終結果が得られます。

歴史的に、dif/2は最も古い組み込み述語の1つです。dif/2それは、最初のプロローグであるとしばしば認識される次のバージョンと区別するために、プロローグ0と呼ばれることもある最初のプロローグシステムに存在しました—マルセイユプロローグ—プロローグ1。プロローグがエジンバラにやってきた形。また、dif/2これは、coroutiningのようなメカニズムを必要とするため、（現在）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、Scryerのライブラリにあります。

この回答も参照してください。

オーバーヘッドに関する私の主張を裏付けるために、同じマシン上のさまざまなPrologでのテストを次に示します。SWIでは10倍のオーバーヘッドがあり、Bではオーバーヘッドはありません。@nfzが指摘しているように、コンパイル時の数値はわずかに異なります。そのため、マイレージは異なる場合があります。

SWI 6.3.4-55

？-1000 = I、time（（dif（X、Y）、between（1、I、X）、between（1、I、Y）、false））。
％22,999,020推論、 5.192秒で5.162 CPU（99％CPU、4455477リップ）
false。

？-1000 = I、time（（between（1、I、X）、between（1、I、Y）、X \ == Y、false））。
％2,000,001推論、 0.521秒で0.511 CPU（98％CPU、3912566リップ）
false。

B 7.8

| ？-1000 = I、time（（dif（X、Y）、between（1、I、X）、between（1、I、Y）、false））。
CPU時間0.364秒。
いいえ
| ？-1000 = I、time（（between（1、I、X）、between（1、I、Y）、X \ == Y、false））。   
CPU時間0.356秒。
いいえ

YAP

？-1000 = I、time（（dif（X、Y）、between（1、I、X）、between（1、I、Y）、false））。
2.566秒で％2.528 CPU（98％CPU）
いいえ
？-1000 = I、time（（between（1、I、X）、between（1、I、Y）、X \ == Y、false））。
0.963秒で％0.929 CPU（96％CPU）
いいえ
于 2012-12-07T19:47:57.353 に答える
7

クエリはメタ解釈され、オーバーヘッドは と の違いを上回る場合がdif(X,Y)ありX\==Yます。次の 2 つの述語を比較する必要があります。

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.
于 2012-12-09T22:08:18.657 に答える