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

[xdsl]

Тестируйте если надо. Но у вас же нет Windows, как у всякого идейного линуксоида. Или вы ее тщательно прячете.

Читайте внимательно, было сказано - "под рукой нет". А что-бы стало под рукой - стимула нет, неинтересно. Что было интересно - продемонстрировал кодом. В отличии от.

Насчет утверждения об отсутствии кэширования сетевых ресурсов в Windows один из авторов RFC по CIFS имеет отличное от Вашего мнение. Ссылка: "3.2.6 Клиентское кэширование" главы "3. Сетевые хранилища данных" книги "Системы хранения данных в Windows".

Насчет утверждения неэффективности перенаправления в Windows хотелось-бы ссылки на страницы, как Вы выражаетесь, "адекватных учебников". Из Ваших слов следует, что учебников, как минимум, два.

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

[SSerge]

Насчет утверждения об отсутствии кэширования сетевых ресурсов в Windows один из авторов RFC по CIFS имеет отличное от Вашего мнение. Ссылка: "3.2.6 Клиентское кэширование" главы "3. Сетевые хранилища данных" книги "Системы хранения данных в Windows".

Вот, вот... Следует внимательно прочитать материал по данной вами ссылке. Дабы не заниматься подменой понятий "кэширования" с точки зрения того, что под этим понимает Microsoft. Вообще то раньше это называлось локальным дублированием сетевого ресурса и к буферизации на операциях I/O не имеет ни малейшего отношения.

хотелось-бы ссылки на страницы

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

[Сквозняк]

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

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

Не важно, на чем это написано.

Вообще-то важно, турбопаскалевское Blockread за раз 100 мегабайт не прочитает.

При работе с буферизованными потоками получается двойная буферизация - со стороны библиотеки файлового I/O вашей RTL и cо стороны операционной системы, причем особая пикантность получается, когда I/O RTL пытается синхронизировать себя с буферизацией файловой системы - из-за циклов взаимного ожидания может возникнуть резкое замедление обмена информацией. Чем меньше единица чтения данных, тем больше вероятность такой ситуации.

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

[xdsl]

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

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

Хм. Вроде это высказывание SSerge, причем здесь я?

Добавлено спустя 6 минут 36 секунд:

Ссылок не будет.

Спасибо, дальше можно не продолжать.

[Сквозняк]

Хм. Вроде это высказывание SSerge, причем здесь я?

Натыкалось мышкой а во время проверки написанного реал в самый ответственный момент имеет свойство отрывать от процесса. Отвечал ему а имя скопипастилось твоё.

[Kitayets]

IvanS Вы бы привели бы кусок файла для примера...

Я бы использовал стандартный TParser и не парился бы с производительностью. Единственно сохранять в памяти массив потенциально размером в несколько ГБ - это круто конечно... Я бы зачитывал куда нибудь в sqlite базу на диске.

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

...
uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes, sysutils;
const
  INPUT_FILE_NAME = 'input.txt';
var
  fsInput: TFileStream;     //входной поток
  Parser: TParser;          //парсер
  data: array of double;
  I: int64; //инкремент для массива - должен быть большим т.к. чисел по условию задачи дофига
begin
  DecimalSeparator:='.'; // устанвливаем разделитель целой части (в зависимости какие в файле разделители целой части)
  //без обработки ошибок для сокращения кода
  fsInput:= TFileStream.Create(INPUT_FILE_NAME, fmOpenRead);
  i:= 0;
  //Разбираем текст при помощи TParser
  Parser:= TParser.Create(fsInput);
  while Parser.Token <> toEOF do begin
    if Parser.Token = toFloat then begin
      SetLength(data, i + 1); //это очень плохо увеличивать размер на 1, лучше сразу по много и следить отдельно
      data[i]:= Parser.TokenFloat;
      i:= i + 1; //функция inc() с int64 не работает :(
    end;
    Parser.NextToken;
  end;
  FreeAndNil(fsInput);
  //тут работаем с data
end.


Увеличивать размер массива на 1 - это много потерь. лучше на 1000 (например. но лучше что-бы размер был близок к конечному размеру массива) и отдельной переменной следить за моментом, когда следующую 1000 добавить, а после "зачитки" всех данных - конец подрезать до реального кол-ва.

Добавлено спустя 23 часа 18 минут 40 секунд:
вот подправил листинг для уменьшения кол-ва операций выделения памяти:

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

program parsing_floats;

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes, sysutils;
const
  INPUT_FILE_NAME = 'input.txt';
  ALLOC_MEM_SIZE  = 10000; //выделяем память в массиве на 10 000 ячеек в "за раз"
var
  fsInput: TFileStream;     //входной поток
  Parser: TParser;          //парсер
  data: array of double;
  I,            //инкремент для массива - должен быть большим т.к. чисел по условию задачи дофига
  freeCells: int64;  //количество свободных ячеек в дин. массиве
