搜索算法中的时钟函数通常返回 0
Clock function in search algorithm generally returning 0
我确信这看起来像是一个微不足道的问题,但我在程序中遇到了“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
您的问题可能是 clock()
没有足够的分辨率:您确实 将零时间控制在允许的精度范围内。如果不是,那么几乎可以肯定编译器正在优化计算,因为它正在计算未被使用的东西。
默认情况下,您确实应该使用 chrono
header 而不是过时的 C 工具来计时。特别是,如果您发现自己确实需要它,high_resolution_clock
往往有利于衡量相对快速的事物。
准确地对事物进行基准测试是一项重要的工作,您真的应该仔细阅读如何正确地进行基准测试。有很多问题涉及诸如缓存或令人惊讶的编译器优化或变量 CPU 频率等许多程序员以前从未想过的问题,而忽略它们可能会导致错误的结论。
一个特殊的方面是,您通常应该安排时间实际需要一些时间的事情;例如运行 无论您是在数千个不同的输入上进行测试,因此持续时间大约为一秒或更长时间。这往往会提高基准的精度和准确性。
感谢大家的帮助!这似乎是任何 windows/windows 仿真软件的某种问题。
我决定启动 ubuntu 并在那里试一试,瞧!我得到了完美的输出:)
我想开源确实是最好的方式:D
我确信这看起来像是一个微不足道的问题,但我在程序中遇到了“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
您的问题可能是 clock()
没有足够的分辨率:您确实 将零时间控制在允许的精度范围内。如果不是,那么几乎可以肯定编译器正在优化计算,因为它正在计算未被使用的东西。
默认情况下,您确实应该使用 chrono
header 而不是过时的 C 工具来计时。特别是,如果您发现自己确实需要它,high_resolution_clock
往往有利于衡量相对快速的事物。
准确地对事物进行基准测试是一项重要的工作,您真的应该仔细阅读如何正确地进行基准测试。有很多问题涉及诸如缓存或令人惊讶的编译器优化或变量 CPU 频率等许多程序员以前从未想过的问题,而忽略它们可能会导致错误的结论。
一个特殊的方面是,您通常应该安排时间实际需要一些时间的事情;例如运行 无论您是在数千个不同的输入上进行测试,因此持续时间大约为一秒或更长时间。这往往会提高基准的精度和准确性。
感谢大家的帮助!这似乎是任何 windows/windows 仿真软件的某种问题。
我决定启动 ubuntu 并在那里试一试,瞧!我得到了完美的输出:)
我想开源确实是最好的方式:D