PHP 递归效率分析

而且是差了3倍的效率。所以，PHP中的递归一定要小心的对待。
最近写了一个快速排序的算法，发现PHP中的递归效率不能一刀切，在各种不同的服务器中，可能会表现不一样。


代码如下:

function qsort(&$arr)
{
_quick_sort($arr, 0, count($arr) - 1);
}

/**
* 采用递归算法的快速排序。
*
* @param array $arr 要排序的数组
* @param int $low 最低的排序子段
* @param int $high 最高的排序字段
*/
function _quick_sort(&$arr, $low, $high)
{
$low_data = $arr[$low];
$prev_low = $low;
$prev_high = $high;
while ($low < $high)
{
while ($arr[$high] >= $low_data && $low < $high) {
$high--;
}
if ($low < $high) {
$arr[$low] = $arr[$high];
$low++;
}
while ($arr[$low] <= $low_data && $low < $high) {
$low++;
}
if ($low < $high) {
$arr[$high] = $arr[$low];
$high--;
}
}
$arr[$low] = $low_data;
if ($prev_low < $low) {
_quick_sort($arr, $prev_low, $low);
}
if ($low + 1 < $prev_high) {
_quick_sort($arr, $low + 1, $prev_high);
}
}

function quick_sort(&$arr)
{
$stack = array();
array_push($stack, 0);
array_push($stack, count($arr) -1);
while (!empty($stack)) {
$high = array_pop($stack);
$low = array_pop($stack);
$low_data = $arr[$low];
$prev_low = $low;
$prev_high = $high;
while ($low < $high)
{
while ($arr[$high] >= $low_data && $low < $high) {
$high--;
}
if ($low < $high) {
$arr[$low] = $arr[$high];
$low++;
}
while ($arr[$low] <= $low_data && $low < $high) {
$low++;
}
if ($low < $high) {
$arr[$high] = $arr[$low];
$high--;
}
}
$arr[$low] = $low_data;
if ($prev_low < $low) {
array_push($stack, $prev_low);
array_push($stack, $low);
}
if ($low + 1 < $prev_high) {
array_push($stack, $low + 1);
array_push($stack, $prev_high);
}
}
}

下面是测试速度的代码：


代码如下:

