字符串搜索算法

Question

我有一个关于基准测试字符串匹配算法的项目，我想知道是否每个算法都有一个标准，这样我就可以用我的实验获得公平的结果。我打算使用java的system.nanotime来获取每个算法的运行时间。非常感谢对我的问题的任何评论或反应。谢谢！

Answer 1

我不完全确定你在问什么。不过，我猜你正在问如何得到最现实的结果。你需要运行你的算法数百次，甚至数千次迭代才能获得平均值。关闭你的语言可能做的任何缓存也是非常重要的，并且不要重用对象，除非它是你的算法的一部分。

Answer 2

我不完全确定你在问什么。然而，对于你所问的问题的另一种解释可以通过试图找出给定算法如何增加问题的大小来解决。使用原始时间比较给定字符串大小的算法不一定能够进行准确的比较。相反，您可以尝试使用不同字符串大小的每种算法，并查看算法在字符串大小变化时的行为。

马克的建议也不错。因此，您正在对许多不同的字符串长度进行重复试验，以获得一个算法如何工作的图片，然后针对下一个算法重复该操作。

Answer 3

再次，目前还不清楚你问什么，但这里除了又一想什么托尼和马克说：

要非常小心，只测试“真实”输入或只是“随机”的输入。一些算法被调整为在典型输入（在英文文本中搜索单词）上做得很好，而另一些算法则被调整用于在病态严重病例中良好工作。您需要各种不同类型和大小的可能输入的大量组合才能做出真正的好的基准。