Вот тут наткнулся на, в общем-то, простую задачку состоящую в парсинге текстового файла, содержащего 5 миллионов float'ов (и подсчете их суммы). Файл генерируется следующим C#-кодом:
Задача ставилась в контексте обсуждения производительности haskell'я в применении его к задачам парсинга. Я знал, что на прологе подобные задачи решаются красиво и непринужденно используя технику DCG (Definite clause grammar: 1, 2, 3, 4). Фактически, это описание грамматик на языке Пролог, и парсинг по ним, основанный на переборно-откатном принципе работы пролога.
Ну то есть обычно получается очень кратко и красиво (например, вот решение задачки о сбалансированности скобок этим методом: программа из 7 строк), но, я подозревал, что не всегда быстро. Собственно, это мне захотелось проверить.
Довольно быстро (минут 15) была написана очевидная (naive) версия программы:
Я, конечно, подозревал облом на парсинге такого большого файла, но подкол случился раньше. Предикат 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'-виде. Для непосвященных расскажу немножко подробнее: в функциональных и логических языках программирования вы обычно не можете создавать циклы, поэтому практически все делается с использованием рекурсии. Но если её правильно написать (когда это возможно), то можно достичь того эффекта, что код скомпилируется в цикл, хотя внешне это будет рекурсия. На прологе для написания хвостовой рекурсии, предикат нужно оформить в виде
Собственно, основное в хвостовой рекурсии, это то, что в самом конце предиката происходит вызов его же самого.
Код был переписан следующим образом:
Однако опять облом, на этот раз с local stack (и потребление памяти порядка 130 мб)
Это могло означать только то, что хвостовая рекурсия не сработала, и на этот раз оказался виноват предусмотрительно (вот уж, воистину, преждевременная оптимизация — корень всех бед) поставленный в конце предиката sum/2 значек отсечения (cut, !). Именно он, призванный отсечь перебор ненужных альтернатив, будучи поставленным в конце, выключал и оптимизацию хвостовой рекурсии.
В общем, убрав оттуда этот злополучный (!), но добавив его во float после альтернативы связанной с парсингом знака (чтоб избезать запоминания точек возврата), получил окончательную версию программы:
На Core2Duo@3Ghz работает ~1мин потребляя памяти не больше 5 мб и развивая скорость парсинга ~1.3 Мб/сек. Ну что же, не так быстро как вариант на Haskell, но, имхо, очень недурно для интерпретируемого SWI-Prolog'а, и при этом весьма изящно, по сравнению с решением из корневого поста RSDN ).
Кстати, python, на удивление не порадовал скоростью. Наивный, правда, вариант
скушал 236 мегабайт памяти и проработал ~4 мин на той же конфигурации.
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 мин на той же конфигурации.
