代码之家  ›  专栏  ›  技术社区  ›  R.. GitHub STOP HELPING ICE

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

  •  5
  • R.. GitHub STOP HELPING ICE  · 技术社区  · 15 年前

    我正在尝试评估不同的子字符串搜索(ala strstr)算法和实现,并寻找一些精心设计的针线和干草堆字符串,这些字符串将捕获最坏情况下的性能和可能出现的错误。我想我可以自己解决这些问题,但我认为必须有人在某个地方收集大量的测试用例。。。

    4 回复  |  直到 15 年前
        1
  •  3
  •   R.. GitHub STOP HELPING ICE    15 年前

    我的一些想法和部分答案:

    暴力算法的最坏情况:

    a^(n+1) b 在里面 (a^n b)^m

    例如 aaab 在里面 aabaabaabaabaabaabaab

    SMOA的最坏情况:

    差不多 yxyxyxxyxyxyxx 在里面 (yxyxyxxyxyxyxy)^n .需要进一步完善。我试图确保每次前进的长度只有部分匹配长度的一半,并且最大后缀计算需要最大数量的回溯。我很确定我的思路是正确的,因为这种情况是我迄今为止发现的唯一实现SMOA的方法(它是渐进的) 6n+5 )跑得比glibc的双向(渐进)慢 2n-m 但有适度痛苦的预处理开销)。

    最糟糕的情况是基于哈希的滚动:

    任何字节序列都会导致散列与指针的散列发生冲突。对于任何合理快速的散列和给定的指针,应该很容易构造一个haystack,其散列在每个点上都与指针的散列冲突。然而,似乎很难同时创建长部分匹配,这是获得最坏情况行为的唯一方法。当然,对于最坏的情况,指针必须具有一定的周期性,并且可以通过调整最终字符来模拟散列。

    双向最坏情况:

    似乎是非常短的针与非平凡的MS分解-类似的东西 bac -干草堆在针的右半部分包含重复的假阳性,比如 dacdacdacdacdacdacdac .这个算法的唯一方法可能是缓慢的(除了glibc作者执行得很差的情况…)是通过使外部循环多次迭代并重复产生该开销(并且使设置开销显著)。

    其他算法:

    我真的只对 O(1) 在空间和低预处理开销,所以我没有看到他们最坏的情况这么多。至少是Boyer Moore(未经修改) O(n) )在最坏的情况下 O(nm) .

        2
  •  0
  •   tathagata    15 年前

    不会直接回答你的问题,但你可能会发现书中的算法——关于字符串、树和序列的算法:计算机科学和计算生物学——很有趣(有许多关于子字符串搜索的新算法)。此外,它也是特殊和复杂案件的良好来源。

        3
  •  0
  •   vlabrecque    15 年前

    这个过程可能会给出有趣的统计数据,尽管我现在没有时间测试:

    在字符串长度上随机化, 然后随机选择该长度的字符串内容, 然后随机化子字符串的偏移量/长度(可能是字符串中没有的内容), 然后随机敲击子串(可能根本没有), 重复

        4
  •  0
  •   Mau    15 年前

    您可以通过以下方式递归生成容器字符串(相应地,包含测试值):

    从空字符串开始,通过将字母表中的一个字符添加到左侧或右侧(两者都添加),生成集合中当前字符串的扩充所给出的所有字符串。

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

    测试两个字母表中包含的字符串。一个是组成容器字符串的字符串,另一个是它的补码。