数据结构和算法 - 为什么复杂的算法都用java或者c来实现而不是使用php这样子都脚本语言？

Question

为什么复杂的算法都用java或者c来实现而不是使用php这样子都脚本语言？

Answer 1

我觉得先用PHP实现，然后用C写也是可以的，毕竟写的时候要不断验证，这时PHP不需要编译、弱类型都是优势，等写好了再用C重写实现高性能，比如这是国人用PHP写的一个红黑树算法：

<?php
/*
红黑树是算法导论中最复杂的算法之一.
实际上虽然需要处理的情况很多,但处理的过程和步骤都是固定的,是一些早已被验证的方法,
所以尽管看起来有些复杂,实际处理的时候按照单个case来观察的话则很简单.
下面的php代码是按照算法导论中的描述写的.
*/
class RBTree
{
    public $root;
    public $nil;//哨兵
    
    public function __construct()
    {
        // construct the sentinel
        $this->nil = array("left" => null ,"right" => null,"parent" => null,"color" => "BLACK","isnil" => true,"data" => "sentinel");// data 无意义
        
        // set sentinel as the root
        $this->root = &$this->nil;
        
    }
    
    public function Isnil(&$n)
    {
        return $n["isnil"];
    }
    
    // 按照算法导论
    /* 
    
    PHP 里面没有引用这回事,只有别名,引用本身是一种类型,但是别名则不是一种类型
    别名赋值给另外一个变量并不使其成为一个别名,而引用赋值另一个变量,那个变量也是引用
    PHP中变量名都是别名
    $a = 1;
    $b = &a;
    $a 和 $b 地位一样
    
    别名就如同指针一样,但又有区别
    
    REB BLACK TREE初始化的时候sentinel会作为root
    sentinel相当于NULL节点,树中所有在bst中为NULL的指针均指向sentinel ,包括root的parent指针
    */
    public function insert($n)
    {
        $y = &$this->nil;
        $x = &$this->root;//root是一个引用,$x仍然是引用并且引用正确的对象吗?, $y = $x = $this->root $y仍然引用那个对象?
        //看起来实际情况是 $x 得到的是root所引用对象的拷贝,最终$y也拷贝了一份
        
        while( !$this->Isnil($x) )
        {
            $y = &$x;//每次进入新的子树,y代表root,第一次循环的时候,y会代表root,同时如果循环一次也未运行,y可以检测到树为空
            if ($n["data"] < $x["data"])
                $x = &$x["left"];
            else
                $x = &$x["right"];
        }
        
        
        
        if( $this->Isnil($y))
            $this->root = &$n;
        else if( $n["data"] < $y["data"] )
            $y["left"] = &$n;
        else
            $y["right"] = &$n;
            
        $n["parent"] = &$y;    
        $n["left"] = &$this->nil;//新加入的节点的right left都指向sentinel
        $n["right"] = &$this->nil;
        $n["color"] = "RED";
        $n["isnil"] = false;
        
        $this->insertFixup($n);
        
    }
    
    public function insertFixup(&$node)         
    {    
        
        $n = &$node;
        while ( $n["parent"]["color"]  == "RED" )
        {
            //echo "calling inserFixup,do actually fixup:".$n["data"]."parent:".$n["parent"]["data"]."(".$n["parent"]["color"].")n";
            // php 中如何表示两个别名指向同一块内存
            // 实际上比较两个别名,PHP是比较它们所指向的值,
            // 如果有两块内存,存放了相同的东西,实际上它们的引用应该是不同的
            // 但是PHP里面会认为相同
            
            // 如果两个引用指向了不同的位置,但是其内容相等,应该有机制可以区别这两个引用
            // 但是PHP是没有的
            
            // PHP中似乎不能直接比较两个引用,一旦比较必然是比较变量本身,
            
            $tmp = &$n["parent"]["parent"];
            if( $n["parent"]["data"] == $tmp["left"]["data"] )
            {
                $y = &$n["parent"]["parent"]["right"];// uncle
                //if uncle is red
                if( $y["color"] == "RED" )
                {
                    $n["parent"]["color"] = "BLACK";
                    $y["color"] = "BLACK";// SET UNCLE to black
                    $n["parent"]["parent"]["color"] = "RED";
                    $n = &$n["parent"]["parent"];
                }
                else  //case 2
                {
                    if ( $n["data"] == $n["parent"]["right"]["data"] )
                    {
                        $n  = &$n["parent"];//将n指向其parent ,然后left rotate
                        $this->leftRotate($n);
                    }
                    $n["parent"]["color"] = "BLACK";
                    $n["parent"]["parent"]["color"] = "RED";
                    $this->rightRotate($n["parent"]["parent"]);                    
                }
            }
            else // 对称的, n的parent是一个right child
            {
                $y = &$n["parent"]["parent"]["left"];// uncle
                //if uncle is red
                if( $y["color"] == "RED" )
                {
                    $n["parent"]["color"] = "BLACK";
                    $y["color"] = "BLACK";// SET UNCLE to black
                    $n["parent"]["parent"]["color"] = "RED";
                    $n = &$n["parent"]["parent"];
                }
                else  //case 2
                {
                    if ( $n["data"] == $n["parent"]["left"]["data"] )
                    {
                        // 如果n是一个 left child
                        $n  = &$n["parent"];
                        $this->rightRotate($n);
                    }
                    $n["parent"]["color"] = "BLACK";
                    $n["parent"]["parent"]["color"] = "RED";
                    $this->leftRotate($n["parent"]["parent"]);                    
                }            
            }
        }
        
        $this->root["color"] = "BLACK";
    }
    
