Я работаю над академическим проектом: пишу библиотеку для поиска кратчайшего пути на больших, взвешенных ориентированных графах.
Технические характеристики:
Пример набора данных - это график из 1500 вершин со средним значением 5,68 ребер на узел. Спецификация может варьироваться до 20 000 узлов.
Более того, я работаю в режиме процессора / памяти, окружение: Android.
Вес края не является ни тривиальным, ни дорогостоящим. Это зависит от переменных состояний графа.
Мы должны работать в автономном режиме.
Я сталкиваюсь с несколькими трудностями:
Мне нужен эффективный способ хранения, извлечения и обновления данных графика. Должен ли я использовать объект SQLite с запросами из классов Java, большой пользовательский объект Java в куче или что? Я думаю, что это наиболее критичный для производительности аспект.
Мне нужен эффективный способ для реализации некоторого алгоритма короткого пути. Поскольку все веса положительны, я должен применить алгоритм Dijikstra с ArrayList в качестве контейнера посещенных узлов?
Это хороший случай, чтобы использовать NDK? Задача требует значительных ресурсов процессора, но она также обеспечивает частый доступ к памяти, поэтому я так не думаю, но я открыт для участия.
Всегда помните, что ресурсов мало, оперативной памяти недостаточно, диск медленный, процессор драгоценный (с батарейным питанием).
Любые советы приветствуются, ура :) 1043 *