Heim >Backend-Entwicklung >PHP-Tutorial >数据结构和算法 - 为什么复杂的算法都用java或者c来实现而不是使用php这样子都脚本语言?
为什么复杂的算法都用java或者c来实现而不是使用php这样子都脚本语言?
为什么复杂的算法都用java或者c来实现而不是使用php这样子都脚本语言?
我觉得先用PHP实现,然后用C写也是可以的,毕竟写的时候要不断验证,这时PHP不需要编译、弱类型都是优势,等写好了再用C重写实现高性能,比如这是国人用PHP写的一个红黑树算法:
<code><?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"] Isnil($y)) $this->root = &$n; else if( $n["data"] 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 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 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 printTreeRecursion($nextroots); } public function printTreePreorder(&$r,$d) { for( $i = 0 ; $i 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 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 // 红黑树在实际使用的时候,似乎会倾向于像右边倾斜 ?> </code>
算法是什么?
教科书说
Algorithm是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。
再读一遍,发现什么?
我发现了
1. 算法是一个解决问题的方案,你乐意的话,完全可以用中文描述出来,中文写出来的人类语言那也是算法。
2. 算法跟计算机没有必然联系关系,没有发明计算机,世界上仍旧会有算法的问题。
3. 计算机发扬了算法,让算法得意引用,计算机语言就是算法的计算机表述。
4. 因此你用任何语言都可以实现
为什么复杂的算法都用java或者c来实现而不是使用php这样子都脚本语言?
首先: 这个问题有bug。
"都用"是你主管臆断,其实js,python实现的算法有很多。
那多用c,或者java的原因是?
- c和java程序员多
- c就是编程界的English,属于通用语言,到哪儿都可以被人读懂,并且顺利的翻译为任何语言。
- 数学好的人,少会js,php,因为js和php都属行业语言,太局限某个领域,例如离开了互联网,php有什么优势?js有什么优势呢?
- 复杂算法的关注人群大多对性能有追求,因此用C不是很合乎逻辑么?