    /*
                         n
                        / 
                       a   y
                          / 
                         b   c

                          y
                         / 
                        n   c
                       / 
                      a   b
    */
    public function leftRotate(&$n)
    {
        $y = &$n["right"];
        $n["right"] = &$y["left"];
        
        if ( !$this->Isnil($y["left"]) )
        {
            $y["left"]["parent"] = &$n;
        }
        
        $y["parent"] = &$n["parent"];
        
        if ( $this->Isnil($n["parent"]) )
        {
            $this->root = &$y;
        }
        else if ( $n["data"] == $n["parent"]["left"]["data"] )//Fatal error: Nesting level too deep - recursive dependency?
        {
            $n["parent"]["left"] = &$y;
        }
        else
        {
            $n["parent"]["right"] = &$y;
        }
        
        $y["left"] = &$n;
        $n["parent"] = &$y;
        
    }

    /*
                         n
                        / 
                       y   a
                      / 
                     b   c

                          y
                         / 
                        b   n
                           / 
                          c   a
    */
    public function rightRotate(&$n)
    {
        $y = &$n["left"];
        $n["left"] = &$y["right"];
        
        if ( !$this->Isnil($y["right"]) )
        {
            $y["right"]["parent"] = &$n;
        }
        
        $y["parent"] = &$n["parent"];
        
        if ( $this->Isnil($n["parent"]) )
        {
            $this->root = &$y;
        }
        else if ( $n["data"] == $n["parent"]["left"]["data"] )
        {
            $n["parent"]["left"] = &$y;
        }
        else
        {
            $n["parent"]["right"] = &$y;
        }
        
        $y["right"] = &$n;
        $n["parent"] = &$y;
        
    }
    
    // 按照数据结构和算法分析里面的操作
    public function delete($data,&$r)
    {
        if ( $r == null )
            return;//没有找到节点,或者视图从一个空树中删除节点
        if ( $data < $r["data"] )
            $this->delete( $data, $r["left"] );
        else if ( $data > $r["data"] )
            $this->delete( $data, $r["right"] );
        else if ( $r["left"] != null && $r["right"] != null )
        {
            //往下的都是$data == $r["data"] ,找到节点,而且其左右均不为空
            
            $min =  $this->findMin( $r["right"] );// y replace z , 
            $r["data"] = $min["data"];
            $this->delete( $r["data"] , $r["right"]);//delete y which in z's right subtree
        }
        else
        {
            //找到,但是该节点最多只有一个child
            $r = ( $r["left"] != null ) ? $r["left"] : $r["right"];
        }
    }
    
    // 检测是否违反红黑树性质, 用于测试插入和删除
    public function checkerror()
    {
        if($this->root["color"] == "RED")
        {
            echo "root must be black n";
            return;
        }
        
        
    }
    
    public function transplant(&$u,&$v)
    {
        if ( $this->Isnil($u["parent"]) )
            $this->root = &$v;
        else if ( $u["data"] == $u["parent"]["left"]["data"] ) // whats wrong with the php
            $u["parent"]["left"] = &$v;
        else
            $u["parent"]["right"] = &$v;
            
        $v["parent"] = &$u["parent"];
    }
    