begin
  DecimalSeparator:='.'; // устанвливаем разделитель целой части (в зависимости какие в файле разделители целой части)
  //без обработки ошибок для сокращения кода
  fsInput:= TFileStream.Create(INPUT_FILE_NAME, fmOpenRead);
  i:= 0;
  SetLength(data, ALLOC_MEM_SIZE);
  freeCells:= ALLOC_MEM_SIZE;
  //Разбираем текст при помощи TParser
  Parser:= TParser.Create(fsInput);
  while Parser.Token <> toEOF do begin
    if Parser.Token = toFloat then begin
      data[i]:= Parser.TokenFloat;
      freeCells:= freeCells - 1;
      if freeCells = 0 then begin //если выделеные ячейки закончились то добавим ещё
        SetLength(data, Length(data) + ALLOC_MEM_SIZE);
        freeCells:= ALLOC_MEM_SIZE;
      end;
      i:= i + 1; //функция inc() с int64 не работает :(
    end;
    Parser.NextToken;
  end;
  //подрежим массив если нужно, иначе в конце мусор окажется
  if freeCells > 0 then
    SetLength(data, Length(data) - freeCells);
  FreeAndNil(fsInput);
  //тут работаем с data
end.

[IvanS]

Я бы использовал стандартный TParser и не парился бы с производительностью.

Пример файла:
This is first section
1E-5 2.3E-5 3.5E-4
/

This is second section
2*3 3*2 3*5 4*3 /

--This is comment
/ This is comment also

This is third section
2*3E-3 3*2.034 3*-5.03E-5 4*-3.045e4 / may be comments here
/ and here

Файл требуется зачитывать в память целиком, так как с ним потом надо оперативно работать.
Звездочки, двойные минусы-комментарии создают определенные неудобства при парсинге. Придется переопределять SkipWhitespace;

Ну а самое печальное, что TParser будет работать не быстрее того, что было в начале обсуждения этой ветки из-за этого:
function TParser.TokenString: string;
begin
case fToken of
toWString : Result:=fLastTokenWStr;
toFloat : if fFloatType<>#0 then
Result:=fLastTokenStr+fFloatType
else Result:=fLastTokenStr
else
Result:=fLastTokenStr;
end;
end;
А быстродействие парсинга - главная проблема работы с большими файлами.

[SSerge]

Мда, коллеги...
Я тут озадачился переводом действующего парсера с сишарпа на Благословенный Фрипаскаль...
Лучше бы я этого не пробовал - ибо нечто...

По задаче, текстовый файл, 1.3Gb, поля переменной длины, разделены табуляторами. 11 полей. Соответственно каждая строка парсится на 11 подстрок, три из которых обрабатываются. Unix Timestamp + 2 шт. IP адресов.
По словарику сверяются оба IP адреса и считается кое-что незначительное.

Итак, подход первый. Крайне близко к оригиналу. Не имеющий аналога HashMap тупо заменён на unsorted TStringList с подвешанными на него объектами TList, в коем собственные объекты. Долго ковырялся. Переписал. Оригинал: 120 секунд, новое творение 16! минут.

Задумался. Ну, дело, наверное в TStringList. Несортированный, долго ищет. Плохо. Отсортировал.
Оригинал: 120 секунд, новое творение 14 минут.

Задумался еще. Дай, думаю, сделаю собственную коллекцию. В ключе то ip-адреса, кои прекрасно сводятся в 4 байта. Сделал. У Сишарпа тоже, чтобы в равных условиях. Код коллекции почти идентичен.
Оригинал - 126 секунд, новое творение 475 секунд.

Оптимизация. Убраны параноидальные проверки.
Оригинал - 89 секунд, новое творение 430 секунд.

Далее, делаем странное. А именно, выключаем "длинные" строки {$H-}. Казалось бы, не даст ничего, да? Ан нет:
Оригинал - 89 секунд (он, не забываем так и трудится с уникодом) - программа на freepascal, уникодом не пахнет вообще, теперь еще и ShortStrings повсеместно - 240 секунд.

Всё, по тексту уже оптимизировать некуда, лезем в настройки проекта и чекаем уровень оптимизации O3.
Угу, оригинал - 89 секунд, новое творение - 195 секунд.

Что-то плохо дело в RTL со строками то, однако. Особенно, со строками AnsiStrings
Пытался, кстати, файловый буфер на файлы ввода/вывода подменить - по умолчанию там аж 256 байт - ни малейшего эффекта.
Компилятор, правда, 2.7.1
Не ожидал, не ожидал такого эффектного слива производительности.

[Sergei I. Gorelkin]

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

[Kitayets]

