前几天发现老外的开源项目中事件队列中用的就是std::qsort排序,后续插入时候使用了堆方式。
快速排序实际应用中是比堆排序要快的,这主要是因为硬件层次会对数据执行高速缓存,
数据使用一二三级高速缓存比访问内存块很多,
所以堆排序实际上是比较慢的。
面试一般是考快速排序,
我没有事也默写了一个,并且和std::qsort与std::sort比较了一下,
代码的核心就是递归:
每个递归:
1)拿左边第一个元素作为标杆,小于的放它左侧,大于的放右侧,最后找到标杆合适的位置;
2)处理左侧;
2)处理右侧;
备注,递归深度与先后没有关系,与标杆是否平衡有关系;教科书算法没有考这些:
// 快速排序
static int GetMark(int *v, int i, int j)
{
int temp = v[i];
while (i < j)
{
while (temp <= v[j] && i < j)
j--;
v[i] = v[j];
while (temp >= v[i] && i < j)
i++;
v[j] = v[i];
}
v[i] = temp;
return i;
}
void quickSort(int * v, int begin, int end)
{
if (begin >= end)
return;
int index = GetMark(v, begin, end);
quickSort(v, begin, index - 1);
quickSort(v, index + 1, end);
}
这个写法是比较标准的教科书写法,下面写个计时器:
//使用高性能计时器实现的 GetTickCount 函数
double GetTickCountA()
{
__int64 Freq = 0;
__int64 Count = 0;
if (QueryPerformanceFrequency((LARGE_INTEGER*)&Freq)
&& Freq > 0
&& QueryPerformanceCounter((LARGE_INTEGER*)&Count))
{
//乘以1000,把秒化为毫秒
return (double)Count / (double)Freq * 1000.0;
}
return 0.0;
}
我们用一组随机数测试一下:
// 配套的比较函数
int cmpInt(const void * a, const void * b)
{
return *(int *)a - *(int *)b;
}
void testSort()
{
int n = 100000;
int * v = new int[n];
static default_random_engine engine;
static uniform_int_distribution<int> uniform(0, 750);
for (int i = 0; i < n; i++)
{
v[i] = uniform(engine);
//cout << v[i] << "\t";
}
cout << endl;
double tms1 = GetTickCountA();
InsertSort(v, n);
//quickSort(v, 0, n - 1);
//std::qsort(v, n, sizeof(int), cmpInt);
//std::sort(v, v + n-1);
double tms2 = GetTickCountA();
cout << tms2 - tms1 << endl;
/*for (int i = 0; i < n; i++)
{
cout << v[i] << "\t";
}*/
cout << "ok" << endl;
}
测试100万一下的数,其实还算好的,很快就算完了,
但是加到1000万时候,栈就崩了,vc默认的栈大小是1M,可以使用参数加载
linux设置环境变量可以加大,但是这不是解决问题的终极办法。
当随机的数类似二叉树时候,递归深度是log2(n),但是如果分左右时候比较极端,直接考1侧分开,则深度可能达到N;
我打算看看有没有使用循环来代替的方法,但是好像应该没有;
实际上可以自己用堆上建立一个栈对象模拟递归,但是我更想知道人家怎么做到的。
1000万数据使用std::qsort时候很快,2秒多就结束了,人家没有崩溃,
std::sort非常慢,比自己写的还要慢,所以还是不要用了;
直接插入排序更慢,也不要用了;
所以很想看看qsort怎么实现的,于是我使用everything工具进行搜索,找到了微软的qsort.cpp文件,
它 核心思想有3个:
1)短于8个元素,改用选择排序;
2)因为有相等的部分,找标杆时候,使用2个标杆,分为三个部分:小于,等于,大于;这样就不再继续处理等于部分了;
3)使用自定义栈来避免递归。
歌词大意是这样的:
1)当分组下降到某个临界值时候,使用短距离排序;(注释里写的插入排序,但是看代码应该是选择排序)
临界值设置为8,注释所经过了测试,发现这个数值比较合适。
#define CUTOFF 8
2)这样递归堆栈的理论的深度应该是: 1 + log2(num) - log(CUTOFF) , 即log2(num) - 2,
num= 2^32,或者2^64
那么 32-bit系统上不超过30 的栈对象, 64-bit 系统需要62个;当然这是理论上的,所以源码定义了一个值:
#define STKSIZ (8 * sizeof(void*) - 2)
// 64位机器寻址范围是2^64, 这里就是字节数*8bits, 得到最大log2(2^64)
3)于是在程序的开始自己定义了2个栈
char* lostk[STKSIZ]; // 低标志的栈大小
char* histk[STKSIZ]; // 高标志的栈大小
int stkptr = 0; // 栈顶
4)定义栈之后,就可以开始准备手动递归了,定义一个标志,用于goto
recurse:
手动递归开始:
计算当前排序范围的距离,
5)如果长度小于8 ,则使用短距离排序,
否则:
6)使用第1个,最后1个元素,中间元素,三者进行比较,按顺序排列3个元素;
这样就用三个数定义了2个区间,lo----------mid------------hi,
比如:250----------460------------730
注释这样说:
首先我们要选择一个分区项(partition)。算法的高效性要求我们找到一个近似数组中间值的项,但我们要保证能够很快找到它。
我们选择数组的第一项、中间项和最后一项的中间值,来避免最坏情况下的低效率。
测试表明,选择三个数的中间值,比单纯选择数组的中间项的效率要高。
7)将数组分为3个部分:比分区值小,等于分区值,大于分区值;所以加了2个标记位:
char* loguy = lo; // lo + guy
char* higuy = hi;
那么:lo --------小于分区值------------loguy ------------等于分区值------------higuy -----------------大于分区值------------------hi
方法是:
循环:满足 (higuy < loguy)
a) loguy从左向右,如果A[loguy] <= A[mid] 移动;直到 A[loguy] > A[mid] ,(其中loguy可能越过mid),
b) higuy从右向左,如果A[higuy] >A[mid] 则向左移动;直到 A[higuy] <= A[mid], (其中higuy一直在mid右侧),
c) if (higuy < loguy) break; 不需要交换了,停止!!!
d)交换A[loguy] 和 A[higuy], 则 loguy左侧 <= A[mid], higuy右侧 > A[mid]
lo -------------loguy ------------mid------------higuy -------大于-------------hi
lo---------小于等于------------mid------------大于-----------------------------hi
e)因为我们要求:higuy一直在mid右侧,
所以如果,higuy==mid,则令mid = loguy,
这样算法进入状态:loguy在mid右侧向右移动,higuy准备向左移动,
lo ----小于等于旧Amid---------[mid] --loguy===================higuy -------大于旧Amid-------------hi,
比如:
lo ----小于等于旧Amid---------500 --489,458,501===================600-------大于旧Amid-------------hi,
下面循环中,[mid] 不再移动,相当于两侧向中间移动,保证大的交换到右侧,小于等于的在左侧;
结束循环!
8)如果a[higuy] == A[mid] ,则继续左移,也就是找到相等的部分
lo ----------- higuy--------------[mid] ----------loguy------------------hi,
9)将一部分压栈,另一部分直接处理!
10)如果栈顶到负数,则结束。
简化后代码如下:
1)交换与交换排序
// 交换
void swapint(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
// 选择交换排序
void shortSort(int *v, int begin, int end)
{
int index; // 最大值的索引
while (begin < end)
{
index = begin; // 左侧不动,每个循环将最大的交换到最后,不稳定
for (int i=index+1; i<=end; i++)
{
if (v[i] > v[index])
{
index = i;
}
}
if (index < end)
swapint(v[index], v[end]);
end--;
}
}
2)寻找标记,分为三段:
//#define IS_PRINT_MARK2
inline void DEBUG_PRINT_MARK2(const char *str,int *v, int begin, int end, int mark1, int mark2, int mid)
{
#ifdef IS_PRINT_MARK2
// 调试输出
cout << str << endl;
for (int i = begin; i <= end; i++)
{
if (i == mid)
{
cout << "[" << v[i] << "]" << " ";
}
else if (i == mark2)
{
cout << "(" << v[i] << ")" << " ";
}
else if (i == mark1)
{
cout << "{" << v[i] << "}" << " ";
}
else if ((i+1 == mid) || (i+1 == mark2) || (i+1 == mark1)
|| (i - 1 == mid) || (i - 1 == mark2) || (i - 1 == mark1))
{
cout << v[i] << " ";
}
else
cout << v[i] << " ";
}
cout << endl;
#endif
}
// 分三个部分;返回mid
// 分为三段, 执行后,begin------mark2 等于部分不用处理 mark1---- - end
// 传统算法是将第1个元素作为标准,分左右,
// 这里是先选3个,第1,最后,中间,比较一下取中间作为标杆,之后执行分界
inline int Get2Mark(int *v, int& mark1, int &mark2, int begin, int end)
{
// 这里不少于8个元素
int count = end - begin + 1;
int mid = begin + count / 2;
// 冒泡法,排序3个数字
if (v[begin] > v[mid])
swapint(v[begin], v[mid]);
if (v[begin] > v[end])
swapint(v[begin], v[end]);
if (v[mid] > v[end])
swapint(v[mid], v[end]);
mark1 = begin; // 处理过了,跳过
mark2 = end;
DEBUG_PRINT_MARK2("准备开始:", v, begin, end, mark1, mark2, mid);
while (true)
{
// 这里是分阶段的,所有要判断左右关系
// 首先是: begin------mark1------mid------mark2-----end
// 之后是: begin------mid------mark1------mark2-----end
// 最后是: begin------mark2------mid------mark1-----end
// 找到大于的 微软这么做的,但是似乎有逻辑问题,不知道为啥,
//if (mark1 < mid) // 1) 阶段
//{
// do { mark1++; }
// while (mark1 < mid && v[mark1] <= v[mid]);
//
//}
//else // 2) 阶段
//{
while (mark1 <= end && v[mark1] <= v[mid])
mark1++;
//}
// 向左找到小于等于的;这里可能会越过mid,越过mark1
while (mark2 > mid && v[mark2] > v[mid])
mark2--;
if (mark2 < mark1) // 证明不需要交换了,这里从2阶段结束
break;
// 如同传统算法一样,交换一下,左边小于或者等于,右边大于
DEBUG_PRINT_MARK2("交换前:", v, begin, end, mark1, mark2, mid);
swapint(v[mark1], v[mark2]);
DEBUG_PRINT_MARK2("交换后:", v, begin, end, mark1, mark2, mid);
//cout << endl;
// 之前1)阶段,mark1 < mid,这里不会出现mark1 == mid,直到mark2左移到mid,
// 进入2) 阶段,begin------mid---[mark1]------[mark2]-----end
// 此时,mid和mark1之间都是小于等于mid, 大于的都放到右侧,
// 也就是在【mark1】 和【mark2】 位置上交换【mid】为标杆的数字,与传统算法近似但不同,
if (mid == mark2)
mid = mark1;
}
// 循环结束时候,mark2位置的数字应该是小于等于v[mid]
// 满足:
// 1) mark1左侧都是 <= v[mid]; mid 也在mark1左侧;
// 2) mark2右侧都是 >= v[mid];
// 3) mark2-----mark1
// 一般来说:mark2 == mark1 - 1
// 如图:-[mid:10]--9--8--10--[mark2][mark1]--11--12--11--
// 或者:v[end] == v[mid],mark2 == end - 1, mark1 == end + 1,
// 如图 -[mid:10]--9--8--10--[mark2][end:10]|[mark1] j
// 所以要移动一次mark2
mark2++;
do
{
mark2--;
} while (mark2 >= begin && v[mark2] == v[mid]);
// 连续移动后,mark2----mark1之间如果有数据,则与v[mid]相等;
// 也可能没有;
//cout << mid << "," << mark2 << "," << mark1 << endl;
DEBUG_PRINT_MARK2("结束:", v, begin, end, mark1, mark2, mid);
return mid;
}
// 检测分界是否错误;
BOOL checkMark2(int *v, int begin, int end, int mark1, int mark2, int mid)
{
// 小于等于部分
for (int i=begin; i<mark2; i++)
{
if (v[i] > v[mid])
return FALSE;
}
// 都是大于
for (int j=mark1; j<=end; j++)
{
if (v[j] <= v[mid])
return FALSE;
}
return TRUE;
}
// 测试分界效果
int testmark2()
{
int n = 1000;
int *v = new int[n];
static default_random_engine engine;
static uniform_int_distribution<int> uniform(0, 750);
for (int i = 0; i < n; i++)
{
v[i] = uniform(engine);
// cout << v[i] << ", ";
}
cout << endl;
int mark1, mark2;
int mid = Get2Mark(v, mark1, mark2, 0, n-1);
int ret = checkMark2(v, 0, n - 1, mark1, mark2, mid);
if (ret == FALSE)
{
for (int i = 0; i < n; i++)
{
if (i == mid)
{
cout << "[" << v[i] << "]" << " ";
}
else if (i == mark2)
{
cout << "(" << v[i] << ")" << " ";
}
else if (i == mark1)
{
cout << "{" << v[i] << "}" << " ";
}
else if ((i + 1 == mid) || (i + 1 == mark2) || (i + 1 == mark1)
|| (i - 1 == mid) || (i - 1 == mark2) || (i - 1 == mark1))
{
cout << v[i] << " ";
}
else
cout << v[i] << " ";
}
cout << endl;
cout << endl;
}
delete[]v;
return ret;
}
这段代码和微软的流程有改动,因为测试发现微软的代码有点逻辑问题,但是没有想通,直接改了,如果有发现错误的,请告知!!
分界单独测试结果:生成30个随机数,查看与[mid], (mark2), {mark1}位置:
结果还算满意:
6, 3, 10, 9, 4, 7, 0, 6, 5, 4, 2, 3, 3, 8, 0, 5, 2, 3, 2, 7, 6, 5, 7, 8, 6, 3, 1, 7, 1, 6,
准备开始:
{5} 3 10 9 4 7 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 1 7 1 (6)
交换前:
5 3 {10} 9 4 7 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 1 7 1 (6)
交换后:
5 3 {6} 9 4 7 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 1 7 1 (10)
交换前:
5 3 6 {9} 4 7 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 1 7 (1) 10
交换后:
5 3 6 {1} 4 7 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 1 7 (9) 10
交换前:
5 3 6 1 4 {7} 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 (1) 7 9 10
交换后:
5 3 6 1 4 {1} 0 6 5 4 2 3 3 8 0 [6] 2 3 2 7 6 5 7 8 6 3 (7) 7 9 10
交换前:
5 3 6 1 4 1 0 6 5 4 2 3 3 {8} 0 [6] 2 3 2 7 6 5 7 8 6 (3) 7 7 9 10
交换后:
5 3 6 1 4 1 0 6 5 4 2 3 3 {3} 0 [6] 2 3 2 7 6 5 7 8 6 (8) 7 7 9 10
交换前:
5 3 6 1 4 1 0 6 5 4 2 3 3 3 0 [6] 2 3 2 {7} 6 5 7 8 (6) 8 7 7 9 10
交换后:
5 3 6 1 4 1 0 6 5 4 2 3 3 3 0 [6] 2 3 2 {6} 6 5 7 8 (7) 8 7 7 9 10
结束:
5 3 6 1 4 1 0 6 5 4 2 3 3 3 0 [6] 2 3 2 6 6 (5) {7} 8 7 8 7 7 9 10
最后一个关键的函数:
// 按照微软的qsort.cpp简化处理
void ms_qsort(int * v, int begin, int end)
{
const int CUTOFF = 8; // 临界值
const int STKSIZ = 100; // 堆栈100个;
int *lowStack = new int[STKSIZ];
int *higStack = new int[STKSIZ];
int top = 0; // 栈顶,栈顶为空
int mark1; // 用于分段的游标
int mark2;
int mid;
// goto 手动递归
recurse:
int count = end - begin + 1; // 计算个数
if (count <= 8)
{
shortSort(v, begin, end); // 优化;
}
else
{
// 第一阶段,分段;
// 如果分段后分成3部分,就压栈一部分,剩下的递归,直到都是小于7的小部分,小部分执行后会退栈
mark1 = begin;
mark2 = end;
// 分为三段, 执行后,begin------mark2 等于部分不用处理 mark1-----end
mid = Get2Mark(v, mark1, mark2, begin, end);
// 为了缩短栈深度,先做短的部分,长的部分先压栈,
// 这里能缩短,主要是8以下直接算不用压栈;传统算法标准递归不需要,没有用
// 如果左侧长
if (mark2-begin >= end-mark1)
{
if (begin < mark2) // 左侧部分先不处理,压栈,回头再说
{
// Save the big recursion for later:
lowStack[top] = begin;
higStack[top] = mark2;
++top;
}
if (mark1 < end) // 设置边界,直接处理后面的部分
{
begin = mark1;
goto recurse;
}
}
else // 如果右侧长
{
if (mark1 < end) // 右侧延展
{
lowStack[top] = mark1;
higStack[top] = end;
++top;
}
if (begin < mark2) // 左侧直接处理
{
end = mark2;
goto recurse;
}
}
}// end of else
--top; // 退栈
if (top >= 0)
{
// Pop sub-array from the stack:
begin = lowStack[top];
end = higStack[top];
goto recurse;
}
else
{
delete[] lowStack;
delete[] higStack;
return;
}
}
性能测试:
数据 \ 算法 | std::qsort | 简化版 | 栈最大深度 |
100万 int | 322毫秒 | 210毫秒 | 6 |
1000万int | 2.4秒 | 1.7秒 | 7 |
有兴趣大家可以测试一下。测试代码如下:
void testSort()
{
int n = 1000000;
int * v = new int[n];
static default_random_engine engine;
static uniform_int_distribution<int> uniform(0, 750);
for (int i = 0; i < n; i++)
{
v[i] = uniform(engine);
//cout << v[i] << " ";
}
cout << endl;
double tms1 = GetTickCountA();
//InsertSort(v, n);
//quickSort(v, 0, n - 1);
//std::sort(v, v + n-1);
//shortSort(v, 0, n - 1);
//int mark1, mark2;
//int mid = Get2Mark(v, mark1, mark2, 0, n-1);
//ms_qsort(v, 0, n - 1);
std::qsort(v, n, sizeof(int), cmpInt);
double tms2 = GetTickCountA();
cout << "-----------------------------------------------------------" <<endl;
//for (int i = 0; i < n; i++)
{
//cout << v[i] << " ";
}
cout << endl;
cout << tms2 - tms1 << " ";
cout << "ok" << endl;
delete[]v;
}
总结:
简化后之所以比std::qsort快,是因为比较部分都是直接比较,没有调用函数开销。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)