    public function delete2($data,&$r)
    {
        if ( $this->Isnil($r)  )
            return ;//没有找到节点
        if ( $data < $r["data"])
            $this->delete2( $data, $r["left"] );
        else if ( $data > $r["data"] )
            $this->delete2( $data, $r["right"] );
        else
        {
            // we find the node , now we can call the algorithm in introduction to algorithm
            $y = &$r;
            $y_origin_color = $r["color"];
            
            if ( $this->Isnil($r["left"]) )
            {
                // simulator the transplant z , z.right
                // 我们没有改变指针间的关系,而是直接改变了变量的内容,将z所在的变量用z.right覆盖
                // 在C++的实现中r是指针的引用,指向某个Node,这个引用的对象是parent的right或left
                // 在那里是修改指针的内容为z.right,
                // 但是PHP里面引用就代表变量本身,我们parent.left只是一个别名,别名实际上等于变量名
                // 我们实际上没有得到parent的right 或 left,而是得到了一个和他等价的,也就是指向同一个变量的变量名
                // 所以我们无法改变引用本身,只能改变其所指向的变量
                $x = &$r["right"];
                $this->transplant($r,$r["right"]);
                //相当于transplant
                
            }
            else if( $this->Isnil($r["right"])  )
            {
                $x = &$r["left"];
                $this->transplant($r,$r["left"]);
            }
            else
            {
                // 有两个 child
                
                $y =  &$this->findMin( $r["right"] ); // 加& 得到节点的引用
                $y_origin_color = $y["color"];
                echo "y.data is ".$y["data"]." ".$r["data"]."n";
                
                // y has no left child
                $x = &$y["right"];
                
                if ( $y["parent"]["data"] == $r["data"]) 
                {
                    // y 是r的直接child
                    $x["parent"] = &$y;// x could be sentinel , x will 取代y的位置
                } else
                {
                    // y 是right subtree中的某个节点
                    // 要用 y的right 取代y的位置
                    $this->transplant($y,$y["right"]);//因为PHP不是按照指针来区别节点的,因此如果y有两个sentinel节点,transplant函数会失效
                    
                    $y["right"]  = &$r["right"];
                    $y["right"]["parent"] = &$y; // 这里的right不是y原来的parent,而是来自r的 right,对transplant的继续
                    
                }
                
                $this->transplant($r,$y);
                $y["left"] = &$r["left"];//继续y取代r的步骤
                $y["left"]["parent"] = &$y;// left could be sentinel
                $y["color"] = $r["color"];
                

                
            }
        }
        
        if ( $y_origin_color == "BLACK" )
            $this->deleteFixup($x);
    }
    
