Doge
Тут мне кажется, не надо ничего придумывать прям своего, а взять какой-то готовый вариант.
Если не жалко денег, то опять-таки тем же флойдом уоршеллом эта задача параллелится нормально. Только кластер нужен норм
Doge
Я вчера смотрел, там подходы к этому спокойно гуглятся
Doge
На MPI вполне норм ложится
Anonymous
Тут мне кажется, не надо ничего придумывать прям своего, а взять какой-то готовый вариант.
Если не жалко денег, то опять-таки тем же флойдом уоршеллом эта задача параллелится нормально. Только кластер нужен норм
Я сегодня говорил с представителем математиков, и про CH, и про этот алгоритм, мне ответили «мы подумаем и дадим ответ в пятницу».
Doge
Я сегодня говорил с представителем математиков, и про CH, и про этот алгоритм, мне ответили «мы подумаем и дадим ответ в пятницу».
А они писали то, что ты сейчас пытаешься ускорить?
Anonymous
На Джире там статьи, заметки, немного псевдокода.
Anonymous
Они не пишут код.
Anonymous
Они чисто математики.
Doge
Плохой знак
Anonymous
И у меня нет полномочий на это влиять.
Doge
Да это понятно, приходится жить с тем, что есть.
И как я понимаю, поменять что-то особо не выйдет. То есть ни сам принцип расчёта, ни тот факт, что зачем-то нужно рассчитать расстояния между всеми вершинами в графе.
Doge
А эти расстояния в итоге где хранят, кстати?
Anonymous
А эти расстояния в итоге где хранят, кстати?
Ряд баз от Постгресиквел до Монги и оперативной памяти (собирается через события поверх Рэббит).
Ilya
Кккккккостылити!
Anonymous
Кккккккостылити!
Конкретно разнообразие БД? Нет, там все ок, там у каждого созвездия миросервисов своя база и они как правило выбраны с умом, а то, что копии везде это никого не смущает, карты меняются очень редко.
Anonymous
Да это понятно, приходится жить с тем, что есть.
И как я понимаю, поменять что-то особо не выйдет. То есть ни сам принцип расчёта, ни тот факт, что зачем-то нужно рассчитать расстояния между всеми вершинами в графе.
Поменять может и выйдет, но медленно. С другой стороны это РНД, его цель (с моей точки зрения) - получить знания, которых не было до этого.
Anonymous
То есть, по результатам РНД вполне можно констатировать, что все, что сделано - не отвечает запросу бизнеса и нужно пробовать вот это и вот это.
Anonymous
Но сначла по-любому придется написать код, который имплементит текущую схему и оптимизировать его. Вот мемоизация должна помочь по моим интуитивным ожиданиям.
Anonymous
Еще не проверял.
Doge
Поменять может и выйдет, но медленно. С другой стороны это РНД, его цель (с моей точки зрения) - получить знания, которых не было до этого.
Я просто как-то слабо понимаю необходимость держать и хранить расстояния между всеми вершинами.
Вот это, имхо, главный WTF момент во всей этой схеме. По идее тут хватило бы запросов на сервера с картографией тем сервисам, которым это нужно именно для расчёта тех расстояний, которые сейчас нужны в данный момент времени.
Благо даже опен сорс решения в этом плане безумно шустрые.
Anonymous
Это по историческим причинам. Я не знаю как в деталях у них сейчас это работает, но все орхетекторы почему-то очень верят в матрицу расстояний + кеш. Эта вера еще до меня появилась.
Anonymous
Сложно вникнуть, почему так.
Anonymous
Но это прям целый эпик в джире, я отвечаю за техстэк и имплементацию
Mikhαil
Будто задача программиста делать гавно если сказали делать гавно
Mikhαil
А не предлагать решения лучше
Anonymous
Почитай выше, я предложил.
Anonymous
Ответили "мы подумаем".
Anonymous
То есть, никто мое предложение не отверг и "мы подумаем" ответили честно, по ощущениям, не ради вежливости.
Doge
Это по историческим причинам. Я не знаю как в деталях у них сейчас это работает, но все орхетекторы почему-то очень верят в матрицу расстояний + кеш. Эта вера еще до меня появилась.
Не, задумку я понимаю, понятно, что это будет быстро, если при этом в нормальном хранилище в памяти это держать.
Но вот сам предрасчёт, который при этом обычным (даже не many-to-many насколько я понял) дейсктрой идёт - это очень сомнительный вариант.
Anonymous
Я просто как-то слабо понимаю необходимость держать и хранить расстояния между всеми вершинами.
Вот это, имхо, главный WTF момент во всей этой схеме. По идее тут хватило бы запросов на сервера с картографией тем сервисам, которым это нужно именно для расчёта тех расстояний, которые сейчас нужны в данный момент времени.
Благо даже опен сорс решения в этом плане безумно шустрые.
А сколько препроцессинг CH занимает больних графов?
Doge
А сколько препроцессинг CH занимает больних графов?
Где-то минут 30-60, но там от многих факторов может зависеть.
Doge
Это на РФ опять-таки
Anonymous
Да, очень быстро.
Anonymous
Слушай, а many-to-many в этом контексте это что?
Anonymous
Тоже какая-то разновидность дейкстры?
Doge
Да, очень быстро.
Кстати, я ведь правильно понимаю, что расчёт всех пар расстояний у вас идёт наивно?
То есть прям тупо в двойном цикле по всем вершинами дергается дейкстра заново?
Anonymous
Кстати, я ведь правильно понимаю, что расчёт всех пар расстояний у вас идёт наивно?
То есть прям тупо в двойном цикле по всем вершинами дергается дейкстра заново?
Да самого расчета еще как такового нет, одни наброски, там математики четко прописали 2 этапа: разметка графа с целью понизить размерность и потом расчет полной матрицы. Менеджеры так по Джире и пустили.
Anonymous
Там немного хаос, как и в любом РНД.
Anonymous
Сейчас дошли до точке, где эта чудесная разметка должна произойти.
Anonymous
Я это все дело померял на Запорожье, вкрай ахуел, и пришел к вам с вопросом, вот и все.
Anonymous
То есть, основной сюжет с развязкой вепереди :)
Anonymous
Конкретно сейчас есть сервис, который умеет прочитать граф из приватного хранилища и должен его заимпортировать в Монгу, которую уже выбрал я на время РНД. И заимпортировать должен с учетом разметки, т.е. там этот алгоритм в процессе должен выполниться.
Anonymous
На малых графах до 1000 вершин, тестовых, в основном рэндомных, все быстро работает.
Anonymous
На Запорожье уже неподъемно.
Doge
А в монгу в каком виде оно закидывается?
Обычно такие графы для того же CH хранят в итоге в кастомных бинарных форматах.
Lars
Ряд баз от Постгресиквел до Монги и оперативной памяти (собирается через события поверх Рэббит).
Немного оффтоп, но может полезно будет. Посмотрите на H3 от Uber : https://eng.uber.com/h3/ и процессинг этого дела в ClickHouse https://clickhouse.tech/docs/en/sql-reference/functions/geo/h3/
Anonymous
А в монгу в каком виде оно закидывается?
Обычно такие графы для того же CH хранят в итоге в кастомных бинарных форматах.
Неэффективно кидается, но это не проблема, весь алгоритм в РАМе считается, в РАМе полная копия графа
Doge
Неэффективно кидается, но это не проблема, весь алгоритм в РАМе считается, в РАМе полная копия графа
Я скорее задумался насколько потом эффективно оттуда будет читать и норм ли будет монге
Anonymous
Я скорее задумался насколько потом эффективно оттуда будет читать и норм ли будет монге
Меньше чем за 10 секунд вычитывает запорожье в N потоков с учетом RWLock, мной использованного для храрения синглтона-графа
Anonymous
и отдает рединесс
Anonymous
там проблем ваще нет
Doge
Doge
Я просто обычно чуть побаиваюсь монгу, скорее всего зря
Anonymous
и это через триебучие ВПН
Anonymous
то есть, внутри системы будет еще быстрее
Anonymous
Я просто обычно чуть побаиваюсь монгу, скорее всего зря
В этом смысле к ней вообще нет претензий, транзакционность там говно полное
Anonymous
то есть, атомарно записать уже сложно сложную транзакцию, хотя там добавили какое-то АПИ
Vasily
Vasily
Как тонко подмечено
Ilya
Как думаете, Василий унижает окружающих?🤔
Ayrat
дедушка старый - ему все равно!
Vasily
Я не занимаюсь унижением. Люди с этим сами прекрасно справляются
Ilya
Я не занимаюсь унижением. Люди с этим сами прекрасно справляются
То есть у тебя взгляд тяжёлый просто?
Ilya
Потому ты в очках?
Vasily
41 год скоро
Vasily
И бурчу
Hog
Ilya
Динозавры в чате