Нет

А как тогда? Я чето в толк не возьму? Размер графа какой и что именно считается?

А как тогда? Я чето в толк не возьму? Размер графа какой и что именно считается?

Считается матрица расстояний для произвольных 1000 точек в графе дорог для всей РФ

Точно? Там, скорее, есть кластеры, в каждом кластере условные 10К и между ними внутри кластера считается всё. А между кластерами 3-4 магистрали.

Не понял

Считается матрица расстояний для произвольных 1000 точек в графе дорог для всей РФ

А граф прям вся Россия? Это сколько ж блять вершин, миллионы небось?

А граф прям вся Россия? Это сколько ж блять вершин, миллионы небось?

Да, там миллионы. Но любой (ЛЮБОЙ) опенсорс роутер по графам дорог такое прожует точно так же.

Ну, если надо строить расстояние от любой точки для любой, не нужно считать попарно все расстояния. Достаточно разбить на кластеры (как город на районы). Если две точки из разных кластеров, то есть из кластера несколько "выездов", вот они попарно считаются. Но их немного. Внутри кластера да, считать всё.

Ну, если надо строить расстояние от любой точки для любой, не нужно считать попарно все расстояния. Достаточно разбить на кластеры (как город на районы). Если две точки из разных кластеров, то есть из кластера несколько "выездов", вот они попарно считаются. Но их немного. Внутри кластера да, считать всё.

Да не надо ничего придумывать, можно взять любую реализацию тех же contraction hierarchies и оно будет быстро и предрасчитывать и работать.

Да не надо ничего придумывать, можно взять любую реализацию тех же contraction hierarchies и оно будет быстро и предрасчитывать и работать.

Не надо, значит, не надо. Меня просто удивило, что считается матрица 200К на 200К. Мне кажется, это лишнее для такой задачи.

Не надо, значит, не надо. Меня просто удивило, что считается матрица 200К на 200К. Мне кажется, это лишнее для такой задачи.

Это точно лишнее, но если им так нужно по процессам, то что поделать.

Но тут в любом случае надо не просто дейкстру юзать, а взять ManyToMany вариант

Да, там миллионы. Но любой (ЛЮБОЙ) опенсорс роутер по графам дорог такое прожует точно так же.

Так, мне походу надо уволиться и пойти грузчиком работать. Давай я еще раз задам этот вопрос, чтобы точно понять, что происходит. У тебя в РАМе лежит граф всей матушки-России на миллионы вершин и десятки миллионов ребер и между произвольными 1000 парами точек (например, Владивосток-Екатеринбург) расчет занимает < 1 секунды в 95% случаев?

Так, мне походу надо уволиться и пойти грузчиком работать. Давай я еще раз задам этот вопрос, чтобы точно понять, что происходит. У тебя в РАМе лежит граф всей матушки-России на миллионы вершин и десятки миллионов ребер и между произвольными 1000 парами точек (например, Владивосток-Екатеринбург) расчет занимает < 1 секунды в 95% случаев?

Между прям совсем произвольными может оно и будет дольше, но на реальных данных примерно в секунду укладывается.

Так, мне походу надо уволиться и пойти грузчиком работать. Давай я еще раз задам этот вопрос, чтобы точно понять, что происходит. У тебя в РАМе лежит граф всей матушки-России на миллионы вершин и десятки миллионов ребер и между произвольными 1000 парами точек (например, Владивосток-Екатеринбург) расчет занимает < 1 секунды в 95% случаев?

Более того, все большие опен сорс роутеры по графам дорог могут так же

Интересно, а почему тогда наши математики выбрали именно тот подход, который выбрали. Вот реально интересно.

Интересно, а почему тогда наши математики выбрали именно тот подход, который выбрали. Вот реально интересно.

Потому что велосипедостроение интереснее

А после этой оптимизации, Contraction hierarchies, размер графа какой?

Интересно, а почему тогда наши математики выбрали именно тот подход, который выбрали. Вот реально интересно.

А вам прям нужны расстояния между всеми точками в графе, а не между всеми водителями и клиентами?

Я так понимаю, оно должно его очень существенно разрядить?

А вам прям нужны расстояния между всеми точками в графе, а не между всеми водителями и клиентами?

Ой, не спрашивай, на данном этапе полная матрица расстояний, а дальше поверх этого у них еще что-то считается. Там дохрена кода написана по этому принципу, давно написана.

@omgszer мне тут теперь в инсту лезет реклама работы в microsoft ireland

А после этой оптимизации, Contraction hierarchies, размер графа какой?

Там всё же чуть по другому алгоритм работает, так сравнивать не совсем корректно будет.

Там всё же чуть по другому алгоритм работает, так сравнивать не совсем корректно будет.

У меня начинает складываться ощущение, что предложенный сейчас подход просто тупиковый.

Ты можешь сходить в Гугл и рассказать им об этом. Они могут быть не в курсе фундаментальной проблемы в их стеке

Правильно на плюсах писать тоже не очень приятно.

У них там очень особые кресты. Там столько макросов, что чисто по тексту оно напоминает жаву

У них там очень особые кресты. Там столько макросов, что чисто по тексту оно напоминает жаву

А макросы вообще дебажить можно на С++?

Я помню в С там какие-то трудности были ахтунговые, я глубоко так не вникал, ибо слишком на макросы никогда не полагался. Иные вон дженерик структуры через макросы делают, на С.

А макросы вообще дебажить можно на С++?

Можно отпут препроцессора посмотреть, в gcc флаг -E, студия даже умеет хендлить stdout этого дела и дампить в файл

Посмотреть

У меня начинает складываться ощущение, что предложенный сейчас подход просто тупиковый.

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

А подебажить?

