Масштабирование реализации алгоритма Дейкстры
У меня есть график с каждым Edge имея некоторые weight,
Я реализовал алгоритм Дейкстры, чтобы найти кратчайший путь из Vertex От А до Б.
Weights для Графа считываются из БД Ключ / Значение. [redis.io].
- каждый
Weights DBсоставляет около 2 ГБ. - Есть 50 БД для
weights, [Или 50 разных файлов по 2 ГБ со значениями веса, которые я сохранил в Redis.io]. - Чтобы найти кратчайший путь,
function FindPath(Start, End, DB_name)используется.
Dijkstras считывает значения веса из памяти [Redio.io — хранилище значений ключа в памяти]. Но моя оперативная память составляет всего 6 ГБ. Невозможно хранить 2 ГБ * 50 БД в памяти одновременно.
Запрос на Путь может быть Случайным и Одновременным.
Как лучше всего хранить базу данных весов?
Является ли увеличение оперативной памяти единственным вариантом для увеличения скорости выполнения программы?
РЕДАКТИРОВАТЬ
Количество краев: 4,62,505
Решение
Если скорость связана с основным параметром, это увеличить оперативную память. Вы не можете достичь аналогичной производительности с базой данных nosql (например, mongodb). Другой вариант — попытаться распараллелить алгоритм в многоядерной системе. Но это очень сложно, так как окончательное решение является глобальным.
[РЕДАКТИРОВАТЬ] Самый быстрый способ хранения весов — это непрерывный массив весов, проиндексированных по номеру ребра. Один массив на БД. Если все массивы не могут уместиться в вашем оперативной памяти, вы можете разработать некоторые базовые механизмы кэширования, перемещая БД из файла в массив (надеясь, что не все БД доступны одновременно).Другие решения
Других решений пока нет …