哇擦，传说中的堆栈溢出和快速排序

stack overflow

堆栈溢出和快速排序这两个概念对开发人员来说并不陌生，但是通知都只是听说过，真正开发过程中却很少会遇到。我也是敲代码好些行后非常有幸撞上了，而且还是两个一起出现的，这其中过程的滋味还是相当酸爽，值得回味。

问题背景：

某项目中有个POI离线检索功能，比如搜索附近的加油站，底层引擎逻辑提供了一个C函数。

输入：经纬点，搜索范围半径，搜索类别。

输出：按照距离由近到远排好序的POI结果列表。

这是一个C函数，是同步接口，所以我在OC 上层做了一次封装，改成了异步调用，在子线程中执行。

问题现象：

（1）如果搜索加油站，酒店等匹配结果数据较少的类型，功能正常；

（2）如果搜索饭店，酒店这种匹配结果较多的类型时，则会导致程序Crash。Crash时线程堆栈显示crash在搜索子线程，Crash对应的代码行不固定，每次crash时都不一样，略诡异，但是都是Crash在对搜索结果进行快速排序的那个快排函数中；

（3）如果我减少搜索范围的半径，再搜索饭店或者酒店时，功能又正常了。

问题分析：

（1）只有检索结果列表中元素比较多的时候才出现问题，元素较少时功能正常；

（2）快速排序函数是非常标准的实现，而且大多数类别的搜索都是正常的，所以应该可以排除嫌疑。但是Crash线程调用堆栈却显示挂在了快速排序函数里面。说明函数的执行环境有问题；

快速排序函数代码

（3）该函数是放在子线程中执行的。难道是子线程默认堆栈空间太小，快速排序递归层级过多时因为堆栈溢出导致crash？  特意查了一些苹果官方文档，

apple堆栈大小说明

iOS系统中子线程默认堆栈大小是512K，果然比较小。

问题解决方案：

（1）直接增大子线程的堆栈大小。我用的是Cocoa的线程NSThread，直接通过setStackSize方法配置线程堆栈大小，需要注意的是配置的stacksize最小值是16k，而且必须是4K的整数倍。需要在线程开始执行之前进行配置（NSThread 对象的start方法调用之前）。

调整堆栈大小

（2）对快速排序做优化。

问题总结：

1、关于堆栈溢出

一般情况下应用程序是不需要考虑堆和栈的大小的，但是事实上堆和栈都不是无上限的，过多的递归会导致栈溢出，过多的alloc变量会导致堆溢出。默认情况下iOS主线程1M，子线程512K。

iOS 应用程序执行时内存布局如下图所示：

内存空间

在应用程序分配的内存空间里面，最低地址位是固定的代码段和数据段，往上是堆，向上生长，用来存放全局变量，对于 ObjC对象 来说，就是 alloc 出来的变量，都会放进这里，堆不够用的时候就会往上申请空间。最顶部高地址位是栈，向下生长，局部的基本类型变量都会放进栈里，函数调用时参数、返回地址等信息都是放在栈里。 ObjC 的对象都是以指针进行操控的，局部变量的指针都在栈里，全局的变量的指针在堆里。

所以预防堆栈溢出的方法：

（1）避免层次过深的递归调用；

（2）不要使用过多的局部变量，控制局部变量的大小；

（3）避免分配占用空间太大的对象，并及时释放;

（4）实在不行，适当的情景下调用系统API修改线程的堆栈大小；

2、关于快速排序的优化

快速排序是数据结构课程中介绍的最基础的一种算法。这里单独拿出来聊这个话题，主要是想强调两个事情，第一，基础真的很重要；第二，基础算法在实际编程中确实可能用到不多，大部分情况下都是直接调用系统的封装好的接口即可，但并不代表不会遇到，并且校招面试中出现几率也是比较大的。

关于快速排序的优化，百度里面一搜能找到很多方法，甚至还有不少人用这个题目来写各种小论文。我这里也简单分享一下我觉得比较容易实现且效果较好的方法。

我们先看看快速排序的标准教科书实现：

快速排序标准实现

改进措施如下：

（1）中枢值的选取。这个很显然，如果每次都选中实际大小中中间的那个值，那么就能达到最优的排序效果，避免最坏的情况的;

（2）划分的最小数列长度。因为快速排序是对子序列不停递归的一个过程（分治法）。所以如果递归的过多，堆栈带来的性能损失也是不容小视的。还有最重要的一点就是在数据量很小的情况下，插入排序在时间上的性能要比快速排序的性能要好，所以当子序列长度小于某阈值时，调整为插入排序；

（3）对是否交换做标记，如果全过程没有发生交换，直接返回就可以了；

（4）栈的深度。要优先对小的数组进行排序，这样可以减少递归调用栈的深度。

改进后的伪代码如下:

快速排序改进 快速排序改进

当然，用非递归的方式来实现快速排序或者去掉尾递归也是另外一种思路的优化，感兴趣的同学可以去尝试一下。