无聊闲做，从使用PHP数组实现约瑟夫环问题谈性能

时间：2010-10-18 来源：xin478

问题大概这样子：一群猴子排成一圈，按 1,2,...,n 依次编号。然后从第 1 只开始数，数到第 m 只,把它踢出圈，从它后面再开始数，再数到第 m 只，在把它踢出去...，如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入 m、n, 输出最后那个大王的编号。

脑子比较直，所以第一个想法就是这n只首尾相接排成环状的猴子，不就是一个环状链表吗？用C的话，马上就是这个概念了。但是PHP里面没有这东西，也不能定义结构体，如果用类来实现，实际上开销有点大好像。剩下来现成点的就是数组了，虽然php中的数组实际上就是哈希表，开销也远大于C中的数组，不过，能想到的就是这家伙了。

原来的兄弟是用prev,next等函数来操作，但是顾名思义，prev、next每次它只能前进一步、后退一步，这样实际上就无法避免要使用循环，例如往后6个，就要运行6次的next，所以，在性能上是不划算的。很抱歉，我是用虚拟主机用惯的人，太过计较一点性能上的浪费，没办法，苦日子过惯了，见不得奢侈。

先申明一点，我并没有任何别的意思，原来的兄弟也说了只是想实现下并未注重算法性能。

换一个角度看，假设说现在圈里面有5个人，我们要数12个，那么我们真的要一个一个去数，数6下？不要吧，相信大家都知道只要数2个，因为其中的10次实际上就是对圈里的5人数了2圈，在这期间，没有人会被踢出去，换句话说，这10次就是白数的。真正决定的，是后面的2次，所以，换一个方法如下：

function getKingMonkey1($n,$m)
{
    $a=range(1,$n); //声明一个包含n个元素的数组
    $c=$n;  //记录当前圈子中的人数
    $t=0;    //开始数数的位置
    while($c>1)  //圈中剩一个就结束
    {
        $t=$m%$c+$t;
        if($t>$c) $t=$t%$c;
        $t=$t>0?--$t:0;
        array_splice($a,$t,1);  //将不幸的兄弟踢出去
        --$c;   //圈中人数减一
        if($t==0) $t=$c;
    }
    return reset($a);
}

这个是原来的兄弟写的

//转自http://www.cnblogs.com/catprayer/archive/2010/10/04/1842085.html
function getKingMonkey($n, $m) 
{ 
    $a = array();//声明内部数组 
    for($i = 1; $i <= $n; $i ++) 
    { 
        $a[$i] = $i;//这一步是对号入座 
    } 
    reset($a);//为了严谨，我们来一个 reset() 函数，其实也可以省去 
    while(count($a) > 1)//主循环开始，这里使用的判别条件是数组元素的个数等于 1 的时候停止循环 
    { 
        for($counter = 1; $counter <= $m; $counter++)//嵌套的 for 循环，用来“踢出”数到 m 的猴子 
        { 
            if(next($a)){//如果存在 next 元素 
                if($counter == $m) 
                { 
                    unset($a[array_search(prev($a), $a)]);//当数到 m 时，使用 unset() 删除数组元素 
                } 
            } 
            else//如果不存在 next 元素 
            { 
                reset($a);//则数组的第一个元素充当 next 元素 
                if($counter == $m) 
                { 
                    unset($a[array_search(end($a), $a)]);//当数到 m 时，使用 unset() 删除数组元素，注意这里是 end() 
                    reset($a);//记得让数组内部指针“归位” 
                } 
            } 
        } 
    } 
    return current($a); 
}

一、首先，用for循环为数组赋连续的值，是不划算的，用内置的range函数，就可以实现。

二、尽量避免多次调用count来获取数组数量，php中获取数组数量的方法和c#中不同，不如其高效，多次使用时，请使用局部变量来记录

三、在逻辑结构允许的情况下，++$t远比$t--来的合算，因为这点上，php是特殊的，像$t++,$t--这类的结构，它内部实际上多使用了一个局部变量来记录原值，所以，要多执行一个opcode

四、至于为什么踢出去的时候，使用array_splice而不用unset呢？虽然unset属于语法结构，速度远比array_splice这种函数调用来的快，也都是可以将数组中的一个元素移除，但是，他们还是有不同之处。array_splice在移除数组的同时，会更改其后面索引类型为数字的元素的索引，而unset则不会。如

$a=array(0,1,'a'=>4,2,3,4,5,6);
array_splice($a,1,1);

则结构就由原来的
array
  0 => int 0
  1 => int 1
  'a' => int 4
  2 => int 2
  3 => int 3
  4 => int 4
  5 => int 5
  6 => int 6
变为:
array
  0 => int 0
  'a' => int 4
  1 => int 2
  2 => int 3
  3 => int 4
  4 => int 5
  5 => int 6

换句话说，就是array_splice在移除元素之后，会对索引做一个重排，所以，在不影响使用的情况下，尽量使用unset来取代array_splice，即使是一次需要移除多个元素的情况。我这里要它重排下，所以只能依了它。

最终，运行的结果如下

在10人中数6人的情况

在人数及数人的数量增多的情况下，循环带来的开销会更明显，例如100人数81

也是过苦日子的兄弟，可以参考优化php代码的40条建议