gpt4 book ai didi

php - Dijkstra算法优化/缓存

转载 作者:行者123 更新时间:2023-12-03 17:06:35 28 4
gpt4 key购买 nike

我有以下带有 3 个输入变量(开始、停止和时间)的 Dijkstra 算法。大约需要0.5-1s完成。我的托管服务提供商说它使用了太多资源,我应该实现一些缓存机制。我的问题是,怎么做?

因为我有 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) {
...
}

也可能证明速度更快(只需检查逻辑是否循环了正确的次数)。

关于php - Dijkstra算法优化/缓存,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5034623/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com