我的C程序有很多strstr函数调用.标准库strstr已经很快但在我的情况下搜索字符串总是长度为5个字符.我用特殊版本替换它以获得一些速度:
int strstr5(const char *cs, const char *ct)
{
while (cs[4]) {
if (cs[0] == ct[0] && cs[1] == ct[1] && cs[2] == ct[2] && cs[3] == ct[3] && cs[4] == ct[4])
return 1;
cs++;
}
return 0;
}
该函数返回一个整数,因为它足以知道ct中是否出现ct.在这种特殊情况下,我的功能比标准的strstr简单快捷,但我很想知道是否有人可以应用一些性能改进.即使是小改进也是受欢迎的
摘要:
编辑:感谢您的所有答案和评论.我必须研究和测试想法,看看什么是最好的.我将从MAK关于后缀trie的想法开始.
MAK*_*MAK 14
有几种快速字符串搜索算法.试着看看Boyer-Moore(正如Greg Hewgill所建议的那样),Rabin-Karp和KMP算法.
如果需要在同一大块文本中搜索许多小图案,还可以尝试实现后缀树或后缀数组.但这些是恕我直言,有点难以理解和正确实施.
但要注意,这些技术非常快,但如果涉及的字符串非常大,那么只会给你一个明显的加速.对于长度小于1000个字符的字符串,您可能看不到明显的加速.
编辑:
如果您在相同的文字一遍遍重新搜索(即价值cs始终/经常同在调用),您将使用一个后缀特里(基本上是得到了大的提速线索后缀).由于您的文本小到100或200个字符,您可以使用更简单的O(n ^ 2)方法来构建trie,然后对其进行多次快速搜索.每次搜索只需要5次比较,而不是通常的5*200.
编辑2:
正如caf的评论所提到的,C的strstr算法依赖于实现.glibc使用线性时间算法,在实践中应该或多或少与我提到的任何方法一样快.虽然OP的方法渐近变慢(O(N*m)而不是O(n)),但它更快可能是因为n和m(模式和文本的长度)都非常小而且它不必在glibc版本中进行任何长时间的预处理.
dra*_*ard 12
减少比较次数将提高搜索速度.保持字符串的运行int并将其与搜索项的固定int进行比较.如果匹配则比较最后一个字符.
uint32_t term = ct[0] << 24 | ct[1] << 16 | ct[2] << 8 | ct[3];
uint32_t walk = cs[0] << 24 | cs[1] << 16 | cs[2] << 8 | cs[3];
int i = 0;
do {
if ( term == walk && ct[4] == cs[4] ) { return i; } // or return cs or 1
walk = ( walk << 8 ) | cs[4];
cs += 1;
i += 1;
} while ( cs[4] ); // assumes original cs was longer than ct
// return failure
添加对短cs的检查.
编辑:
添加了评论中的修复程序.谢谢.
这可以很容易地用于使用64位值.您可以将cs [4]和ct [4]存储在局部变量中,而不是假设编译器会为您执行此操作.您可以在循环之前向cs和ct添加4,并在循环中使用cs [0]和ct [0].
strstr的界面强加了一些可以打败的约束.它采用以null结尾的字符串,任何首先对其目标进行"strlen"的竞争对手都将失败.它不需要"状态"参数,因此设置成本不能在(例如)相同目标或模式的许多调用中分摊.预计可以处理各种输入,包括非常短的目标/模式和病理数据(考虑在"ABABABABAB ... C"字符串中搜索"ABABAC").libc现在也依赖于平台.在x86-64世界中,SSE2已有七年历史了,使用SSE2的libc strlen和strchr比朴素算法快6-8倍.在支持SSE4.2的Intel平台上,strstr使用PCMPESTRI指令.但你也可以击败它.
Boyer-Moore(以及Turbo BM和Backward Oracle Matching等人)的设置时间几乎让他们无法运行,甚至没有计算出null终止字符串问题.Horspool是受限制的BM,在实践中运作良好,但不能很好地处理边缘情况.我在该领域发现的最好的是BNDM("向后非确定性定向 - 非循环 - 词 - 图形匹配"),其实现小于其名称:-)
以下是一些可能感兴趣的代码片段. 智能SSE2击败天真的SSE4.2,并处理空终止问题. BNDM实施显示了一种保持设置成本的方法.如果您熟悉Horspool,您会注意到相似性,除了BNDM使用位掩码而不是跳过偏移.我即将发布如何为Horspool和BNDM等后缀算法(有效地)解决null-terminator问题.
所有良好解决方案的共同属性是针对不同的参数长度分成不同的算法.一个例子是Sanmayce的"Railgun"功能.