Дано:
Текстовый файл, содержащий действительные числа, разделенные либо пробелами либо знаками табуляции (результаты расчета в стороннем научном ПО). Размер файла порядка 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);
Чтение и парсинг больших текстовых файлов
Модератор: Модераторы
IvanS
А Вы не пробовали читать числа из файла просто (Read()), без всяких преобразований, поисков и т.п. причуд научной мысли?
А Вы не пробовали читать числа из файла просто (Read()), без всяких преобразований, поисков и т.п. причуд научной мысли?
Vadim писал(а):А Вы не пробовали читать числа из файла просто (Read()), без всяких преобразований, поисков и т.п. причуд научной мысли?
Да, кстати, будет быстрее.
До тех пор, пока в одной из строк не окажется больше или меньше читаемых чисел, чем в остальных То есть, при таком чтении придется внимательно контролировать странное состояние EOLN, иначе можно такого начитаться...
IvanS писал(а):Идея решения:
1.Читается строка.
2. Ищутся позиции разделителей (пробел либо табуляция) предшествующего первому символу и следующего за последним символом числа. Подстрока, между разделителями и есть число, которое преобразуется в double с помощью val.
3. Действие 2 повторяется для всех чисел в строке.
4. Повторяются действия 1 - 3 пока не закончится массив чисел в файле.
2. Строку проходим один раз. При наличии непробельного символа, записываем его адрес в указатель PChar для очередной "буферной переменной", далее читаем до тех пор, пока не встретим следующий пробельный символ и заменяем его на #0. Повторяем до нужного числа аргументов в строке
- так будет быстрее, чем вы предлагаете.
Vadim писал(а):IvanS
А Вы не пробовали читать числа из файла просто (Read()), без всяких преобразований, поисков и т.п. причуд научной мысли?
Вопрос не в чтении, а в парсинге. На самом деле в строке могут оказаться не только числа и пробелы, но и "комментарии", которые нужно отделять. В общем, там парсинг нужно писать вручную. Поэтому подходит только Readln.
Добавлено спустя 3 минуты 30 секунд:
SSerge писал(а):Vadim писал(а):А Вы не пробовали читать числа из файла просто (Read()), без всяких преобразований, поисков и т.п. причуд научной мысли?
Да, кстати, будет быстрее.
То есть, при таком чтении придется внимательно контролировать странное состояние EOLN, иначе можно такого начитаться...IvanS писал(а):Идея решения:
1.Читается строка.
2. Ищутся позиции разделителей (пробел либо табуляция) предшествующего первому символу и следующего за последним символом числа. Подстрока, между разделителями и есть число, которое преобразуется в double с помощью val.
3. Действие 2 повторяется для всех чисел в строке.
4. Повторяются действия 1 - 3 пока не закончится массив чисел в файле.
2. Строку проходим один раз. При наличии непробельного символа, записываем его адрес в указатель PChar для очередной "буферной переменной", далее читаем до тех пор, пока не встретим следующий пробельный символ и заменяем его на #0. Повторяем до нужного числа аргументов в строке
- так будет быстрее, чем вы предлагаете.
Симпатичная идея. А не будет ли в предлагаемом Вами решении возникать преобразование типов string -> pchar? Это затратная процедура.
SSerge писал(а):Vadim писал(а):А Вы не пробовали читать числа из файла просто (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. Жаль что, как я понял, такой способ не очень-то подойдет.
P.S. Жаль что, как я понял, такой способ не очень-то подойдет.
В текстовом файле еще комментарии понатыканы.
Идея решения:
1.Читается строка.
Совсем необязательно, да и если строка больше свободной памяти то будут тормоза. Намного проще открыть файл как нетипизованный и работать с байтами напрямую пропуская мусорные байты или воспринимая их как разделители. Если памяти достаточно чтобы целиком загрузить файл в массив типа byte то разобрать его несколькими вложенными циклами будет несложно. Если не вместится то придётся грузить файл в массив по частям и подгружать следующие сегменты по мере необходимости не забывая изменять индекс читаемого байта.
vada писал(а):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 писал(а):Смело. Есть проверяемые тесты?
Конечно же нет.
Моя имха фишку помнит еще года с 1991, когда всякими тестами было уяснено, что попытка побайтового чтения информации из буферизованных потоков с ее обработкой "на лету" обречена на резкую деградацию производительности. Особенно деградация проявляется при попытках позиционировать позицию чтения. "Буферизованные" - соответственно поток, связанный со структурой FILE в си и нетипизированные стандартные файлы в BP, из которых данные читаются по BlockRead().xdsl писал(а):система с буферизацией сама неплохо справляется, по крайней мере под линуксом
вот под линуксом то она может быть и справляется за счет "lazy read/write" политики. А вот возьмите экстремум - ваша ОС Windows, и файл - на сетевом для вашей машины диске. Сразу ощутите прелесть подхода.
ddin <data.txt >result.txt
тоже прекрасно под windows. Можете получить самые неожиданные глюки, вплоть до потери части информации
xdsl писал(а):vada писал(а):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". Так что парсинг придется додумывать.
Но основной вопрос сняты. Спасибо всем за советы!
SSerge писал(а):...и это будет самый медленный способ между прочим. То что годится для Си (да и то не для всех операционных систем), для паскаля неприемлемо ввиду тотальной медлительности его файловых библиотек. Разве что будете считывать информацию блоками, кратными логической единице файловой системы
Что-то я в этом не уверен. В турбопаскале был ограничен доступ к ресурсам а в fpc можно за раз грузить в массив хоть мегабайт, хоть 500 мегабайт и после обрабатывать побайтно. При таких больших блоках, если ОС не устроит конфликт доступа к файлу, всё само должно устаканиться. Для линукса есть хорошая функция fpread, для нелинукса можно использовать sysutils.fyleread. Возможно для доса нет быстрых процедур для чтения файлов но в линуксе и виндовсе многие функции представляют собой морды для системных функций написанных на С/С++
Как-бы двадцать лет прошло.SSerge писал(а):xdsl писал(а):Смело. Есть проверяемые тесты?
Конечно же нет.
В любом случае, тестов нет, значит не факт, а мнение.
Нет у меня под рукой ОС Windows. И в чем могут быть проблемы при чтении с сетевого ресурса - не понимаю. Обрыв сетевого соединения? Так ответ на это такой-же, как и на возможный физической сбой жесткого диска: добавить в программу обработку исключения при чтении данных или {$I-} c проверкой ioresult.SSerge писал(а):А вот возьмите экстремум - ваша ОС Windows, и файл - на сетевом для вашей машины диске. Сразу ощутите прелесть подхода.
С чего-бы потери? Демонстрирующие этот факт тесты есть?SSerge писал(а):ddin <data.txt >result.txt
тоже прекрасно под windows. Можете получить самые неожиданные глюки, вплоть до потери части информации
xdsl писал(а):С чего-бы потери? Демонстрирующие этот факт тесты есть?
Тестируйте если надо. Но у вас же нет Windows, как у всякого идейного линуксоида.
Или вы ее тщательно прячете.Так то во всех адекватных учебниках написано, что хотя и переназначение I/O средствами операционной системы в DOS/Windows формально работает, но эту методику перегона данных между программами использовать не рекомендуется из-за низкого быстродействия и того факта, что при экстремальных нагрузках ядро системы может без уведомления останавливать такие потоки.
xdsl писал(а):в чем могут быть проблемы при чтении с сетевого ресурса - не понимаю
Ну и зря.
Сетевые ресурсы, как потенциально нестабильное соединение, в нормальном случае операционной системой не кэшируются. Поэтому при обращении на них обычно получается истинная физическая скорость доступа, а не замаскированная оптимизаторами ОС. Сквозняк писал(а):В турбопаскале был ограничен доступ к ресурсам а в fpc можно за раз грузить в массив хоть мегабайт, хоть 500 мегабайт и после обрабатывать побайтно
Речь шла о том, чтобы побайтно читать из файла мелкие единицы информации (aka char или byte), причем тут доступ к ресурсам и загрузка массива целиком?
Сквозняк писал(а):Возможно для доса нет быстрых процедур для чтения файлов но в линуксе и виндовсе многие функции представляют собой морды для системных функций написанных на С/С++
Не важно, на чем это написано. При работе с буферизованными потоками получается двойная буферизация - со стороны библиотеки файлового I/O вашей RTL и cо стороны операционной системы, причем особая пикантность получается, когда I/O RTL пытается синхронизировать себя с буферизацией файловой системы - из-за циклов взаимного ожидания может возникнуть резкое замедление обмена информацией. Чем меньше единица чтения данных, тем больше вероятность такой ситуации. Посему в общем случае, при оперировании именно байтами в потоке не стоит рассчитывать на высокую скорость такой обработки. Кстати, в "профессиональных" библиотеках баз данных на Си при доступе к файлам обычно использовались функции прямого небуферизованного взаимодействия с ОС - open/read/write, работающие через handle, а не буферизованные потоки со структурой FILE *, полным аналогом которых являются все стандартные ф-и паскаля, работающие через FILE. По причине, описанной тут.