我浪费了很多时间来弄清楚为什么一种算法应该比另一种算法更有效,然而,就速度而言,另一种算法却完全相同。我做了这些操作:我在一个单独的终端窗口中编译了第一个源代码;而第二个源代码在另一个窗口中。我只是用了一个:
$抄送号码_v1.c
编译第一个,然后:
$抄送号码_v2.c
第二个源代码。 我正在使用 Mac OS X Darwin 内核版本 18.7.0:2019 年 8 月 20 日星期二 16:57:14 PDT; root: xnu-4903.271.2 ~ 2/RELEASE_X86_64 x86_64.
作为回应,我得到了完全相同的计时结果。鉴于第二个源代码的最佳算法,这是不可能的。
然后我关掉所有东西,第二天再试一次。令我惊讶的是,我终于看到了不同之处:第二个源代码的完成时间比第一个短得多。 看来编译器第一次没有编译出listing的代码,确实,可能还是考虑老版本;考虑到我曾多次尝试通过相对编译修改源代码,但结果总是一样。
这件事发生在我前一段时间处理另一个源代码时(相对浪费时间)。 不幸的是,该事件不可复制且不会经常发生。
谁能解释一下为什么会这样?在这些情况下是否有一种缓存可以重置?
它们各自的源代码如下;这是关于找到从 2 到 1000000 之间的素数。
/* cc number_v1.c */
#include <stdio.h>
int main(void) {
int i, j, n = 1000000;
for(i = 2; i <= n; i++) {
for(j = 2; j < i && i % j != 0; j++)
;
if(j >= i) printf("%d ", j);
}
return 0;
}
/* cc number_v2.c */
#include <stdio.h>
int main(void) {
int i, j, n = 1000000;
for(i = 2; i <= n; i++) {
for(j = 2; j * j <= i && i % j != 0; j++)
;
if(j * j > i) printf("%d ", i);
}
return 0;
}
最佳答案
您应该在代码中包含测量。您的测量显然有问题,您需要清楚地展示您的方法。
我执行了以下测试修改为使用 uint64_t
以防止 alg1()
中的算术溢出,并且还替换了 printf()
输出带有 volatile 水槽:
{volatile uint64_t x = i ;}
测量包含 I/O 的算法的性能可能会产生误导 - 您可能正在测量系统的 I/O 性能。
#include <stdio.h>
#include <time.h>
#include <stdint.h>
#define MAX 1000000 ;
void alg1( void )
{
uint64_t i, j, n = MAX;
for( i = 2; i <= n; i++ )
{
for( j = 2; j < i && i % j != 0; j++ )
;
if( j >= i ){volatile uint64_t x = i ;}
}
}
void alg2( void )
{
uint64_t i, j, n = MAX;
for( i = 2; i <= n; i++ )
{
for( j = 2; j * j <= i && i % j != 0; j++ )
;
if( j * j > i ){volatile uint64_t x = i ;}
}
}
int main()
{
clock_t start = clock() ;
alg1() ;
int alg1_clocks = clock() - start ;
start = clock() ;
alg2() ;
int alg2_clocks = clock() - start ;
printf( "\nalg1() took %f seconds", (double)(alg1_clocks) / CLOCKS_PER_SEC ) ;
printf( "\nalg2() took %f seconds", (double)(alg2_clocks) / CLOCKS_PER_SEC ) ;
return 0 ;
}
结果:
alg1() took 336.681000 seconds
alg2() took 0.621000 seconds
所以你的结果无法重现,所以我怀疑它们的完整性。
关于cc 编译器和缓存,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58040303/