13

我的 C 程序有很多 strstr 函数调用。标准库 strstr 已经很快，但在我的情况下，搜索字符串的长度始终为 5 个字符。我用一个特殊版本替换它以获得一些速度：

int strstr5(const char *cs, const char *ct)
{
    而（cs [4]）{

        if (cs[0] == ct[0] && cs[1] == ct[1] && cs[2] == ct[2] && cs[3] == ct[3] && cs[4] == ct[4])
            返回 1；

        c++;
    }

    返回0；
}

该函数返回一个整数，因为它足以知道 ct 是否出现在 cs 中。在这种特殊情况下，我的函数比标准 strstr 简单且更快，但我很想知道是否有人可以应用一些性能改进。即使是小的改进也是受欢迎的。

概括：

  • cs 的长度 >=10，否则它可能会有所不同。长度之前是已知的（未在我的函数中使用）。cs 的长度通常在 100 到 200 之间。
  • ct 的长度为 5
  • 字符串的内容可以是任何东西

编辑：感谢您的所有回答和评论。我必须研究和测试想法，看看什么最有效。我将从 MAK 关于后缀 trie 的想法开始。

4

5 回答 5

15

有几种快速字符串搜索算法。尝试查看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 版本中进行任何长时间的预处理。

于 2010-06-27T19:34:12.330 回答
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] 存储在局部变量中，而不是假设编译器会为您执行此操作。您可以在循环之前将 4 添加到 cs 和 ct 并在循环中使用 cs[0] 和 ct[0] 。

于 2010-06-27T19:46:50.563 回答
5

strstr 的接口施加了一些可以克服的约束。它采用以空字符结尾的字符串，任何首先对其目标执行“strlen”的竞争者都将失败。它不需要“状态”参数，因此设置成本不能在具有（例如）相同目标或模式的许多调用中分摊。预计它可以处理广泛的输入，包括非常短的目标/模式和病理数据（考虑在“ABABABAB...C”字符串中搜索“ABABAC”）。libc 现在也依赖于平台。在 x86-64 世界中，SSE2 已经七岁了，libc 使用 SSE2 的 strlen 和 strchr 比 naive 算法快 6-8 倍。在支持 SSE4.2 的 Intel 平台上，strstr 使用 PCMPESTRI 指令。但你也可以打败它。

Boyer-Moore （以及 Turbo BM 和 Backward Oracle Matching 等人）的设置时间几乎使它们无法运行，甚至还没有计算空终止字符串问题。Horspool 是一种受限制的 BM，在实践中运行良好，但在边缘情况下表现不佳。我在该领域发现的最好的是 BNDM（“反向非确定性有向无环词图匹配”），它的实现比它的名字小:-)

以下是一些可能感兴趣的代码片段。 智能 SSE2 击败了幼稚的 SSE4.2，并处理了空终止问题。 BNDM 实施显示了一种保持设置成本的方法。如果您熟悉 Horspool，您会注意到相似之处，只是 BNDM 使用位掩码而不是跳过偏移量。我即将发布如何（有效地）解决 Horspool 和 BNDM 等后缀算法的空终止符问题。

所有好的解决方案的一个共同属性是针对不同的参数长度分成不同的算法。Sanmayce 的“Railgun”功能就是一个例子。

于 2012-02-05T18:06:33.147 回答
3

如果少于 4 个字符，您的代码可能会cs超出其分配范围。cs

字符串搜索的一个常见优化是使用Boyer-Moore算法，您从what would becs的末尾ct开始查找。有关算法的完整描述，请参见链接页面。

于 2010-06-27T19:14:47.223 回答
3

您不会在现代 x86 计算机上击败一个好的实现。

新的 Intel 处理器有一条指令，该指令占用您正在检查的字符串的 16 个字节，最多 16 个字节的搜索字符串，并在单个指令中返回搜索字符串可能所在的第一个字节位置（或者如果没有）。例如，如果您在字符串“abcdefghijklmnHexyz”中搜索“Hello”，第一条指令将告诉您字符串“Hello”可能从偏移量 14 开始（因为读取 16 个字节，处理器具有字节 H、e、未知这可能是“Hello”的位置。从偏移量 14 开始的下一条指令然后告诉该字符串不存在。是的，它知道尾随零字节。

这是两个指令来发现 19 个字符的字符串中不存在 5 个字符的字符串。尝试使用任何特殊情况代码击败它。（显然这是专门为 strstr、strcmp 和类似指令构建的）。

于 2015-12-02T17:25:52.517 回答