alefedor/JB_Spring_Practice_19

Parallel Dijkstra Algorithm

Формулировка задания

В рамках этого тестового задания вам необходимо реализовать параллельную версию алгоритма Дейкстры для поиска кратчайшего пути в графе. Файл Graph.kt содержит классы Node и Edge, описывающие граф. Вы можете использовать поле Node.distance для того, чтобы хранить расстояние до текущей вершины во время поиска; функция clearNodes(..) сбрасывает эти расстояния на Int.MAX_VALUE.

Реализация параллельной весии должна содержаться в функции shortestPathParallel в файле Dijkstra.kt. Там находится некоторый скелет для будушего алгоритма, но его использование не обязательно и никак не влияет на оценивание.

Если говорить вкратце, то идея параллельного алгоритма заключается в том, что каждый из worker-ов берёт вершину с минимальным расстоянием из приоритетной очереди и релаксирует выходящие из неё ребра; если релаксация прошла успешно (расстояние до вершины на другом конце ребра уменьшили), то добавляем соответствующую вершину в очередь. Из-за того, что вершины обрабатываются параллельно, возможны ситуации, когда они обрабатываются по несколько раз, -- это нормально.

В качестве многопоточной приоритетной очереди предлагается использовать обычную бинарную кучу с глобальной блокировкой. Вы так же можете изменять класс Node по своему усмотрению (добавить блокировку для синхронизации, дополнительную информацию для поддержки операции decreaseKey, сделать возможным использование CAS на поле distance и так далее). Предполагается, что пока очередь пуста, но работа ещё не окончена, worker-ы могут крутиться в цикле в ожидании нового элемента или окончания работы и кушать CPU.

Решение

Для данного тестового задание был выбран следующий подход: предложенная очередь с приоритетами с глобальной блокировкой, а также AtomicInteger и CAS, чтобы хранить и обновлять расстояния. В самой очереди расстояния не обновляются, добавляется новая информация про вершины, а старую мы удалим потом, т.к. ее легко проверить (новые расстояния строго меньше старых). При этом асимптотика времени работы в с таким подходом не ухудшается, т.к. мы просто вместо того, чтобы удалять лишнюю информацию сразу, удаляем ее позже.

Поток завершает свое исполнение, только когда этот и все остальные потоки начинают ждать элементов очереди, информацию о чем можно поддерживать с помощью AtomicInteger.

Сейчас основная проблема многопоточной реализации Дейкстры это взятие блокировки при каждом добавлении или получении элемента из очереди. Всего получается O(V) таких блокировок, что по сравнению с O(E log V) простейших операций в однопоточной версии (при обычной реализации с кучей) выглядит не как оптимизация (хотя текущая реализации и быстрее предложенной тестовой реализации однопоточной Дейкстры). Я бы предложил использовать очередь из какой-нибудь библиотеки, потому что очередь можно значительно оптимизировать на многопоточное изменение, пользуясь, например, тем, что добавление всегда происходит в конец, а удаление из начала.

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

Update

И раз уж решение почти во всех остальных форках подозрительно напоминают мое, то приведу пару примеров, как можно было сделать по-другому, чтобы не считали, что это единственное возможное решение:

• Можно было написать свою бинарную кучу (благо, это не сложная структура данных), например, на алгебраических типах в стиле Scala и Haskell, а также поддерживать Map<Node, HeapNode>, позволяющий по вершине исходного графа получить соответствующую ей вершину бинарной кучи. А имея вершину бинарной кучу тривиально делается операция decreaseKey. Делая все операции с кучей или соответствующей ей таблицей, нужно, конечно, сначала брать lock на кучу. Время работы при этом подходе ускорится, т.к. самописная куча быстрее priorityQueue. Это бинарную кучу также можно заменить на кучу Фибоначчи, в которой decreaseKey работает на за O(log n), а за амортизированное O(1).

• Можно было использовать стандартный PriorityQueue<Node> с компаратором расстояний, а после обновления расстояния у вершины добавлять ее в кучу второй раз. Тогда у нас предыдущие ее вхождение в кучу могут стать не очень "честными", но последнее добавление будет точно расположено правильно. При этом можно заметить, что никаких причин на то, чтобы алгоритм как-нибудь ломался. Те вершины, которые ниже "поломанных" вершин, все равно должны быть ниже в куче, т.к. мы только уменьшаем веса, и тогда мы сначала достанем поломанную вершину, увидем, что она уже была, а затем будем доставать вершины, которые были ниже нее в куче. Реализация еще на пару строчек короче, время работы такое же.

• Можно было использовать TreeSet<Pair<Int, Node>>, чтобы обладать и возможностями кучи и способностью удалять устаревшие пары. Кода при этом столько же сейчас, а удаление в том же месте, в котором обычно и пишется в Дейкстре, а не в начале цикла, как обычно пишу Дейкстру я.

При этом если первое можно еще с натяжкой назвать слишком сложным, второе - хаком, то третье вполне законно по заданию. Замена PriorityQueue<Node> на PriorityQueue<Pair<Int, Node>> или замена Int на AtomicInteger ничем не лучше замены PriorityQueue<Node> на TreeSet<Pair<Int, Node>>. В общем, кто-то обладает недостаточно богатой фантазией. Но спасибо им, что они оценили мое изначальное решение и сочли его самым простым. По этому признаку я и выбрал именно его, хотя оно и не самое тривиальное по сравнению с тем же TreeSet.