| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Увеличить скорость выполнения [D7, XP]
User © (2010-04-06 22:02:00)Здравствуйте. Очень нужен совет опытных людей.
У меня имеется список строковых предложений (По 4-5 слов в среднем) загруженных в TStringList. Количество предложений около 50 тыс.
Пример предложений:
0. Товарищество с ограниченной ответственностью
1. Открытое Акционерное Общество
2. закрытое Акционерное Общество
и т.п.
При вводе пользователем определенного текста, например "Акционерное общество", система ищет данный текст по нашему списку, и сравнивает с помощью "специальной функции сравнения 2х текстов" на процент схожести. Если процент переваливает за (например 70%) текст из списка должен быть отображен.
Проблема в том, что поиск происходит очень долго, при явном сравнении текстов типа (Str = SL.String[i]) Поиск на много быстрее, но функция сравнения на процент схожести, единственная самая быстрая которую я нашел. Подскажите, как можно ускорить процесс поиска, может быть использование потоков? Если да, то если можно по подробнее. Спасибо.
Сама функция нечеткого сравнения, взято из http://www.delphikingdom.com/asp/viewitem.asp?catalogid=1147
function CompareStrings(S1, S2: string; MatchCount: integer;
out NCount: integer):integer;
var i, j, Count_, Count: integer;
S1_, S2_: String;
function Flag:Boolean;
begin
Result:= false;
if (i + Count_ <= Length(S1_))and(j + Count_ <= Length(S2_)) then
if (UpCharRus(S1_[i+Count_]) = UpCharRus(S2_[j+Count_]))
{and(S1[j+Count_] <> ' ')} then
Result:= true;
end;
begin
Count:= 0;
NCount:= 0;
S1_:=S1;
ReplaceAllStr(S1_, ' ', '');
S2_:=S2;
ReplaceAllStr(S2_, ' ', '');
if (S1_ = '')or(S2_ = '') then
begin
Result:= 0;
NCount:= 255;
Exit;
end;
i:= 1;
repeat
j:= 1;
repeat
if (UpCharRus(S1_[i]) = UpCharRus(S2_[j])){and(S1[i] <> ' ')} then
begin
Count_:= 1;
while flag do
Inc(Count_);
i:= i + Count_ - 1;
j:= j + Count_ - 1;
if Count_ >= MatchCount then
Count:= Count + Count_;
end;
inc(j)
until j >= Length(S2_);
inc(i)
until i >= Length(S1_);
if Length(S1_) < Length(S2_) then
Count_:= Length(S1_)
else
Count_:= Length(S2_);
Result:= Count;
NCount:= Count_ - Count;
end;
Игорь Шевченко (2010-04-07 14:51:00) [1]
> дальше думаю нужно кидать в потоки.
не нужно
User (2010-04-07 14:12:00) [2]
> А не получится как с кэшем браузера? Типа если он небольшой,
> то ускоряет, а если вырос бесконтрольно - тормозит.
Возможно и получится. Сейчас пробую потоковое решение данной проблемы, при миллионе записей работает быстренько, дальше думаю нужно кидать в потоки.
Sergey13 (2010-04-07 13:42:00) [3]> [18] User (07.04.10 11:52)
А не получится как с кэшем браузера? Типа если он небольшой, то ускоряет, а если вырос бесконтрольно - тормозит.
User (2010-04-07 11:52:00) [4]
> А что это, если не секрет? Локальный вариант гугла?
Это, что-то вроде самодельного ПО Trados. "Translation Memory", когда переводчик переводит тексты предложений, затем уже переведенные тексты заносит в базу, в след. раз что бы заново одно и тоже не переводить, программа покажет варианты переводов из БД, по проценту схожести.
Sergey13 (2010-04-07 10:50:00) [5]> [16] User (07.04.10 10:16)
А что это, если не секрет? Локальный вариант гугла?
Средний словарный запас человека для повседневого общения - это около 3-5 тысяч слов.
50000 выражений с ежедневным пополнением - это запись потоков мыслей? 8-)
Я бы попробовал выделять из выражений слова без последних 3-4 букв и забить их их в справочник. Выражения записал бы индексами этих слов. И по ним уже искал. Разумеется в БД.
User (2010-04-07 10:16:00) [6]Все, решил проблему. При загрузке списка сразу привел к верхнему регистру все тексты, а из функции убрал приведение к верхнему регистру. Функция в разы стала работать быстрее. Всем спасибо.
User (2010-04-07 09:39:00) [7]
> >UpCharRus(), ReplaceAllStr
> Что это такое? Что-то это не то. Совсем не то. Приведи код.
Да, в этих моментах я подправил.
UpCharRus - это AnsiUpperCase
ReplaceAllStr - StringReplace(, ' ', '', [rfReplaceAll]);
> Как ты перебираешь список? Не хочешь ли ты сказать, что
> у тебя до 50 000 * 50 000 = 2 500 000 000 сравнений?
Нет, в примере сравнений 50 тыс, один пробег по списку. Это пример, в реале список будет пополняться ежедневно.
> Самое правильное решение - положить все эти "стотыщпяцот"
> названий на какой-нибудь склсервер и привести его в порядок
> (по крайней мере избавиться от перестановок одинаковых слов
> и "разнокапитанистых" букав) - на "доске" сразу прояснится,
> гад буду :)
Вот это уже интересно. Ускорится ли поиск если я при занесении в список сразу буду названий приводить в порядок?
> Т.е пройти курс [само]обучения по известным талмудам для
> тебя не хляет ?
Ну посоветуйте хотя бы книжку, статью - что читать, кого читать. Не во всех ведь книгах найдешь нужное.
Игорь Шевченко (2010-04-07 01:03:00) [8]Дмитрий Белькевич (07.04.10 00:52) [12]
> Интересно, насколько метод надёжен? У нас тоже эта проблема
> имеется.
Для нашей задачи хватило.
> Поиск цепочек возможен средствами базы? Или хитрый предрассчёт
> - занесение цепочек в базу, потом - выборка?
Нам был нужен не поиск подцепочек, а полное сравнение результатов применения операции мамбл-ванго к выбранным из базы данным. То есть, имелся поисковый реквизит, по которому выбиралось ограниченное количество фамилий, к ним применялась мамбл-ванго, к входной фамилии тоже применялась одноименная операция, а потом тупо сравнивалось - совпало/не совпало. Если не совпало - штраф :)
Дмитрий Белькевич (2010-04-07 00:54:00) [9]Поиск цепочек возможен средствами базы? Или хитрый предрассчёт - занесение цепочек в базу, потом - выборка?
Дмитрий Белькевич (2010-04-07 00:52:00) [10]
> Это первое, что пришло на ум из опыта решения проблемы поиска
> совпадения фамилий на авиабилетах (транлитерация по хитрым
> правилам) с реальными фамилиями на русском языке
Интересно, насколько метод надёжен? У нас тоже эта проблема имеется.
Дмитрий Белькевич (2010-04-07 00:47:00) [11]
> Так вот , даже на миллионных таблицах время сканирования
> одного столбца не превышает нескольких минут.
Тут, думаю, проблема не в посимвольности. Если бы алгоритм только один раз пробегался по строке (как и в случае обычного сравнения), то всё бы работало быстро (даже если без индексов и посимвольно делать). Но алгоритм, как я себе представляю, делает множество обращений к каждому элементу сраниваемых строк.
Игорь Шевченко (2010-04-07 00:46:00) [12]Я только не совсем понял, требуется четкое совпадение или нечеткое ?
Если четкое, то хэш-таблица однозначный выбор при неплохой хэш-функции, если нечеткое, то сравнивать можно
а) в одном регистре
б) без учета гласных, кроме первой (для русского языка)
то есть,
Товарищество с ограниченной ответственностью => ТВРЩСТВСОГРНЧНОТВСТВНСТ
Открытое Акционерное Общество => ОТКРТАКЦНРНОБЩСТВ
далее - поиск подцепочек
Это первое, что пришло на ум из опыта решения проблемы поиска совпадения фамилий на авиабилетах (транлитерация по хитрым правилам) с реальными фамилиями на русском языке
MsGuns (2010-04-07 00:38:00) [13]Эх, а вот интересно, у меня есть программулька, которая в указанной таблице сканирует столбец (CHAR) и определяет те поля, в которых не все символы в русской, украинской или английской кодировке, т.е. смешанный.
Сравнение идет посимвольное.
Так вот , даже на миллионных таблицах время сканирования одного столбца не превышает нескольких минут.
MsGuns (2010-04-07 00:32:00) [14]Самое правильное решение - положить все эти "стотыщпяцот" названий на какой-нибудь склсервер и привести его в порядок (по крайней мере избавиться от перестановок одинаковых слов и "разнокапитанистых" букав) - на "доске" сразу прояснится, гад буду :)
Дмитрий Белькевич (2010-04-07 00:32:00) [15]Предлагайте, Jeer, свой метод.
И так... Морщины сокращаются на 34.56%...
Дмитрий Белькевич (2010-04-07 00:19:00) [16]
> Типа, пошел к цыганке, она нагадала, ты скинул ей и все
> путем ?
Типа как-то так, да.
Jeer (2010-04-06 23:17:00) [17]
> Неалгоритмическое ускорение, если повезёт, даст ускорение
> на порядок, думаю, не больше.
Типа, пошел к цыганке, она нагадала, ты скинул ей и все путем ?
***
Бляха-муха - я просто валяюсь в песке под пирамидами от таких вот "советчиков".
Дмитрий Белькевич (2010-04-06 22:50:00) [18]
> Как ты перебираешь список? Не хочешь ли ты сказать, что
> у тебя до 50 000 * 50 000 = 2 500 000 000 сравнений?
Ну почему же - юзер ввёл строку, сравнили с 50-ю тысячами образцов.
1. Перевести код в асм. Может дать некоторое ускорение.
2. Попробовать распараллелить на 5-10 потоков. Все сравниваемые строки предварительно делятся на 5-10 TStringList'ов, каждый TStringList считается своим потоком.
3. Идеальный вариант - это использовать не саму строку, но её 'слепок' - хэш, либо какую-то свою функцию - резать строку как-то на буквы/слоги/слова, считать их количество, или еще как-то. Идея в том, что бы сравнивать не 'сырые данные' - строки, а предварительно так подготовленные, что бы можно было сравнивать 'слепки' строк обычным сравнением, что даст наибыстрейшее нечёткое сравнение.
С этим алгоритмом, думаю, существенного прироста добиться не удастся. Неалгоритмическое ускорение, если повезёт, даст ускорение на порядок, думаю, не больше.
Jeer (2010-04-06 22:35:00) [19]
> User (06.04.10 22:02)
Т.е пройти курс [само]обучения по известным талмудам для тебя не хляет ?
Харакири (2010-04-06 22:28:00) [20]>Забыл добавить, поиск по вхождению исключается, поиск должен быть именно "нечеткого сравнения"
Смотрю, у тебя не только сравнение "нечеткое", но и все остальное - такое же нечеткое. Особенно постановка вопросов.
Тебе что надо-то: "нечеткое сравнение" или "увеличить скорость выполнения"?
>UpCharRus(), ReplaceAllStr
Что это такое? Что-то это не то. Совсем не то. Приведи код.
>Количество предложений около 50 тыс.
Как ты перебираешь список? Не хочешь ли ты сказать, что у тебя до 50 000 * 50 000 = 2 500 000 000 сравнений?
Вообще, хорошо бы для каждой строки один раз высчитать свой некий хеш, наподобие SoundEx, и сравнивать хеши.
| |
Страницы: 