在排序数组中，为什么较大的搜索值的实际运行时间比较低的搜索值要更小？

Question

我在一个包含所有唯一元素的范围为[1, 10000]、按递增顺序排列的数组上执行了线性搜索，并将运行时间和搜索值绘制成了如下的图表：

仔细分析缩放后的图表，如下所示：

我发现对于某些较大的搜索值，运行时间比较小，而对于一些较小的搜索值，则相反。

我猜测这种现象与CPU使用主存和高速缓存处理数据有关，但没有一个明确的可量化的理由来解释这个问题。

任何提示将不胜感激。

PS: 代码是用C++编写的，在托管在Google Cloud上的虚拟机上运行。运行时间是使用C++ Chrono库测量的。

- Deepak Tatyaji Ahire

---

你的计时器精度是多少？简单来说，离散化是计时器分辨率的直接结果（以及基于环境变量如系统负载预期的运行时间微小扰动）。 - ldog

我在C++中使用Chrono来测量运行时间 @ldog - Deepak Tatyaji Ahire

Answer 1

CPU缓存大小取决于CPU型号，有几个缓存级别，因此您的实验应考虑所有这些因素。L1缓存通常为8 KiB，约为10000数组的4倍小。但我认为这不是缓存未命中。L2延迟大约为100ns，比最低和第二行之间的差异（约为5微秒）要小得多。我想这（第二行云）是由上下文切换导致的。任务越长，上下文切换发生的可能性就越大。这就是为什么右侧的云更厚的原因。

现在看放大的图。由于Linux不是实时操作系统，所以其时间测量不太可靠。我IRC它的最小报告单位是微秒。现在，如果某个任务恰好需要15.45微秒，则其结束时间取决于它何时开始。如果任务在精确的零点开始，报告的时间将是15微秒。如果它在内部时钟处于0.1微秒时开始，则会得到16微秒。您在图表上看到的是模拟直线与离散值轴的线性逼近。因此，您获得的任务持续时间不是实际任务持续时间，而是真实值加上微秒级的任务开始时间（其均匀分布约为U[0,1]），并将其舍入为最接近的整数值。

- igrinis