设计网站需要哪些流程,福州网站建设策划方案,企点,qq网页版在线直接登录stack overflow堆栈溢出和快速排序这两个概念对开发人员来说并不陌生#xff0c;但是通知都只是听说过#xff0c;真正开发过程中却很少会遇到。我也是敲代码好些行后非常有幸撞上了#xff0c;而且还是两个一起出现的#xff0c;这其中过程的滋味还是相当酸爽#xff0c;…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栈的深度。要优先对小的数组进行排序这样可以减少递归调用栈的深度。改进后的伪代码如下:快速排序改进快速排序改进当然用非递归的方式来实现快速排序或者去掉尾递归也是另外一种思路的优化感兴趣的同学可以去尝试一下。微信公众号云峰小罗分享 编程.生活.段子
