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 中抄写了 Parsing numbers with multiple numbers 中的数字处理。

我遇到的问题是其中一些文件很大，例如大约 5-10 MB。SWI-Prolog 中的默认堆栈对此不够用，并且解析这些文件需要大量时间，大约 5-15 秒。我对这种情况有几个问题：

  1. 这段代码的效率问题在哪里？我认为它要么在要么，trace_file_phrase//1但nat//1这些只是预感。
  2. 如果问题是列表，有没有比这更好的方法来处理带有 DCG 的列表？
  3. 一般来说，如何诊断和治疗此类 DCG 的性能问题？
4

3 回答 3

18

作为一般评论，您会在名称下找到更多关于它的信息library(pio)。同样干净地使用它的方法是：

:- use_module(library(pio)).

你的例子太复杂了，所以我只会考虑一个稍微简单的例子，一个换行符分隔的数字列表：

nats([]) --> []。
nats([N|Ns]) --> nat(N)，换行，nat(Ns)。

那么，如何有效地测试呢？（那是您的问题 3）的基本点library(pio)是您可以使用常规 DCG 进行文件处理。但是对于小型测试，您仍然可以使用简单的phrase/2. 所以我这样做：

?- 短语(nats(Ns),"1\n")。
Ns = [1]；
错误的。

看到;提示了吗？这意味着：Prolog 无法决定是否可以计算进一步的答案——因此它留下了一个或多个选择点。而这只是一个数字你可以想象事情会如何堆积。

让我们深入挖掘：

?- 短语（数字（D），“1”）。
D = 1；
错误的。

又是邪恶;！为了完成这项工作，一切都必须确定。有以下三种方法：

使用削减（并失去你的灵魂）

祝你好运 - 最好的似乎是在重复元素之后：

trace_file_phrase([]) --> []。
trace_file_phrase([T|Ts]) -->
   跟踪短语（T），
   ！，％丑陋，但是...
   跟踪文件短语（Ts）。

（这应该回答问题1）

但是，等一下！这有什么不好!？只要事情只有一个答案，trace_phrase//1就是完美的。只是，如果有更多答案（或实际解决方案），削减可能会删除宝贵的答案。你怎么知道，如果有更多的解决方案？好吧，你没有。而且你不会看到它们，因为它们已经被切掉了。

call_semidet/1

这是一种确保不会发生这种情况的方法。这仅适用于可以调用两次而没有任何效果的无副作用目标：

call_semidet（目标）：-
   ( call_nth(目标, 2)
   -> 抛出(错误(mode_error(semidet,Goal),_))
   ; 一次（目标）
   ）。

这使用call_nth/2，如另一篇文章中所定义。Goal（作为一种优化，当没有选择点打开时，实现可以避免调用两次......）只是为了明确，它是如何工作的：

?- 短语（nat（N），“1234”）。
N = 1234 ;
错误的。

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

?- call_semidet((X=1;X=2))。
错误：未知错误术语：mode_error(semidet, (2=1;2=2))

所以它让你的小语法有效地确定！因此没有必要重新制定任何东西！

现在缺少的是把它整合到语法中。你可以做这个非常低级的，或者相当干净地使用library(lambda).

短语_semidet(NT) -->
   呼叫（S0^S^call_semidet（短语（NT，S0，S）））。

请注意，在这种非常特殊的情况下，我们不使用\重命名。

trace_file_phrase([]) --> []。
trace_file_phrase([T|Ts]) -->
   短语_semidet（trace_phrase（T）），
   跟踪文件短语（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((...,"searchstring",...),fichier)。

与 grep 一样高效——在空间方面。也就是说，它在恒定空间中运行。所以希望将来有更多的代码运行得更好。

编辑：顺便说一句，library(pio)在效率方面确实已经产生了影响：GC 阶段得到了显着改善，与 Wadler 的修复一些空间泄漏的方式非常相似——四分之一世纪前的论文。事情发展...

于 2012-10-17T20:10:09.250 回答
6

我已经在 2Mb 文件上验证了 stackoverflow。然后我使用库（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

关于效率问题：

如果您的输入通常格式正确，那么我认为您应该交换 and 的子句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) --> [].

因为您只想在没有更多数字可供使用时停止解析数字。

如果使用得当，cut ( !) 可以帮助您提高性能，还可以帮助您解决堆栈溢出问题，因为它会修剪 prolog 评估树。例如，您可以!在末尾trace_file_phrase/3（即 ）之后提交 ( )，newline因为您不需要再次重新解析该部分输入以找到其他解决方案。

于 2012-10-17T18:22:09.610 回答