Чтение и парсинг больших текстовых файлов

[IvanS]

Дано:
Текстовый файл, содержащий действительные числа, разделенные либо пробелами либо знаками табуляции (результаты расчета в стороннем научном ПО). Размер файла порядка 1 - 5 Гб.
Числовая информация разбита на строки, содержащие по нескольку чисел.

Задача:
Прочитать файл и получить массив array of double за максимально короткое время.

Идея решения:
1.Читается строка.
2. Ищутся позиции разделителей (пробел либо табуляция) предшествующего первому символу и следующего за последним символом числа. Подстрока, между разделителями и есть число, которое преобразуется в double с помощью val.
3. Действие 2 повторяется для всех чисел в строке.
4. Повторяются действия 1 - 3 пока не закончится массив чисел в файле.

Для ускорения поиска разделителей, на сколько я понял, нужно использовать указатель на char, как это сделано в быстрой версии функции Pos
Function Pos (c : Char; const s : AnsiString) : SizeInt;

В связи с задачей хотел бы получить ответ на следующий вопрос:
Получить подстроку строки можно функцией Copy(s, index, count). Правильно ли я понимаю, что при этом происходит физическое копирование подстроки во вновь выделенную область памяти? Если это так, то это не эффективно.
Можно ли придумать способ передать в процедуру Val подстроку строки без выделения памяти и копирования?
То есть хочется получить указатель на подобласть памяти строки s и именно ее и передавать в процедуру Val, что-то вроде
Val(pointerof(s,index,count), value, Err);

[Vadim]

IvanS
А Вы не пробовали читать числа из файла просто (Read()), без всяких преобразований, поисков и т.п. причуд научной мысли?

[SSerge]

А Вы не пробовали читать числа из файла просто (Read()), без всяких преобразований, поисков и т.п. причуд научной мысли?

Да, кстати, будет быстрее. До тех пор, пока в одной из строк не окажется больше или меньше читаемых чисел, чем в остальных
То есть, при таком чтении придется внимательно контролировать странное состояние EOLN, иначе можно такого начитаться...

Идея решения:
1.Читается строка.
2. Ищутся позиции разделителей (пробел либо табуляция) предшествующего первому символу и следующего за последним символом числа. Подстрока, между разделителями и есть число, которое преобразуется в double с помощью val.
3. Действие 2 повторяется для всех чисел в строке.
4. Повторяются действия 1 - 3 пока не закончится массив чисел в файле.

2. Строку проходим один раз. При наличии непробельного символа, записываем его адрес в указатель PChar для очередной "буферной переменной", далее читаем до тех пор, пока не встретим следующий пробельный символ и заменяем его на #0. Повторяем до нужного числа аргументов в строке

- так будет быстрее, чем вы предлагаете.

[IvanS]

IvanS
А Вы не пробовали читать числа из файла просто (Read()), без всяких преобразований, поисков и т.п. причуд научной мысли?

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

Добавлено спустя 3 минуты 30 секунд:

А Вы не пробовали читать числа из файла просто (Read()), без всяких преобразований, поисков и т.п. причуд научной мысли?

Да, кстати, будет быстрее. До тех пор, пока в одной из строк не окажется больше или меньше читаемых чисел, чем в остальных
То есть, при таком чтении придется внимательно контролировать странное состояние EOLN, иначе можно такого начитаться...

Идея решения:
1.Читается строка.
2. Ищутся позиции разделителей (пробел либо табуляция) предшествующего первому символу и следующего за последним символом числа. Подстрока, между разделителями и есть число, которое преобразуется в double с помощью val.
3. Действие 2 повторяется для всех чисел в строке.
4. Повторяются действия 1 - 3 пока не закончится массив чисел в файле.

2. Строку проходим один раз. При наличии непробельного символа, записываем его адрес в указатель PChar для очередной "буферной переменной", далее читаем до тех пор, пока не встретим следующий пробельный символ и заменяем его на #0. Повторяем до нужного числа аргументов в строке

- так будет быстрее, чем вы предлагаете.

Симпатичная идея. А не будет ли в предлагаемом Вами решении возникать преобразование типов string -> pchar? Это затратная процедура.

[xdsl]

А Вы не пробовали читать числа из файла просто (Read()), без всяких преобразований, поисков и т.п. причуд научной мысли?

Да, кстати, будет быстрее. До тех пор, пока в одной из строк не окажется больше или меньше читаемых чисел, чем в остальных
То есть, при таком чтении придется внимательно контролировать странное состояние EOLN, иначе можно такого начитаться...

В принципе ничего сложного в чтении с контролем eoln.
Для проверки пишем простенький генератор (ddout.pp), чтобы было на чем проверять:

Код: Выделить всё

