Как оптимизировать обработку длинных циклов?

Question

[IvanKalinin]

Все доброго времени суток, не могли бы вы помочь оптимизировать работу следующей процедуры:

procedure TForm1.Button3Click(Sender: TObject);
var L1,L2,L3:TStringList;
D1:TOpenDialog;
n1:string;
i:integer;
begin
L1:=TStringList.Create; //создание 1го стринглиста
L2:=TStringList.Create; //создание 2го стринглиста
L3:=TStringList.Create; //создание 3го стринглиста
 
D1:=TOpenDialog.Create(self);
 
if D1.Execute then n1:=D1.Filename else exit;
L1.LoadFromFile(n1);
 
if D1.Execute then L2.LoadFromFile(D1.Filename) else exit;
 
for i:=0 to L1.Count-1 do
if L2.IndexOf(L1[i])=-1 then L3.Add(L1[i]);
 
L3.SaveToFile('3.txt');
D1.Free;L1.Free; L2.Free; L3.Free;
 
end;

В общих чертах:
есть файл 1 с набором строк
есть файл 2 с набором строк-2

Задача из файла 1 удалить все строки, которые встречаются в файле 2 и результат записать в файл 3.
НО проблема заключается вот в чем. В файле 1 около 2 млн. строк, в файле 20 тыс.
В данном алгоритме обрабатывается 1000 строк из 2х млн. в 7-8 секунд, что даже не вооруженным взглядом видно, что очень долго.

Есть ли какие нибудь идеи, как оптимизировать обработку файлов, чтобы значительно ускорить процесс

На одном из ресурсов предлагали использовать хешированные таблицы, но как ими пользоваться не научился.

Answer 1

[Hint]

Я бы первым делом проверил время выполнения при отсортированном списке (в этом случае при IndexOf используется умный алгоритм поиска, а не обычный перебор). Т. е. добавьте "L2.Sorted := True". Если результат не устроит, то экспериментируйте дальше. Например, попробуйте для L2 вместо TStringList использовать хеш-таблицу TDictionary и метод ContainsKey.

А еще у вас утечки памяти. В случае exit объекты не уничтожаются. Используйте try и finally.

Answer 2

[Masterme]

Псевдокод если сначала дублировать в список:

L3 = L1.clone
for line in L3
    if line not in L2
        L3.remove line
    endif
endfor
L3.savetofile '3.txt'

Псевдокод если писать сразу в файл (если работать только с файлами, то стринглисты не нужны, можно читать из первого файла построчно):

for line in L1
    if line not in L2
        line.append_to_file '3.txt'
    endif
endfor

Теперь к вопросу о проверке строки в L2 и хэшах.
Есть два понятия хэшей.
Первое - хэш-функция от некоего объекта H(S), такая, что если S1=S2, то H(S1)=H(S2). Это значит, что для проверки равенства объектов достаточно сравнить их хэши. В качестве объектов сравнения могут быть строки, файлы и т.д. В качестве хэш-функции обычно используют MD5.
Второе - это хэш-массивы или ассоциативные массивы. Они хороши тем, что поиск значения в них всегда по сложности O(1). То есть, для проверки не нужно перебирать все элементы.
Теперь пример:
пусть у нас есть три строки: 'abc', 'def', 'ghi'.
md5('abc') = '900150983cd24fb0d6963f7d28e17f72'
md5('def') = '4ed9407630eb1000c0f6b63842defa7d'
md5('ghi') = '826bbc5d0522f5f20a1da4b60fa8c871'
строим хэш-массив

L2_hash = {
  '900150983cd24fb0d6963f7d28e17f72' = 'abc',
  '4ed9407630eb1000c0f6b63842defa7d' = 'def',
  '826bbc5d0522f5f20a1da4b60fa8c871' = 'ghi'
}

теперь при проверки, есть ли строка some_string можно сделать так (псевдокод)

if L2_hash[md5(some_string)]
  // строка содержится
endif

более того, не обязательно хранить строки, можно сделать так

L2_hash = {
  '900150983cd24fb0d6963f7d28e17f72' = 1,
  '4ed9407630eb1000c0f6b63842defa7d' = 1,
  '826bbc5d0522f5f20a1da4b60fa8c871' = 1
}

всё это псевдокод, я паскаль уже забыл. надеюсь принцип понятен

Answer 3

[Nikita Permin]

Мой вам совет - не используйте TStringList для обработки больших объемов данных. Лучше в простые массивы строк загрузите ваши файлы и далее можете таким же перебором их обойти. Результат будет заметен невооруженным глазом, говорю это из своего опыта.

Comments

[Hint]

TStringList внутри использует обычный массив (правда строки динамические, а не фиксированные, плюс указатель на объект). Класс добавляет свои методы и оптимизирует некоторые операции. С ним просто нужно уметь работать (не забывать про BeginUpdate, EndUpdate и пр.). Например, как вы будете считывать файл в массив? Читать построчно, увеличить размер массива на 1, заносить в последний элемент строку? И каждый раз массив будет копироваться в памяти туда-сюда. Можно при необходимости увеличивать размер массива каждый раз на тысячу (или любое другое число), но за этим уже нужно следить (хранить где-то реальное число элементов и работать с ним). В TStringList это уже реализовано. Нужен поиск по массиву? Перебором искать медленно. Давайте отсортируем и будем искать делением. Так это в TStringList уже тоже реализонова :) И так далее.

Answer 4

[M_PRO]

Вариант 1 - вставить ProgressBar, Application.ProcesMessages, курсор - часики.
Вариант 2 - не использовать IndexOf в таком контексте.

Псевдокод:

List1.Sorted := True;
List2.Sorted := True;
Index1 := 0;
Index2 := 0;
while (Index1 < List1.Count - 1) and (Index2 < List1.Count - 1) do
begin
   Cmp := CompareStrings(List1[Index1],
                                         List2[Index2]);
   if Cmp = 0 then Inc(Index1);
   if Cmp > 0 then Inc(Index2);
   if Cmp < 0 then 
   begin
      List3.Add(List1[Index1]);
      Inc(Index1);
   end;
end;

Будет проще и быстрее хэшей.

Answer 5

[Арман Токсимбаев]

LoadFromFile создает копию файла в оперативной памяти.
Это может быть оооочень долго при большом файле.
В вашем случае, Список1 лучше оставить на диске и считывать из него построчно.
Список3 также не хранить в памяти, а сразу записывать на диск.
Список2, можно оставить в памяти, но как уже говорили, желательно предварительно отсортировать.