 |
|
Модераторы: Daevaorn |
 
|
|
Что использовать для быстрого поиска? 
| xvr |
|
|||
|
Эксперт  Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
А это что? (Или у вас так хэш таблицы называются?) |
|||
|
||||
Загрузка ...
| fish9370 |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 663 Регистрация: 15.4.2007 Где: Москва Репутация: -1 Всего: 1 |
вообще у нас (в университете) это называется таблица с вычисляемым входом, а перемешаная таблица, это ее частный случай.. ну впринципе хеш-таблица, это тоже ее частный случай.. Добавлено через 1 минуту и 54 секунды ну впринципе, да они обе основаны на хеш-функции.. -------------------- undefined |
|||
|
||||
| xvr |
|
|||
|
Эксперт Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
Хеш в данном случае будет эффективен если будет идеальным, т.е. без коллизий. Да и даже без коллизий потребуется как минимум 2 раза обработать входную строку - 1 раз для вычисления хеша, второй раз для посимвольного сравнения с найденным образцом. Trie дерево требует только одного прохода по исходной строке и не дает коллизий. С другой стороны оно требует дополнительных обращений в память (по штуке в каждом узле). Так что подходы приблизительно одинаково эффективны (в идеале) |
|||
|
||||
| fish9370 |
|
||||||
|
Опытный Профиль Группа: Участник Сообщений: 663 Регистрация: 15.4.2007 Где: Москва Репутация: -1 Всего: 1 |
я не до конца понял условие задачи, я думал, что все строки уникальные, а значит и хеш будет уникальным (для этого существуют офигительные хеш-функции, которые используются для поиска процесса в ядре или в астере для поиска строк) так же я предположил, что количество строк будет не более 2000
ну это реализиуется элегантно..
такая хеш таблица, будет работать со скоростью O(1) (плюс-минус разрешение коллизий, но их быть не должно если строки будут уникальными) - так что этот способ быстрее.. -------------------- undefined |
||||||
|
|||||||
| volatile |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 37 Всего: 85 |
Не-а. Строго говоря, какой бы замечательный хеш не был, это не избавляет от возможности коллизий. |
|||
|
||||
| xvr |
|
|||
|
Эксперт Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
Вычисление самого хэша от строки потребует по ней пройти как минимум 1 раз, так что скорость работы такая же |
|||
|
||||
| fish9370 |
|
||||
|
Опытный Профиль Группа: Участник Сообщений: 663 Регистрация: 15.4.2007 Где: Москва Репутация: -1 Всего: 1 |
вероятность коллизий мизерная, что ей можно принебречь..
стоило бы проверить.. -------------------- undefined |
||||
|
|||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0466 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |