我开始认真研究算法和数据结构,并有兴趣学习如何比较我可以实现A&DT的不同方式的性能。
对于简单的测试,我可以获得运行之前/之后的时间,运行该事物10 ^ 5次,并平均运行时间。我可以按大小参数化输入,或者对随机输入进行采样,并获得运行时间与输入大小的列表。我可以将其输出为csv文件,并将其输入到pandas中。
我不确定是否有任何警告。我也不确定如何测量空间复杂度。
我正在学习用C ++编程。有没有人性化的工具来实现我的目标?
基准代码并不容易。我发现最有用的是Google benchmark library.即使你不打算使用它,也可以阅读一些例子。它有很多可能性来参数化测试,将结果输出到文件,甚至返回算法的Big O符号复杂性(仅举几例)。如果您熟悉Google测试框架,我建议您使用它。它还可以使编译器优化得以管理,因此您可以确保您的代码未被优化。
关于CppCon 2015: Chandler Carruth "Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My!"上的代码基准测试,也有很好的讨论。您可以犯的错误有许多见解(它也使用谷歌基准测试)
它是特定于操作系统和编译器(因此特定于实现)。你可以使用profiling工具,你可以使用计时工具等。
在Linux上,请参阅time(1),time(7),perf(1),gprof(1),pmap(1),mallinfo(3)和proc(5)以及Invoking GCC。
另见this。在实践中,确保您的跑步持续足够长的时间(例如,在一个过程中至少持续一秒钟)。
请注意,optimizing compilers可以彻底改变您的计划。参见CppCon 2017:Matt Godbolt谈论“What Has My Compiler Done for Me Lately? Unbolting the Compiler's Lid”
从架构的角度来讲,您还可以使用Intel Pin,perf tool等不同的架构工具对C ++代码进行基准测试。您可以使用这些工具来研究代码的体系结构依赖性。例如,您可以编译代码以进行不同级别的优化,并检查IPC / CPI,缓存访问和加载存储访问。您甚至可以检查您的代码是否因库函数而受到性能影响。这些工具功能强大,可以为您提供对代码的深入洞察。
您还可以尝试反汇编代码并研究代码在大多数情况下花费的时间并尝试优化代码。您可以查看不同的技术,以确保频繁访问的数据保留在缓存中,从而确保高命中率。
比如说,您意识到您的代码主要由循环控制,您可以针对不同的循环边界运行代码,并在2种情况下检查指标。例如,将循环绑定设置为100,000并找到所需的性能指标“X”,然后将循环绑定设置为200,000并找到性能指标“Y”。现在,计算Y-X。这将使您更好地了解循环的行为,因为通过减去两个指标,您已经有效地删除了代码的静态效果。
比如说,您运行代码10次并使用不同的用户输入大小。您可以找到每个用户输入大小的运行时间,然后按升序对此新指标进行排序,删除第一个和最后一个值(删除异常值),然后取平均值。最后,找到方差系数以了解运行时间的行为方式。
另一方面,我们最终会轻率地使用术语“平均值”或“算术平均值”。查看您计划平均的指标,并查看每种情况下的谐波平均值,算术平均值和几何平均值。例如,找到费率的算术平均值将给出错误的答案。简单地找到两个在时间上不均匀发生的事件的算术平均值会产生不正确的结果。相反,使用加权算术手段。