Pull to refresh
15
0
Али Абдуллаев @Junkers

Пользователь

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

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

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

Опечатки: 20 секунд это не опечатка, в моем случае путь действительно измерялся в секундах поэтому и длина дуги из метров конвертировалась в секунды.
комментарий удалён
Да, из 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 битная адресация памяти.
Проверил на всякий случай. Весь массив d расстояний совпадает, как при расчете с использованием красно-черного дерева, так и в случае сортирующей хэш-таблицы.
Попробую, в течении месяца найду время и дополню статью, вроде готовая реализация на Java есть.
В хэш-таблице хранится диапазон значений расстояний, а номера в узле, все верно.
За замечание по баге спасибо)
Корректность проверялась путем проверки полного совпадения массива d расстояний.
Нет, но прелесть массива примитивов в скорости его работы. Тут скорее имеет смысл сравнить с бинарной кучей, к примеру.
Да, интересно было попробовать реализовать битовую маску применяя сравнение без ifов. Вполне вероятно, что можно применить и готовые библиотеки.
По поводу длины дуг, большое спасибо, очень интересное дополнение, попробую обязательно реализовать и дополню статью.

Information

Rating
Does not participate
Registered
Activity