Сравнение двух огромных (!) файлов

@enk · Регистрация: 16.06.2012

Студворк — интернет-сервис помощи студентам

Привет. Потребовалось сравнивать текстовые файлы (несколько файлов сравниваются с другим):
Файл 1.txt содержит 1 миллион строк.
Файл 2.txt содержит 10 миллионов строк.
Файл 3.txt содержит 5 миллионов строк.
Все их нужно сравнить с файлом keys.txt, который содержит 11 тысяч строк.
Если в открытом файле текущая строка совпадает с одной из строк в файле keys.txt, то записывать её в выходной файл.
Если сравнивать "в лоб", получается около 150 миллиардов операций. Сравнение в один поток даёт 1-3 операции за 1 мс. Подскажите, как уменьшить время сравнения.

Добавлено через 10 минут
p.s. Сейчас сравниваю так:

Pascal

procedure Thread.saveStr(sToSave: string);
var
  fOut: TextFile;
begin
  AssignFile(fOut, 'output.txt');
  if FileExists(ExtractFilePath(Paramstr(0)) + 'output.txt') then
    Append(fOut)
  else
    Rewrite(fOut);
  writeLn(fOut, sToSave);
  CloseFile(fOut);
end;
 
//..
 
function Thread.checkKeys(sLine: string): boolean;
var
  SR: TStreamReader;
  line: string;
begin
  Result := false;
  SR := TStreamReader.Create(sKeyFile);
  try
    while (not(SR.EndOfStream)) and (not(Result))do
      begin
        line := SR.ReadLine;
        if LowerCase(line) = LowerCase(sLine) then
          begin
            saveStr(sLine);
            inc(iMatch);
            Result := true;
          end;
      end;
  finally
    SR.Free;
  end;
end;
 
//..
// В цикле по файлам прохожусь
AssignFile(fInput, tsFiles[iCurFile]);
Reset(fInput);
while not(EOF(fInput)) do
  begin
    readLn(fInput, sInput);
    checkKeys(sInput);
  end;

@Mawrat · 16.10.2013, 16:40

Скорость падает из-за того, что для проверки каждой строки заново с диска читается файл ключей. Файл ключей надо полностью в память загрузить - до начала проверок. Загрузить можно в экземпляр TStringList, например. Тогда проверка строки будет выглядеть так:

Delphi

var
  Sl : TStringList;
  Line : String;
begin
  Sl := TStringList.Create;
...
  //Поиск строки Line в списке Sl без учёта регистра букв.
  if Sl.IndexOf(Line) <> -1 then begin
    //Строка Line найдена в списке Sl.
    //...
    //...
    //...
  end;
...
  FreeAndNil(Sl);
end;

@enk · 16.10.2013, 18:09 **[ТС]**

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

Скорость падает из-за того, что для проверки каждой строки заново с диска читается файл ключей. Файл ключей надо полностью в память загрузить - до начала проверок. Загрузить можно в экземпляр TStringList, например. Тогда проверка строки будет выглядеть так:

Delphi

var
  Sl : TStringList;
  Line : String;
begin
  Sl := TStringList.Create;
...
  //Поиск строки Line в списке Sl без учёта регистра букв.
  if Sl.IndexOf(Line) <> -1 then begin
    //Строка Line найдена в списке Sl.
    //...
    //...
    //...
  end;
...
  FreeAndNil(Sl);
end;

Спасибо, но! В файле ~11 тысяч строк. Что, если больше? А если строки длинные? (32 символа + каретка) * 11000. Память она не резиновая. На stackoverflow уже ответили. Использую TDictionary<string, boolean> скорость возросла в сотни раз.

@chizz · 16.10.2013, 18:20

Можно еще разбить большие файлы на файлы поменьше, сделать отдельные потоки для каждого файла и запускать их параллельно.

@gazlan · 16.10.2013, 18:31

Стандартное решение - использование Aho–Corasick string matching algorithm.

Этот алгоритм используют многие AV (с сотнями тысяч сигнатур в базе). В отличие от поиска в словаре за квадратичное время, время работы AC-автомата линейно.

В одной из моих программ, таким образом в бинарных файлах отыскиваются вхождения первых 100,000 простых чисел. Думаю, это вполне сравнимо с вашими 11,000 строк.

@chizz 993 / 521 / 102 Регистрация: 19.03.2013 Сообщений: 3,113 Записей в блоге: 19
	16.10.2013, 18:20	4
	Можно еще разбить большие файлы на файлы поменьше, сделать отдельные потоки для каждого файла и запускать их параллельно. 0

@gazlan 3174 / 1933 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	16.10.2013, 18:31	5
	Стандартное решение - использование Aho–Corasick string matching algorithm. Этот алгоритм используют многие AV (с сотнями тысяч сигнатур в базе). В отличие от поиска в словаре за квадратичное время, время работы AC-автомата линейно. В одной из моих программ, таким образом в бинарных файлах отыскиваются вхождения первых 100,000 простых чисел. Думаю, это вполне сравнимо с вашими 11,000 строк. 0

Опции темы