IvanS ну в начальном сообщении было сказано что файл содержит вещественные числа разделённые пробелами и табами, а сейчас вы приводите пример - тут каша из выражений (?), вещественных чисел в обычном представлении и научного представления вещественных чисел. тут конечно TParser в изначальном виде не подходит.
тут нужно резать на подстроки по разделителям (например extractstrings) и далее каждую строку посимвольный (с помощью стеков, очередей, или конечных автоматов) собирать и если нужно вычислять (насколько я понял строки типа 3*2.034 - это выражения) в вещественные числа.

т.е. как всегда - разговор об одном, а потом оказывается, что речь о другом.

[IvanS]

IvanS ну в начальном сообщении было сказано что файл содержит вещественные числа разделённые пробелами и табами, а сейчас вы приводите пример - тут каша из выражений (?), вещественных чисел в обычном представлении и научного представления вещественных чисел. тут конечно TParser в изначальном виде не подходит.
тут нужно резать на подстроки по разделителям (например extractstrings) и далее каждую строку посимвольный (с помощью стеков, очередей, или конечных автоматов) собирать и если нужно вычислять (насколько я понял строки типа 3*2.034 - это выражения) в вещественные числа.

т.е. как всегда - разговор об одном, а потом оказывается, что речь о другом.

Не совсем так. Звездочки надо рассматривать как разделители. Но согласен, вещественные числа в самом разнообразном представлении могут быть. Помогает только то, что определенная структура все-таки есть. Если пошли числа, то они идут большим массивом (до нескольких Гб) сплошняком до следующего "комментария".

Добавлено спустя 9 минут 17 секунд:
Основной тормоз в копировании подстроки. Чтобы получить массив чисел нужно в строке найти подстроку-число (не очень затратная процедура), потом ее скопировать в другую строку (а это уже затратная процедура), чтобы преобразовать в число (затраты не оптимизируемы) с помощью Val.

Хочу избавиться от копирования.

Добавлено спустя 2 часа 25 минут 23 секунды:
Забавно, но один и тот же код в Delphi и FPC работает по-разному:

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

procedure TForm1.Button1Click(Sender: TObject);
Var
p : PChar;
s, s1: string;
// s1: array [1..5] of char;
xp, xs,xs1: double;
e: integer;

begin
s:='2.45';
s1:=' 2.47  4 ';
p:=@s1[2];
s1[6]:=#0;
Val(s,xs,e);
Val(p,xp,e);
Label1.Caption:=FloatToStr(xs);
Label2.Caption:=FloatToStr(xp);
end;


В Delphi вернет 2.45 и 2.47, а в FPC- 2.45 и 0 (ошибка при преобразовании в Val).

[bormant]

Позвольте не согласиться.

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

var
  s: string;
  p: pchar;
  xp: double;
  e: integer;
 
begin
  s := ' 2.47 4 ';
  s[6] := #0;
  p := @s[2];
  val(p, xp, e);
  writeln(p, '; ', xp, '; ', e);
end.

Прогон:

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

2.47;  2.47000000000000E+000; 0

fpc-2.6.0

Добавлено спустя 4 минуты 36 секунд:
Причём лидирующие пробелы оно само пропускать умеет:

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

var
  s: string;
  p: pchar;
  xp: double;
  e: integer;
 
begin
  s := ' 2.47 4 ';
  s[6] := #0;
  p := @s[1];
  val(p, xp, e);
  writeln(p, '; ', xp, '; ', e);
end.


Прогон (лидирующий пробел в блоке code съеден при отображении сообщения на форуме):

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

2.47;  2.47000000000000E+000; 0

[IvanS]

Позвольте не согласиться.

Странно. Похоже, где-то с какими-то ключами компиляции в Лазарусе не так. В консоли действительно работает как в дельфи.

Добавлено спустя 10 минут 19 секунд:
Результат работы зависит от наличия или отсутствия ключа компилятора {$H+}
Если ключ есть, то дает ошибку, если нет - работает без ошибки. Но почему-то только на нижеприведенном примере.

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

Program t2;
{$mode objfpc}{$H+}
Var
  p : PChar;
  s, s1: string;
  xp, xs: double;
  e: integer;

begin
  s:='2.45';
  s1:=' 2.47  4 ';
  p:=@s1[2];
  s1[6]:=#0;
  Val(s,xs,e);
  Val(p,xp,e);
  writeln('xs = ', s,  ';  ', xs);
  writeln('xp = ', s1, ';  ', p, ';  ', xp);
end.


[Сквозняк]

Не ожидал, не ожидал такого эффектного слива производительности.

Это не паскаль слил а дельфийский подход, использовал бы вместо строк большой массив типа byte и парсер состоящий из нескольких вложенных циклов с пачкой goto и была бы скорость нормальная а за красивости надо платить.

[haword]

SSerge ты бы исходник показал чего там наваял, может все таки не до оптимизировал?