    /*
    这里要讨论一下,是否会出现,x的parent的两个孩子都是nil的情况
    不可能,因为x的doubly black, 如果x是sentinel,那么x.parent的另一个节点绝不可能是sentinel too
     
                                     p
                                    / 
                                   x   sentinel
    这样的话,从到x的black节点比p到sentinel要多,
    因此
    if ( $x == $x["parent"]["left"] )
    总会得到正确的结果
    */
    public function deleteFixup(&$x)
    {
        while ( $x["data"] != $this->root["data"] && $x["color"] == "BLACK" )        // nest level too deep
        {
            // X is a doubly black
            if ( $x["data"] == $x["parent"]["left"]["data"] ) // nest level too deep
            {
                // 如果x是sentinel,而x是right child,而parent也有一个sentinel的left child,
                // 那么这个判断会失效
                // 发现如果x是sentinel,那么无法判断x是left 还是right
                
                $s = &$x["parent"]["right"]; // sibling
                if (  $s["color"] == "RED" )
                {
                    $s["color"] = "BLACK";
                    $x["parent"]["color"] = "RED";
                    $this->leftRotate($x["parent"]);
                    $s = $x["parent"]["right"];// sibling , now  the sibling is BLACK , not introduce any violation , transform to case 2
                }
                
                if ( $s["left"]["color"] == "BLACK" && $s["right"]["color"] == "BLACK" )
                {
                    $s["color"] = "RED";
                    $x = &$x["parent"];// float up the x , go back to the while iteration , the loop invariant : x is doubly or red blck node hold
                }
                else 
                {
                    if( $s["right"]["color"] == "BLACK" )
                    {
                        // SIBLING IS BLACK , 并且sibling的两个child不同时是BLACK , 如果right是BLACK ,left 一定是RED
                        // 操作是transform到 case 4
                        
                        $s["left"]["color"] = "BLACK";
                        $s["color"] = "RED";// exchange s and s.left , then rightRotate
                        $this->rightRotate($s);
                        $s = &$x["parent"]["right"];
                        // now ,sibling is black ,and sibling has a RED right child , is case 4
                    }
                    
                    // into case 4
                    
                    $s["color"] = $x["parent"]["color"];
                    $x["parent"]["color"] = "BLACK";// SIBLING D PARENT 和 sibling 交换眼色
                    // 等价于
                    //$s["parent"]["color"] = "BLACK";,因为事先知道s的color,因此交换无须中间变量
                    $s["right"]["color"] = "BLACK";// 因为下面要rotate,经过right的路径会减少一个BLACK,因此将right改成黑色
                    $this->leftRotate($x["parent"]);
                    $x = &$this->root;// 完成
                }
            }
            else
            {
                // 如果x是sentinel,而x是right child,而parent也有一个sentinel的left child,
                // 那么这个判断会失效
                // 发现如果x是sentinel,那么无法判断x是left 还是right
                
                $s = &$x["parent"]["left"]; // sibling
                if (  $s["color"] == "RED" )
                {
                    $s["color"] = "BLACK";
                    $x["parent"]["color"] = "RED";
                    $this->rightRotate($x["parent"]);
                    $s = $x["parent"]["left"];// sibling , now  the sibling is BLACK , not introduce any violation , transform to case 2
                }
                
                if ( $s["right"]["color"] == "BLACK" && $s["left"]["color"] == "BLACK" )
                {
                    $s["color"] = "RED";
                    $x = &$x["parent"];// float up the x , go back to the while iteration , the loop invariant : x is doubly or red blck node hold
                }
                else 
                {
                    if( $s["left"]["color"] == "BLACK" )
                    {
                        // SIBLING IS BLACK , 并且sibling的两个child不同时是BLACK , 如果right是BLACK ,left 一定是RED
                        // 操作是transform到 case 4
                        
                        $s["right"]["color"] = "BLACK";
                        $s["color"] = "RED";// exchange s and s.left , then rightRotate
                        $this->leftRotate($s);
                        $s = &$x["parent"]["left"];
                        // now ,sibling is black ,and sibling has a RED right child , is case 4
                    }
                    
                    // into case 4
                    
                    $s["color"] = $x["parent"]["color"];
                    $x["parent"]["color"] = "BLACK";// SIBLING D PARENT 和 sibling 交换眼色
                    // 等价于
                    //$s["parent"]["color"] = "BLACK";,因为事先知道s的color,因此交换无须中间变量
                    $s["left"]["color"] = "BLACK";// 因为下面要rotate,经过right的路径会减少一个BLACK,因此将right改成黑色
                    $this->rightRotate($x["parent"]);
                    $x = &$this->root;// 完成
                }
            }
        }
        
        $x["color"] = "BLACK";
    }
    
    public function & findMin( &$r )
    {
        if ( $this->Isnil($r) )
            return null;
        if ( $this->Isnil($r["left"]) )
            return $r;
        return $this->findMin($r["left"]);//此处不加&,返回的也是别名而不是拷贝
    }
    
    //按层,从左到右输出
    public function printTree()
    {
        // 存储一个数组,是上一层的全部树根
        $roots = array();
        
        //初始只包含树根
        $roots[] = $this->root;
        
        $this->printTreeRecursion($roots);
    }
    
    public function printTreeRecursion($roots)
    {
        $nextroots = array();//当前层的所有节点的left right 组成的数组
        
        if( count($roots) == 0 )//退出条件,某层为空
            return;
        
        for( $i = 0 ; $i < count($roots); $i++ )
        {
            if( $roots[$i] != null)
            {
                echo $roots[$i]["data"]." ";
                $nextroots[] = $roots[$i]["left"];
                $nextroots[] = $roots[$i]["right"];
            }            
        }
        echo "n";//end of current layer
        
        
        $this->printTreeRecursion($nextroots);
    }
    
