我有以下Dijkstra算法,有3个输入变量(开始,停止和时间).完成需要大约0.5-1秒.我的托管服务提供商说它使用了太多资源,我应该实现一些缓存机制.我的问题是,怎么样?
因为我有3个变量,如果只有其中一个变化 – 整个结果是不同的(因为我有一些额外的陈述与时间,从来没有).那么如何实现一些缓存机制或做一些优化呢?
我有1700个节点.
<?PHP require_once("../includes/db_connection.PHP"); ?> <?PHP require("../includes/functions.PHP"); ?> <?PHP require("../includes/global_variables.PHP"); ?> <?PHP // Function to put "maxValues" into time (in my case 10 000 because I know it can't take longer than that from source to end node) function array_push_key(&$array,$key,$value) { $array[$key] = $value; } // Start the counter $timeM = microtime(); $timeM = explode(' ',$timeM); $timeM = $timeM[1] + $timeM[0]; $start = $timeM; // Get provided values $startStop = $_GET["start"]; $endStop = $_GET["end"]; $startTime = $_GET["time"]; // Initialize arrays $time = array(); $prevIoUsNode = array(); $allStops = array(); // [5] = 119 --> You can get to stop no. 5 by line no. 119 // line to source node is 0 $lineToThisStop = array(); $lineToThisStop[$startStop] = 0; // Populate arrays $result=MysqL_query("SELECT stop_id FROM db_stops",$connection); potvrdi_unos($result); $counter = 0; while($rows = MysqL_fetch_array($result)){ array_push_key($time,$rows["stop_id"],10000); array_push($allStops,$rows["stop_id"]); // Locate startStop in the allStops array to unset it few lines later if ($rows["id"] == $startStop) { $poz = $brojac; } $counter++; } // Set starting time to starting stop $time[$startStop] = $startTime; // Set it activeNode $activeNode = $startStop; // Unset it in allStops array (so it doens't have to be checked later) unset($allStops[$poz]); $allStops = array_values($allStops); // I can put "while (true)" because all nodes are connected in "one piece",there is NO UNCONNECTED nodes while (true) { $result=MysqL_query("SELECT route_id,next_stop FROM db_stop_times WHERE stop_id = $activeNode",$connection); potvrdi_unos($result); while($rows = MysqL_fetch_array($result)) { // Draw paths from active node to all other (connected) stops $nextStopArray = $rows["next_stop"]; // nextStopArray is something like "0,34,123,3123,213" - those are all stops from current,active node/stop $nextStopArray = explode(",",$nextStopArray); // sometimes it's just "4" to convert it into array if (!is_array($nextStopArray)) { $nextStopArray[0] = $nextStopArray; } for ($p = 0; $p < sizeof($nextStopArray); $p++) { $nextStop = $nextStopArray[$p]; $walkToTheStop = false; // Few checks if ($p == 0) { if ($nextStop != 0) { $pathDuration = 2; if ($lineToThisStop[$activeNode] != $rows["route_id"]) { $pathDuration = $pathDuration * 2; } } } else { $walkToTheStop = true; $pathDuration = 1; } // If that's shortest path from ActiveNode to nextStop insert it into it's time array (time to get to that stop) if (($pathDuration + $time[$activeNode]) < $time[$nextStop]) { $time[$nextStop] = $pathDuration + $time[$activeNode]; array_push_key($prevIoUsNode,$nextStop,$activeNode); // Some aditional records (5000 means "you must walk to that stop") if ($walkToTheStop) { $lineToThisStop[$nextStop] = 5000; } else { $lineToThisStop[$nextStop] = $rows["route_id"]; } } } } // Traži slijedeću stanicu (vrh) s najmanjom vrijednosti $lowestValue = 10000 + 1; for ($j = 0; $j < sizeof($allStops); $j++) { if ($time[$allStops[$j]] < $lowestValue) { $lowestValue = $time[$allStops[$j]]; $activeNode = $allStops[$j]; // Record it's position so I can unset it later $activeNodePosition = $j; } } // Unset the active node from the array - so loop before will be shorter every time for one node/stop unset($allStops[$activeNodePosition]); $allStops = array_values($allStops); // If you get to the end stop,feel free to break out of the loop if ($activeNode == $endStop) { break; } } // How long did it take? $timeM = microtime(); $timeM = explode(' ',$timeM); $timeM = $timeM[1] + $timeM[0]; $finish = $timeM; $total_time = round(($finish - $start),4); echo 'Total time '.$total_time.' seconds.'."<br />"; ?> <?PHP require_once("../includes/close_connection.PHP"); ?>
微观优化,但不做:
for ($p = 0; $p < sizeof($nextStopArray); $p++) { ... }
在循环之前计算sizeof($nextStopArray),否则你每次迭代都在计算(并且这个值没有被改变)
$nextStopArraySize = sizeof($nextStopArray); for ($p = 0; $p < $nextStopArraySize; ++$p) { ... }
有几个地方应该改变.
如果你迭代几千次,$p比$p快
但是要对功能进行分析……找出执行时间最长的部分,然后进行优化.
编辑
摆脱array_push_key作为一个函数,简单地执行它内联…它会花费你不必要的函数调用否则
在while(true)循环之外构建数据库中所有节点的数组…检索单个SQL查询中的所有数据并构建查找数组.
更换
for ($p = 0; $p < sizeof($nextStopArray); $p++) {
同
$nextStopArraySize = sizeof($nextStopArray); $p = -1 while (++$p < $nextStopArraySize) { ... }
也可能更快地证明(只需检查逻辑是否循环了正确的次数).