Поиск среди тьмы тьмущей данных, контейнеры..

← →
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]

Т.е. контейнер для максимально бодрого поиска
Посоветует кто нить чего?

>Вопрос на самом деле такой: поиск осуществляется перебором или как?

Нет, не такой.
Поиск осуществляется так, как напишет его писатель.

← →
maep (2006-01-12 11:19) [20]

"Поиск осуществляется так, как напишет его писатель."
Именно про это писатель и спрашивает, как его написать ?

> 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 © (12.01.06 11:20) [21]

> Т.е., следующим шагом к ускорению может стать использование
> TList для индексирования исходного TStringList.

Точнее сказать, что TList содержит указатели на
THStrVal = packed record hash : Longint; name: String[..]; value: Longint; end;
Список сортируется по hash, а для поиска используется
вычисленное для name значение (Find), с последующей
проверкой на полное совпадение строк.

--
Regards, LVT.

Поиск среди тьмы тьмущей данных, контейнеры.. Найти похожие ветки