    public function printTreePreorder(&$r,$d)
    {
        for( $i = 0 ; $i < $d * 2 ; $i++ )
            echo " ";
        
        if( $this->Isnil($r))    
            echo "nilln";
        else
            echo $r["data"]."(".$r["color"].") PARENT:".$r["parent"]["data"]."n";
        
        if( $this->Isnil($r))
            return;
        $this->printTreePreorder($r["left"],$d+1);
        $this->printTreePreorder($r["right"],$d+1);
    }
    
    // 中序可按顺序输出,中间的某个元素是跟
    // 这个元素的左边所有元素是其左树,右边全部是其右树
    public function printTreeInorder(&$r,$d)
    {
        if ( $r != null )
            $this->printTreeInorder($r["left"],$d+1);

        for( $i = 0 ; $i < $d * 2 ; $i++ )
            echo " ";
        
        if( $r == null)    
            echo "nilln";
        else
            echo $r["data"]."n";
        
        if( $r != null)            
            $this->printTreeInorder($r["right"],$d+1);
    }

}

$rbt = new RBTree();
echo "hahn";
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 1));
echo "hahn";
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 2));
echo "hahn";
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 3));
echo "hahn";
//$rbt->printTreePreorder($rbt->root,0);
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 4));//执行此处的时候出了问题
echo "hahn";
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 5));

$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 6));

$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 7));

$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 8));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 9));
//$rbt->printTreePreorder($rbt->root,0);

$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 23));

//$rbt->printTreePreorder($rbt->root,0);
/*
下面插入12之后,红黑树被破坏了
之前的树

                          4B
                        /   
                       2B    6B
                      /    /  
                     1B  3B 5B  8R
                               /  
                              7B   9B      
                                    
                                    23R


正确的做法应该是12 会加到 23的left child, RED RED 冲突
uncle是BLACK,z本身是left child,我们应该做一个right rotate

                          4B
                        /   
                       2B    6B
                      /    /  
                     1B  3B 5B  7B
                                  
                                  9B      
                                 /  
                                8R  23R   
                                   /
                                  12R

正确的结果应该是

                          4B
                        /   
                       2B    6B
                      /    /  
                     1B  3B 5B  8R
                               /  
                               7B  12B      
                                  /  
                                 9R  23R   
                                  
*/
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 12));
//$rbt->printTreePreorder($rbt->root,0);
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 10));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 24));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 28));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => -12));
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => -5));
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => -20));
//$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => -3));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 102));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 90));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 72));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 720));
$rbt->insert(array("left" => null,"right" => null,"parent" => null,"color" => "RED","isnil" => false,"data" => 121));
$rbt->printTreePreorder($rbt->root,0);

$rbt->delete2(4,$rbt->root);

$rbt->delete2(5,$rbt->root);

$rbt->delete2(8,$rbt->root);
$rbt->delete2(24,$rbt->root);
$rbt->delete2(28,$rbt->root);
$rbt->delete2(9,$rbt->root);
$rbt->delete2(6,$rbt->root);
$rbt->delete2(12,$rbt->root);
echo "hahan";
$rbt->printTreePreorder($rbt->root,0);

//finishing

//  红黑树在实际使用的时候,似乎会倾向于像右边倾斜
?>

Answer 2

算法是什么？
教科书说

Algorithm是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
再读一遍，发现什么？

我发现了
1. 算法是一个解决问题的方案，你乐意的话，完全可以用中文描述出来，中文写出来的人类语言那也是算法。
2. 算法跟计算机没有必然联系关系，没有发明计算机，世界上仍旧会有算法的问题。
3. 计算机发扬了算法，让算法得意引用，计算机语言就是算法的计算机表述。
4. 因此你用任何语言都可以实现

上面都是废话，那我切入正题吧。

为什么复杂的算法都用java或者c来实现而不是使用php这样子都脚本语言？
首先： 这个问题有bug。
"都用"是你主管臆断，其实js，python实现的算法有很多。
那多用c，或者java的原因是？

• c和java程序员多
• c就是编程界的English，属于通用语言，到哪儿都可以被人读懂，并且顺利的翻译为任何语言。
• 数学好的人，少会js，php，因为js和php都属行业语言，太局限某个领域，例如离开了互联网，php有什么优势？js有什么优势呢？
• 复杂算法的关注人群大多对性能有追求，因此用C不是很合乎逻辑么？