performance - 如何比较两个数据结构的运行时间

Question

我想比较两个整数搜索树（AVL树和RedBlack树）的性能那么，我应该如何设计/设计测试来实现这一点呢？例如，让我们考虑一下insert操作，我应该遵循哪些步骤来声明在rb情况下这个操作平均更快？我应该只插入一个元素（假设树是预先填充的）还是插入序列的时间？另外，我应该考虑什么来正确地测量CPU时间？
提前谢谢。

Answer 1

这是一个非常广泛的问题，因此，我不认为你应该希望有人能在这里，给你一个关于如何衡量绩效的最后正确答案。有人说…
首先，您应该开发一套测试。存在两种流行的技术：监视应用程序所做的实际操作序列（因此，找到一些使用AVL或RB树的开放源代码应用程序，并添加一些代码来打印它执行的操作序列），或者以分析（或综合）的方式创建这样的操作流，以针对任意数量的操作。例数（平均用法、特殊类型的异常用法或其他异常用法、随机用法等）。你测试的痕迹越多越好。
一旦你有你的跟踪集要测试，你需要开发一个驱动程序来做评估。驱动程序应该很简单，对于avl和rb树都是一样的（我认为在这种情况下，这不应该是个问题；两者都向用户提供相同的接口，只是在内部实现细节方面有所不同）。驱动程序应该能够有效地再现记录在跟踪集中的使用情况，并使跟踪操作在数据结构上执行我喜欢做的一件事是包含第三个什么都不做的“虚拟”候选；这样，我就可以看到跟踪处理对整体性能的影响有多大。
每个跟踪应该执行很多次您可以将其形式化（以将统计不确定性降低到已知范围内），但经验法则是，错误的顺序将根据1/sqrt（n）缩小，其中n是试验次数。换言之，通过运行每个跟踪10000次而不是100次，您将得到平均小10倍的错误。记录所有值；要查找的是平均值、中值、模式等。对于每次运行，请尝试保持系统条件不变；没有其他程序正在运行等。为了帮助消除由于外部因素更改而产生的虚假结果，可以剔除底部和顶部10%的异常值……
现在，只需比较数据集。也许你最关心的是追踪的平均时间？也许是最坏的也许你真正关心的是一致性；标准差是大还是小？您应该有足够的数据来比较在两个测试结构上执行的给定跟踪的结果；对于不同的跟踪，查看不同的图可能更有意义（例如，如果您创建了一个对RB树来说应该是最坏情况的合成基准，您可能会问RB树和AVL树的性能有多差然而，对于另一个表示avl树的最佳情况的跟踪，您可能并不关心这个问题，等等。）
CPU上的计时本身就是一个挑战。您需要确保计时器的分辨率足以测量事件clock（）和gettimeofday（）函数以及其他函数是记录事件时间的常用选择如果跟踪完成得太快，则可以获得多个测试的聚合时间（因此，如果计时器支持微秒计时，并且跟踪在10微秒内完成，则可以测量跟踪的100次执行，而不是1次执行，并获取10毫秒的时间值，这应该是准确的）。
另一个潜在的陷阱是每次都提供相同的执行环境。在两次跟踪运行之间，至少可以考虑确保从干净缓存开始的技术。要么这样，要么不计时第一次执行，要么理解在消除异常值时可能会剔除此结果。重置缓存（通过操作某个大型数组的每个元素，例如在执行跟踪之间）可能更安全，因为代码A可能会从缓存中包含某些值中获益，而代码B可能会受到影响。
以下是在进行自己的绩效评估时可能会考虑的一些事项其他工具（例如papi和其他分析器）可以测量某些事件（缓存命中/未命中、指令等），而且这些信息可以进行比简单比较挂钟运行时间更丰富的比较。