Модераторы: Poseidon, Snowy, bems, MetalFan
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Предельная оптимизация. TObjectList 
:(
    Опции темы
SteelEagle
Дата 25.11.2006, 12:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 25.11.2006

Репутация: нет
Всего: нет



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

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

Как я делаю:
Создаю объект 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;

PM MAIL   Вверх
jack128
Дата 25.11.2006, 16:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 81
Регистрация: 18.5.2005

Репутация: 2
Всего: 4



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

долго - это сколько?
PM MAIL   Вверх
skyboy
Дата 25.11.2006, 16:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


неОпытный
****


Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 4
Всего: 260



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

Добавлено @ 16:45 
можно загнать все строки/предложения в один список, отсортировать - потом и смотреть уникальность. не надо бегать по списку туда-сюда, сравнивая каждое предложение с каждым.
PM MAIL   Вверх
BUGOR
Дата 25.11.2006, 16:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 325
Регистрация: 12.3.2006

Репутация: 5
Всего: 16



Код

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


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



--------------------
Живу недоумевая, всё время хочу понять...
http://hunger.ru 
PM MAIL WWW ICQ   Вверх
jack128
Дата 25.11.2006, 17:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 81
Регистрация: 18.5.2005

Репутация: 2
Всего: 4



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

твой метод нарушает порядок строк.
PM MAIL   Вверх
BUGOR
Дата 25.11.2006, 17:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 325
Регистрация: 12.3.2006

Репутация: 5
Всего: 16



jack128, а где сказано, что этого нельзя делать?


--------------------
Живу недоумевая, всё время хочу понять...
http://hunger.ru 
PM MAIL WWW ICQ   Вверх
SteelEagle
Дата 29.11.2006, 11:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 25.11.2006

Репутация: нет
Всего: нет



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

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


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

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


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


PM MAIL   Вверх
Bose
Дата 29.11.2006, 16:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник Клуба
Сообщений: 1458
Регистрация: 5.3.2005
Где: Riga, Latvia

Репутация: 23
Всего: 51



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

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

Кстати, посмотри ещё первую тему внизу: Информация по оптимизации проекта.
PM MAIL WWW Skype   Вверх
Romkin
Дата 29.11.2006, 22:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 189
Регистрация: 14.11.2006
Где: Москва

Репутация: 2
Всего: 5



Что такое "уникальное слово"? То, которое встречается только в этой строке, или просто похожесть?
В первом случае лучше сначала построить список уникальных слов, и смотреть в него.
Во втором - строится список из номера строки и самой строки, в которой слова упорядочены по алфавиту. После этого этот список упорядочивается уже по строкам. Все "похожие строки" окажутся рядышком, остается их убрать. Если добавить трретье поле, саму строку, то остается после уборки лишнего отсортировать список по номерам строк и вывести в итоговый файл.
PM ICQ   Вверх
SteelEagle
Дата 29.11.2006, 23:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 25.11.2006

Репутация: нет
Всего: нет



Когда сравниваем  строки: уникальное слово-то которого нет во другом предложении
Строки сравниваем парами

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

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



PM MAIL   Вверх
Romkin
Дата 29.11.2006, 23:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 189
Регистрация: 14.11.2006
Где: Москва

Репутация: 2
Всего: 5



Ну значит как делать я уже написал smile Начать надо с упорядочивания слов в строке
PM ICQ   Вверх
SteelEagle
Дата 29.11.2006, 23:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 25.11.2006

Репутация: нет
Всего: нет



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

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

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

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

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

Это сообщение отредактировал(а) SteelEagle - 29.11.2006, 23:33
PM MAIL   Вверх
Romkin
Дата 30.11.2006, 09:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 189
Регистрация: 14.11.2006
Где: Москва

Репутация: 2
Всего: 5



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

Добавлено @ 09:23 
И постепенно делить для каждого слова множество строк на две части: есть это слово и нет этого слова.
PM ICQ   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Delphi: Общие вопросы"
SnowyMetalFan
bemsPoseidon
Rrader

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Литературу по Дельфи обсуждаем здесь
  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь
  • 90% ответов на свои вопросы можно найти в DRKB (Delphi Russian Knowledge Base) - крупнейшем в рунете сборнике материалов по Дельфи


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Snowy, MetalFan, bems, Poseidon, Rrader.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Delphi: Общие вопросы | Следующая тема »


 




[ Время генерации скрипта: 0.0966 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.