网站建设常用模板下载,合肥做网站多少钱,哪家可以做网站,建wap手机网站2019独角兽企业重金招聘Python工程师标准 前一段时间#xff0c;实验室的一哥们突然跑过来跟我说#xff0c;“我自己写了个C的快速排序#xff0c;排了一个10000000个int的数组#xff0c;貌似比C库中是qsort算法要快#xff0c;咋回事#xff1f;C的STL中… 2019独角兽企业重金招聘Python工程师标准 前一段时间实验室的一哥们突然跑过来跟我说“我自己写了个C的快速排序排了一个10000000个int的数组貌似比C库中是qsort算法要快咋回事C的STL中快排quick sort算法的效率如何”。 听他这么一说我就立即做了个实验写了如下代码 !-- lang: cpp --
#include iostream
#include algorithm
#include time.husing namespace std;#define MAX_LEN 10000000int arri[MAX_LEN];int compare(const void* i, const void* j)
{return (*(int*)i - *(int*)j);
}int main()
{for (int i 0; i MAX_LEN; i) {arri[i] rand() % MAX_LEN;}::clock_t start, finish;//STL sortstart ::clock();sort(arri, arri MAX_LEN);finish ::clock();cout STL sort:\t finish - start ms endl;for (int i 0; i MAX_LEN; i) {arri[i] rand() % MAX_LEN;}//C qsortstart ::clock();qsort(arri, MAX_LEN, sizeof(arri[0]), compare);finish ::clock();cout C qsort:\t\t finish - start ms endl;return 0;
}我机器上装的是CodeBlocks10.05MinGW4.7.2的环境。 首先在debug模式下CodeBlocks显示出当前的编译器命令 !-- lang: shell --
mingw32-g.exe -Wall -fexceptions -g -stdc0x -c D:\Workspaces\CodeBlocks\TestSortQ\main.cpp -o obj\Debug\main.o
mingw32-g.exe -o bin\Debug\TestSortQ.exe obj\Debug\main.o运行结果 运行结果让我大吃一惊STL不可能这么慢啊后来仔细一想这是debug模式没有加任何优化加上优化看看什么结果 !-- lang: shell --
mingw32-g.exe -Wall -fexceptions -O2 -stdc0x -c D:\Workspaces\CodeBlocks\TestSortQ\main.cpp -o obj\Release\main.o
mingw32-g.exe -o bin\Release\TestSortQ.exe obj\Release\main.o -s运行结果 果然O2选项一加上STL sort瞬间完成了逆袭运行时间优化了75%而C qsort优化前后变化不是很明显大概减少了10%。 问题来了为什么C标准库的快排的优化效果如此明显而C库的快排优化不是很明显呢 答案是inline。 我们知道STL是泛型编程的杰出成果里面的容器、迭代器、算法几乎都是通过泛型实现的使得STL的通用性很强。泛型编程的一个负面效果就是破坏了接口与实现的分离即头文件中声明源文件中实现源文件单独编译成库用户只需要拿到头文件和库就可以使用了看不到具体实现这就是所谓的ABI也是C的传统做法。有人会问为什么不能做到接口与实现的分离因为泛型编程中的函数和类在没有接受一个模版参数之前是没办法实例化的只有当用户给定了模版参数的时候编译器才会去实例化一个具体的类或函数。 如C STL中的快速排序算法定义 !-- lang: cpp --
template class RandomIt
void sort( RandomIt first, RandomIt last );只有RandomIt这个类型真正确定了编译器才会去实例化这个方法。在上面的代码中我这么写 !-- lang: cpp --
sort(arri, arri MAX_LEN);编译器通过自动类型推导知道了RandomIt其实是一个int*于是产生这个函数 !-- lang: cpp --
sort(int*, int*);具体实现中的RandomIt已经都替换成相应的int*一个完整的函数就产生了。 关键的问题出现了编译器在实例化一个函数类也一样的时候它必须知道具体的实现代码才能够产生完整的函数。这也是为什么如果大家自己写模版的时候.h文件和.cpp文件的关系变得十分奇怪的原因一般做饭是在.h文件末尾#include xx.cpp其中xx.cpp中实现了.h文件中的函数声明或者干脆直接在.h文件中写实现。否则如果按照一般的.h和.cpp的关系编译器会报错说找不到函数的实现。写过模版的程序猿应该都知道这个。 事实上C标准委员会为了解决这个问题曾经引入了export关键字来试图解决这个问题但很少有编译器实现了估计是实现难度较大且增加了复杂度得不偿失所以这个关键字后来基本上费了。 大家或许会问你是不是走题了刚开始不是讨论C的效率问题吗怎么说了半天泛型和模版的事情了 答案是真是由于泛型的这个“副作用”使得编译器可以做更多的优化 既然编译器知道具体的实现那么inline是编译器可以在优化上大显身手的一个手段sort函数中需要一个compare函数在C中还可以通过函数对象或者操作符重载实现来知道如何比较两个元素的大小sort函数每次比较的时候都会调用这个函数。对于一个10000000个元素的数组一共会调用多少次这个compare函数是可想而知的具体数目可以算出来而一次函数调用的开销比较大如栈的分配等等这就很大程度上限制了C库中的qsort的威力因为qsort的实现是在编译在库中的它所调用的函数就没法inline到qsort函数里面去。但是STL是可以做到的所以它的优化效果非常明显。 另外一个STL sort效率高的原因在于算法的实现不仅仅是快速排序算法估计这也是为什么名字叫sort而不叫qsort的原因吧。在SGI STL(GNU所使用的STL)的实现中sort函数一共采用了三种排序算法分别是quick sortheap sort和insert sort。使用策略如下 1、函数主体为quick sort但是在递归调用的时候加上了一个参数记录迭代层数如果迭代次数超过一定数目转而采用heap sort。原因是如果迭代次数过多很可能意味着quick sort落入了最坏情况O(n2)而heap sort的最坏情况依然是O(nlogn)。 2、当数组划分到很小的一段时采用insert sort。原因是对于小数据量采用quick sort有些不划算quick sort适合处理大量数据因为quick sort本身是递归的递归就是一次函数调用开销较大。而insert sort在较小数据量的情况下表现很好。 具体算法可参考SGI STL和侯捷的《STL源码剖析》。 说了这么一大堆其实想表达的一点就是C为了提高效率可以说无所不用其极无论是STL算法实现还是编译器的优化语言本身为了编译器能做优化也下了很多功夫都体现了C的三大设计思想或者叫做约束可参考孟岩《关于C复杂性的零碎思考》之一最高性能。 回到那位哥们的问题为什么他的快排效率比C库的要高我不否认他的水平但是我感觉最大的原因还是自己写的函数编译器可以将compare的功能内敛到函数里面去所以效率比C库的qsort效率要高。 关于C的高效我还想继续写一些文章这篇博客且当作一个开始吧。 转载于:https://my.oschina.net/chen0dgax/blog/156156
