c - 比较两个匹配字符串算法 - 实用方法

Question

我编写了两种不同的算法来解决字符串匹配的一些特殊情况（在 C 中实现）。我知道这个算法的理论 O 是相等的，但我认为在实践中，一个比 oder 更好。我的问题是，有人可以向我推荐一些论文或一些阅读材料，其中展示了如何将算法与实用方法进行比较？我有几个测试集，我对测量执行时间和内存大小感兴趣。我需要尽可能独立于操作系统和其他可能同时运行的程序来获取这些值。

谢谢！！！

Answer 1

您可以通过生成汇编代码来比较您的算法并进行比较。

gcc -S mycode.c您可以使用命令生成汇编代码

Answer 2

我发现“查看代码”是一个好的开始。如果一个使用更多变量并且比另一个更复杂，它可能会更慢。

但是，当然有一些巧妙的技巧可以使更复杂的函数实际上运行得更快（例如，一次读取 8 个字节的代码 - 但当然，一旦你发现不同之处，代码就会更复杂 - 对于长字符串大体相似，有很大的胜利'）。

因此，最后，没有什么可以替代实际运行代码、使用时钟周期计时（例如 x86 处理器上的 RDTSC 指令）或运行一个大循环来多次执行代码以提供合理长度的运行时间。

如果您的代码不应该在单个嵌入式目标上运行，您可能希望在一组不同的硬件上运行代码，以确定在处理器 A 上更快的代码在 B、C 和 D 类型处理器上是否也更快. 通常这确实有效，但有时您会发现特定处理器型号对于某些操作更快，而另一种处理器型号对于另一种操作更快（例如基于缓存大小等）。

在字符串操作的情况下，尝试使用不同大小的输入、不同的差异点（例如，长字符串，但“早”不同，与“晚”不同的长字符串）也是非常重要的。有时，不同的方法会对短/长字符串或早/晚差异点（当然还有长或短的“相等”字符串）显示不同的结果。

Answer 3

In order to complete all comments, I found a book called "A guide to experimental algorithmics" by Catherine C. Mcgeoch Amazon and a profesor recommend me a practical paper pdf.