Алгоритм Dijkstra оптимизация / кеширование - PullRequest
2 голосов
/ 18 февраля 2011

У меня есть следующий алгоритм Дейкстры с 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"); ?>

Ответы [ 3 ]

4 голосов
/ 18 февраля 2011

Микрооптимизации, но не делают:

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

вычисляют sizeof ($ nextStopArray) перед циклом, иначе вы делаетеподсчитывать каждую итерацию (и это значение не изменяется)

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

Есть пара мест, где это следует изменить.

И если вы выполняете итерацию несколько тысяч раз,++ $ p быстрее, чем $ p ++

Но профилируйте функцию ... выясните, какие части выполняются дольше всего, и попытайтесь оптимизировать их.

EDIT

Избавьтесь от array_push_key как функции, просто запустите его встроенным ... в противном случае это обойдется вам ненужным вызовом функции

Создайте массив всех узлов из вашей базы данных вне времени(истинный) цикл ... извлечение всех данных в одном запросе SQL и построение поискового массива.

Замена

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

на

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

также можетдоказать еще быстрее (просто убедитесь, что логика проходит через правильное числораз).

2 голосов
/ 18 февраля 2011

он использует слишком много ресурсов

Какой ресурс? (ЦП? Память? Пропускная способность сети? Нагрузка ввода-вывода на сервере базы данных?)

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.

2 голосов
/ 18 февраля 2011

С первого взгляда (кстати, вам действительно нужно выполнить некоторое профилирование), виновником является тот факт, что вы выполняете запрос для каждого узла графа, чтобы найти его соседей:

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

Если у вас есть 1700 узлов, это будет выдавать порядка тысячи запросов. Вместо того, чтобы часто обращаться к базе данных, кэширование этих результатов приводит к чему-то вроде memcached , и происходит откат к базе данных только при отсутствии кеша.

...