16

一連の行で構成されるかなり単純なファイル形式を解析しています。各行には、次のようなスペースで区切られたフィールドがあります。

l 0x9823 1
s 0x1111 3
l 0x1111 12
⋮

SWI-Prolog を使用しています。これは私がこれまで持っているDCGです：

:- consult(library(pure_input)).

load_trace(Filename, Traces) :-
    phrase_from_file(trace_file_phrase(Traces), Filename).

trace_file_phrase([]) --> [].
trace_file_phrase([T|Ts]) --> trace_phrase(T), trace_file_phrase(Ts).

trace_phrase(access(Type, Address, SinceLast)) -->
    access_type(Type), space,
    address(Address),  space,
    nat(SinceLast),    newline.

access_type(load)  --> "l".
access_type(store) --> "s".

address(Number) --> "0x", hexnum(Number).

hexdigit(N)  --> digit(N).
hexdigit(10) --> "a". hexdigit(11) --> "b". hexdigit(12) --> "c".
hexdigit(13) --> "d". hexdigit(14) --> "e". hexdigit(15) --> "f".
hexnum(N) --> hexdigit(D), hexnum(D, N).
hexnum(N, N) --> [].
hexnum(A, N) --> hexdigit(D), { A1 is A*16 + D }, hexnum(A1, N).

newline --> "\n".
space --> " ".

%% the following two productions are courtesy of Lars Mans at
%% https://stackoverflow.com/questions/3279822/parsing-numbers-with-multiple-digits-in-prolog
digit(0) --> "0". digit(1) --> "1". digit(2) --> "2".
digit(3) --> "3". digit(4) --> "4". digit(5) --> "5".
digit(6) --> "6". digit(7) --> "7". digit(8) --> "8".
digit(9) --> "9".

nat(N)   --> digit(D), nat(D,N).
nat(N,N) --> [].
nat(A,N) --> digit(D), { A1 is A*10 + D }, nat(A1, N).

コメントで述べたように、Prolog で複数の数字を持つ数字を解析するから数字の処理を引用しました。

私が直面している問題は、これらのファイルの一部が 5 ～ 10 MB のように大きいことです。SWI-Prolog のデフォルト スタックはこれには不十分であり、これらのファイルの解析には 5 ～ 15 秒程度のかなりの時間がかかります。この状況についていくつか質問があります。

  1. このコードのどこに効率の問題がありますか? trace_file_phrase//1またはどちらかだと思いますnat//1が、これらは単なる勘です。
  2. 問題がリストである場合、これよりも DCG を使用してリストを処理するためのより良い方法はありますか?
  3. 一般に、このような DCG のパフォーマンスの問題をどのように診断し、治療するのでしょうか?
4

3 に答える 3

18

一般的な意見として、SO についての詳細は、名前の下にありますlibrary(pio)。また、きれいに使用する方法は次のとおりです。

:- use_module(library(pio)).

あなたの例はあまりにも複雑なので、改行で区切られた数値のリストである、少し単純なケースのみを検討します。

nats([]) --> [].
nats([N|Ns]) --> nat(N)、改行、nats(Ns)。

では、これを効果的にテストするにはどうすればよいでしょうか。(あなたの質問 3 です) の基本的なポイントはlibrary(pio)、ファイル処理に通常の DCG を使用できることです。ただし、小規模でのテストには、単純なphrase/2. 私もです：

?- 句(nats(Ns),"1\n")。
Ns = [1] ;
間違い。

;プロンプトを見ましたか？つまり、Prolog は、さらに回答を計算できるかどうかを判断できませんでした。そのため、1 つまたは複数の選択ポイントが開いたままになっています。それも一桁だけ積み上げていく様子が想像できます。

さらに掘り下げてみましょう。

?- 句(数字(D),"1")。
D = 1;
間違い。

再び悪;！これを機能させるには、すべてが決定的でなければなりません。これには 3 つの方法があります。

カットを使用する（そしてあなたの魂を失う）

幸運を祈ります-繰り返し要素の直後が最高のようです：

trace_file_phrase([]) --> [].
trace_file_phrase([T|Ts]) -->
   trace_phrase(T),
   !, % 醜いですが...
   trace_file_phrase(Ts)。

(これは質問 1 に答える必要があります)

でも、ちょっと待って！これの何が悪いの!？物事に対する答えが 1 つしかない限り、trace_phrase//1完璧です。カットによって貴重な答えが削除される可能性があるのは、より多くの答え (または実際の解決策) がある場合のみです。他に解決策がある場合、どうすればわかりますか? まあ、あなたはしません。そして、それらはすでに切り取られているため、表示されません。

call_semidet/1

これが起こらないようにする方法を次に示します。これは、何の効果もなく 2 回呼び出すことができる、副作用のないゴールに対してのみ機能します。

