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

我的计时功能在这里遇到问题。我有一个计划计时二进制搜索在数组中的排序元素列表中找到给定数字所需时间的程序。

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

例如，我上次运行时，程序说花了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;
}

最佳答案

使用最坏情况的搜索来运行您的代码，我的机器始终能获得25到86微秒的时间。将cout移到代码的计时部分之外，我得到一个恒定的0微秒。

也许您的stdout缓冲区已挂起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;
}

关于c++ - 在搜索算法上获得微秒输出，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28554273/