Dijkstra算法優化/緩存

Question

我有以下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"); ?> 

Answer 1

微的優化，但不做：

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）loop ...檢索單個SQL查詢中的所有數據並構建查找數組。

與

$nextStopArraySize = sizeof($nextStopArray); 
$p = -1 
while (++$p < $nextStopArraySize) { 
    ... 
} 

更換

for ($p = 0; $p < sizeof($nextStopArray); $p++) { 

也證明仍然快（只需檢查邏輯通過正確的次數不循環）。

Answer 2

一覽（你應該做一些剖析，順便說一句），罪魁禍首就是您正在執行的每個圖節點的查詢來查找其鄰國的事實：

$result=mysql_query("SELECT route_id, next_stop FROM db_stop_times WHERE stop_id = $activeNode", $connection); 

如果你有這將在一千個查詢的順序上發佈1,700個節點。而不是頻繁地點擊數據庫，將這些數據庫結果緩存到類似memcached之類的地方，並且僅在緩存未命中時纔回退到數據庫。

Answer 3

它使用了太多的資源

哪些資源？ （CPU？內存？網絡帶寬？數據庫服務器上的I/O負載？）

while (true) {  
    $result=mysql_query("SELECT route_id, next_stop FROM db_stop_times WHERE stop_id = $activeNode", $connection); 

如果我正在閱讀這個權利，您將在每個尋路嘗試中爲每個節點進行一次數據庫調用。這些調用中的每一個都會等待數據庫的響應。即使你擁有一個快速的數據庫，這也必然需要幾毫秒（除非數據庫與你的代碼在同一臺服務器上運行）。所以我敢打賭，大部分執行時間都花在等待數據庫回覆上。

而且，如果你的數據庫缺乏適當的索引，每個查詢可以做一個全表掃描...

解決辦法很簡單：負載db_stop_times到在應用程序啓動的內存，並解決當使用內存中表示鄰居節點。

編輯：是的，stop_id上的索引將是該查詢的適當索引。至於實際的緩存，我不知道PHP，但像Java（或C＃或C++，甚至C）我會使用形式的表示

class Node { 
    Link[] links; 
} 

class Link { 
    int time; 
    Node destination; 
} 

這將是一個有點快比memcached，但假設你可以舒適地適合整個表在主內存。如果你不能這樣做，我會使用像memcached這樣的緩存系統。