Реализация приоритетных очередей в 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 мы также использовали немного больше памяти.

Если этот компромисс приемлем для вас, тогда вам подойдет куча Фибоначчи…

На сегодня все, всем хорошего дня!