[To_wave]

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

Код:

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 секунд, что даже не вооруженным взглядом видно, что очень долго.

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

[Veider]

Операции с файлами - они вообще медленные.

[To_wave]

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

Операции с файлами - они вообще медленные.

У Вас есть идей по ускорению обработки? Например из файла выгрузить в БД, или что-то еще. Это ускорит процесс?. К тому же из кода видно, что он работает не с самими файлами, а со строками, загруженными в память.

[lmikle]

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

[poli-smen]

Если всё не упирается в долгое чтение/запись то можно оптимизировать следующим образом.
Во-первых список в котором ищется совпадение нужно либо отсортировать, либо вместо TStringList использовать что нибудь вроде THashedStringList. Тогда получим такое приращение: В несортированном списке из 20000 элементов прийдётся для поиска каждого из 2млн элементов выполнить в худшем случае 20000 сравнений или в среднем 10000 сравнений. В сортированном же списке нужно в худшем случае 15 сравнений или в среднем всего 8 сравнений. Если же использовать хэш-таблицу то при незначительном количестве коллизий нужно будет примерно 1-3 сравнения.

Во-вторых вместо того чтобы устраивать цикл из 2млн повторений в котором искать элемент из списка в 20000 элементов стоит по возможности переделать наоборот - устроить цикл из 20000 повторений в котором искать элементы из списка размером в 2млн (но сортированном или хэшированном).

[icWasya]

замечание по структуре программы

Чтобы делать Exit из середина процедуры,
не забывайте использовать try finally

[Bargest]

Как бы делал я. Хотя почему бы, я почти такое и делал.
Видно, что файл 2 значительно меньше. Загружаем его в память, считая от каждой строки быстрый хеш, к примеру crc32 (табличный код есть в вике) и составляя таблицу из списков строк.
В таблице делаем, например, 32768 элементов - тогда скорее всего коллизий в файле будет очень мало, и для каждой строки будет выполняться только 1 сравнение.
От каждой строки мы считаем crc32 и добавляем в список, который в нашем массиве списков имеет индекс (crc32 and $7FFF).
Затем читаем по очереди строки из файла 1, от каждой считаем crc32, переходим к соответствующему списку, для каждого элемента сравниваем сами строки. Если в итоге строка была найдена - мы ее не пишем в файл 3. Иначе - пишем.
В чем плюс подхода - в реальности для каждой строки будет выполняться 1 сравнение строки. Когда я переделал одну прогу сравнения тысяч строк во множестве файлов на подобную хеш-таблицу, все стало работать в тысячи раз быстрее.
Минус - как всегда для хеш-таблиц, память.