【算法】C程序的运行速度测试

慕雪的小助手正在绞尽脑汁···

慕雪小助手的总结

LongCat-Flash-Chat

C语言程序的运行速度测试

代码随想录上提到了一点，即我们应该学会估计一个时间复杂度较高的算法，在机器上的运行速度。

如果题目给出的数据量级在高复杂度的算法中会超时，那就应该放弃使用这个代码，而想其他时间复杂度更优的解法；
这样能避免在刷题的时候，图简单写了个暴力写法却发现超时不过的尴尬（没错说的就是我自己）

大部分OJ题目，对C/C++代码的时间限制都是1s。所以我们测试的目标也将放在1s上。

1.代码

来源：http://www.360doc.com/content/23/0119/15/2690044_1064211133.shtml

我的Git：Gitee

1.1 循环

首先是func.h，内部包含了三个循环函数，时间复杂度分别为O(N) O(N^2) O(NlogN)

//func.h
#include <stdio.h>
// O(N)
void func1(long long n)
{
    printf("开始执行O(N)的函数：%lld\n",n);
    long long k=0;
    for(long long i=0;i<n;i++)
    {
        k++;
    }
}
// O(N^2)
void func2(long long n)
{
    printf("开始执行O(N^2)的函数：%lld\n",n);
    long long k=0;
    for(long long i=0;i<n;i++)
    {
        for(long long j=0;j<n;j++)
        {
            k++;
        }
    }
}

// O(NlogN)
void func3(long long n)
{
    printf("开始执行O(NlogN)的函数：%lld\n",n);
    long long k=0;
    for(long long i=0;i<n;i++)
    {
        // j要从1开始
        for(long long j=1;j<n;j*=2)
        {
            k++;
        }
    }
}

1.2 获取毫秒级时间戳

随后是主文件，这里我们需要进行时间的测试，所以得想办法获取到毫秒级的时间戳。

time.h中的time函数只能够返回秒级时间戳，对于代码的时间测试来说显然是不够的。我们需要借助Windows和Linux的系统函数，获取到毫秒级时间戳

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdint.h>
#include <stdio.h>
// http://www.360doc.com/content/23/0119/15/2690044_1064211133.shtml
// 宏编译，分别使用windows和linux的系统函数 
#ifdef _WIN32
    #include<time.h>
    #include<windows.h>
#else
    #include <sys/time.h>
    #include <unistd.h>
#endif

// 获取当前毫秒级时间，给一个char指针，则打印到其中（字符串）
// 后三位为毫秒
uint64_t GetCurrentTimerMS(char* szTimer)
{
    uint64_t nTimer = 0;
#ifdef _WIN32
    SYSTEMTIME currentTime;
    GetLocalTime(&currentTime);
    struct tm temptm = { currentTime.wSecond,
        currentTime.wMinute,
        currentTime.wHour,
        currentTime.wDay,
        currentTime.wMonth - 1,
        currentTime.wYear - 1900
    };
    nTimer =  mktime(&temptm) * 1000 + currentTime.wMilliseconds;
#else
    struct timeval tv;
    gettimeofday(&tv,NULL);
    // printf("second:%ld\n",tv.tv_sec);  //秒
    nTimer = tv.tv_sec*1000 + tv.tv_usec/1000;
#endif
    if(szTimer != NULL)
        sprintf(szTimer, "%llu", nTimer);
    return nTimer;
}
// 测试时间函数
int test_def()
{
    char szTimer[64];
    uint64_t nTimer=-1;
    GetCurrentTimerMS(szTimer);	//带参数，字符串
    nTimer = GetCurrentTimerMS(NULL); //不带参数
    printf("millisecond1:%s\nmillisecond2:%llu\n",szTimer,nTimer );  //毫秒
    return 0;
}

1.3 获取时间戳测试

先来执行一下这个测试函数test_def，结果如下

$ gcc test.c -o test
$ ./test
millisecond1:1681878963361
millisecond2:1681878963361

成功打印出了毫秒级的时间戳，分别是字符串类型和uint64_t长整型

#ifdef _WIN32
    #include <time.h>
    #include<windows.h>
#else
    #include <sys/time.h>
    #include <unistd.h>
#endif

这里还采用了宏定义，自动判断windows还是linux，调用各自的系统接口函数。

如下图，在Windows下的Vs2019也成功执行这个函数

2.开始测试

这个命令可以查看linux下的cpu型号

1 2	$ cat /proc/cpuinfo \| grep 'model name' \|uniq model name : Intel(R) Celeron(R) N5105 @ 2.00GHz

2.1 示例

先测试O(N)算法在何等数量级时会超过1s

$ ./test
请键入n：500000000
start_time: 1681880952986
开始执行O(N)的函数：500000000
end_time:   1681880954073
diff:       1087ms
start_time: 1681880963999
开始执行O(N)的函数：450000000
end_time:   1681880964993
diff:       994ms
请键入n：460000000
start_time: 1681881111806
开始执行O(N)的函数：460000000
end_time:   1681881112804
diff:       998ms
请键入n：470000000
start_time: 1681881117572
开始执行O(N)的函数：470000000
end_time:   1681881118604
diff:       1032ms
请键入n：400000000
start_time: 1681880967163
开始执行O(N)的函数：400000000
end_time:   1681880968043
diff:       880ms
请键入n：550000000
start_time: 1681880970538
开始执行O(N)的函数：550000000
end_time:   1681880971736
diff:       1198ms

如上，是我的linux服务器的测试结果。

数量级大概在460000000的时候，就会达到998ms，也就是将近1s

所以，当我们看到Oj的测试用量超过4500000000数量级的时候，就应该放弃O(N)算法！

而在windows下，我的R7 5800H笔记本，运行到700000000数量级的时候，才需要1s

请键入n：500000000
start_time: 1681881322528
开始执行O(N)的函数：500000000
end_time:   1681881323236
diff:       708ms
请键入n：1000000000
start_time: 1681881327548
开始执行O(N)的函数：1000000000
end_time:   1681881328965
diff:       1417ms
请键入n：600000000
start_time: 1681881332928
开始执行O(N)的函数：600000000
end_time:   1681881333792
diff:       864ms
请键入n：800000000
start_time: 1681881337404
开始执行O(N)的函数：800000000
end_time:   1681881338537
diff:       1133ms
请键入n：700000000
start_time: 1681881341486
开始执行O(N)的函数：700000000
end_time:   1681881342486
diff:       1000ms

2.2 结果

按如上办法测试，我分别测试了三种时间复杂度在多个平台上的结果。稍微了解这些数字，能帮助我们在判断题目选用算法上提供帮助。

表中E8是科学计数法，代表10的8次方

平台/CPU	时间复杂度	数量级	时间(毫秒)
windows (amd R7-5800H)	O(N)	7E9	1000
	O(N²)	3E4	1022
	O(NlogN)	1.7E7	996
Centos8 (Intel N5105)	O(N)	4.5E8	994
	O(N²)	2E4	920
	O(NlogN)	1.8E7	966
Centos7.2 (Intel Xeon Platinum 8255C)	O(N)	5.8E8	990
	O(N²)	2.4E4	976
	O(NlogN)	2.1E7	976