Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Delphi: Общие вопросы > Предельная оптимизация. TObjectList


Автор: SteelEagle 25.11.2006, 12:33
Добрый день, друзья!
Возникла небольшая проблема, программа работает слишком долго.
Суть такая. 

Задача: Удалить из файла НЕуникальные строки

Как я делаю:
Создаю объект Sentence:TObjectList, в котором хранятся TStrings
из файла считываю каждую строчку , РАЗбиваю на слова и записываю в TStrings
Т.О. в TStrings(Sentence.Item[i])[j] хранится jое слово из iого предложения
Ищу количество уникальных слов( в предложении с номером CurrentSentence по отношению к предложению CompareSentence.
если uniqWords<=1 , то предложение CompareSentence не уникально и я его удаляю из Sentence


Проблема: 
Все это слииишком долгооо работает. 

Предложите либо другой алгоритм , либо улучшения для этого.

Заранее спасибо!

Код

var
    deleted, ShoulBeUniq:integer;
  FilePath:string;
  TotalCombinations:longint;
  Sentence: TObjectList;
  percentUniq:real;

procedure MakeUniq(CurrentSentence:integer);
var 
    CompareSentence,minUniqWords, uniqWords:integer;
    i,j:integer;
    slovoNeSoderzhitsya: boolean;
begin
  minUniq:=1;
  CompareSentence:=CurrentSentence+1;
  GotoNextSentence:= false;
  uniqWords:=0;

  while (CompareSentence <= Sentence.Count-1) do
  begin
   uniqWords:=0;
   i:=0;
  while (i <= TStrings(Sentence.Items[CurrentSentence]).Count-1) do
   begin
    slovoNeSoderzhitsya:=true;
    j:=0;

    while (j <= TStrings(Sentence.Items[CompareSentence]).Count-1)and (slovoNeSoderzhitsya)  do
    begin
    if TStrings(Sentence.Items[CurrentSentence])[i] = TStrings(Sentence[CompareSentence])[j] then slovoNeSoderzhitsya:=false;
    inc(j);
    end;
    if slovoNeSoderzhitsya then inc(uniqWords);

    if (uniqWords>ShoulBeUniq) then  i:= Sentence.Count;
    inc(i);
   end;

   curUniq:=uniqWords/(TStrings(Sentence[CurrentSentence]).Count-1);
   if (curUniq<percentUniq)or(uniqWords<=1) then
   begin
    Sentence.Delete(CompareSentence);
    inc(deleted);
   end
   else
    inc(CompareSentence);

  end;
end;

Автор: jack128 25.11.2006, 16:04
Цитата(SteelEagle @  25.11.2006,  12:33 Найти цитируемый пост)
Все это слииишком долгооо работает.

долго - это сколько?

Автор: skyboy 25.11.2006, 16:43
как загружаешь данные? как разбиваешь на предложения? уверен, что основная потеря времени в приведенном коде? профайлером прошелся? кстати, разве "строка" == "предложение"? не слишком ли намудрил, может, надо только со строками работать?

Добавлено @ 16:45 
можно загнать все строки/предложения в один список, отсортировать - потом и смотреть уникальность. не надо бегать по списку туда-сюда, сравнивая каждое предложение с каждым.

Автор: BUGOR 25.11.2006, 16:55
Код

  str := TStringList.Create;
  str.Sorted:=True;
  str.Duplicates := dupIgnore;
  str.LoadFromFile('E:\1.txt');


Это чтоли? Или тебе неуникальные строки надо удалить вообще? Или только дубликаты?

Автор: jack128 25.11.2006, 17:12
Цитата(BUGOR @  25.11.2006,  16:55 Найти цитируемый пост)
Это чтоли?

твой метод нарушает порядок строк.

Автор: BUGOR 25.11.2006, 17:15
jack128, а где сказано, что этого нельзя делать?

Автор: SteelEagle 29.11.2006, 11:28
Спасибо за ответы!
Поясняю.
Смысл задачи удалить неуникальные строки(где количество уникальных слов < UniqWords)
То есть , полюбому надо разбивать на слова

долго - это сколько?
Долго -это файл из 2000 строк проверял минуты 2.


как загружаешь данные? как разбиваешь на предложения? уверен, что основная потеря времени в приведенном коде? профайлером прошелся? кстати, разве "строка" == "предложение"? не слишком ли намудрил, может, надо только со строками работать?

Добавлено @ 16:45 
можно загнать все строки/предложения в один список, отсортировать - потом и смотреть уникальность. не надо бегать по списку туда-сюда, сравнивая каждое предложение с каждым.

Загружаю из файла, TString::LoadFromFile()
Загружает быстро, но Да основная проблема в том, что "бегает по всему списку много раз.
Сортировка в особо не поможет, т.к нужно проверять по количеству уникальных слов в предложении.

Автор: Bose 29.11.2006, 16:42
SteelEagle, попробуй подключить к программе мэнеджер памяти FastMM и библиотеки FastCode и FastMove. Точные линки искать лень - они уже неоднократно пробегали и по этому форуму, и Google сразу выдаёт ссылки, и на SourceForge их можно найти.

Это совсем не ответ на твой вопрос, но подключение этих библиотек млжет существенно уменьшить время выполнения твоего алгоритма, без какой-либо существенной оптимизации. smile 

Кстати, посмотри ещё первую тему внизу: Информация по оптимизации проекта.

Автор: Romkin 29.11.2006, 22:25
Что такое "уникальное слово"? То, которое встречается только в этой строке, или просто похожесть?
В первом случае лучше сначала построить список уникальных слов, и смотреть в него.
Во втором - строится список из номера строки и самой строки, в которой слова упорядочены по алфавиту. После этого этот список упорядочивается уже по строкам. Все "похожие строки" окажутся рядышком, остается их убрать. Если добавить трретье поле, саму строку, то остается после уборки лишнего отсортировать список по номерам строк и вывести в итоговый файл.

Автор: SteelEagle 29.11.2006, 23:04
Когда сравниваем  строки: уникальное слово-то которого нет во другом предложении
Строки сравниваем парами

1.Папа жевал жевачку, а мама пила
2.Папа жевал жевачку, а мама пела
3.Папа жевал хлеб, а мама пела

сравниваем 1 и 2
пила - уникальное слово
оно только одно , поэтому 2ое предложение удаляем
сравниваем 1 и 3
3е предложение не удаляем , т.к уникальных слов 2: жевачку, пила.
итд

Автор: Romkin 29.11.2006, 23:05
Ну значит как делать я уже написал smile Начать надо с упорядочивания слов в строке

Автор: SteelEagle 29.11.2006, 23:06
Ой,не правильно понял...
Попробую сделать как ты сказал, должно получиться

а вот вопрос, 
а как определить количество уникальных слов в 1ом предложении по сравнению со 2ым? все равно надо разбивать на слова.

Все было бы проще если бы надо было просто удалить не уникальные, а тут надо проверить , 
что первая строка отличается от iой на 2 слова , если меньше чем на 2, то удалить, если больше то оставить.
При этом каждую 

PS 
Цитата
 Все "похожие строки" окажутся рядышком, остается их убрать 

 а как это сделать?

Автор: Romkin 30.11.2006, 09:20
Да, похоже, стоять не обязаны. А есть дополнительные данные, например, сколько максимально слов в строке? И сколько примерно разных слов в тексте? Это произвольный текст?
Похоже, упорядочивать слова надо не по алфавиту, а по частоте употребления.

Добавлено @ 09:23 
И постепенно делить для каждого слова множество строк на две части: есть это слово и нет этого слова.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)