{$mode objfpc}
var chars:integer=100000000;
begin
while chars<>0 do begin
  case random(10) of
   0..3: write(' ');
   4..7: write(#9);
   8:write(random():18:15);
   else writeln;
  end;
  dec(chars);
end;
end.


Запускаем его с перенаправлением в файл: ./ddout > data.txt
Получим файл вещественных чисел, произвольно разбавленный пробелами, табуляциями и переводами строк, размером порядка 250 метров (по теории вероятности)
Затем пишем столь-же простенький ридер (ddin.pp):

Код: Выделить всё

var x:double;
begin
while true do begin;
  read(x);
  writeln(x);
  if seekeoln then readln;
  if seekeof then break;
end;
end.


Запускаем его с перенаправлением данных из сгенерированного файла: ./ddin <data.txt >result.txt
В result.txt секунд за 15(dell lattitude 5520) получаем набор вещественных чисел. Заменяем тестовый writeln(x) на свой код и все, обработчик готов.

P.S. Жаль что, как я понял, такой способ не очень-то подойдет.

[vada]

P.S. Жаль что, как я понял, такой способ не очень-то подойдет.

В текстовом файле еще комментарии понатыканы.

[Сквозняк]

Идея решения:
1.Читается строка.

Совсем необязательно, да и если строка больше свободной памяти то будут тормоза. Намного проще открыть файл как нетипизованный и работать с байтами напрямую пропуская мусорные байты или воспринимая их как разделители. Если памяти достаточно чтобы целиком загрузить файл в массив типа byte то разобрать его несколькими вложенными циклами будет несложно. Если не вместится то придётся грузить файл в массив по частям и подгружать следующие сегменты по мере необходимости не забывая изменять индекс читаемого байта.

[xdsl]

P.S. Жаль что, как я понял, такой способ не очень-то подойдет.

В текстовом файле еще комментарии понатыканы.

Ну тогда только последовательная обработка символ за символом. Что-то типа этого:

Код: Выделить всё

var x:char;
    mode:integer; // текущей режим: 0 - разделители, 1 - число, 2 - паскалевские комментарии вида { }
    value:shortstring;
begin
mode:=0;
while not eof do begin;
  read(x);
  case mode of
    0: begin
        if x in ['0'..'9','.'] then begin mode:=1; value:=x; end
        else
        if x = '{' then mode:=2
        else
        if x<=' ' then continue
        else begin writeln('ERROR'); break; end;
       end;
    1: begin
        if x in ['0'..'9','.'] then value+=x
        else
        if x = '{' then begin mode:=2; writeln(value); end
        else
        if x<=' ' then begin mode:=0; writeln(value); end
        else begin writeln('ERROR'); break; end;
       end;
    2: begin
        if x = '}' then mode:=0
        else continue;
       end;
   end;
end;
end.


Исходный файл на 250 метров обрабатывает на моей машине за 30 секунд. А если результат в /dev/null перенаправлять вместо регулярного файла, то вообще за 10 секунд

Теперь осталось вместо writeln(value) вставить свою обработку.
Ну и парсинг вещественного числа можно скорректировать. Вместо примитивного x in ['0'..'9','.'] обработать вариант записи в экспоненциальной форме, избавиться от возможного повторения точки в записи числа и т.п.
При желании еще сверху обертку можно прикрутить для буферизации, заменив read(x) чтением символа из буфера в оперативной памяти с подзагрузкой из файла при необходимости. Хотя последнее, думаю, без особой надобности, т.к. система с буферизацией сама неплохо справляется, по крайней мере под линуксом.

[SSerge]

Намного проще открыть файл как нетипизованный и работать с байтами напрямую пропуская мусорные байты или воспринимая их как разделители

...и это будет самый медленный способ между прочим. То что годится для Си (да и то не для всех операционных систем), для паскаля неприемлемо ввиду тотальной медлительности его файловых библиотек. Разве что будете считывать информацию блоками, кратными логической единице файловой системы

[xdsl]

тотальной медлительности его файловых библиотек

Смело. Есть проверяемые тесты?

[SSerge]

Смело. Есть проверяемые тесты?

Конечно же нет. Моя имха фишку помнит еще года с 1991, когда всякими тестами было уяснено, что попытка побайтового чтения информации из буферизованных потоков с ее обработкой "на лету" обречена на резкую деградацию производительности. Особенно деградация проявляется при попытках позиционировать позицию чтения. "Буферизованные" - соответственно поток, связанный со структурой FILE в си и нетипизированные стандартные файлы в BP, из которых данные читаются по BlockRead().

система с буферизацией сама неплохо справляется, по крайней мере под линуксом

вот под линуксом то она может быть и справляется за счет "lazy read/write" политики. А вот возьмите экстремум - ваша ОС Windows, и файл - на сетевом для вашей машины диске. Сразу ощутите прелесть подхода.

ddin <data.txt >result.txt

тоже прекрасно под windows. Можете получить самые неожиданные глюки, вплоть до потери части информации

[IvanS]

P.S. Жаль что, как я понял, такой способ не очень-то подойдет.

В текстовом файле еще комментарии понатыканы.

Ну тогда только последовательная обработка символ за символом. Что-то типа этого:

Код: Выделить всё

var x:char;
    mode:integer; // текущей режим: 0 - разделители, 1 - число, 2 - паскалевские комментарии вида { }
    value:shortstring;
begin
mode:=0;
while not eof do begin;
  read(x);
  case mode of
    0: begin
        if x in ['0'..'9','.'] then begin mode:=1; value:=x; end
        else
        if x = '{' then mode:=2
        else
        if x<=' ' then continue
        else begin writeln('ERROR'); break; end;
       end;
    1: begin
        if x in ['0'..'9','.'] then value+=x
        else
        if x = '{' then begin mode:=2; writeln(value); end
        else
        if x<=' ' then begin mode:=0; writeln(value); end
        else begin writeln('ERROR'); break; end;
       end;
    2: begin
        if x = '}' then mode:=0
        else continue;
       end;
   end;
end;
end.


Исходный файл на 250 метров обрабатывает на моей машине за 30 секунд. А если результат в /dev/null перенаправлять вместо регулярного файла, то вообще за 10 секунд

Теперь осталось вместо writeln(value) вставить свою обработку.
Ну и парсинг вещественного числа можно скорректировать. Вместо примитивного x in ['0'..'9','.'] обработать вариант записи в экспоненциальной форме, избавиться от возможного повторения точки в записи числа и т.п.
При желании еще сверху обертку можно прикрутить для буферизации, заменив read(x) чтением символа из буфера в оперативной памяти с подзагрузкой из файла при необходимости. Хотя последнее, думаю, без особой надобности, т.к. система с буферизацией сама неплохо справляется, по крайней мере под линуксом.

Комментарии могут быть такие: "-- bla-bla-bla/De/dE/DE", а числа могут быть такие "-2.324e-04" или (о ужас, это FORTRAN!) даже такие "-2.43D+00". Так что парсинг придется додумывать.

Но основной вопрос сняты. Спасибо всем за советы!

[Сквозняк]

...и это будет самый медленный способ между прочим. То что годится для Си (да и то не для всех операционных систем), для паскаля неприемлемо ввиду тотальной медлительности его файловых библиотек. Разве что будете считывать информацию блоками, кратными логической единице файловой системы

Что-то я в этом не уверен. В турбопаскале был ограничен доступ к ресурсам а в fpc можно за раз грузить в массив хоть мегабайт, хоть 500 мегабайт и после обрабатывать побайтно. При таких больших блоках, если ОС не устроит конфликт доступа к файлу, всё само должно устаканиться. Для линукса есть хорошая функция fpread, для нелинукса можно использовать sysutils.fyleread. Возможно для доса нет быстрых процедур для чтения файлов но в линуксе и виндовсе многие функции представляют собой морды для системных функций написанных на С/С++

[xdsl]

Смело. Есть проверяемые тесты?

Конечно же нет. Моя имха фишку помнит еще года с 1991

Как-бы двадцать лет прошло.
В любом случае, тестов нет, значит не факт, а мнение.

А вот возьмите экстремум - ваша ОС Windows, и файл - на сетевом для вашей машины диске. Сразу ощутите прелесть подхода.

Нет у меня под рукой ОС Windows. И в чем могут быть проблемы при чтении с сетевого ресурса - не понимаю. Обрыв сетевого соединения? Так ответ на это такой-же, как и на возможный физической сбой жесткого диска: добавить в программу обработку исключения при чтении данных или {$I-} c проверкой ioresult.

ddin <data.txt >result.txt

тоже прекрасно под windows. Можете получить самые неожиданные глюки, вплоть до потери части информации

С чего-бы потери? Демонстрирующие этот факт тесты есть?

[SSerge]

С чего-бы потери? Демонстрирующие этот факт тесты есть?

Тестируйте если надо. Но у вас же нет Windows, как у всякого идейного линуксоида. Или вы ее тщательно прячете.
Так то во всех адекватных учебниках написано, что хотя и переназначение I/O средствами операционной системы в DOS/Windows формально работает, но эту методику перегона данных между программами использовать не рекомендуется из-за низкого быстродействия и того факта, что при экстремальных нагрузках ядро системы может без уведомления останавливать такие потоки.

в чем могут быть проблемы при чтении с сетевого ресурса - не понимаю

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

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

Речь шла о том, чтобы побайтно читать из файла мелкие единицы информации (aka char или byte), причем тут доступ к ресурсам и загрузка массива целиком?

Возможно для доса нет быстрых процедур для чтения файлов но в линуксе и виндовсе многие функции представляют собой морды для системных функций написанных на С/С++

Не важно, на чем это написано. При работе с буферизованными потоками получается двойная буферизация - со стороны библиотеки файлового I/O вашей RTL и cо стороны операционной системы, причем особая пикантность получается, когда I/O RTL пытается синхронизировать себя с буферизацией файловой системы - из-за циклов взаимного ожидания может возникнуть резкое замедление обмена информацией. Чем меньше единица чтения данных, тем больше вероятность такой ситуации. Посему в общем случае, при оперировании именно байтами в потоке не стоит рассчитывать на высокую скорость такой обработки. Кстати, в "профессиональных" библиотеках баз данных на Си при доступе к файлам обычно использовались функции прямого небуферизованного взаимодействия с ОС - open/read/write, работающие через handle, а не буферизованные потоки со структурой FILE *, полным аналогом которых являются все стандартные ф-и паскаля, работающие через FILE. По причине, описанной тут.