logo标签列表

基准测试和压力测试子字符串搜索算法的好测试用例是什么？

calgorithmstringbenchmarking
6

我正在尝试评估不同的子字符串搜索算法和实现，并寻找一些经过精心制作的针和干草堆字符串，以捕获最坏情况下的性能和可能的边角案例错误。我想我可以自己解决这些问题，但我认为某个人必须有一个好的测试用例集合坐在某个地方...

2
你的最终目标是什么？只是想学习算法吗？还是你有一个包含不寻常的针和草堆的应用程序？ - Cascabel
短期来看，只是为了学习算法。长期来看，我有一个面向非常小的C库实现，具有高于平均水平的性能，使用了naive方法来查找strstr，并且我想考虑用O(n)时间/O(1)空间算法之一来替换它。SMOA看起来很有前途，但我想看看比较上限6n+5中的常数6在实践中是否有问题（我的初步测试显示它在远程合理数据上要低得多，并且在性能上与glibc相当，而不需要所有针对短/长针的特殊情况）。 - R.. GitHub STOP HELPING ICE
4个回答
5

以下是一些想法和部分答案：

暴力算法的最坏情况：

a^(n+1) b 在 (a^n b)^m 中

例如，在 aabaabaabaabaabaabaab 中的 aaab

SMOA 的最坏情况：

类似于 yxyxyxxyxyxyxx 在 (yxyxyxxyxyxyxy)^n 中。需要进一步完善。我试图确保每次前进只有部分匹配长度的一半，并且最大后缀计算需要最大量的回溯。我相当确定我走在正确的轨道上，因为这种类型的情况是我迄今发现的唯一使我的 SMOA 实现（渐近复杂度为 6n+5）比 glibc 的 Two-Way 运行得更慢的方法（它的渐近复杂度为 2n-m，但具有适度的痛苦预处理开销）。

基于滚动哈希的任何算法的最坏情况：

无论什么字节序列都会导致与针的哈希值发生碰撞的哈希值。对于任何相对较快的哈希和给定的针，应该很容易构造一个干草堆，其哈希与针的哈希在每个点上发生碰撞。然而，似乎难以同时创建长的部分匹配，这是获取最坏情况行为的唯一方法。自然地，对于最坏情况行为，针必须具有某种周期性，并且可以通过仅调整最终字符来模拟哈希。

Two-Way 的最坏情况：

似乎是非常短的针，具有非平凡的 MS 分解 - 例如 bac - 其中干草堆包含右半部分组件中重复的误报 - 例如 dacdacdacdacdacdacdac。这种算法变慢的唯一方法（除了 glibc 作者实现不好之外...）是使外部循环多次迭代并反复发生那种开销（并使设置开销显着）。

其他算法：

我只对空间复杂度为 O(1) 且预处理开销低的算法感兴趣，因此我没有过多考虑它们的最坏情况。至少 Boyer-Moore（没有修改使其成为 O(n) 的修饰）具有一个非平凡的最坏情况，其中它变为 O(nm)。

0

虽然没有直接回答你的问题，但你可能会发现这本书《字符串、树和序列算法：计算机科学与计算生物学》中的算法很有趣（包含许多关于子字符串搜索的新颖算法）。此外，它也是一个特殊和复杂情况的良好信息来源。

谢谢，但我真正需要的是测试/基准测试的想法。我在这里有一个算法的不错参考： http://www-igm.univ-mlv.fr/~lecroq/string/index.html 双向和SMOA似乎是唯一“快速”（在大O表示法中）的算法，适用于不能有失败情况的代码，因为其余算法在空间上是非常量的，并且在内存压力条件下可能会失败。然而，朴素实现也非常有趣，看起来可能是极大的针尺寸的最优解。对于我尝试过的短到中等长度的字符串，它大约比glibc的Two Way快两倍。 - R.. GitHub STOP HELPING ICE
谢谢提供链接！这是一个非常好的精确字符串匹配算法汇编。 - tathagata
0
一个可能会产生有趣统计数据的过程，虽然我现在没有时间测试：
随机字符串长度， 然后随机该长度的字符串内容， 然后随机子字符串的偏移量/长度（可能不在字符串中）， 然后随机地破坏子字符串（可能根本不破坏）， 重复以上步骤。
0

您可以通过以下方式递归生成容器字符串（或包含的测试值）：

从空字符串开始，通过将字母表中的字符添加到左侧或右侧（或两者都添加）来生成集合中当前字符串的增量字符串。

生成容器字符串的字母表由您选择。

您可以测试包含的字符串的2个字母表。一个是组成容器字符串的字母表，另一个是它的补集。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接