Форум: "Начинающим";
Текущий архив: 2006.01.29;
Скачать: [xml.tar.bz2];
ВнизПоиск среди тьмы тьмущей данных, контейнеры.. Найти похожие ветки
← →
maep (2006-01-12 07:57) [0]Господа, есть страшная задача: Запихать в память целую таблицу с базы (string, integer), и осуществлять в ней поиск по значению строки.
Размер таблицы непотребнейший, более 2 000 000 записей.
Только не спрашивайте, почему нельзя искать прям в базе, вот так вот нужно мне:).
Есть такая штука THashedStringList. Конечно не очень быстро, но работает. Но странное дело... я его использую в двух местах, еще для одной задачи ... и мне кажется, что использование его в еще одном месте влечет ж0сткое сниженеи производительности. В настоящий момент провожу эксперименты:). Ну и, кроме того, скорость оставляет желать лучшего.
Поиск осуществлять нужно по значению строки. Велосипед изобретать не хочется, посоветуйте что-нибудь умное, пожалуйста:)
Спасибо!
← →
evvcom © (2006-01-12 08:28) [1]
> Поиск осуществлять нужно по значению строки.
Надеюсь по полному значению? И Case Sensitive?
← →
Leonid Troyanovsky © (2006-01-12 09:40) [2]
> maep (12.01.06 07:57)
> Есть такая штука THashedStringList. Конечно не очень быстро,
Не очень понятно, почему именно THashedStringList.
Я бы начал с простого TStringList (Sorted) со значениями Integer,
записанными в Objects.
--
Regards, LVT.
← →
TUser © (2006-01-12 09:43) [3]Суффиксное дерево из строчек построй.
← →
maep (2006-01-12 09:55) [4]"Надеюсь по полному значению? И Case Sensitive?"
Да, это не надо:)
"Не очень понятно, почему именно THashedStringList."
Хм... и правда.. Сказали - быстрее...
а ведь не проверял:)
← →
maep (2006-01-12 10:31) [5]Проверил.
THashedStringList быстрее TStringList (sorted) в полтора раза при объеме списка 2500 записей
"Суффиксное дерево из строчек построй."
самому писать контейнер?:)
В жизни не поверю, что я первый, кто столкнулся с такой задачей. Неужели нет готовых решений?
Кстаи что такое суффиксное дерево?
← →
stone © (2006-01-12 10:41) [6]
> В жизни не поверю, что я первый, кто столкнулся с такой
> задачей.
Поверь. Мне бы даже в голову не пришло загрузить из базы сразу 2 млн. записей. Наверняка можно найти другие способы решения задачи.
← →
Johnmen © (2006-01-12 10:43) [7]Храни хеши строк. Поисковую строку хешируй и ищи по хешам.
Это обычный подход.
← →
maep (2006-01-12 10:54) [8]"http://delphimaster.net/view/2-1137041866/"
Мне бы тоже не пришло, но есть такая штука, как обстоятельства:)
Когда скорость критична - что может быть лучше?:)
"Храни хеши строк. Поисковую строку хешируй и ищи по хешам.
Это обычный подход."
Можно подробнее? Или сцылку толковую...
← →
Frozzen (2006-01-12 11:01) [9]У товаришча вопрос: как это хранить в памяти?
← →
maep (2006-01-12 11:01) [10]И вообще, как эти хеши хранить. Строку в число преобразовать это я понимаю, а дальше-то что
← →
TUser © (2006-01-12 11:02) [11]
> Кстаи что такое суффиксное дерево?
См. яндекс.
← →
Johnmen © (2006-01-12 11:02) [12]>Или сцылку толковую...
Сцылок не будет....
>Можно подробнее?
Не понятно, куда подробнее, но попробую.
Для каждой "строки" в таблице в соотв.поле хранится вычисленный для неё хеш.
После "всасывания" таблицы (с полем хеша) операция поиска сводится к построению хеша поисковой строки, и собственно поиска по нему...
← →
maep (2006-01-12 11:04) [13]"После "всасывания" таблицы (с полем хеша) операция поиска сводится к построению хеша поисковой строки, и собственно поиска по нему..."
Тоесть я пишу Najdi.Pojalujsta(...)?:)
Господа, я был неаккуратен в формулировках.
Я согласен на таблицу (int64, integer), вопрос - ТОТ ЖЕ.
Как осуществлять поиск?
← →
evvcom © (2006-01-12 11:07) [14]
> "Надеюсь по полному значению? И Case Sensitive?"
> Да, это не надо:)
Так да? Или не надо? Не надо чего?
Почему я спросил? Обычно делается поиск по части строки и нечуствительно к регистру. В этом случае ни о каких поисках по хешу не может идти и речи.
> Можно подробнее?
Так в нете полно такого.
> Или сцылку толковую...
Предлагаешь нам за тебя на яндекс лезть? Разжевать, в рот положить, чтоб тебе только проглотить осталось?
← →
Johnmen © (2006-01-12 11:08) [15]>Как осуществлять поиск?
Ключевой встречный вопрос - где и чего?
← →
frozzen (2006-01-12 11:09) [16]Вопрос на самом деле такой: поиск осуществляется перебором или как?
← →
maep (2006-01-12 11:12) [17]evvcom:
CaseSencitive, строка целиком. Все просто:) Хешировать мона...
"Так в нете полно такого."
веришь ли. Ничего путненго не нашел.
"Предлагаешь нам за тебя на яндекс лезть? Разжевать, в рот положить, чтоб тебе только проглотить осталось?"
Хорошо сформулирую вопрос по-другому:
Не встречал ли кто из уважаемых господ такую штуку в своей работе, о которой может сказать "о, да это вот ОНО! и работает зашибись!"
← →
Frozzen (2006-01-12 11:16) [18]Т.е. контейнер для максимально бодрого поиска
Посоветует кто нить чего?
← →
Johnmen © (2006-01-12 11:17) [19]>Вопрос на самом деле такой: поиск осуществляется перебором или как?
Нет, не такой.
Поиск осуществляется так, как напишет его писатель.
← →
maep (2006-01-12 11:19) [20]"Поиск осуществляется так, как напишет его писатель."
Именно про это писатель и спрашивает, как его написать ?
← →
Leonid Troyanovsky © (2006-01-12 11:20) [21]
> 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.
← →
Leonid Troyanovsky © (2006-01-12 11:38) [22]
> 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.
Страницы: 1 вся ветка
Форум: "Начинающим";
Текущий архив: 2006.01.29;
Скачать: [xml.tar.bz2];
Память: 0.5 MB
Время: 0.032 c