| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Поиск среди тьмы тьмущей данных, контейнеры.. [D7, WinXP]
maep © (2006-01-12 07:57:00)Господа, есть страшная задача: Запихать в память целую таблицу с базы (string, integer), и осуществлять в ней поиск по значению строки.
Размер таблицы непотребнейший, более 2 000 000 записей.
Только не спрашивайте, почему нельзя искать прям в базе, вот так вот нужно мне:).
Есть такая штука THashedStringList. Конечно не очень быстро, но работает. Но странное дело... я его использую в двух местах, еще для одной задачи ... и мне кажется, что использование его в еще одном месте влечет ж0сткое сниженеи производительности. В настоящий момент провожу эксперименты:). Ну и, кроме того, скорость оставляет желать лучшего.
Поиск осуществлять нужно по значению строки. Велосипед изобретать не хочется, посоветуйте что-нибудь умное, пожалуйста:)
Спасибо!
Leonid Troyanovsky (2006-01-12 11:38:00) [1]
> Leonid Troyanovsky © (12.01.06 11:20) [21]
> Т.е., следующим шагом к ускорению может стать использование
> TList для индексирования исходного TStringList.
Точнее сказать, что TList содержит указатели на
THStrVal = packed record
hash : Longint;
name: String[..];
value: Longint;
end;
Список сортируется по hash, а для поиска используется
вычисленное для name значение (Find), с последующей
проверкой на полное совпадение строк.
--
Regards, LVT.
Leonid Troyanovsky (2006-01-12 11:20:00) [2]
> maep (12.01.06 10:31) [5]
> Проверил.
> THashedStringList быстрее TStringList (sorted) в полтора
> раза при объеме списка 2500 записей
Дык, все равно, непонятно, зачем THashedStringList, а не лежащий
в основе TStringHash.
Ну, а если HSL быстрее сортированного SL, то, видимо строки
в среднем длиннее 4 байт.
Т.е., следующим шагом к ускорению может стать использование
TList для индексирования исходного TStringList.
Индекс надо строить по хеш-функции (взять за основу TStringHash.HashOf).
Для TList необходимо модифицировать Find, для поиска по сортированному
списку. См. также:
http://groups.google.com/group/fido7.ru.delphi/msg/23b08e929a768df3
--
Regards, LVT.
maep (2006-01-12 11:19:00) [3]"Поиск осуществляется так, как напишет его писатель."
Именно про это писатель и спрашивает, как его написать ?
Johnmen (2006-01-12 11:17:00) [4]>Вопрос на самом деле такой: поиск осуществляется перебором или как?
Нет, не такой.
Поиск осуществляется так, как напишет его писатель.
Frozzen (2006-01-12 11:16:00) [5]Т.е. контейнер для максимально бодрого поиска
Посоветует кто нить чего?
maep (2006-01-12 11:12:00) [6]evvcom:
CaseSencitive, строка целиком. Все просто:) Хешировать мона...
"Так в нете полно такого."
веришь ли. Ничего путненго не нашел.
"Предлагаешь нам за тебя на яндекс лезть? Разжевать, в рот положить, чтоб тебе только проглотить осталось?"
Хорошо сформулирую вопрос по-другому:
Не встречал ли кто из уважаемых господ такую штуку в своей работе, о которой может сказать "о, да это вот ОНО! и работает зашибись!"
frozzen (2006-01-12 11:09:00) [7]Вопрос на самом деле такой: поиск осуществляется перебором или как?
Johnmen (2006-01-12 11:08:00) [8]>Как осуществлять поиск?
Ключевой встречный вопрос - где и чего?
evvcom (2006-01-12 11:07:00) [9]
> "Надеюсь по полному значению? И Case Sensitive?"
> Да, это не надо:)
Так да? Или не надо? Не надо чего?
Почему я спросил? Обычно делается поиск по части строки и нечуствительно к регистру. В этом случае ни о каких поисках по хешу не может идти и речи.
> Можно подробнее?
Так в нете полно такого.
> Или сцылку толковую...
Предлагаешь нам за тебя на яндекс лезть? Разжевать, в рот положить, чтоб тебе только проглотить осталось?
maep (2006-01-12 11:04:00) [10]"После "всасывания" таблицы (с полем хеша) операция поиска сводится к построению хеша поисковой строки, и собственно поиска по нему..."
Тоесть я пишу Najdi.Pojalujsta(...)?:)
Господа, я был неаккуратен в формулировках.
Я согласен на таблицу (int64, integer), вопрос - ТОТ ЖЕ.
Как осуществлять поиск?
Johnmen (2006-01-12 11:02:00) [11]>Или сцылку толковую...
Сцылок не будет....
>Можно подробнее?
Не понятно, куда подробнее, но попробую.
Для каждой "строки" в таблице в соотв.поле хранится вычисленный для неё хеш.
После "всасывания" таблицы (с полем хеша) операция поиска сводится к построению хеша поисковой строки, и собственно поиска по нему...
TUser (2006-01-12 11:02:00) [12]
> Кстаи что такое суффиксное дерево?
См. яндекс.
maep (2006-01-12 11:01:00) [13]И вообще, как эти хеши хранить. Строку в число преобразовать это я понимаю, а дальше-то что
Frozzen (2006-01-12 11:01:00) [14]У товаришча вопрос: как это хранить в памяти?
maep (2006-01-12 10:54:00) [15]" http://www.delphimaster.ru/cgi-bin/forum.pl?n=18&id=1137041866"
Мне бы тоже не пришло, но есть такая штука, как обстоятельства:)
Когда скорость критична - что может быть лучше?:)
"Храни хеши строк. Поисковую строку хешируй и ищи по хешам.
Это обычный подход."
Можно подробнее? Или сцылку толковую...
Johnmen (2006-01-12 10:43:00) [16]Храни хеши строк. Поисковую строку хешируй и ищи по хешам.
Это обычный подход.
stone (2006-01-12 10:41:00) [17]
> В жизни не поверю, что я первый, кто столкнулся с такой
> задачей.
Поверь. Мне бы даже в голову не пришло загрузить из базы сразу 2 млн. записей. Наверняка можно найти другие способы решения задачи.
maep (2006-01-12 10:31:00) [18]Проверил.
THashedStringList быстрее TStringList (sorted) в полтора раза при объеме списка 2500 записей
"Суффиксное дерево из строчек построй."
самому писать контейнер?:)
В жизни не поверю, что я первый, кто столкнулся с такой задачей. Неужели нет готовых решений?
Кстаи что такое суффиксное дерево?
maep (2006-01-12 09:55:00) [19]"Надеюсь по полному значению? И Case Sensitive?"
Да, это не надо:)
"Не очень понятно, почему именно THashedStringList."
Хм... и правда.. Сказали - быстрее...
а ведь не проверял:)
TUser (2006-01-12 09:43:00) [20]Суффиксное дерево из строчек построй.
| |
Страницы: 