如何将我的字符串搜索算法与当前基准测试进行严格比较。目前击败/等于 Boyer-Moore ~在我的测试中的一半

How to rigorously compare my String-Search algorithm against current benchmarks. Currently beating/equaling Boyer-Moore ~half the times in my test

提问人:Menachem Kalmenson 提问时间:6/20/2023 更新时间:6/20/2023 访问量:53

问:

我编写的字符串搜索算法在我自己的测试中表现得非常好,但我想更严格地测试它,以了解它的客观表现如何。有谁知道我可以用来运行此类测试的资源?

我创建的测试将 5000 个随机单词放在一起,然后随机选择其中一个单词作为“模式”。当我运行测试 1000 次时(每次使用一组新的 5000 个随机单词和一个新的“模式”),我的算法(在速度上)击败 Boyer-Moore 大约 1/3 倍,击败/等于 Boyer-Moore 大约 3/5 倍。

当我计算所有 1000 个测试的平均时间时,有时我的算法有一个更好的平均值,但更多时候 Boyer-Moore 有一个更好的平均值,尽管通常不会太多 (<0.0005ms)。

下面是 n=1000 的散点图的比较效果,黑线比较了任何特定集合的两种算法(蓝色标记是我的算法时间,橙色标记是 Boyer-Moore 的时间)。红线比较了这 n 个测试的两个平均值。平均值写在标题中。

enter image description here

因此,如果您知道任何可以帮助我测试的资源,请发送我的方式。

谢谢。

python 算法 性能 比较 string-search

评论

0赞 sahasrara62 6/20/2023
在峰值点进行测试并将限制从 5k 增加到 500k(比方说),也增加字长,然后测试所有情况
0赞 Matt Timmermans 6/21/2023
比较字符串搜索算法并不容易。即使是最简单的搜索在随机数据上也能很好地执行。比较最坏情况的性能很有用,但不同的算法有不同的最坏情况。您可以尝试针对“平均”或“现实”情况进行测试,但这也不容易,因为字符串搜索算法的实际用途非常多样化。
2赞 Matt Timmermans 6/21/2023
此外,由于可比算法的复杂性是相同的,因此您还将比较实现的质量。使用高质量的实现很重要,你真的无法在 python 中生成高质量的实现。根据 python 的内置字符串搜索测试您的算法,看看原因。内置功能将快很多倍。

答: 暂无答案