У меня есть список из примерно сотни уникальных строк в C ++, мне нужно проверить, существует ли значение в этом списке, но желательно молниеносно.
В настоящее время я использую hash_set с std :: strings (поскольку я не могу заставить его работать с const char *) примерно так:
stdext::hash_set<const std::string> _items;
_items.insert("LONG_NAME_A_WITH_SOMETHING");
_items.insert("LONG_NAME_A_WITH_SOMETHING_ELSE");
_items.insert("SHORTER_NAME");
_items.insert("SHORTER_NAME_SPECIAL");
stdext::hash_set<const std::string>::const_iterator it = _items.find( "SHORTER_NAME" ) );
if( it != _items.end() ) {
std::cout << "item exists" << std::endl;
}
Кто-нибудь еще может предложить более быстрый метод поиска без создания полной хэш-таблицы сам?
Список - это фиксированный список строк, который не изменится. Он содержит список имен элементов, на которые влияет определенная ошибка, и должен быть исправлен на лету при открытии с более новой версией.
Я построил хеш-таблицы до использования Aho-Corasick, но я не очень-то готов добавить слишком много сложности.
Я был поражен количеством ответов. В итоге я протестировал несколько методов их работы и использовал комбинацию ответов Киркуса и Роба К. Я пробовал бинарный поиск и раньше, но, думаю, у меня возникла небольшая ошибка (насколько сложно это может быть ...).
Результаты были шокирующими ... Я думал, что у меня быстрая реализация с использованием hash_set ... ну, в конце концов, я этого не сделал. Вот немного статистики (и возможный код):
Случайный поиск 5 существующих ключей и 1 несуществующего ключа, 50.000 раз
Мой оригинальный алгоритм занял в среднем 18,62 секунд
Поиск линии в среднем занял 2,49 секунд
Бинарный поиск занимал в среднем 0,92 секунд.
Поиск с использованием идеальной хеш-таблицы, сгенерированной gperf, занял в среднем 0,51 секунд.
Вот код, который я сейчас использую:
bool searchWithBinaryLookup(const std::string& strKey) {
static const char arrItems[][NUM_ITEMS] = { /* list of items */ };
/* Binary lookup */
int low, mid, high;
low = 0;
high = NUM_ITEMS;
while( low < high ) {
mid = (low + high) / 2;
if(arrAffectedSymbols[mid] > strKey) {
high = mid - 1;
}
else if(arrAffectedSymbols[mid] < strKey) {
low = mid + 1;
}
else {
return true;
}
}
return false;
}
ПРИМЕЧАНИЕ. Это Microsoft VC ++, поэтому я не использую std :: hash_set из SGI.
Сегодня утром я провел несколько тестов с использованием gperf, как и VardhanDotNet , и это действительно немного быстрее.