[Taras2020]

Добрый день, Уважаемые форумчане.

У меня возник такой вопрос: Строки текстового файла 1.txt необходимо проверить на совпадение - со строками текстового файла 2.txt. И уникальные строки, которых нет в файле 1.txt, записать в файл 3.txt.

К примеру:

Tекст в первом файле - 1.txt
Test1
Test2
Test3
Test4
Test5

Текст во втором файле - 2.txt
Test1
Test2
Test3
Test4
Test5
Stroka1
Stroka2
stroka3

После сравнения, результат в третьем файле - 3.txt
Stroka1
Stroka2
stroka3

Вот мои решения и их недостатки =>

Вариант №1 (Загрузка в память):

Код:

var
  i: integer;
  s1, s2: TStrings;
begin
  s1 := TStringList.Create;
  s2 := TStringList.Create;
  Try
    s1.LoadFromFile('1.txt');
    s2.LoadFromFile('2.txt');
    for i := s1.Count - 1 downto 0 do
      if s2.IndexOf(s1[i]) >= 0 Then
        s1.Delete(i);
    s1.SaveToFile('3.txt');
  Finally
    s1.Free;
    s2.Free;
  End;
end;

Проблема в следующем: Если файл размеров 500 мегабайт то вся память забивается и выскакивает ошибка - Out of memory. Ну это само собой понятно поскольку я загружаю и обрабатываю все в памяти.

Вопрос: Может как то можно оптимизировать код в этом варианте, кто что может подсказать ?

Вариант №2 (Чтение построчно):

Код:

var
  f1, f2, f3: textfile;
  s1, s2: string;
  b: boolean;
begin
  assignfile(f1,  '1.txt');
  assignfile(f2,  '2.txt');
  assignfile(f3, '3.txt');
  rewrite(f3);
  reset(f1);
  while not eof(f1) do
  begin
    readln(f1, s1);
    reset(f2);
    b := true;
    while not eof(f2) and b do
    begin
      readln(f2, s2);
      if s2 = s1 then
        b := false;
    end;
    if b then
      writeln(f3, s1);
  end;
  closefile(f1);
  closefile(f2);
  closefile(f3);
end;

Проблема в следующем: Очень и очень медленно работает, ну и тут принцип понятен:
1.Читаем строку из 1.txt файла
2.Открываем 2.txt, проходим по нему ищем совпадение
3.Закрываем 2.txt файл
И так для каждой строки из первого файла. Это куча времени и затрат.

Вопрос, скорее всего утверждение: В этом варианте, само собой понятно что далеко не уедешь.

П.С: Подскажите еще варианты, при использования которых, можно обрабатывать файлы до 1 гигабайта, не загружая память и при этом, иметь, хотя бы, среднюю скорость обработки ?. Заранее благодарен за помощь...

[lmikle]

Вариант 1, гибридный. Работает, если файл образцов (т.е. 1.txt) не очень большой. Грузишь 1.txt в память. Другой файл читаешь построчно и проверяешь против списка строк в памяти.

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

Кстати, примерный расчет по памяти в случае второго варианта.
Пусть средняя длинна строки будет 40 байт. Размер хэша - 128 бит, т.е. 16 байт. Плюс 32 бита (4 байта) на позицию строки. Т.о. получаем 20 байт. Т.е. сокращение объема данных в 2 раза. Если средняя длинна строки больше, то и выигрыш по пямяти больше.

ЗЫ. Кстати, если грузить в память только один файл, то, как мне кажется, вполне можно уместиться. Пусть у нас 32-битное приложение, т.е. мы можем адресовать 2Гб памяти (вариант расширенной адресации до 3Гб не рассматриваем, хотя он тоже есть). На загрузку одного из файлов уйдет 1Гб, на маппинг системы и самой программы уйдет, ну пусть по макс, еще где-то 0.5Гб. Соответсвенно, у тебя остается около 0.5Гб для данных из второго файла.

ЗЗЫ. Кстати, читать файл, который фильтруешь, можно и блоками. Допустим, читаешь блок из 1000 строк, проверяешь их, потом читаешь следующий блок.

ЗЗЗЫ. Сорри, сумбурно немного. Просто накидывал идеи, все идеи надо проверять против реальных данных, какая эвристика даст лучший результат.

[Taras2020]

Сообщение от lmikle

ЗЗЫ. Кстати, читать файл, который фильтруешь, можно и блоками. Допустим, читаешь блок из 1000 строк, проверяешь их, потом читаешь следующий блок.

Отличные советы. Интересный вариант про чтение блоками, но вот как его реализовать, нет опыта . Хотя бы приблизительно, наброску кода можете сделать. Буду премного благодарен....

[lmikle]

Ну так и читать. Собственно, тут и делать ничего на самом деле не надо.
Просто окрываешь файл через стандартные средства паскаля (AssignFile/Reset/CloseFile), Библиотека сама закеширует.
Если же хочется самому контролировать процесс, то можно примерно так:
1. Открываем файл через TFileStream.
2. Читаем блок данных определенного размера в байтах.
3. Ищем ближайший конец строки (#13#10) с конца файла.
4. Смещаем указатель в потоке на найденную дистанцию (Stream.seek - параметры посмотри в справке - тебе нужно от текущей позиции назад).
5. Грузми прочитанный блок в TStringList или что-то подобное и начинаем обработку полученного блока.

ЗЫ. Код лень ваять в 3 часа ночи...

[Taras2020]

Сообщение от lmikle

Ну так и читать. Собственно, тут и делать ничего на самом деле не надо.
Просто окрываешь файл через стандартные средства паскаля (AssignFile/Reset/CloseFile), Библиотека сама закеширует.
Если же хочется самому контролировать процесс, то можно примерно так:
1. Открываем файл через TFileStream.
2. Читаем блок данных определенного размера в байтах.
3. Ищем ближайший конец строки (#13#10) с конца файла.
4. Смещаем указатель в потоке на найденную дистанцию (Stream.seek - параметры посмотри в справке - тебе нужно от текущей позиции назад).
5. Грузми прочитанный блок в TStringList или что-то подобное и начинаем обработку полученного блока.

ЗЫ. Код лень ваять в 3 часа ночи...

Лады, попробую разобраться. По возможности, как будет время, подкиньте пример. В любом случае спасибо!

[Страдалецъ]

А вы уверены что вам нужен этот велосипед? Существуют отличные готовые решения. Может имеет смысл воспользоваться готовым? Например можно попробовать Beyong Compare.

[lmikle]

Да что уж там, можно и обычным юниксовым diff'ом сделать при желании.
Вот только мы ж не значем зачем и для чего это конкретно нужно... Если это какой-то средний шаг в обработке данных, то не совсем удобно использовать внешнее решение, если можно сделать самому.

[Taras2020]

Сообщение от lmikle

Да что уж там, можно и обычным юниксовым diff'ом сделать при желании.
Вот только мы ж не значем зачем и для чего это конкретно нужно... Если это какой-то средний, то не совсем удобно использовать внешнее решение, если можно сделать самому.

Читаете мои мысли, да это шаг в обработке данных. Я бы так, давно, уже готовую программу использовал, их полно в сети. Ну ничего, я настойчив и попробую разобраться. В любом случае спасибо за наставление!