Дейкстра за линейное время

[@yeputons]

Как проверялась корректность реализации? Например, верно ли, что ответы двух реализаций (стандартной и с корзинами) совпали на всех вершинах графа при поиске расстояний от фиксированной вершины `V`?

Не пробовали ли вы в каждой ячейке воспользоваться обычной кучей (например, для Java это `PriorityQueue`) вместо массива?

Есть ли какой-то смысл в написании своей реализации `BitArray` и частичной реализации `ArrayList` внутри `NewSortedHashMapEntry`?

А каковы длины дуг? Например, если длина дуги всегда больше, чем размер корзины, то можно отсортировать каждую корзину перед её первым посещением и появится гарантия, что каждая вершина посещается не больше одного раза. Ну или можно просто отсортировать и посмотреть, что будет. Или сделать `Collections.shuffle` перед первым проходом.

[@aliffka_93]

Корректность проверялась путем проверки полного совпадения массива d расстояний.
Нет, но прелесть массива примитивов в скорости его работы. Тут скорее имеет смысл сравнить с бинарной кучей, к примеру.
Да, интересно было попробовать реализовать битовую маску применяя сравнение без ifов. Вполне вероятно, что можно применить и готовые библиотеки.
По поводу длины дуг, большое спасибо, очень интересное дополнение, попробую обязательно реализовать и дополню статью.

[@yeputons]

Да, неточно выразился, бинарная куча (binary heap) и подразумевалась. Это получится этакая оптимизация стандартного алгоритма с двоичной кучей, просто в которой куча разделена на несколько корзин. Мне кажется, чем-то напоминает radix sort.

Не очень понял, что вы подразумеваете под "сравнением без if'ов". Можете пояснить? Я не понимаю, чем ваша реализация принципиально лучше массива boolean, кроме того, что может занимать меньше места. А вообще в Java есть встроенный битовый массив — BitSet.

[@aliffka_93]

Да, из radix sort идею я и подчерпнул.
Про BitSet — принципиально мне кажется ничем, просто интересно было. А программирование без if-ов это когда, к примеру, необходимо сравнить a < b и если да то сделать c += 10. В этом случае можно сделать следующую магию:

public static int getSign(int a, int b) {
    int c = a - b;
    return (c >> 31) & 0x1;
}
c += 10 * getSign(a, b);

Такая штука:
1) это прямые указания процессору и работу с очень быстрыми битовыми сдвигами
2) и вы можете не надеется на то, что проц сам соптимизирует.
3) работает, к сожалению, только с обратным порядком байт и в jvm, где размер int не зависит от 32-битная или 64 битная адресация памяти.

[@yeputons]

Корректность проверялась путем проверки полного совпадения массива d расстояний.

В статье написано, что проверялись только расстояния до случайной тысячи узлов и её хорошо бы исправить или я чего-то не понимаю?

показавшие полное совпадение длины кратчайшего пути от 1000 рандомных узлов до 1000 других рандомных узлов на графе.

[@aliffka_93]

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

[@nobodyhave]

Можете еще посмотреть на Radix heap. Там тоже корзины и все такое, а в реализации ИМХО попроще чем куча Фибоначчи.

[@aliffka_93]

Попробую, в течении месяца найду время и дополню статью, вроде готовая реализация на Java есть.

[@ankh1989]

Я немного затупил на том месте где хеш таблица описана. Там ключ это расстояние или диапазон расстояний (например 0..20, 20..40 и т.д.), а значение это номер узла в графе?

Весьма годная идея. На вашем месте я бы такие статьи публиковал ещё и на github.io, чтобы была visibility за пределами русскоязычной аудитории. Очень полезно для резюме и повышения зарплаты :)

Мелкий баг: надо поменять difficulty на complexity.

[@aliffka_93]

В хэш-таблице хранится диапазон значений расстояний, а номера в узле, все верно.
За замечание по баге спасибо)

[@RomanSt]

Насколько я понимаю, этот алгоритм имеет ограничения по сравнению с классическим алгоритмом Дейкстры. То что бросается в глаза это необходимость иметь равномерное распределение вершин по бакетам. Прокомментируйте, пожалуйста, т.к. не уверен что уловил все детали вашего подхода.

Полагаю, вы сравнили по времени свое решение и классическое. Хорошая асимптотика может не означать ускорение на практике (пример: умножение матриц методом Штрассена), поэтому хочется увидеть эти сравнения тоже.

PS: Поправьте, пожалуйста, опечатки («алгоримт», «lon(n)», «20 секунд» на картинке ...)

[@aliffka_93]

Ограничений нет, алгоритм так же корректно будет работать в случае любого графа, вопрос лишь в производительности.

Равномерное распределение иметь вовсе не обязательно. Важно лишь уменьшить вероятность повторного просмотра вершины. Сама по себе вероятность повторного просмотра зависит от двух факторов:
1. Мощность бакета должна быть чуть меньше чем, к примеру, 10% персентиль распределения длины дуг. Тогда вы получите гарантированно малую вероятность повторного просмотра.
2. Распределение расстояний из точки: оно может быть равномерным по бакетам и так получиться, что даже при фиговом подборе параметра мощности бакета вы получите неплохую производительность, надо смотреть конкретные случаи, но в случае дорожного графа, замечу, проблем не возникло ни в одном из трех городов на которых алгоритм сейчас работает (Москва, Питер, Казань).

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

Опечатки: 20 секунд это не опечатка, в моем случае путь действительно измерялся в секундах поэтому и длина дуги из метров конвертировалась в секунды.

[@aliffka_93]

комментарий удалён