测试一下我的电脑有多快

前言

弄了一台 Dell XPS 9570， 4K屏。终于满足了我在高分屏下玩 Linux 桌面的愿望。我已经给这台电脑安装了最新的 Ubuntu 20.10，并进行了适当的美化。昨天，又折腾了一晚上 Vim，主要是配置了 YouCompleteMe 和 vim-airline，所以迫不及待地想写写代码找找手感。那就测试一下我的电脑能运行多快，计时的精度有多高吧，顺便看看，通过我自己手撸的快速排序算法，程序又能提速到多快。

Linux 下的计时及其精度

以前用的计时函数是 gettimeofday()，其精度可以达到毫秒。有一天我在翻看《Unix环境高级编程》的时候，发现里面提到，gettimeofday() 早就废弃不用了，现在推荐使用 clock_gettime() 函数，精度可以达到 1 纳秒。听起来都好诱人。

下面写个小程序测试一下，就是连续两次调用 clock_gettime() 函数，然后打印时间间隔，看我的电脑记一次时，最快能达到多少纳秒。程序如下：

#include
#include
#include
using namespace std;
void print_timer(struct timespec start, struct timespec end){
long timer = (end.tv_sec - start.tv_sec)*1000000000 + end.tv_nsec - start.tv_nsec;
cout < cout < cout < cout <}
int main(){
struct timespec start;
struct timespec end;
clock_gettime(CLOCK_REALTIME, &start);
clock_gettime(CLOCK_REALTIME, &end);
print_timer(start, end);
return 0;
}


本来写这篇文章就是想找找 Vim 的手感，所以必须来一张 Vim 的图片，如下：

运行结果如下：

从上面的结果可以看出，我的电脑计时的精度可以达到 348ns，真的好厉害。以后，我的所有需要测试程序运行时间的，都使用上面这样的模板代码。

测试对长度为 1000000 的数组进行排序的时间：1.冒泡排序

冒泡排序的代码我就不列出了，因为是在是太简单了，就是两重循环，其时间复杂度为 \(O(n^2)\) ，那么，我们测出的时间是多少呢？

2645,822,408,482 ns

两千多秒，也就是四十多分钟，实在是太慢了。

测试对长度为 1000000 的数组进行排序的时间：2.快速排序

当然，上面程序的慢是每一个算法书上都会提到的，所以我们需要使用更快的算法。我这里使用的是快速排序，其时间复杂度为 \(O(n\log{n})\) 。算法是我手撸的，如下：

#include
#include
#include
using namespace std;
const int ARR_LEN = 1000000;
template
void init_arr(T* a, int len){
for(int i=0; i a[i] = (T)rand();
}
}
template
void print_arr(T* a, int len){
if(len<10){
for(int i=0; i cout < }
cout < }else{
for(int i=0; i<5; i++){
cout < }
cout <<"... ";
for(int i=len-5; i cout < }
cout < }
}
template
void quick_sort(T* a, int len){
if(len<2)return;
if(len == 2){
if(a[0] > a[1]){
T temp = a[0];
a[0] = a[1];
a[1] = temp;
}
}

int i=0, left=0, right=len-1;
while(left while(a[right] > a[i] && left right--;
}
if(left T temp = a[right];
a[right] = a[i];
a[i] = temp;
i = right;
left ++;
}
while(a[left] left++;
}
if(left T temp = a[left];
a[left] = a[i];
a[i] = temp;
i = left;
right--;
}
}

quick_sort(a, i);
quick_sort(a+i+1, len-i-1);
}
void print_timer(struct timespec start, struct timespec end){
long timer = (end.tv_sec - start.tv_sec)*1000000000 + end.tv_nsec - start.tv_nsec;
cout < cout < cout < cout <}
int main(){
int* a = (int*)malloc(sizeof(int)*ARR_LEN);
init_arr(a, ARR_LEN);
print_arr(a, ARR_LEN);
struct timespec start;
struct timespec end;
clock_gettime(CLOCK_REALTIME, &start);
quick_sort(a, ARR_LEN);
clock_gettime(CLOCK_REALTIME, &end);
print_arr(a, ARR_LEN);
print_timer(start, end);
return 0;
}


编译，运行。它的时间是多少呢？

000,123,209,970 ns

也就是 123ms，比冒泡排序足足提速两万一千五百多倍。我的天哪！看来算法还是非常重要的呀。

测试对长度为 1000000 的数组进行排序的时间：3.使用多线程的快速排序

这是最快的速度了吗？显然不是，我的电脑 CPU 可是 6 核 12 线程的。不充分利用多核优势怎么对得起自己。我上面的快速排序算法使用的是递归，那么使用 OpenMP 就没戏了（主要是我自己水平太菜，没找到递归算法的 OpenMP 写法）。那么只好自己写 thread 了，好在是自从 C++ 11 之后，写 thread 也很简单。我的方法就是在 quick_sort() 函数中判断一下待排序的数组的长度，如果待排序的数组的长度大于总数组长度的 1/8，就在新创建的线程里递归调用 quick_sort()，否则就直接递归调用 quick_sort()。如下图：

编译，运行。它的时间是多少呢？

000,040,038,803 ns

速度再次提升三倍，终于使时间达到了 40ms 的级别。这可能就是我的电脑和我本人的水平所能达到的最快速度吧。

下面是运行截图：

总结

电脑很 NB，Linux 的计时器也很 NB，算法很 NB，配置了 YouCompleteMe 和 vim-airline 的 Vim 也很 NB。

版权申明

该随笔由京山游侠在2021年05月16日发布于博客园，引用请注明出处，转载或出版请联系博主。QQ邮箱：1841079@qq.com