测量二分搜索性能时的奇怪计时

Question

好吧，所以这里发生的事情让我困惑了两天。基本上，作为一项活动，我正在测量某些算法在最差、平均和最佳情况下执行所需的时间。到目前为止，我测试的所有结果都得到了预期的结果，除了二分搜索：线性搜索时间线性增加，冒泡排序在 N^2 之后增加，等等。平均值也符合预期，所以在线性搜索中这几乎是最坏情况的一半，等等

然后是二分查找。正如预期的那样，平均情况和最坏情况都遵循 log(N)，但最坏情况是曲线小于平均情况（??????），我不明白为什么。这是用于检索数据的代码：

    for(int i = 0; i<sample_size;i++){
        
        int search_target;
        switch (mode)
        {
            case BEST_CASE:
                search_target = *(int*)vector_get(vec, (vector_size(vec)-1)/2);
                break;
            case AVERAGE_CASE:
                search_target = *(int*)vector_get(vec, rand() % element_amt); //random index
                break;
            case WORST_CASE:
                search_target = *(int*)vector_get(vec, vector_size(vec)-1); //Biggest value
                break;
        }
        
        double start_time = _get_timestamp(); 
        int itt = vector_binary_search(vec, &search_target, _diff_number);
        double time_taken = _get_timestamp() - start_time;

        total_time += time_taken;  
        total_itt += itt;
    }

所以基本上对于不同大小的向量，我会使用样本大小运行这个函数（以消除一点噪音），然后绘制图表（这是正确完成的，我没有将平均值绘制为更差或类似的东西） ，我检查了多次）。此外，vec 是一个向量，其值从 0 到 size-1。

这就是我多次尝试并以多种不同方式得到的结果：

绿色是一般情况，紫色是最差情况。 （x=向量大小，y=花费的时间）

同样的事情（x = vec 大小，y = 进行的迭代）

我不知道为什么会发生这种情况。

所以，这是完整的代码，如果有人想尝试一下： https://github.com/rsadr0pyz/weird

Answer 1

您是否遵循良好的基准实践？你应该：

1. 运行预热阶段（一遍又一遍地重复该操作几分钟）。这会预热你的缓存
2. 多次运行测试并取平均值。有些测试很吵
3. 分析您的结果，看看哪些函数花费的时间最长。 pyspy 可以为 python 工作。结果可能会令人惊讶。

现代 CPU 执行无序和推测执行，因此算法时间并不总是转化为现实。编译器有时也可以找出循环并优化它们（尽管这是Python）。如果您的代码确实有分支，那么预取器可能会遇到困难。否则你的 CPU 可能会提前执行多条指令。