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

@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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 строк.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

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

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