function qsort_test1()
{
$arr = range(1, 1000);
shuffle($arr);
$arr2 = $arr;
$t1 = microtime(true);
quick_sort($arr2);
$t2 = microtime(true) - $t1;
echo "非递归调用的花费：" . $t2 . "\n";
$arr1 = $arr;
$t1 = microtime(true);
qsort($arr1);
$t2 = microtime(true) - $t1;
echo "递归调用的花费：" . $t2 . "\n";
｝

在我的IIS 服务器上（CGI）模式，我的测试结果是：
非递归调用的花费：0.036401009559631
递归调用的花费：0.053439617156982
在我的Apache 服务器上，我的测试结果是：
非递归调用的花费：0.022789001464844
递归调用的花费：0.014809131622314
结果完全相反，而PHP的版本是一样的。
看来对递归的效率要具体问题具体分析了。

赞 (0)

相关推荐

  • PHP 递归效率分析

    而且是差了3倍的效率.所以,PHP中的递归一定要小心的对待. 最近写了一个快速排序的算法,发现PHP中的递归效率不能一刀切,在各种不同的服务器中,可能会表现不一样. 复制代码 代码如下: function qsort(&$arr) { _quick_sort($arr, 0, count($arr) - 1); } /** * 采用递归算法的快速排序. * * @param array $arr 要排序的数组 * @param int $low 最低的排序子段 * @param int $hig

  • Python八大常见排序算法定义、实现及时间消耗效率分析

    本文实例讲述了Python八大常见排序算法定义.实现及时间消耗效率分析.分享给大家供大家参考,具体如下: 昨晚上开始总结了一下常见的几种排序算法,由于之前我已经写了好几篇排序的算法的相关博文了现在总结一下的话可以说是很方便的,这里的目的是为了更加完整详尽的总结一下这些排序算法,为了复习基础的东西,从冒泡排序.直接插入排序.选择排序.归并排序.希尔排序.桶排序.堆排序.快速排序入手来分析和实现,在最后也给出来了简单的时间统计,重在原理.算法基础,其他的次之,这些东西的熟练掌握不算是对之后的工作或者

  • C++ 多重继承和虚拟继承对象模型、效率分析

    C++ 多重继承和虚拟继承对象模型、效率分析

    一.多态 C++多态通过继承和动态绑定实现.继承是一种代码或者功能的传承共享,从语言的角度它是外在的.形式上的,极易理解.而动态绑定则是从语言的底层实现保证了多态的发生--在运行期根据基类指针或者引用指向的真实对象类型确定调用的虚函数功能!通过带有虚函数的单一继承我们可以清楚的理解继承的概念.对象模型的分布机制以及动态绑定的发生,即可以完全彻底地理解多态的思想.为了支持多态,语言实现必须在时间和空间上付出额外的代价(毕竟没有免费的晚餐,更何况编译器是毫无感情): 1.类实现时增加了virtual

  • PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】

    本文实例讲述了PHP四种排序算法实现及效率分析.分享给大家供大家参考,具体如下: PHP的四种基本排序算法为:冒泡排序.插入排序.选择排序和快速排序. 下面是我整理出来的算法代码: 1. 冒泡排序: 思路:对数组进行多轮冒泡,每一轮对数组中的元素两两比较,调整位置,冒出一个最大的数来. //简单版: function bubbleSort($arr) { $n = count($arr); for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮) for($j=0;$j<

  • c++ 前自增/后自增操作符效率分析

    c++ 前自增/后自增操作符效率分析

    1.前自增/后自增操作符示例 class Integer { public:     // ++i  first +1,then return new value     Integer &operator++()     {         value_ += 1;         return *this;     }       // i++  first save old value,then +1,last return old value     Integer operator++

  • php函数之strtr和str_replace的用法详解以及效率分析 原创

    目录 一. str_repalce()用法 二. strtr()用法 三. 效率对比 四. 总结 PHP中主要用strtr()和str_repalce()这两个函数替换字符串和数组,但你们都知道他们这两个函数的区别和用法吗?有不少文章在说使用strtr函数比str_replace快4倍,那为什么很多时候都在用str_replace,到底应该使用哪个函数呢? 一. str_repalce()用法 str_replace(find,replace,string,count)find:规定要查找的字符

  • Javascript 字符串字节长度计算函数代码与效率分析（for VS 正则）

    先看看一下两段代码吧,它们分别用for循环和正则表达式来检测字符串的字节长度: for循环检测字符串的字节长度方法一: 复制代码 代码如下: var lenFor = function(str){ var byteLen=0,len=str.length; if(str){ for(var i=0; i<len; i++){ if(str.charCodeAt(i)>255){ byteLen += 2; } else{ byteLen++; } } return byteLen; } els

  • 详解Mysql多表联合查询效率分析及优化

    1. 多表连接类型 1. 笛卡尔积(交叉连接) 在MySQL中可以为CROSS JOIN或者省略CROSS即JOIN,或者使用','  如: SELECT * FROM table1 CROSS JOIN table2 SELECT * FROM table1 JOIN table2 SELECT * FROM table1,table2 由于其返回的结果为被连接的两个数据表的乘积,因此当有WHERE, ON或USING条件的时候一般不建议使用,因为当数据表项目太多的时候,会非常慢.一般使用LE

  • sql中left join的效率分析与提高效率方法

    网站随着数据量与访问量越来越大,访问的速度变的越来越慢,于是开始想办法解决优化速度慢的原因 下面是对程序中一条sql的分析过程,当然程序的执行效率不单单是sql语句的问题,还有可能是服务器配置,网速,程序语言等各方法的问题,今天我们先来分析一下sql语句中left join的效率问题 sql语句中包含以下信息: 1.sql包含数据处理函数,比如nvl函数,case when函数等 2.sql中包含inner join,left join等关联关系 3.sql中有排序和分页 下面是分析过程 1.首

  • MYSQL 随机 抽取实现方法及效率分析

    复制代码 代码如下: 请教怎么从数据库随机读出15条记录? order by rand() limit 0,15 怎么从数据库随机读出所有记录? order by rand() 但是,后来我查了一下MYSQL的官方手册,里面针对RAND()的提示大概意思就是,在ORDER BY从句里面不能使用RAND()函数,因为这样会导致数据列被多次扫描.但是在MYSQL 3.23版本中,仍然可以通过ORDER BY RAND()来实现随机. 但是真正测试一下才发现这样效率非常低.一个15万余条的库,查询5条

随机推荐