Реализация приоритетных очередей в PHP
В своей предыдущей статье я сравнил производительность различных алгоритмов поиска маршрута, написанных на PHP.
Я показал, как алгоритм Дейктры может найти кратчайший путь во взвешенном ориентированном графе.
Этот конкретный алгоритм используется в широком диапазоне практических приложений от протоколов сетевой маршрутизации до навигации.
Один из способов уменьшить временную сложность алгоритма Дейкстры — использовать приоритетные очереди.
В информатике приоритетная очередь — это абстрактный тип данных, похожий на обычную очередь или структуру данных стека. Каждый элемент в очереди приоритетов имеет соответствующий приоритет. В очереди с приоритетом элементы с высоким приоритетом обслуживаются раньше элементов с низким приоритетом. — Википедия
Очередь с приоритетом сама по себе может иметь множество реализаций и применений, а также ограничение полосы пропускания и т. д.
В PHP можно использовать класс SplPriorityQueue или, например, Ds\PriorityQueue.
Это хорошие реализации общего назначения очереди с приоритетами, но им не хватает нескольких важных функций, которые мне понадобились для ускорения моего алгоритма Дейкстры.
«Хорошая» очередь с приоритетом должна иметь как минимум следующие методы для достижения нашей цели:
- add_with_priority: добавить элемент в очередь с заданным приоритетом
- уменьшение_приоритета: уменьшить приоритет данного элемента в очереди
- Extract_min: извлечь элемент с самым низким приоритетом из очереди
- содержит: проверить, находится ли данный элемент в очереди
Очереди с приоритетом не предназначены для поиска. Они предназначены для вставки и извлечения.
Если вам нужно искать в такой очереди, то это может быть очень дорогой операцией с точки зрения временной сложности.
Я решил поэкспериментировать с двумя подходами:
- реализация очереди приоритетов на основе массива
- и так называемая куча Фибоначчи
К счастью, куча Фибоначчи уже была реализована в PHP mathieuviossat
.
Вы можете получить доступ к его исходному коду здесь: https://github.com/viossat/fibonacci-heap.
Для начала я создал класс интерфейса, перечислив все необходимые методы:
interface PriorityQueue { public function append(int $item, int $priority); public function extract_min(); public function decrease_priority(int $item, int $newPriority); public function add_with_priority(int $item, int $priority); public function count(); public function contains(int $item); }
Начнем с приоритетной очереди на основе массива:
class ArrayPriorityQueue implements PriorityQueue { protected array $q = []; public function __construct() { // } // append an item to the end of our q without checking it's priority public function append (int $item, int $priority): void { $this->q[$item] = $priority; } public function extract_min(): int { asort($this->q); $min = array_key_first($this->q); unset($this->q[$min]); return $min === null ? 0 : $min; } public function decrease_priority(int $item, int $newPriority): void { if ($this->contains($item)) $this->q[$item] = $newPriority; } public function add_with_priority(int $item, int $priority): void { $this->q[$item] = $priority; } public function count(): int { return count($this->q); } public function contains(int $item): bool { return isset($this->q[$item]); } }
При подходе, основанном на массиве, мы поддерживаем очередь в массиве. Поскольку мы используем приоритетную очередь для алгоритма поиска по графу, ключи — это узлы, а значения — это приоритеты в нашем массиве.
Каждая операция выполняется за O(1), кроме extract_min.
Вместо того, чтобы постоянно поддерживать порядок по приоритету в нашей очереди, мы позаботимся об этом только в том случае, если кто-то захочет извлечь элемент из очереди.
В таком случае мы сортируем массив по значению (наша приоритетная очередь — это минимальная очередь, поэтому узел с самым низким приоритетом должен быть «наверху»), извлекаем первый узел и возвращаем его.
Это простая для понимания и простая реализация, поддерживающая все необходимые функции.
Давайте посмотрим, как он работает по сравнению с нашими алгоритмами поиска BFS и двунаправленного поиска:
Неплохо, учитывая, что этот алгоритм может работать и на взвешенных графах, в отличие от BFS.
Теперь давайте посмотрим, можем ли мы улучшить это с помощью кучи Фибоначчи. Я не буду вдаваться в подробности организации кучи Фибоначчи. Если вам интересно, в Интернете доступно множество документации.
Одна вещь, о которой я уже упоминал, это отсутствие поддержки поиска в этих сложных структурах данных.
Чтобы помочь с этим ограничением, нам нужно вести отдельный реестр наших узлов.
Я использовал для этого массив, поскольку его достаточно легко реализовать.
class FibonacciPriorityQueue implements PriorityQueue { protected FibonacciHeap $h; protected array $nodesList = []; public function __construct() { $this->h = new FibonacciHeap; } public function append(int $item, int $priority): void { $this->add_with_priority($item, $priority); } public function extract_min(): int { if (!$this->h->isEmpty()) { $item = $this->h->extractMin()->data; unset($this->nodesList[$item]); return $item; } return 0; } public function decrease_priority(int $item, $newPriority): void { if ($this->contains($item)) $this->h->decreaseKey($this->nodesList[$item], $newPriority); } public function add_with_priority(int $item, int $priority): void { $this->nodesList[$item] = $this->h->insert($priority, $item); } public function count(): int { return $this->h->count(); } public function contains(int $item): bool { return isset($this->nodesList[$item]); } }
Наш список узлов используется для ведения списка узлов (как следует из названия .. :-)), которые в данный момент зарегистрированы в очереди. Каждый элемент в массиве имеет узел в качестве ключа и указывает на элемент в куче Фибоначчи.
Очень важно иметь ссылку на элементы кучи, так как это то, что вы собираетесь использовать при уменьшении приоритета узла в методе уменьшения_приоритета.
Теперь давайте посмотрим, как эта версия нашей приоритетной очереди работает с алгоритмом Дейкстры.
Согласно странице википедии, временная сложность должна быть улучшена до:
Ух ты. Как видите, мы значительно улучшили производительность нашего алгоритма Дейкстры, используя кучу Фибоначчи.
Однако здесь следует упомянуть одну вещь: из-за использования нашего вспомогательного массива nodeList мы также использовали немного больше памяти.
Если этот компромисс приемлем для вас, тогда вам подойдет куча Фибоначчи…
На сегодня все, всем хорошего дня!