c++ - 在搜索算法上获得微秒输出

Question

我这里的计时功能有问题。我有一个程序可以计算二进制搜索在数组中的已排序元素列表中查找给定数字所花费的时间。

所以我得到了奇怪的结果，我不确定为什么。

例如，我最后一次运行时，程序说用 0 微秒找到不在大小为 100,000 个元素的数组中的值，但就在它之前，程序搜索了一个包含 95,000 个元素的数组，它也找到了值是不在数组中，但它花费了 4080005 微秒。

这是我的函数代码。 感谢您的帮助!

int binarySearch(int array[], int numElems, int value)
{
    auto start =chrono::steady_clock::now();

    cout << "Searching..."<< endl;
    //variables
    int first = 0,
        last = numElems - 1,
        middle,
        position = -1;

    bool found = false;


    //Checks values for match
    while (!found && first <= last)
    {
        //divides elements
        middle = (first + last) / 2;
        if (array[middle] == value)
        {
            found = true;
            position = middle;
        }
        else if (array[middle] > value)
            last = middle - 1;
        else
            first = middle + 1;
    }

    auto end = chrono::steady_clock::now();
    auto elasped = std::chrono::duration_cast<std::chrono::microseconds>(end-start);
    cout << "Time Taken: " << elasped.count() << " microseconds." << endl;

    return position;
}

Answer 1

使用最坏情况搜索运行您的代码时，我的机器上的时间始终在 25 到 86 微秒之间。将 cout 移到代码的时钟部分之外，我得到一致的 0 微秒。

也许您的标准输出缓冲区已挂起 4 秒。向终端发送文本是一个非常缓慢的过程。二分查找很快； O(log(n))，对于 100,000 是 6 次比较，最坏的情况。 0 微秒很有意义。我敢打赌这是你的终端缓冲区不稳定。

现在为了好玩，我切换到 high_resolution_clock .

$ ./a.out 
Searching...
Time Taken: 619 nanoseconds.
Position: 99999

来源:

int binarySearch(int array[], int numElems, int value)
{

  cout << "Searching..."<< endl;
  auto start =chrono::high_resolution_clock::now();

  //variables
  int first = 0,
  last = numElems - 1,
  middle,
  position = -1;

  bool found = false;


  //Checks values for match
  while (!found && first <= last)
  {
    //divides elements
    middle = (first + last) / 2;
    if (array[middle] == value)
    {
        found = true;
        position = middle;
    }
    else if (array[middle] > value)
        last = middle - 1;
    else
        first = middle + 1;
  }

  auto end = chrono::high_resolution_clock::now();
  auto elasped = std::chrono::duration_cast<std::chrono::nanoseconds>(end-start);
  cout << "Time Taken: " << elasped.count() << " nanoseconds." << endl;

  return position;
}