c++ - 在 C++ 中快速搜索排序的字符串列表

Question

我在 C++ 中有一个包含大约数百个唯一字符串的列表，我需要检查该列表中是否存在某个值，但最好快如闪电。

我目前正在使用带有 std::strings 的 hash_set(因为我无法让它与 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 之前已经构建了哈希表，但我真的不愿意增加太多的复杂性。

---

我对答案的数量感到惊讶。我最终测试了几种方法的性能，并最终结合使用了 Kirkus 和 Rob K. 的答案。我之前曾尝试过二进制搜索，但我想我在实现它时遇到了一个小错误(这有多难......)。

结果令人震惊……我以为我可以使用 hash_set 快速实现……好吧，结果我没有。以下是一些统计数据(以及最终代码):

Random lookup of 5 existing keys and 1 non-existant key, 50.000 times

My original algorithm took on average 18,62 seconds
A lineair search took on average 2,49 seconds
A binary search took on average 0,92 seconds.
A search using a perfect hashtable generated by gperf took on average 0,51 seconds.

这是我现在使用的代码:

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;
      }
      else if(arrAffectedSymbols[mid] < strKey) {
         low = mid + 1;
      }
      else {
         return true;
      }
   }

   return false;
}

注意:这是 Microsoft VC++，所以我没有使用 SGI 的 std::hash_set。

---

我今天早上使用 gperf 作为 VardhanDotNet 做了一些测试建议，这确实快了很多。

Answer 1

如果你的字符串列表在编译时是固定的，使用 gperf http://www.gnu.org/software/gperf/引用: gperf 是一个完美的哈希函数生成器。对于给定的字符串列表，它以 C 或 C++ 代码的形式生成哈希函数和哈希表，用于根据输入字符串查找值。哈希函数是完美的，这意味着哈希表没有冲突，哈希表查找只需要单个字符串比较。

据我所知，gperf 的输出不受 gpl 或 lgpl 控制。