快速搜索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的快速实现......好吧,最后我没有.这是一些统计信息(以及最终的代码):

随机查找5个现有密钥和1个非现有密钥,50.000次

我原来的算法了平均18,62秒
208和208'的搜索了平均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++,所以我没有使用SGI的std :: hash_set.

---

我今天早上使用gperf进行了一些测试,正如VardhanDotNet建议的那样,这确实要快得多.

Answer 1

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

gperf的输出不受gpl或lgpl,afaik的控制.

Answer 2

如果没有标准容器满足您的需求,您可以尝试PATRICIA Trie.

最坏情况查找受到您正在查找的字符串长度的限制.此外,字符串共享公共前缀,因此它在内存中非常容易.所以,如果你有很多相对较短的字符串,这可能是有益的.

在这里查看.

注意:PATRICIA =检索以字母数字编码的信息的实用算法