Форум по Delphi программированию

Delphi Sources



Вернуться   Форум по Delphi программированию > Все о Delphi > [ "Начинающим" ]
Ник
Пароль
Регистрация <<         Правила форума         >> FAQ Пользователи Календарь Поиск Сообщения за сегодня Все разделы прочитаны

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 11.11.2013, 12:01
To_wave To_wave вне форума
Прохожий
 
Регистрация: 11.11.2013
Сообщения: 5
Версия Delphi: delphi 2006
Репутация: 10
По умолчанию Оптимизация обработки длинных циклов

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

Код:
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  
Старый 11.11.2013, 12:47
Аватар для Veider
Veider Veider вне форума
Прохожий
 
Регистрация: 02.11.2012
Сообщения: 2
Репутация: 10
По умолчанию

Операции с файлами - они вообще медленные.
Ответить с цитированием
  #3  
Старый 11.11.2013, 12:53
To_wave To_wave вне форума
Прохожий
 
Регистрация: 11.11.2013
Сообщения: 5
Версия Delphi: delphi 2006
Репутация: 10
По умолчанию

Цитата:
Сообщение от Veider
Операции с файлами - они вообще медленные.
У Вас есть идей по ускорению обработки? Например из файла выгрузить в БД, или что-то еще. Это ускорит процесс?. К тому же из кода видно, что он работает не с самими файлами, а со строками, загруженными в память.
Ответить с цитированием
  #4  
Старый 11.11.2013, 18:05
lmikle lmikle вне форума
Модератор
 
Регистрация: 17.04.2008
Сообщения: 8,004
Версия Delphi: 7, XE3, 10.2
Репутация: 49089
По умолчанию

Не думаю, что получится сильно оптимизировать, т.к. там и так алгоритмически все нормально. Можно попробовать разбить задачу на несколько потоков, отсортировав файл образца и прверку выносить в поток, который работает только с кусочком. Только может оказаться, что подготовка к этому и синххронизация сожрут весь выигрыш.
Ответить с цитированием
  #5  
Старый 11.11.2013, 18:26
Аватар для poli-smen
poli-smen poli-smen вне форума
Профессионал
 
Регистрация: 06.08.2012
Адрес: Кривой Рог
Сообщения: 1,791
Версия Delphi: Delphi 7, XE2
Репутация: 4415
По умолчанию

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

Во-вторых вместо того чтобы устраивать цикл из 2млн повторений в котором искать элемент из списка в 20000 элементов стоит по возможности переделать наоборот - устроить цикл из 20000 повторений в котором искать элементы из списка размером в 2млн (но сортированном или хэшированном).
Ответить с цитированием
Этот пользователь сказал Спасибо poli-smen за это полезное сообщение:
To_wave (11.11.2013)
  #6  
Старый 11.11.2013, 20:24
icWasya icWasya вне форума
Местный
 
Регистрация: 09.11.2010
Сообщения: 499
Репутация: 10
По умолчанию

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

Чтобы делать Exit из середина процедуры,
не забывайте использовать try finally
Ответить с цитированием
Этот пользователь сказал Спасибо icWasya за это полезное сообщение:
To_wave (11.11.2013)
  #7  
Старый 11.11.2013, 20:33
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

Как бы делал я. Хотя почему бы, я почти такое и делал.
Видно, что файл 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  
Старый 11.11.2013, 21:54
To_wave To_wave вне форума
Прохожий
 
Регистрация: 11.11.2013
Сообщения: 5
Версия Delphi: delphi 2006
Репутация: 10
По умолчанию

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

А можно примером кода по моему случаю?
Ответить с цитированием
  #9  
Старый 12.11.2013, 06:41
lmikle lmikle вне форума
Модератор
 
Регистрация: 17.04.2008
Сообщения: 8,004
Версия Delphi: 7, XE3, 10.2
Репутация: 49089
По умолчанию

Цитата:
Сообщение от To_wave
А можно примером кода по моему случаю?

А можно узнать - зачем самому писать HashArray (HashList)? TDictionary чем не устраивает?
Ответить с цитированием
Этот пользователь сказал Спасибо lmikle за это полезное сообщение:
To_wave (12.11.2013)
  #10  
Старый 12.11.2013, 08:20
To_wave To_wave вне форума
Прохожий
 
Регистрация: 11.11.2013
Сообщения: 5
Версия Delphi: delphi 2006
Репутация: 10
По умолчанию

Цитата:
Сообщение от lmikle
TDictionary чем не устраивает?
Уметь бы еще им пользоваться.... Не подскажите по частному случаю?
Ответить с цитированием
  #11  
Старый 12.11.2013, 09:25
lmikle lmikle вне форума
Модератор
 
Регистрация: 17.04.2008
Сообщения: 8,004
Версия Delphi: 7, XE3, 10.2
Репутация: 49089
По умолчанию

Цитата:
Сообщение от To_wave
Уметь бы еще им пользоваться.... Не подскажите по частному случаю?

Вот тут пара примеров (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  
Старый 12.11.2013, 13:26
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

Цитата:
А можно примером кода по моему случаю?
Нет, я это делал на другом языке. Для делфи как правило проще взять готовое, если оно есть (а lmikle подсказывает, что есть). Сам я готовыми компонентами почти не баловался (не люблю я это дело), поэтому ничего почти о них не знаю.
__________________
jmp $ ; Happy End!
The Cake Is A Lie.
Ответить с цитированием
  #13  
Старый 18.11.2013, 12:19
To_wave To_wave вне форума
Прохожий
 
Регистрация: 11.11.2013
Сообщения: 5
Версия Delphi: delphi 2006
Репутация: 10
По умолчанию

сортировка файлов в памяти аля L2.Sorted := True ускорило процесс в тысячи раз.
Ответить с цитированием
  #14  
Старый 18.11.2013, 12:29
Аватар для Freeman
Freeman Freeman вне форума
Местный
 
Регистрация: 05.10.2012
Адрес: Санкт-Петербург
Сообщения: 576
Версия Delphi: 6
Репутация: выкл
По умолчанию

Из первоначальной постановки не было понятно, важна ли последовательность исходных строк. Автору двойка за постановку задачи.
__________________
Не стоит путать форумы с богадельнями. © Bargest
Ответить с цитированием
  #15  
Старый 18.11.2013, 12:33
Аватар для poli-smen
poli-smen poli-smen вне форума
Профессионал
 
Регистрация: 06.08.2012
Адрес: Кривой Рог
Сообщения: 1,791
Версия Delphi: Delphi 7, XE2
Репутация: 4415
По умолчанию

Цитата:
Сообщение от Freeman
Из первоначальной постановки не было понятно, важна ли последовательность исходных строк. Автору двойка за постановку задачи.
Сортировка второго списка никак не повлияет на конечный результат, за исключением конечно значительного ускорения работы.
Ответить с цитированием
Ответ


Delphi Sources

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB-коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход


Часовой пояс GMT +3, время: 18:34.


 

Сайт

Форум

FAQ

RSS лента

Прочее

 

Copyright © Форум "Delphi Sources" by BrokenByte Software, 2004-2023

ВКонтакте   Facebook   Twitter