c++ - 二进制搜索真的是在 0 时钟 CPU 时间内执行的吗？

Question

我编写了这个程序，它将从文件中读取一些数字，插入到数组中，执行线性搜索，对它们进行排序，然后执行二进制搜索(排序后)。

我使用时钟函数来测量执行上述每项任务需要多长时间。

文件很大，大约有 500 万个数字。插入需要时间并由时钟显示。 (从文件中读取并不是最好的方式)，线性搜索和排序也是如此。但是，二进制搜索需要 0 秒才能执行。显然这是不对的。

我很好奇为什么它以毫秒为单位的时间和时钟滴答数都显示为零？

我在 Windows 8.1、ASUS、Intel i-5、8GB RAM、2.4 GHz 处理器中运行。

这是输出:

$ make
g++  -c -Wall -g  search.cpp
g++  -o search search.o

$ ./search <input-5m.in
Time to insert: 26171
Time to Linear Search: 16
Yes!
Time to Sort: 1390
Time to Binary Search in milliseconds: 0
Time to Binary Search in clock ticks: 0
Time to Binary Search printed with "printf()": 0.000000
Yes!

这是代码。

using namespace std;
#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdio>
#include <iomanip>      // std::setprecision


clock_t clock(void);
...
...
...

int main(int argc, char** argv)
{
...
...
...

   clock_t startLinear, finishLinear;
   double elapsedTimeLinear =0;

    startLinear = clock();
    bool foundLinear = linearSearch(elements, n , x);
    finishLinear = clock();

    elapsedTimeLinear = (double)(finishLinear - startLinear)/CLOCKS_PER_SEC*1000;
    cout << "Time to Linear Search: " << elapsedTimeLinear << endl;
    foundLinear ? std::cout<<"Yes!"<<std::endl : std::cout<<"No!"<<std::endl;

    clock_t startSort, finishSort;
    double elapsedTimeSort =0;

    startSort = clock();
    sort(elements, elements+n);
    finishSort = clock();

    elapsedTimeSort = (double)(finishSort - startSort)/CLOCKS_PER_SEC*1000;
    cout << "Time to Sort: " << elapsedTimeSort << endl;

    clock_t startBinary, finishBinary;
    double elapsedTimeBinary =0, elapsedTimeBinaryTicks=0;

    startBinary = clock();
    //bool foundBinary = binarySearch(elements, n , x);
    bool foundBinary = binary_search(elements, elements+n, x);
    finishBinary = clock();

    elapsedTimeBinary = (double)(finishBinary - startBinary)/CLOCKS_PER_SEC*1000;
    elapsedTimeBinaryTicks = (double)(finishBinary - startBinary);
    cout << "Time to Binary Search in milliseconds: " << elapsedTimeBinary << endl;
    cout << "Time to Binary Search in clock ticks: " << elapsedTimeBinaryTicks << endl;
    printf("Time to Binary Search printed with \"printf()\": %f\n", elapsedTimeBinary);
    foundBinary ? std::cout<<"Yes!"<<std::endl : std::cout<<"No!"<<std::endl;

Answer 1

一百万项意味着最多 20 次比较。使用通常有效的代码(我没有看过你的代码)远低于 1 毫秒。在一个循环中多次执行您想要测量的事情，以获得高于时钟分辨率的结果。