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

我有一个关于C++中数百个唯一字符串的列表，我需要检查列表中是否存在一个值，但最好快闪。快速搜索C++中的字符串排序列表

我currenly与使用的std ::串一的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; 
}

有没有人有一个好主意，以便更快搜索方法没有建立一个完整的散列表我自己？

该列表是不会更改的字符串的固定列表。它包含一个受某些bug影响的元素名称列表，并且应该在用新版本打开时即时修复。

我在使用Aho-Corasick之前就已经构建了哈希表，但是我不太愿意添加太多的复杂性。

我很惊讶的答案的数量。最后，我测试了几种方法，结果使用了kirkus和Rob K.的答案。我之前尝试过二分搜索，但我想我有一个小错误实现它（有多难......）。

结果令人震惊...我以为我有一个快速实现使用hash_set ......好吧，结果我没有。下面是一些统计数据（和最终码）：

现有5个按键和一个不存在的键的随机查找，50.000倍

我原来的算法，平均需18,62秒
平均检索时间平均为2,49秒
二分查找平均需要0,92秒。
使用gperf生成的完美hashtable进行搜索，平均需要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; 
}

注：这是微软VC++所以我不使用从SGI在std ::的hash_set。

我做了一些测试今天上午的gperf使用作为VardhanDotNet建议，这是相当快一点确实如此。

来源

2009-01-26 Huppie

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

gperf的输出不受gpl或lgpl，afaik控制。

来源

2009-01-26 15:25:21 vrdhn

嗯...我想我目前的实现速度够快，但是我会给gperf一个尝试，只是为了体验和比较材料。 – Huppie 2009-01-27 07:30:51

我怀疑你会想出一个更好的哈希表;如果名单不时变化，你可能已经有了最好的办法。

最快的方法是构造一个有限状态机来扫描输入。我不确定最好的现代工具是什么（从我在实践中做这样的事情已经有十几年了），但Lex/Flex是标准的Unix构造函数。

FSM有一个状态表和一个接受状态列表。它从开始状态开始，并对输入进行逐个字符的扫描。每个状态都有一个输入字符。条目可以是进入另一个状态，或者是因为字符串不在列表中而中止。如果FSM在不中止的情况下到达输入字符串的末尾，它会检查它所处的最终状态，它是一个接受状态（在这种情况下，您已经匹配了字符串），或者它不是（在这种情况下，您避难“T）。

任何一本书上的编译器应该有更多的细节，或者你可以毫无疑问在网络上找到更多信息。

来源

2009-01-26 14:28:24

我想出了一台状态机在这里会做得更好，但我不太愿意为这种额外的表现增加更多的复杂性。 – Huppie 2009-01-26 14:34:52

这实际上是Patricia Trie的搜索过程的工作原理。但是实施起来更直接简单。 – user21714 2009-01-26 14:50:10

我不知道哪一种散列函数的MS用来蜇伤，但也许你能想出更简单的东西（=更快），在你的特殊情况工作。该容器应该允许您使用自定义哈希类。

如果它的容器的实现问题，你也可以尝试，如果提升std::tr1::unordered_set给出了更好的结果。

来源

2009-01-26 14:41:33 sth

如果没有标准容器满足您的需求，您可以试试PATRICIA Trie。

最坏情况查找被你正在寻找了字符串的长度为界。此外，字符串共享通用前缀，因此它在内存上非常容易。因此，如果您有很多相对较短的字符串，这可能是有益的。

Check it out here.

注：PATRICIA =实用算法检索字母数字

来源

2009-01-26 14:47:57 user21714

编码信息。如果它是一个固定列表，列表排序，做一个二进制搜索？我无法想象，现代CPU上只有一百个左右的字符串，你会发现算法之间有明显的区别，除非你的应用程序除了在100％的时间内搜索所有的列表之外什么都不做。

来源

2009-01-26 14:50:26 kirkus

如果琴弦组的检查数量在数百就像你说的，这是做I/O（加载一个文件，我认为来自于磁盘，常见）时，那么我会说：在寻找更多奇特/复杂的解决方案之前，先了解一下你的所得。

当然，也可能是你的“文件”包含数亿这些字符串，在这种情况下，我想它真正开始需要时间......没有更详细，很难肯定地说。

我说的归结为“考虑用例和典型场景，之前（过度）优化”，我猜这只是一个关于邪恶根源的旧事物的专业化:) :)

来源

2009-01-26 14:51:28 unwind

散列表是一个很好的解决方案，通过使用预先存在的实现，您可能会获得良好的性能。尽管我相信这个选择被称为“索引”。

保留一些指针到方便的位置。例如如果它使用字母进行排序，请保留一个指向开始aa，ab，ac ... ba，bc，bd的所有内容...这是几百个指针，但意味着您可以跳到列表的一部分在继续之前非常接近结果。例如如果一个条目是“afunctionname”，那么你可以在af和ag指针之间进行二进制搜索，比搜索整个指令要快得多......如果你总共有一百万条记录，你可能只需要二进制搜索一个列表几千。

我重新发明了这个特定的轮子，但可能已经有很多实现，这将为您节省执行头痛，并且可能比我在此处可以粘贴的任何代码都快。 :)

来源

2009-01-26 14:51:58 jheriko

100个独特的字符串？如果这不是频繁调用，并且列表不会动态改变，我可能会使用一个直线型的const char数组来进行线性搜索。除非你经常搜索它，否则小的东西不值得额外的代码。事情是这样的：

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;

对于小，我觉得有什么更复杂的实施和维护成本清单可能会超过其运行时间成本，你不是真的要得到比这个场地费用便宜。为了获得更多的速度，你可以做一个哈希表第一个字符 - >列表索引来设置i的初始值;

对于这个小的列表，你可能不会得到更快。

来源

2009-01-26 17:57:26

std :: vector有什么问题？加载它，先排序（v.begin（），v.end（）），然后使用lower_bound（）来查看字符串是否在向量中。在已排序的随机访问迭代器中lower_bound保证为O（log2 N）。如果值是固定的，我不明白需要散列。向量占用的内存空间比散列少，分配也少。

来源

2009-01-26 18:08:31 jmucchiello

您正在使用二进制搜索，即O（log（n））。你应该看插值搜索，这不是最好的“最坏的情况”，但它的平均情况是更好的：O（log（log（n））。

来源

2009-06-06 20:29:38

我削减&粘贴从上面的二进制搜索代码..有与原来的二分查找代码中的问题，如不能在100项的列表中找到第二个项目

行：

high = mid - 1;

应该是：

high = mid;

来源

2011-05-30 14:47:34

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

回答

相关问题