0

DCG ルールのセットがあります (この場合はドイツ語の人称代名詞):

% personal pronoun (person, case, number, genus)
ppers(1,0,sg,_) --> [ich].
ppers(1,1,sg,_) --> [meiner].
ppers(1,2,sg,_) --> [mir].
ppers(1,3,sg,_) --> [mich].
ppers(2,0,sg,_) --> [du].
ppers(2,1,sg,_) --> [deiner].
ppers(2,2,sg,_) --> [dir].
ppers(2,3,sg,_) --> [dich].
...

それらは意味的に関連しているため、関係のないルールではなく、それらをリスト (たとえば、人ごとにグループ化) に移動して、この情報を保持することは理にかなっています。これにより、物事が少しすっきりします。

ppers(1,sg,_,[ich, meiner, mir, mich]).
ppers(2,sg,_,[du,deiner,dir,dich]).
...

nth0()次に、必要なケースがリスト内のインデックスである場合に、必要なアイテムを選択します。

しかし、プログラムをたどっていくと、ドイツ語の文章の正しい文法をチェックし、その部分が人称代名詞であるかどうかを調べようとすると、上位バージョン (単純なルール) を使用すると、Prolog がすべてのインスタンスをステップ実行しないことに気付きましたが、以下のリスト バージョンを使用すると、すべてのリストをクロールします。

リストと nth0 を使用すると、単純なルールよりもパフォーマンスが低下するということですか? それとも、Prolog トレーサは、リストの場合のように単純なルールのクロールを表示しないだけですか?

（私の質問を十分に明確にすることができれば幸いです。そうでない場合は、拡張します。）

4

4 に答える 4

2

ほとんどの場合、速度とトレースの違いはインデックス (*) によるものではなく、句の先頭の統合と本体呼び出し nth の速度とトレースの違いによるものです。本当に索引付けを利用して、ほとんどの Prolog システムで移植可能 (**) にしたい場合は、最初の引数の索引付けのために問題を再定式化する必要があります。

これを行う 1 つの方法は、追加の述語を使用することです。最初に次の DCG ルールがあるとします。

cat(Attr1, .., Attrn) --> [Terminal1, .., Terminaln].
..

これを次のように変換します。

cat(X1, .., Xn) --> [Y], cat2(Y, X1, .., Xn).

cat2(Terminal1, Attr1, .., Attrn) --> [Terminal2, .., Terminaln].
..

これをあなたの例に適用すると、次のようになります。

% personal pronoun (person, case, number, genus)
ppers(X1,X2,X3,X4) --> [Y], ppers2(Y,X1,X2,X3,X4).

% personal pronoun 2 (first word, person, case, number, genus)
ppers2(ich,1,0,sg,_) --> [].
ppers2(meiner,1,1,sg,_) --> [].
ppers2(mir,1,2,sg,_) --> [].
ppers2(mich,1,3,sg,_) --> [].
ppers2(du,2,0,sg,_) --> [].
ppers2(deiner,2,1,sg,_) --> [].
ppers2(dir,2,2,sg,_) --> [].
ppers2(dich,2,3,sg,_) --> [].

コード内のカテゴリごとにこれを行うことができます。これは一種のレキシコン テーブルです。上記は、DCG がどのように変換されるかに関係なく機能し、最初の引数のインデックス付けが存在する場合、超高速になります。

さよなら

(*) Prolog システムが複数引数の索引付けを実行できる場合でも、複雑な用語の索引付けは実行できない可能性があります。[ich|X] にインデックスを付けるには、Prolog システムはリストに下降する必要がありますが、ほとんどの場合、下降せず、インデックス (.)/2 のみを実行するため、すべての句が同じように見え、インデックス付けにプラスの効果がありません。

(**) 索引付けに関する Prolog システムの唯一の共通項は、最初の引数の索引付けであると思います。それに加えて、すべての Prolog システムが端末を head に入れるわけではありません。本体で =/2 を使用する人もいれば、本体で 'C'/3 を使用する人もいます。DCG は現在、端末のモデル化に関して標準化されていません。

于 2012-05-21T13:08:13.393 に答える
1

なぜ nth0 を使用しているのですか? おそらくパフォーマンスキラーの原因である可能性があります。代わりに memberchk を使用してください。

これとは別に、パフォーマンスに関するあなたの直感には、「引数の索引付け」に関する十分に根拠のある背景があると思います。DCG は通常 Prolog で翻訳されます (ここでは SWI-Prolog を使用しています)。

ppers(1,0,sg,_) --> [ich].

になる

ppers(1, 0, sg, _, [ich|A], A).

SWI-Prolog 仮想エンジンの最近の最適化は、YAP から着想を得て (私が思うに)、十分にバインドされた引数を持つ述語のすべてのインデックスを自動的に構築します。

したがって、最初のスキームでの解析 (SWI-Prolog を使用) がより効率的であることが期待できます。

以前は、「最初の引数のインデックス作成」のみが実装されていました。その場合 (または、インデックス作成機能のない Prolog を使用している場合)、これらのスキーム間で非常に類似したタイミングを見つける必要があります。

HTH

于 2012-05-21T11:19:28.360 に答える
1

一般に、トレーサーは実際に何が起こっているかを示します。そうです、代替定式化がマッチングを介してターゲット用語に直接アクセスする場所を反復する場合、それはあなたが見ていないときにも起こります. しかし、それが実際にパフォーマンスの低下を意味するかどうかを調べるには、実際のシナリオで両方の選択肢を測定して比較する必要があります。トレーサーによって個別のステップとして表示されていなくても、統合が遅くなる可能性があります。または、ランタイムシステムが最適化を行ったり、trace. または、遅いかもしれませんが、心配するほどではありません。ここでは、いつものように、ゴールデン ルールは次のとおりです。測定してから最適化します。

于 2012-05-21T10:56:01.397 に答える
0

文法規則は、通常は索引付けされている述語節にコンパイルされます。すべてではないにしても、ほとんどのPrologコンパイラーは、（デフォルトで）最初の引数の索引付けを使用して、目標を証明するときに証明ツリーの一部になることのない節を試行しないようにします。したがって、呼び出しパターンによっては、Prologコンパイラのトレースサポートを使用して観察したように、すべての述語句にステップインするわけではありません。さらに、インスタンス化されたインデックスを使用してnth0 / 3述語を呼び出すには、指定されたインデックスに到達するまで、リストを線形にトラバースする必要があります。他の人が示唆しているように、memberchk/2述語を使用した場合も同じです。リストはリストです。

于 2012-05-21T20:52:29.690 に答える