call_semidet(ゴール) :-
   ( call_nth(目標, 2)
   -> throw(error(mode_error(semidet,Goal),_))
   ; 1回（目標）
   ）。

call_nth/2別の投稿で定義されているように、これは を使用します。(最適化として、選択ポイントが開いていない場合、実装は2回呼び出すことを避けることができGoalます...) 明確にするために、それがどのように機能するか:

?- フレーズ(nat(N),"1234")。
N = 1234;
間違い。

?- call_semidet(phrase(nat(N),"1234"))。
N = 1234。

?- call_semidet((X=1;X=2))。
ERROR: 不明なエラー用語: mode_error(semidet, (2=1;2=2))

だから、それはあなたの小さな文法を効果的に決定します! したがって、何も再定式化する必要はありません。

現在欠けているのは、これを文法に統合することです。これは非常に低レベルで、またはかなりきれいに を使用して実行できますlibrary(lambda)。

phrase_semidet(NT) -->
   call(S0^S^call_semidet(phrase(NT,S0,S)))。

この非常に特殊なケースでは\、名前の変更に を使用しないことに注意してください。

trace_file_phrase([]) --> [].
trace_file_phrase([T|Ts]) -->
   phrase_semidet(trace_phrase(T)),
   trace_file_phrase(Ts)。

インデックス作成の悪用

最後に、非常に骨の折れるがクリーンな方法は、すべてを書き直してインデックス作成から利益を得る (そして、インデックス作成全般の改善に役立つ可能性があります) ことです。しかし、これは長い道のりです。まず始めに：

桁(D) --> [C],
   {c_digit(C,D)}。

c_digit(0'0,0)。
c_digit(0'1,1)。
c_digit(0'2,2)。
c_digit(0'3,3)。
c_digit(0'4,4)。
c_digit(0'5,5)。
c_digit(0'6,6)。
c_digit(0'7,7)。
c_digit(0'8,8)。
c_digit(0'9,9)。

これにより、次のことがわかります。

?- 句(数字(D),"1")。
D = 1。

しかし、文法を定義する方法が原因である非決定論の別の原因があります。あなたはそれnat//2を見る：

nat(N,N) --> [].
nat(A,N) --> 数字(D), ....

最初のルールは常に適用されます。つまり、最後のルールで十分であることを次のルールだけが認識し、それに固執するため、"1234\n"解析されます。"1" "12" "123" "1234"newline//0

そのために書き直すことはできますが、その場合、コードはあなたが好きだった純粋な小さな仕様ではなくなりますよね? うーん、もしかしたら今後改善されるかもしれません。

たとえば、SWI のインデックス作成は、以前よりもはるかに優れています。おそらく、ここでも物事が進化しています....

の意図は、library(pio)このプロセスを開始することでした。これを Haskell と比較してくださいinteract。ただし、固有のコストはありません。

... --> [] | [_], ... .

?- phrase_from_file((...,"検索文字列",...),fichier).

grep と同じくらい効率的です — スペースに関してです。つまり、一定のスペースで実行されます。そのため、今後、より多くのコードがより適切に実行されることを願っています。

編集: ところで、library(pio)すでに効率面で影響がありました: GC フェーズは大幅に改善されました。これは、四半世紀前の Wadler の一部のスペース リークの修正とほぼ同じ方法です。物事は進化する...

于 2012-10-17T20:10:09.250 に答える
6

2Mb ファイルでスタックオーバーフローを確認しました。次に、ライブラリ(dcg/basics)を使用して文法を書き直し、現在は機能しています。

:- [library(dcg/basics)].

load_trace_0(Filename, Ls) :-
    phrase_from_file(lines(Ls), Filename).

lines([s(H,I)|R]) -->
    "s 0x", xinteger(H), " ",
    integer(I), blanks,
    !, lines(R).
lines([l(H,I)|R]) -->
    "l 0x", xinteger(H), " ",
    integer(I), blanks,
    !, lines(R).
lines([]) --> [].

しかし、私はあなたの文法にカットを入れようとしましたが、同様に機能しています. したがって、@gusbro (+1) からの回答が問題を解決します。

于 2012-10-17T20:05:56.490 に答える
4

効率の問題について：

入力が通常整形式である場合は、nat/4との句を交換する必要があると思います。そうすれば、次hexnum/4のようになります。

nat(A,N) --> digit(D), { A1 is A*10 + D }, nat(A1, N).
nat(N,N) --> [].

hexnum(A, N) --> hexdigit(D), { A1 is A*16 + D }, hexnum(A1, N).
hexnum(N, N) --> [].

消費する桁がなくなったときにのみ数値の解析を停止したいからです。

賢明に使用された場合、カット（!）は、プロローグ評価ツリーを削除するため、パフォーマンス面で、またスタックオーバーフローに関しても役立ちます。たとえば、他の解決策を見つけるために入力のその部分を再度解析する必要がないため!、最後trace_file_phrase/3（つまり、の後に）に（）をコミットできます。newline

于 2012-10-17T18:22:09.610 に答える