Комментарии 13
Как проверялась корректность реализации? Например, верно ли, что ответы двух реализаций (стандартной и с корзинами) совпали на всех вершинах графа при поиске расстояний от фиксированной вершины `V`?
Не пробовали ли вы в каждой ячейке воспользоваться обычной кучей (например, для Java это `PriorityQueue`) вместо массива?
Есть ли какой-то смысл в написании своей реализации `BitArray` и частичной реализации `ArrayList` внутри `NewSortedHashMapEntry`?
А каковы длины дуг? Например, если длина дуги всегда больше, чем размер корзины, то можно отсортировать каждую корзину перед её первым посещением и появится гарантия, что каждая вершина посещается не больше одного раза. Ну или можно просто отсортировать и посмотреть, что будет. Или сделать `Collections.shuffle` перед первым проходом.
Не пробовали ли вы в каждой ячейке воспользоваться обычной кучей (например, для Java это `PriorityQueue`) вместо массива?
Есть ли какой-то смысл в написании своей реализации `BitArray` и частичной реализации `ArrayList` внутри `NewSortedHashMapEntry`?
А каковы длины дуг? Например, если длина дуги всегда больше, чем размер корзины, то можно отсортировать каждую корзину перед её первым посещением и появится гарантия, что каждая вершина посещается не больше одного раза. Ну или можно просто отсортировать и посмотреть, что будет. Или сделать `Collections.shuffle` перед первым проходом.
+1
Корректность проверялась путем проверки полного совпадения массива d расстояний.
Нет, но прелесть массива примитивов в скорости его работы. Тут скорее имеет смысл сравнить с бинарной кучей, к примеру.
Да, интересно было попробовать реализовать битовую маску применяя сравнение без ifов. Вполне вероятно, что можно применить и готовые библиотеки.
По поводу длины дуг, большое спасибо, очень интересное дополнение, попробую обязательно реализовать и дополню статью.
Нет, но прелесть массива примитивов в скорости его работы. Тут скорее имеет смысл сравнить с бинарной кучей, к примеру.
Да, интересно было попробовать реализовать битовую маску применяя сравнение без ifов. Вполне вероятно, что можно применить и готовые библиотеки.
По поводу длины дуг, большое спасибо, очень интересное дополнение, попробую обязательно реализовать и дополню статью.
0
Да, неточно выразился, бинарная куча (binary heap) и подразумевалась. Это получится этакая оптимизация стандартного алгоритма с двоичной кучей, просто в которой куча разделена на несколько корзин. Мне кажется, чем-то напоминает radix sort.
Не очень понял, что вы подразумеваете под "сравнением без if'ов". Можете пояснить? Я не понимаю, чем ваша реализация принципиально лучше массива boolean, кроме того, что может занимать меньше места. А вообще в Java есть встроенный битовый массив — BitSet
.
0
Да, из radix sort идею я и подчерпнул.
Про BitSet — принципиально мне кажется ничем, просто интересно было. А программирование без if-ов это когда, к примеру, необходимо сравнить a < b и если да то сделать c += 10. В этом случае можно сделать следующую магию:
Такая штука:
1) это прямые указания процессору и работу с очень быстрыми битовыми сдвигами
2) и вы можете не надеется на то, что проц сам соптимизирует.
3) работает, к сожалению, только с обратным порядком байт и в jvm, где размер int не зависит от 32-битная или 64 битная адресация памяти.
Про 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 битная адресация памяти.
0
Корректность проверялась путем проверки полного совпадения массива d расстояний.
В статье написано, что проверялись только расстояния до случайной тысячи узлов и её хорошо бы исправить или я чего-то не понимаю?
показавшие полное совпадение длины кратчайшего пути от 1000 рандомных узлов до 1000 других рандомных узлов на графе.
0
Можете еще посмотреть на Radix heap. Там тоже корзины и все такое, а в реализации ИМХО попроще чем куча Фибоначчи.
0
Я немного затупил на том месте где хеш таблица описана. Там ключ это расстояние или диапазон расстояний (например 0..20, 20..40 и т.д.), а значение это номер узла в графе?
Весьма годная идея. На вашем месте я бы такие статьи публиковал ещё и на github.io, чтобы была visibility за пределами русскоязычной аудитории. Очень полезно для резюме и повышения зарплаты :)
Мелкий баг: надо поменять difficulty на complexity.
Весьма годная идея. На вашем месте я бы такие статьи публиковал ещё и на github.io, чтобы была visibility за пределами русскоязычной аудитории. Очень полезно для резюме и повышения зарплаты :)
Мелкий баг: надо поменять difficulty на complexity.
+1
Насколько я понимаю, этот алгоритм имеет ограничения по сравнению с классическим алгоритмом Дейкстры. То что бросается в глаза это необходимость иметь равномерное распределение вершин по бакетам. Прокомментируйте, пожалуйста, т.к. не уверен что уловил все детали вашего подхода.
Полагаю, вы сравнили по времени свое решение и классическое. Хорошая асимптотика может не означать ускорение на практике (пример: умножение матриц методом Штрассена), поэтому хочется увидеть эти сравнения тоже.
PS: Поправьте, пожалуйста, опечатки («алгоримт», «lon(n)», «20 секунд» на картинке ...)
Полагаю, вы сравнили по времени свое решение и классическое. Хорошая асимптотика может не означать ускорение на практике (пример: умножение матриц методом Штрассена), поэтому хочется увидеть эти сравнения тоже.
PS: Поправьте, пожалуйста, опечатки («алгоримт», «lon(n)», «20 секунд» на картинке ...)
0
Ограничений нет, алгоритм так же корректно будет работать в случае любого графа, вопрос лишь в производительности.
Равномерное распределение иметь вовсе не обязательно. Важно лишь уменьшить вероятность повторного просмотра вершины. Сама по себе вероятность повторного просмотра зависит от двух факторов:
1. Мощность бакета должна быть чуть меньше чем, к примеру, 10% персентиль распределения длины дуг. Тогда вы получите гарантированно малую вероятность повторного просмотра.
2. Распределение расстояний из точки: оно может быть равномерным по бакетам и так получиться, что даже при фиговом подборе параметра мощности бакета вы получите неплохую производительность, надо смотреть конкретные случаи, но в случае дорожного графа, замечу, проблем не возникло ни в одном из трех городов на которых алгоритм сейчас работает (Москва, Питер, Казань).
По поводу производительности: я дополнительно произвел исследования на рандомно сгенерированном графе при различных параметрах и сравнил с бинарной кучей и фибоначчиевой кучей и в них алгоритм стабильно работал быстрее в несколько раз. Эти исследования я постараюсь дооформить в ближайшее время и дополнить ими публикацию.
Графики, что вы видели в публикации это поиск на графе дорог Москвы (OSM) из рандомной точки в тысячи рандомных точек, это и есть сравнение на практике.
Опечатки: 20 секунд это не опечатка, в моем случае путь действительно измерялся в секундах поэтому и длина дуги из метров конвертировалась в секунды.
Равномерное распределение иметь вовсе не обязательно. Важно лишь уменьшить вероятность повторного просмотра вершины. Сама по себе вероятность повторного просмотра зависит от двух факторов:
1. Мощность бакета должна быть чуть меньше чем, к примеру, 10% персентиль распределения длины дуг. Тогда вы получите гарантированно малую вероятность повторного просмотра.
2. Распределение расстояний из точки: оно может быть равномерным по бакетам и так получиться, что даже при фиговом подборе параметра мощности бакета вы получите неплохую производительность, надо смотреть конкретные случаи, но в случае дорожного графа, замечу, проблем не возникло ни в одном из трех городов на которых алгоритм сейчас работает (Москва, Питер, Казань).
По поводу производительности: я дополнительно произвел исследования на рандомно сгенерированном графе при различных параметрах и сравнил с бинарной кучей и фибоначчиевой кучей и в них алгоритм стабильно работал быстрее в несколько раз. Эти исследования я постараюсь дооформить в ближайшее время и дополнить ими публикацию.
Графики, что вы видели в публикации это поиск на графе дорог Москвы (OSM) из рандомной точки в тысячи рандомных точек, это и есть сравнение на практике.
Опечатки: 20 секунд это не опечатка, в моем случае путь действительно измерялся в секундах поэтому и длина дуги из метров конвертировалась в секунды.
0
комментарий удалён
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Дейкстра за линейное время