前言

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

Linux 下的计时及其精度

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

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

#include <iostream>
#include <iomanip>
#include <sys/time.h>

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 << setw(3) << setfill('0') << timer/1000000000 << ",";
    cout << setw(3) << setfill('0') << (timer/1000000)%1000 << ",";
    cout << setw(3) << setfill('0') << (timer/1000)%1000 << ",";
    cout << setw(3) << setfill('0') << timer % 1000 << " ns" << endl;
}

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 <iostream>
#include <iomanip>
#include <sys/time.h>
using namespace std;

const int ARR_LEN = 1000000;

template <typename T>
void init_arr(T* a, int len){
    for(int i=0; i<len; i++){
        a[i] = (T)rand();
    }
}

template <typename T>
void print_arr(T* a, int len){
    if(len<10){
        for(int i=0; i<len; i++){
            cout << a[i] << "   ";
        }
        cout << endl;
    }else{
        for(int i=0; i<5; i++){
            cout << a[i] << "   ";
        }
        cout << "...   ";
        for(int i=len-5; i<len; i++){
            cout << a[i] << "   ";
        }
        cout << endl;
    }
}


template <typename T>
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 < right){
        while(a[right] > a[i] && left < right){
            right--;
        }
        if(left<right){
            T temp = a[right];
            a[right] = a[i];
            a[i] = temp;
            i = right;
            left ++;
        }

        while(a[left] < a[i] && left<right){
            left++;
        }
        if(left<right){
            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 << setw(3) << setfill('0') << timer/1000000000 << ",";
    cout << setw(3) << setfill('0') << (timer/1000000)%1000 << ",";
    cout << setw(3) << setfill('0') << (timer/1000)%1000 << ",";
    cout << setw(3) << setfill('0') << timer % 1000 << " ns" << endl;
}

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