組み込み述語の時間複雑度

Question

私はプロローグ付きの小さなプロジェクトに取り組んでいます。私は最適化されたかについて疑問に思った

を（、リストおよび単一の要素を扱うとき[Head | List2]などを差し引くための私自身の述語を書く）を除去する際には他の選択肢について賛成のappend(?List1, ?List2, ?List1AndList2)とsubtract(+Set, +Delete, -Result)などの述語に建てられていることに気付いてきました組み込み述語は一般的にプロローグにありますか？私は、減算の複雑さが|Delete|*|Set|であることを読んで、私が使用して、非常に有意な増加を得た：

removeFriendsOfS(S, [Head | Tail], OutputAcc, Output) :- 
    relation(S, Head), 
    removeFriends(S, Tail, OutputAcc, Output), 
    !. 

removeFriendsOfS(S, [Head | Tail], OutputAcc, Output) :- 
    not(relation(S, Head)), 
    removeFriends(S, Tail, [Head | OutputAcc], Output), 
    !. 

それはあなた自身の述語を記述することなく、既存のものを使用することを推奨していますか？私はちょうどプロローグで始まったので、まだ経験が豊富です。

Answer 1

既存の述語を使用するのではなく、独自の述語を書くことをお勧めしますか？ （おそらく）すべてのプログラミング言語で

と同様に、通常はあるため、既存のものの上に独自の関数を書くことは良いアイデアではありません。

既存のものが時々それらを作る、インタプリタにハードコードされている

もっと早く;
• これらは非常に多くの回数テストされているため、まだバグが存在する可能性は低いです。
• ほとんどのライブラリはエキスパート：効率、セキュリティ、グラフ理論、コンピュータグラフィックスについてよく知っている人によって構成されています。結果として、彼らはおそらく、効率や他の基準に関しては最善ではないが、典型的なアプリケーションに関しては意思決定を行います。
• 新しい仕様が発生した場合、ライブラリは更新されますが、独自のアルゴリズムを自分で更新する必要があります。リスト処理の場合、これはあまりありません。しかし、たとえばHTTPサーバーを自分で作成する場合は、将来、HTTPプロトコルがアプリケーションを非推奨にする可能性があります。 append/3が二つのリスト int型別のリストを追加 - 名前がすでに示唆するように、ため

Result = [Head|Tail]がappend([Head], Tail, Result)オーバー好ましい理由です。 Headはリストではないので、ここでは1つを作成します。[Head]と書くと、実際には暗黙のうちに[Head|[]]と書かれています。したがって、1要素リストを構築することは、コンフリクトを構成する（ほぼ）高価です。[Head|Tail]その後、append/3は新しい短所を構築します。新しい短所は時間がかかりますし、さらに呼び出し自体は高価です。したがって、リストTailを要素Headで先行させるときには、[Head|Tail]がそれを行う簡単な方法です。

removeFriendsOfS/3が高速である理由は、subtract/3以外の何かをするためです：それは述語に基づいてリストをフィルタリングします。 Prologにはこれも述語があります。exclude/3例えば：

:- use_module(library(apply)). 

removeFriendsOfS(S, List, Out) :- 
    exclude(relation(S), List, Out). 

これはO（N × K）Krelations(S,X)クエリの時間で動作します。