Форум программистов, компьютерный форум CyberForum.ru

Поиск - C++

Восстановить пароль Регистрация
 
Sigareta
0 / 0 / 0
Регистрация: 10.06.2009
Сообщений: 4
10.06.2009, 21:15     Поиск #1
Вечер добрый.
Подскажите максимально быстрый способ поиска, меня больше интересует не сама реализация а способ, так сказать или алгоритм..

Есть список ключ - значение. и ключ и значение строковые переменные.

например
354321-фывалорфыдва
13-флыврадфыв
8735187351-флыврдафыв
...

в подпрограмму передается строка вида "4621351" необходимо найти ключ который максимально совпадает с переданной строкой (совпадения максимального количества лидирующих цифр)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Андрейка
419 / 223 / 27
Регистрация: 25.03.2009
Сообщений: 744
10.06.2009, 21:24     Поиск #2
ну ты бери 2 строки и посимвольно находи разность их символов чем меньше разность по модулю будет тем ближе у тя одно число к другому если 0 то они равны.
Rififi
 Аватар для Rififi
2332 / 1047 / 43
Регистрация: 03.05.2009
Сообщений: 2,656
10.06.2009, 21:29     Поиск #3
преобразовать ключ из строки в число. хранить преобразованные ключи в отсортированном порядке. далее бинарным поиском
Sigareta
0 / 0 / 0
Регистрация: 10.06.2009
Сообщений: 4
10.06.2009, 21:33  [ТС]     Поиск #4
ну это не самый шустрый способ, при этом придется пройтись по всем элементам списка... а их там сотни, а может и тысячи...

Добавлено через 1 минуту 31 секунду
Цитата Сообщение от Rififi Посмотреть сообщение
преобразовать ключ из строки в число. хранить преобразованные ключи в отсортированном порядке. далее бинарным поиском
кстати первая идея была.. а разве бинарный поиск не для точного нахождения конкретного значения??ну то есть можно передать такое число которого не найдется в ключах...
Gravity
 Аватар для Gravity
556 / 550 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
10.06.2009, 22:11     Поиск #5
Цитата Сообщение от Sigareta Посмотреть сообщение
а разве бинарный поиск не для точного нахождения конкретного значения??ну то есть можно передать такое число которого не найдется в ключах...
Поиску на это пофиг, если не найдется, то вернет NULL.
Sigareta
0 / 0 / 0
Регистрация: 10.06.2009
Сообщений: 4
10.06.2009, 22:20  [ТС]     Поиск #6
так я ж об этом и говорю ) поиску то пофиг, он не найдет точного совпадения почти никогда (ну или в крайне редких случаях) а мне надо наиболее подходящее , хотя бы скажем первые 2 цифры или 1
Gravity
 Аватар для Gravity
556 / 550 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
10.06.2009, 22:33     Поиск #7
Ты, видимо, не правильно понимаешь алгоритм бинарного поиска. binsearch использует заданную функцию для сравнения, и в качестве нее ты можешь указать то, что тебе нужно, будь то strncmp или еще что-то.
Тут одна только проблема: при нахождении первого подходящего элемента, поиск его и возвращает, поэтому для твоего случая возможно надо дополнить алгоритм, чтобы он мог продолжить искать еще более подходящие ключи.
Sigareta
0 / 0 / 0
Регистрация: 10.06.2009
Сообщений: 4
10.06.2009, 22:35  [ТС]     Поиск #8
Цитата Сообщение от Gravity Посмотреть сообщение
Ты, видимо, не правильно понимаешь алгоритм бинарного поиска. binsearch использует заданную функцию для сравнения, и в качестве нее ты можешь указать то, что тебе нужно, будь то strncmp или еще что-то.
Тут одна только проблема: при нахождении первого подходящего элемента, поиск его и возвращает, поэтому для твоего случая возможно надо дополнить алгоритм, чтобы он мог продолжить искать еще более подходящие ключи.
все понял спасибо
Yandex
Объявления
10.06.2009, 22:35     Поиск
Ответ Создать тему
Опции темы

Текущее время: 09:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru