c++ - 搜索算法中的时钟函数通常返回 0

Question

我确信这看起来像是一个微不足道的问题，但我在程序中遇到了“clock()”函数的问题(请注意我已经检查过类似的问题，但他们没有' 似乎在相同的上下文中相关)。我的时钟输出几乎总是 0，但似乎也有几个 10(这就是我感到困惑的原因)。我考虑了一个事实，也许函数调用处理得太快了，但从排序算法来看，肯定需要一些时间。

提前感谢大家的帮助! :)

P.S 我真的很抱歉关于函数之间变量相关性的困惑(这是我合并在一起的一组代码，我在美化它之前专注于正确的输出):D

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int bruteForce(int array[], const int& sizeofArray);

int maxSubArray (int array[], int arraySize);

int kadane_Algorithm(int array[], int User_size);

int main()
{
    int maxBF, maxDC, maxKD;
    clock_t t1, t2, t3;
    int arraySize1 = 1;
    double t1InMSEC, t2InMSEC, t3InMSEC;

    while (arraySize1 <= 30000)
    {
        int* array = new int [arraySize1];

        for (int i = 0; i < arraySize1; i++)
        {
            array[i] = rand()% 100 + (-50);
        }

        t1 = clock();
        maxBF = bruteForce(array, arraySize1);
        t1 = clock() - t1;
        t1InMSEC = (static_cast <double>(t1))/CLOCKS_PER_SEC * 1000.00;

        t2 = clock();
        maxDC = maxSubArray(array, arraySize1);
        t2 = clock() - t2;
        t2InMSEC = (static_cast <double>(t2))/CLOCKS_PER_SEC * 1000.00;

        t3 = clock();
        maxKD = kadane_Algorithm(array, arraySize1);
        t3 = clock() - t3;
        t3InMSEC = (static_cast <double>(t3))/CLOCKS_PER_SEC * 1000.00;

        cout << arraySize1 << '\t' << t1InMSEC << '\t' << t2InMSEC << '\t' << t3InMSEC << '\t' << endl;
        arraySize1 = arraySize1 + 100;
        delete [] array;
    }
    return 0;
}

int bruteForce(int array[], const int& sizeofArray)
{
    int maxSumOfArray = 0;
    int runningSum = 0;
    int subArrayIndex = sizeofArray;

    while(subArrayIndex >= 0)
    {
        runningSum += array[subArrayIndex];

        if (runningSum >= maxSumOfArray)
        {
            maxSumOfArray = runningSum;
        }

        subArrayIndex--;
    }
return maxSumOfArray;
}

int maxSubArray (int array[], int arraySize)
{
  int leftSubArray = 0;
  int rightSubArray = 0;
  int leftSubArraySum = -50;
  int rightSubArraySum = -50;
  int sum = 0;
  if (arraySize == 1) return array[0];

  else
  {
    int midPosition = arraySize/2;
    leftSubArray = maxSubArray(array, midPosition);
    rightSubArray = maxSubArray(array, (arraySize - midPosition));

    for (int j = midPosition; j < arraySize; j++)
    {
        sum = sum + array[j];
        if (sum > rightSubArraySum)
        rightSubArraySum = sum;
    }
    sum = 0;

    for (int k = (midPosition - 1); k >= 0; k--)
    {
        sum = sum + array[k];
        if (sum > leftSubArraySum)
        leftSubArraySum = sum;
    }

  }
  int maxSubArraySum = 0;

  if (leftSubArraySum > rightSubArraySum)
  {
      maxSubArraySum = leftSubArraySum;
  }

  else maxSubArraySum = rightSubArraySum;

  return max(maxSubArraySum, (leftSubArraySum + rightSubArraySum));
}

int kadane_Algorithm(int array[], int User_size)
{
    int maxsofar=0, maxending=0, i;

    for (i=0; i < User_size; i++)
    {
        maxending += array[i];

        if (maxending < 0)
        {
            maxending = 0 ;
        }

        if (maxsofar < maxending)
        {
            maxsofar = maxending;
        }
    }
return maxending;
}

输出如下:(只是为了可视化使用了一个片段)

• 29001 0 0 0
• 29101 0 10 0
• 29201 0 0 0
• 29301 0 0 0
• 29401 0 10 0
• 29501 0 0 0
• 29601 0 0 0
• 29701 0 0 0
• 29801 0 10 0
• 29901 0 0 0

Answer 1

您的问题可能是 clock() 没有足够的分辨率:您确实在允许的精度范围内花费了零时间。如果不是，那么几乎可以肯定编译器正在优化计算，因为它正在计算未被使用的东西。

默认情况下，您确实应该使用 chrono header 而不是过时的 C 工具来计时。特别是，high_resolution_clock 往往适合测量相对较快的事物，如果您发现自己确实需要它的话。

准确地对事物进行基准测试是一项重要的工作，您真的应该仔细阅读如何正确地进行基准测试。有许多问题涉及诸如缓存或令人惊讶的编译器优化或可变 CPU 频率等许多程序员以前从未想过的问题，而忽略它们可能会导致错误的结论。

一个特别的方面是，您通常应该为实际需要一些时间的事情安排时间；例如运行您正在测试的数千个不同输入的任何内容，以便持续时间为例如整秒或更长时间。这往往会提高基准的精度和准确性。