我正在解析一個由一系列行組成的相當簡單的文件格式，每行都有一些用空格分隔的字段，看起來像這樣：l 0x9823 1s 0x1111 3l 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-prologdigit(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秒。我對此情況有幾個疑問：該代碼中的效率問題在哪里？我認為它要么存在，trace_file_phrase//1要么nat//1只是預感。如果問題是列表，那么有沒有比DCG更好的方法來處理列表了？通常，如何使用DCG診斷和處理諸如此類的性能問題？
3 回答
森林海
TA貢獻2011條經驗 獲得超2個贊
通常，您可以在的名稱下找到更多關于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無法決定是否可以計算出進一步的答案-因此它留下了一個或多個選擇點。而且那僅是個位數，您可以想象事情將如何堆積。
讓我們深入探討：
？-短語（數字（D），“ 1”）。
D = 1;
假。
再次邪惡;！為了使這項工作奏效，必須確定一切。有以下三種方法：
使用削減（并失去你的靈魂）
祝您好運-最好的情況似乎是在重復元素之后：
trace_file_phrase（[]）-> []。
trace_file_phrase（[T | Ts]）->
trace_phrase（T），
！，％ugly，but ...
trace_file_phrase（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（phrase（nat（N），“ 1234”））。
N = 1234。
？-call_semidet（（X = 1; X = 2））。
錯誤：未知錯誤術語：mode_error（semidet，（2 = 1; 2 = 2））
因此，它可以有效確定您的小語法！因此，無需重新構造任何內容！
現在缺少的是將其整合到語法中。您可以非常低級地執行此操作，或者可以使用干凈地進行此操作library(lambda)。
statement_semidet（NT）->
call（S0 ^ S ^ call_semidet（phrase（NT，S0，S）））。
請注意，在這種非常特殊的情況下，我們不使用\來重命名。
trace_file_phrase（[]）-> []。
trace_file_phrase（[T | Ts]）->
statement_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）-> digit（D），...
第一條規則始終適用，也就是說，只有在了解到最后一條就足夠了之后再堅持下去，才會對它"1234\n"進行解析。"1" "12" "123" "1234"newline//0
您可以為此重寫內容，但是代碼不再是您喜歡的純粹的小規范，不是嗎？好吧，也許將來情況會有所改善。
例如，SWI中的索引編制比以前要好得多，也許這里的事情也在發展。
的目的library(pio)是開始此過程。將此與Haskell進行比較-我們距離interact效率還差得遠！但是沒有固有的成本：
...-> [] | [_]，...。
？ - phrase_from_file（（...， “搜索字符串”，...），fichier）。
與grep一樣高效-在空間方面。也就是說，它在恒定的空間中運行。因此，希望將來會有更多的代碼運行得更好。
編輯：順便說一句，library(pio)確實已經在影響效率方面有所改進：GC階段得到了顯著改善，與25年前Wadler的“修復一些空間泄漏”的方法非常相似。事情發展...
蕭十郎
TA貢獻1815條經驗 獲得超13個贊
我已經驗證了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）的答案解決了您的問題。
一只斗牛犬
TA貢獻1784條經驗 獲得超2個贊
關于效率問題：
如果輸入通常是良好的，那么我認為你應該換的條款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）提交（），因為您無需再次重新解析輸入的那部分來查找其他解決方案。
添加回答
舉報
0/150
提交
取消