Быстрый поиск по отсортированному списку строк в C ++

Question

У меня есть список из примерно сотни уникальных строк в 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 , и это действительно немного быстрее.

Answer 1

Если ваш список строк исправлен во время компиляции, используйте gperf http://www.gnu.org/software/gperf/ QUOTE: gperf - идеальный генератор хеш-функций. Для заданного списка строк он создает хеш-функцию и хеш-таблицу в форме кода на C или C ++ для поиска значения в зависимости от входной строки. Хеш-функция идеально подходит, что означает, что хеш-таблица не имеет коллизий, а для поиска в хеш-таблице требуется только сравнение одной строки.

Вывод gperf не регулируется gpl или lgpl, afaik.

Answer 2

Вы можете попробовать PATRICIA Trie, если ни один из стандартных контейнеров не соответствует вашим потребностям.

Поиск в худшем случае ограничен длиной искомой строки. Кроме того, строки имеют общие префиксы, так что это очень просто для памяти. Так что если у вас много относительно коротких строк, это может быть полезно.

Проверьте это здесь.

Примечание: PATRICIA = Практический алгоритм для получения информации, закодированной в буквенно-цифровой форме

Answer 3

Что не так с std :: vector? Загрузите его, отсортируйте (v.begin (), v.end ()) один раз, а затем используйте lower_bound (), чтобы увидеть, находится ли строка в векторе. lower_bound гарантированно будет O (log2 N) на отсортированном итераторе произвольного доступа. Я не могу понять необходимость хэша, если значения фиксированы. Вектор занимает меньше места в памяти, чем хэш, и выделяет меньше ресурсов.

Answer 4

Если это фиксированный список, отсортируйте список и выполните бинарный поиск? Я не могу себе представить, имея всего около сотни строк на современном процессоре, вы действительно увидите заметную разницу между алгоритмами, если ваше приложение ничего не делает, кроме поиска в указанном списке 100% времени.

Answer 5

Я сомневаюсь, что вы придумаете лучшую хэш-таблицу; если список меняется время от времени, вы, вероятно, нашли лучший способ.

Самый быстрый способ - создать конечный автомат для сканирования входных данных. Я не уверен, каковы лучшие современные инструменты (прошло уже более десяти лет, как я делал что-то подобное на практике), но Lex / Flex был стандартным конструктором Unix.

FSM имеет таблицу состояний и список принимающих состояний. Он начинается в начальном состоянии и выполняет посимвольное сканирование ввода. Каждое состояние имеет запись для каждого возможного входного символа. Запись может быть либо для перехода в другое состояние, либо для прерывания, поскольку строка отсутствует в списке. Если FSM доходит до конца входной строки без прерывания, он проверяет конечное состояние, в котором он находится, который либо является принимающим состоянием (в этом случае вы сопоставили строку), либо нет (в этом случае у вас нет «т).

Любая книга о компиляторах должна содержать более подробную информацию, или вы, несомненно, найдете больше информации в Интернете.

Answer 6

100 уникальных строк? Если это не вызывается часто, и список не изменяется динамически, я бы, вероятно, использовал прямой массив константных символов с линейным поиском. Если вы не будете много искать, то такое маленькое не стоит дополнительного кода. Примерно так:

const char _items[][MAX_ITEM_LEN] = { ... };
int i = 0;
for (;  strcmp( a, _items[i] ) < 0 && i < NUM_ITEMS; ++i );
bool found = i < NUM_ITEMS && strcmp( a, _items[i] ) == 0;

Для такого небольшого списка, я думаю, что ваши затраты на внедрение и обслуживание с чем-то более сложным, вероятно, перевесят затраты времени выполнения, и вы на самом деле не получите более дешёвую стоимость, чем эта. Чтобы получить немного больше скорости, вы можете создать хеш-таблицу из первого символа char -> list, чтобы установить начальное значение i;

Для такого маленького списка вы, вероятно, не получите намного быстрее.

Answer 7

Если набор строк для проверки чисел в сотнях, как вы говорите, и это при выполнении операций ввода-вывода (загрузка файла, который, как я предполагаю, обычно происходит с диска), то я бы сказал: профиль что у вас есть, прежде чем искать более экзотические / сложные решения.

Конечно, может быть, что ваши "документы" содержат сотни миллионов этих строк, и в этом случае, я думаю, это действительно займет время ... Без подробностей трудно сказать наверняка.

То, что я говорю, сводится к тому, чтобы «рассмотреть варианты использования и типичные сценарии до (чрезмерной) оптимизации», что, я думаю, является лишь специализацией этой старой вещи о корнях зла ...:)

Answer 8

Я вырезал и вставил двоичный код поиска сверху ... Есть проблема с оригинальным двоичным кодом поиска, например, не может найти второй элемент в списке из 100 элементов.

Линия:

high = mid - 1;

Должно быть:

high = mid;

Answer 9

Вы используете бинарный поиск, который является O (log (n)). Вы должны посмотреть на интерполяционный поиск, который не так хорош, как «наихудший случай», но в среднем он лучше: O (log (log (n)).

Answer 10

хеш-таблица является хорошим решением, и, используя уже существующую реализацию, вы, вероятно, получите хорошую производительность. альтернатива, хотя я считаю, называется "индексация".

держите несколько указателей на удобных местах. например если для сортировки используются буквы, сохраняйте указатель на все, начиная с aa, ab, ac ... ba, bc, bd ... это несколько сотен указателей, но это означает, что вы можете перейти к той части списка, которая довольно близко к результату, прежде чем продолжить. например если запись является «afunctionname», то вы можете выполнять двоичный поиск между указателями af и ag, гораздо быстрее, чем поиск по всему лоту ... если у вас есть миллион записей, вам, скорее всего, придется только двоично искать список несколько тысяч.

Я заново изобрел это колесо, но уже может быть множество реализаций, которые избавят вас от головной боли при реализации и, вероятно, будут быстрее, чем любой код, который я мог бы вставить сюда. :)