Shara & Alkoritm
Shara
Привет, Алгоритм. Я тут возилась с моей реализацией алгоритма Дейкстры для очень больших разреженных графов, но наткнулась на проблему с памятью. Может, у тебя есть какие-нибудь хитрости или подходы, чтобы удержать кучу и списки смежности в более компактном виде, не теряя при этом скорость?
Alkoritm
Конечно, вот пара практичных советов: используй двоичную кучу с кастомной структурой, которая хранит только идентификатор вершины и расстояние – никаких лишних полей, это значительно уменьшит размер кучи. Для списка смежности – упакованный массив рёбер: храни один `vector<Edge>`, где каждое ребро – `{to, weight}`, и отдельно для каждой вершины храни вектор стартовых индексов. Так ты избежишь кучи мелких объектов. Если время не критично, замени очередь приоритетов на pairing heap или Fibonacci heap, они создают меньше копий элементов. Ну и, если тебе нужны только расстояния, можешь удалять рёбра, которые не участвуют в релаксации, используя ленивое удаление или специальную карту. Обычно эти приёмы помогают контролировать потребление памяти, не сильно влияя на скорость работы.
Shara
Это неплохой подход. Просто следи за промахами кэша; обычно, когда рёбра помещают в плоский массив, это даёт хороший скачок локальности. Если столкнёшься с узким местом в очереди приоритетов, бинарная куча с явным массивом индексов позволит тебе обновлять ключ на месте, что сэкономит кучу перераспределений. И ещё, если граф твой статический, можно заранее вычислить простой топологический порядок для DAG и полностью обойтись без кучи. Расскажи, как продвигается.
Alkoritm
Звучит отлично, спасибо за подсказки. Попробую с массивом индексов, посмотрим, поможет ли это снизить волатильность. Напишу, если что-нибудь еще всплывет.
Shara
Пожалуйста. Удачи с массивом индексов, расскажи, что получилось.