|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
|||
|
|||
Оптимизация обработки длинных циклов
Все доброго времени суток, не могли бы вы помочь оптимизировать работу следующей процедуры:
Код:
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 секунд, что даже не вооруженным взглядом видно, что очень долго. Есть ли какие нибудь идеи, как оптимизировать обработку файлов. Спасибо. |
#2
|
||||
|
||||
Операции с файлами - они вообще медленные.
|
#3
|
|||
|
|||
Цитата:
|
#4
|
|||
|
|||
Не думаю, что получится сильно оптимизировать, т.к. там и так алгоритмически все нормально. Можно попробовать разбить задачу на несколько потоков, отсортировав файл образца и прверку выносить в поток, который работает только с кусочком. Только может оказаться, что подготовка к этому и синххронизация сожрут весь выигрыш.
|
#5
|
||||
|
||||
Если всё не упирается в долгое чтение/запись то можно оптимизировать следующим образом.
Во-первых список в котором ищется совпадение нужно либо отсортировать, либо вместо TStringList использовать что нибудь вроде THashedStringList. Тогда получим такое приращение: В несортированном списке из 20000 элементов прийдётся для поиска каждого из 2млн элементов выполнить в худшем случае 20000 сравнений или в среднем 10000 сравнений. В сортированном же списке нужно в худшем случае 15 сравнений или в среднем всего 8 сравнений. Если же использовать хэш-таблицу то при незначительном количестве коллизий нужно будет примерно 1-3 сравнения. Во-вторых вместо того чтобы устраивать цикл из 2млн повторений в котором искать элемент из списка в 20000 элементов стоит по возможности переделать наоборот - устроить цикл из 20000 повторений в котором искать элементы из списка размером в 2млн (но сортированном или хэшированном). |
Этот пользователь сказал Спасибо poli-smen за это полезное сообщение: | ||
To_wave (11.11.2013)
|
#6
|
|||
|
|||
замечание по структуре программы
Чтобы делать Exit из середина процедуры, не забывайте использовать try finally |
Этот пользователь сказал Спасибо icWasya за это полезное сообщение: | ||
To_wave (11.11.2013)
|
#7
|
||||
|
||||
Как бы делал я. Хотя почему бы, я почти такое и делал.
Видно, что файл 2 значительно меньше. Загружаем его в память, считая от каждой строки быстрый хеш, к примеру crc32 (табличный код есть в вике) и составляя таблицу из списков строк. В таблице делаем, например, 32768 элементов - тогда скорее всего коллизий в файле будет очень мало, и для каждой строки будет выполняться только 1 сравнение. От каждой строки мы считаем crc32 и добавляем в список, который в нашем массиве списков имеет индекс (crc32 and $7FFF). Затем читаем по очереди строки из файла 1, от каждой считаем crc32, переходим к соответствующему списку, для каждого элемента сравниваем сами строки. Если в итоге строка была найдена - мы ее не пишем в файл 3. Иначе - пишем. В чем плюс подхода - в реальности для каждой строки будет выполняться 1 сравнение строки. Когда я переделал одну прогу сравнения тысяч строк во множестве файлов на подобную хеш-таблицу, все стало работать в тысячи раз быстрее. Минус - как всегда для хеш-таблиц, память. jmp $ ; Happy End! The Cake Is A Lie. Последний раз редактировалось Bargest, 11.11.2013 в 20:39. |
Этот пользователь сказал Спасибо Bargest за это полезное сообщение: | ||
To_wave (11.11.2013)
|
#8
|
|||
|
|||
Цитата:
А можно примером кода по моему случаю? |
#9
|
|||
|
|||
Цитата:
А можно узнать - зачем самому писать HashArray (HashList)? TDictionary чем не устраивает? |
Этот пользователь сказал Спасибо lmikle за это полезное сообщение: | ||
To_wave (12.11.2013)
|
#10
|
|||
|
|||
Цитата:
|
#11
|
|||
|
|||
Цитата:
Вот тут пара примеров (eng): http://stackoverflow.com/questions/5...jectdictionary http://delphi.about.com/od/beginners...-in-delphi.htm Если Delphi 7, то см здесь: http://gurin.tomsknet.ru/delphidecal.html |
#12
|
||||
|
||||
Цитата:
jmp $ ; Happy End! The Cake Is A Lie. |
#13
|
|||
|
|||
сортировка файлов в памяти аля L2.Sorted := True ускорило процесс в тысячи раз.
|
#14
|
||||
|
||||
Из первоначальной постановки не было понятно, важна ли последовательность исходных строк. Автору двойка за постановку задачи.
Не стоит путать форумы с богадельнями. © Bargest |
#15
|
||||
|
||||
Цитата:
|