Вопросы Теги

Как повысить эффективность лексинга?

Ваша ошибка жалуется «Я не знаю, как читать нулевое значение».

Функция чтения файла options.go имеет оператор switch в строке 117, который реализует способы чтения различных баз данных типы. Вам нужно будет обновить этот оператор switch, чтобы иметь возможность обрабатывать значение типа null («tcNull»?).

5
задан Guy Coder 3 March 2019 в 10:05
поделиться

2 ответа

Это означает, что это глупый код: 

token(T) -->
    ( "1", !, { T = one }
    ; "2", !, { T = two }
    ; "3", !, { T = three }
    )

Это менее глупый код: 

token(T) --> one_two_three(T).

one_two_three(one) --> "1".
one_two_three(two) --> "2".
one_two_three(three) --> "3".

Но все же не так хорошо. Может быть, лучше: 

token(T) --> [X], { one_two_three(X, T) }.

one_two_three(0'1, one).
one_two_three(0'2, two).
one_two_three(0'3, three).

Последний пример также начинает выглядеть глупо, но помните, что теперь у вас есть индексирование по первому аргументу. Вы читаете один раз, нет выбора, нет возврата назад.

Но если вы действительно хотите знать, как писать эффективно, вам нужно измерить, куда уходит время и пространство. Вы измерили?

Но если вы действительно хотите знать, как исправить, то, возможно, прочитайте «Craft of Prolog», я не понимаю всю эту книгу, но помню, что в ней был большой раздел по DCG.

Но если вы действительно хотите анализировать такие форматы, большие файлы могут найти существующие библиотеки на других языках, это может быть намного быстрее, чем самый быстрый Пролог.

0
ответ дан 3 March 2019 в 10:05
поделиться

Решение:

Вы должны заменить следующее: 

lexer(Tokens) -->
   white_space,
   (
      (  ":",       !, { Token = tokColon }
      ;  "(",       !, { Token = tokLParen }
      ;  ")",       !, { Token = tokRParen }
      ;  "{",       !, { Token = tokLMusta}
      ;  "}",       !, { Token = tokRMusta}
      ;  "\\",      !, { Token = tokSlash}
      ;  "->",      !, { Token = tokImpl}
      ;  "+",       !, { Token = tokPlus }
      ;  "-",       !, { Token = tokMinus }
      ;  "*",       !, { Token = tokTimes }
      ;  "=",       !, { Token = tokEqual }
      ;  "<",       !, { Token = tokLt }
      ;  ">",       !, { Token = tokGt }
      ;  "_",       !, { Token = tokUnderscore }
      ;  ".",       !, { Token = tokPeriod }
      ;  "/",       !, { Token = tokForwardSlash }
      ;  ",",       !, { Token = tokComma }
      ;  ";",       !, { Token = tokSemicolon }
      ;  digit(D),  !,
            number(D, N),
            { Token = tokNumber(N) }
      ;  letter(L), !, identifier(L, Id),
            {  member((Id, Token), [ (div, tokDiv),
                                     (mod, tokMod),
                                     (where, tokWhere)]),
               !
            ;  Token = tokVar(Id)
            }
      ;  [_],
            { Token = tokUnknown }
      ),
      !,
      { Tokens = [Token | TokList] },
      lexer(TokList)
   ;  [],
         { Tokens = [] }
   ).

на 

lexer(Tokens) -->
   white_space,
   (
      (
         op_token(Token), ! % replace ;/2 long chain searched blindly with call to new predicate op_token//1 which clauses have indexed access by first arg in Prolog standard way
      ;
         digit(D),  !, number(D, N),
         { Token = tokNumber(N) }
      ;  letter(L), !, identifier(L, Id),
         {  member((Id, Token), [ (div, tokDiv),
                                 (mod, tokMod),
                                 (where, tokWhere)]),
            !
      ;  Token = tokVar(Id)
         }
      ;  [_],
         { Token = tokUnknown }
      ),
      !,
      { Tokens = [Token | TokList] },
      lexer(TokList)
   ;
      [],
      { Tokens = [] }
   ).

%%%
op_token(tokColon)      --> ";".
op_token(tokLParen)     --> "(".
op_token(tokRParen)     --> ")".
op_token(tokLMusta)     --> "{".
op_token(tokRMusta)     --> "}".
op_token(tokBackSlash)  --> "\\".
op_token(tokImpl)       --> "->".
op_token(tokPlus)       --> "+".
op_token(tokMinus)      --> "-".
op_token(tokTimes)      --> "*".
op_token(tokEqual)      --> "=".
op_token(tokLt)         --> "<".
op_token(tokGt)         --> ">".
op_token(tokUnderscore) --> "_".
op_token(tokPeriod)     --> ".".
op_token(tokSlash)      --> "/".
op_token(tokComma)      --> ",".
op_token(tokSemicolon)  --> ";".

Редактировать Guy Coder

I провел тест, используя пример данных, опубликованных в вопросе, в список, где каждый элемент в списке представлял собой строку данных, преобразованную в коды символов. Затем со временем / 1 вызывал lexer для каждого элемента в списке и повторял тест для списка 10000 раз. Причина, по которой данные были загружены в список и преобразованы в коды символов до времени / 1, заключалась в том, что эти процессы не искажали результаты. Каждый из этих прогонов повторялся 5 раз, чтобы получить согласованность данных.

В следующих запусках ниже для всех различных версий лексер был расширен, чтобы охватить все 7-битные символы ASCII, что значительно увеличило количество падежей для специальных символов.

Версия Пролога, используемая для следующего, была SWI-Пролог 8.0.

Для версии в вопросе. 

Version: 1

:- set_prolog_flag(double_quotes,chars).

% 694,080,002 inferences, 151.141 CPU in 151.394 seconds (100% CPU, 4592280 Lips)
% 694,080,001 inferences, 150.813 CPU in 151.059 seconds (100% CPU, 4602271 Lips)
% 694,080,001 inferences, 152.063 CPU in 152.326 seconds (100% CPU, 4564439 Lips)
% 694,080,001 inferences, 151.141 CPU in 151.334 seconds (100% CPU, 4592280 Lips)
% 694,080,001 inferences, 151.875 CPU in 152.139 seconds (100% CPU, 4570074 Lips)

Для версии, опубликованной выше в этом ответе 

Version: 2

:- set_prolog_flag(double_quotes,chars).

% 773,260,002 inferences, 77.469 CPU in 77.543 seconds (100% CPU, 9981573 Lips)
% 773,260,001 inferences, 77.344 CPU in 77.560 seconds (100% CPU, 9997705 Lips)
% 773,260,001 inferences, 77.406 CPU in 77.629 seconds (100% CPU, 9989633 Lips)
% 773,260,001 inferences, 77.891 CPU in 77.967 seconds (100% CPU, 9927511 Lips)
% 773,260,001 inferences, 78.422 CPU in 78.644 seconds (100% CPU, 9860259 Lips)

Версия 2 дает значительное улучшение за счет использования индексации из Версии 1.

При проведении дальнейших исследований кода, взглянув на op_token, который представляет собой DCG и имеет две скрытые переменные для неявного прохождения представления состояния, используя листинг / 1 показал : 

op_token(tokUnderscore,['_'|A], A).

Обратите внимание, что первый параметр не является искомым символом и что в этом ответе индексный код записывается как 

c_digit(0'0,0).

, где первый Параметр - это искомый символ, а второй параметр - результат.

Так что измените этот 

op_token(Token), !

на этот 

[S], { special_character_indexed(S,Token) }

с индексированными предложениями как 

special_character_indexed( ';' ,tokSemicolon).


Версия: 3

] 
:- set_prolog_flag(double_quotes,chars).

% 765,800,002 inferences, 74.125 CPU in 74.348 seconds (100% CPU, 10331197 Lips)
% 765,800,001 inferences, 74.766 CPU in 74.958 seconds (100% CPU, 10242675 Lips)
% 765,800,001 inferences, 74.734 CPU in 74.943 seconds (100% CPU, 10246958 Lips)
% 765,800,001 inferences, 74.828 CPU in 75.036 seconds (100% CPU, 10234120 Lips)
% 765,800,001 inferences, 74.547 CPU in 74.625 seconds (100% CPU, 10272731 Lips)

Версия 3 дает немного лучший, но стабильно лучший результат, чем Версия 2.

Наконец, просто изменив флаг double_quotes на atom, как отмечено в комментарии АнтонДанилова 

Version: 4

:- set_prolog_flag(double_quotes,atom).

% 765,800,003 inferences, 84.234 CPU in 84.539 seconds (100% CPU, 9091300 Lips)
% 765,800,001 inferences, 74.797 CPU in 74.930 seconds (100% CPU, 10238396 Lips)
% 765,800,001 inferences, 75.125 CPU in 75.303 seconds (100% CPU, 10193677 Lips)
% 765,800,001 inferences, 75.078 CPU in 75.218 seconds (100% CPU, 10200042 Lips)
% 765,800,001 inferences, 75.031 CPU in 75.281 seconds (100% CPU, 10206414 Lips)

Версия 4 почти такая же, как и Версия 3.

Просто просматривая номера процессоров, можно быстрее использовать индексацию, например, (Версия: 1) 151.875 против (Версия: 3) 74.547

0
ответ дан Guy Coder 3 March 2019 в 10:05
поделиться
Другие вопросы по тегам:

Похожие вопросы: