Еще о парсинге на Prolog'е

    Вот тут наткнулся на, в общем-то, простую задачку состоящую в парсинге текстового файла, содержащего 5 миллионов float'ов (и подсчете их суммы). Файл генерируется следующим C#-кодом:
    static void Main(string[] args)
    {
      using (Stream stm = new FileStream(@"d:\numbers_large.txt", FileMode.Create))
      {
        TextWriter wr = new StreamWriter(stm);
        System.Random r = new System.Random();
        for (int i = 0; i < 5000000; i++)
        {
          double d=10000*r.NextDouble() * (r.NextDouble() > 0.7 ? -1.0 : 1.0);
          wr.Write("{0} ", d);
        }
        wr.Flush();
      }



    Задача ставилась в контексте обсуждения производительности haskell'я в применении его к задачам парсинга. Я знал, что на прологе подобные задачи решаются красиво и непринужденно используя технику DCG (Definite clause grammar: 1, 2, 3, 4). Фактически, это описание грамматик на языке Пролог, и парсинг по ним, основанный на переборно-откатном принципе работы пролога.

    Ну то есть обычно получается очень кратко и красиво (например, вот решение задачки о сбалансированности скобок этим методом: программа из 7 строк), но, я подозревал, что не всегда быстро. Собственно, это мне захотелось проверить.

    Довольно быстро (минут 15) была написана очевидная (naive) версия программы:

    <br>:- set_prolog_flag(float_format,'%.15g').<br><br>integer(I) --><br>        digit(D0),<br>        digits(D),<br>        { number_chars(I, [D0|D])<br>        }.<br><br>digits([D|T]) --><br>        digit(D), !,<br>        digits(T).<br>digits([]) --><br>        [].<br><br>digit(D) --><br>        [D],<br>        { code_type(D, digit)<br>        }.<br><br><br>float(F) --><br>    ( "-", {Sign = -1}<br>    ; "", {Sign = 1}<br>    ), !,<br>    integer(N),<br>    ",",<br>    integer(D),<br>    {F is Sign * (N + D / 10^(ceiling(log10(D))))<br>    }.<br><br><br>sum(S) --><br>    float(F1), !,<br>    " ",<br>    ( sum(S1)<br>    ; {S1 = 0}<br>    ),<br>    { S is F1 + S1}.<br><br><br>go :-<br>    read_file_to_codes('numbers_large.txt',Codes,[]),<br>    writeln('Processing...'),<br>    sum(S,Codes,[]),<br>    writeln(S).<br>


    Я, конечно, подозревал облом на парсинге такого большого файла, но подкол случился раньше. Предикат read_file_to_codes падал в Out of global stack. Это, в общем-то, было довольно очевидно. Дело в том, что в используемой мною реализации SWI-пролог есть фундаментальное ограничение на 32 битной архитектуре — он не может использовать больше 128 мб на глобальный стек и 128 мб на локальный (в 64бит осях ограничения устранены). Это я позже вычитал в доке, а до этого пробовал играть с ключами -G500M -L500M но это, понятное дело, не спасло, т.к. для прочтения ~82M символов в памяти требовалось значительно больше места (чем 128).

    Помогли ребята из списка рассылки (кстати, хочется особо отметить, что автор SWI Prolog'а, Jan Wielemaker принимает активное участие в рассылке, помог и на этот раз!).

    Подсказали использовать предикат phrase_from_file из library(pio), который работает с потоками в lazy-стиле, и фактически объединяет чтение из файла и разбор в одном предикате. Как раз то что нужно!

    Более того, предвидя дальнейшие проблемы, переписал предикат sum, выполняющий парсинг с одновременным суммированием, в 'tail recursion'-виде. Для непосвященных расскажу немножко подробнее: в функциональных и логических языках программирования вы обычно не можете создавать циклы, поэтому практически все делается с использованием рекурсии. Но если её правильно написать (когда это возможно), то можно достичь того эффекта, что код скомпилируется в цикл, хотя внешне это будет рекурсия. На прологе для написания хвостовой рекурсии, предикат нужно оформить в виде

    head :-
      <guard goals>, !,
      <deterministic stuff>,
      head.
    head :-
      ...



    Собственно, основное в хвостовой рекурсии, это то, что в самом конце предиката происходит вызов его же самого.

    Код был переписан следующим образом:

    :- set_prolog_flag(float_format,'%.15g').<br><br>integer(I) --><br>        digit(D0),<br>        digits(D),<br>        { number_chars(I, [D0|D])<br>        }.<br><br>digits([D|T]) --><br>        digit(D), !,<br>        digits(T).<br>digits([]) --><br>        [].<br><br>digit(D) --><br>        [D],<br>        { code_type(D, digit)<br>        }.<br><br><br>float(F) --><br>    ( "-", {Sign =3D -1}<br>    ; "", {Sign =3D 1}<br>    ),<br>    integer(N),<br>    ",",<br>    integer(D),<br>    {F is Sign * (N + D / 10^(ceiling(log10(D))))<br>    }.<br><br>sum(S, Total) --><br>    float(F1), !,<br>    " ",<br>    { S1 is S + F1},<br>    sum(S1, Total),<br>    !.<br>sum(Total, Total) --><br>    [].<br><br>go1 :-<br>    phrase_from_file(sum(0, S),'numbers_large.txt', [buffer_size(16384)]),<br>    writeln(S).<br>


    Однако опять облом, на этот раз с local stack (и потребление памяти порядка 130 мб)

    ?- go1.
    ERROR: Out of local stack
    Exception: (1,973,549) sum(3943621517.84343, _G2, [45, 50, 55, 54, 57,
    44, 49, 48|...], []) ?


    Это могло означать только то, что хвостовая рекурсия не сработала, и на этот раз оказался виноват предусмотрительно (вот уж, воистину, преждевременная оптимизация — корень всех бед) поставленный в конце предиката sum/2 значек отсечения (cut, !). Именно он, призванный отсечь перебор ненужных альтернатив, будучи поставленным в конце, выключал и оптимизацию хвостовой рекурсии.

    В общем, убрав оттуда этот злополучный (!), но добавив его во float после альтернативы связанной с парсингом знака (чтоб избезать запоминания точек возврата), получил окончательную версию программы:

    <br>:- set_prolog_flag(float_format,'%.15g').<br><br>integer(I) --><br>        digit(D0),<br>        digits(D),<br>        { number_chars(I, [D0|D])<br>        }.<br><br>digits([D|T]) --><br>        digit(D), !,<br>        digits(T).<br>digits([]) --><br>        [].<br><br>digit(D) --><br>        [D],<br>        { code_type(D, digit)<br>        }.<br><br><br>float(F) --><br>    ( "-", {Sign = -1}<br>    ; "", {Sign = 1}<br>    ), !,<br>    integer(N),<br>    ",",<br>    integer(D),<br>    {F is Sign * (N + D / 10^(ceiling(log10(D))))<br>    }.<br><br>sum(S, Total) --><br>    float(F1), !,<br>    " ",<br>    { S1 is S + F1},<br>    sum(S1, Total).<br>sum(Total, Total) --><br>    [].<br><br>go1 :-<br>    phrase_from_file(sum(0, S),'numbers_large.txt', [buffer_size(16384)]),<br>    writeln(S).<br>


    На Core2Duo@3Ghz работает ~1мин потребляя памяти не больше 5 мб и развивая скорость парсинга ~1.3 Мб/сек. Ну что же, не так быстро как вариант на Haskell, но, имхо, очень недурно для интерпретируемого SWI-Prolog'а, и при этом весьма изящно, по сравнению с решением из корневого поста RSDN ).

    Кстати, python, на удивление не порадовал скоростью. Наивный, правда, вариант
    from decimal import *

    getcontext().prec=15

    print sum(Decimal(f.replace(',','.') or '0') for f in open('numbers_large.txt').read().split(' '))


    * This source code was highlighted with Source Code Highlighter.


    скушал 236 мегабайт памяти и проработал ~4 мин на той же конфигурации.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 7

      0
      ну конечно Python сожрёт кучу памяти и будет медленно после этого работать. Нельзя так с большими файлами работать.
      «The xreadlines() function should be used for big files»

      И где же нормальное объяснение про Haskell о котором вы заикнулись, потому-что непросвещенным непонятно, то ли это хаскель, то ли пролог который можно из него использовать
        +1
        ой извиняюсь)=
        пожалуйста не бейте сильно. и забейте на xreadlines
          0
          Просто есть readline и readlines которые поидее быстрее read и которыми я пользовался.
          А неудачный поиск выдал xreadlines который меня дизориентировал

          В общем попробуйте использовать readlines или readlines и возможно это будет быстрее
            0
            задачи особо не стояло обгонять кого-то ) это был чистый just for fun, который показал, что пролог тоже на что-то годится. Ясно, что и на питоне можно написать быструю версию, если захотеть.
            Кстати, readlines тут не поможет, ибо в файле нет ни одного \n, фактически он — одна большая строка. Но да, можно читать по частям. Но прочитать даже целый файл в память — дело быстрое, только память кушается. Странно что обрабатывает его так медленно. Впрочем, я же написал, что решение наивное.
            0
            Нормального объяснения про Haskell нету, потому что я в нем не большой специалист, так, читаю худо-бедно со словарем ) Да и основное обсуждение находится по самой первой ссылке сообщения.
            +1
            Прикольно. :)

            A shameless plug: в UrlDisp для разбора тоже используется Прологоподобный поиск с откатом.
              0
              dcg — это вообще класс! Если бы научиться преобразовывать BNF в DCG… В поставке к Visual prolog такой пакет есть, но не осилил. Там объекты и пролог не кошерный. Кто бы помог?

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

              Самое читаемое