Зная его асимптотику можно будет оценить насколько это смешная затея или нет.

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

Завтра возьму опенсоурсный этот проект под дотнет с готовыми алгоритмами и попробую тамошние роутеры.

Под мой кейс, чтобы между произвольными парами вершин считалось

Посмотреть

Копипастите, что вам компилятор выдал и уже это дебажите

Завтра возьму опенсоурсный этот проект под дотнет с готовыми алгоритмами и попробую тамошние роутеры.

Только там деталь, что они обычно только с OSM'ом дружат.

Только там деталь, что они обычно только с OSM'ом дружат.

Да, у нас тоже в ОСМ есть. А так, в рантайме же граф наверно явно сконструировать тоже можно?

Копипастите, что вам компилятор выдал и уже это дебажите

А, вот оно как.

Завтра возьму опенсоурсный этот проект под дотнет с готовыми алгоритмами и попробую тамошние роутеры.

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

Да, у нас тоже в ОСМ есть. А так, в рантайме же граф наверно явно сконструировать тоже можно?

С графом в рантайме может быть сложно, это зависит от реализации. В другие опен сорс проекты с этим я пролезал, но как у них сделано - вопрос, надо смотреть.

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

Да я помню его, цикл фон n - 1 раз. Он же?

Да я помню его, цикл фон n - 1 раз. Он же?

Там фор 3 раза.

Отсюда и очевидная асимптотика

Там фор 3 раза.

Значит это другой.

Плюс в том, что там никаких сетов, никаких сложных структур данных. Тупо массив и три вложенных циклов со сравнением весов в финале.

Значит это другой.

Вот эта штука, если псевдокодом с вики брать: let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) for each edge (u, v) do dist[u][v] ← w(u, v) // The weight of the edge (u, v) for each vertex v do dist[v][v] ← 0 for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end if

Завтра попробую скачать и заюзать тот проект, что ты вчера кинул

Завтра попробую скачать и заюзать тот проект, что ты вчера кинул

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

Да, для ваших 200 000 вершин нужно будет 60+гб памяти тупо на матрицу, но я думаю, что это не проблема.

Да, для ваших 200 000 вершин нужно будет 60+гб памяти тупо на матрицу, но я думаю, что это не проблема.

Память пофиг

Хоть 600

Да, для ваших 200 000 вершин нужно будет 60+гб памяти тупо на матрицу, но я думаю, что это не проблема.

Но это 200к в кубе вершин.

Интересно, сколько это займёт.

На одном потоке же.

Но это 200к в кубе вершин.

Да, но дейкстра тоже не линейно скейлится и при этом у него сопутствующие расходы нифига не маленькие.

Но это 200к в кубе вершин.

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

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

Добавлю это как коммент к коду.

Да, но дейкстра тоже не линейно скейлится и при этом у него сопутствующие расходы нифига не маленькие.

Просто если ты можешь на РФ рассчитать тыщу точек так быстро, то может тут все вообще изначально абсолютно похерено .

И надо просто препроцессинг графа перевести на рельсы этого подхода.

А дальше жизнь станет гораздо проще.

Добавлю это как коммент к коду.

Владимир Высоцкий. Вершина

Просто если ты можешь на РФ рассчитать тыщу точек так быстро, то может тут все вообще изначально абсолютно похерено .

Оно всё равно не заточено под задачу посчитать расстояния между вообще всеми вершинами.

Для такого лучше взять специализированные алгоритмы. А тому же того же Флойда уоршелла можно на кластере запустить, в отличие от альтернатив https://arxiv.org/abs/1902.04446

Оно всё равно не заточено под задачу посчитать расстояния между вообще всеми вершинами.

Окей, это принято. Но если чуть отойти от спецификации и чуть здоровее посмотреть, то в итоге-то надо знать сколько водителю до пассажира реально нужно проехать, так как цель этого с точки зрения бизнеса это в первую очередь расход бензина. Водители уходят, если маршрут нечестный, особенно сейчас, по крайней мере так говорят бизнес-аналитики. Эти опенсоурсные роутеры такую задачу же по ступ и решают? Специфика в том, что водитель от пассажира может быть сколько угодно далеко.

И запросов на маршрутизацию до тысячи в секунду на продакшин кластер.

И запросов на маршрутизацию до тысячи в секунду на продакшин кластер.

Ну а если вам хватит ресурсов, чтобы посчитать Флойда уоршелла для нужного вам графа, то остальное дело техники.

Можно банально эту матрицу держать в памяти и быстрее этого уже ничего не будет

Проблемы у вас возникнут, только если захочется масштабироваться сильно на другие страны

Но тогда в любом случае от подхода с расчетом всех расстояний между всеми вершинами придется отойти

Проблемы у вас возникнут, только если захочется масштабироваться сильно на другие страны

Пока такой задачи не стоит.

Киев считается пределом мечтаний.

@omgszer мне тут теперь в инсту лезет реклама работы в microsoft ireland

потому что у тебя есть подписчик оттуда?

потому что у тебя есть подписчик оттуда?

Кто бы это мог быть? 🤔

Кто бы это мог быть? 🤔

А на предыдущем допросе показывал, что только аутлук и текст.

А я там код смотрю, но не пишу

А я там код смотрю, но не пишу

Выкрутился! Как Штирлиц! 🤣🤣🤣

А макросы вообще дебажить можно на С++?

Там в основном для классов, логгинг и тп. Но настолько массово, что они там а-ля программисты на спринге

То есть если сравнивать вижлу и райдер, то райдер по функционалу проигрывает в минуса

Да

В C++ даже тестовые фреймворки на макросах чуть более, чем полностью. Весело, в общем.

Ну такоэ

Ну что поделаешь. Семь бед - один ответ в виде макроса.