私はアカデミック プロジェクトに取り組んでいます。大規模で重み付けされた有向グラフの最短経路を見つけるためのライブラリを作成しています。
仕様は次のとおりです。
サンプル データ セットは、ノードあたり平均 5.68 エッジの 1500 頂点のグラフです。仕様は最大 20.000 ノードまで異なる場合があります。
さらに、私はCPU /メモリバウンドの環境で作業しています：Android。
エッジの重みは自明ではなく、一定でもありません。グラフの変数の状態に依存します。
オフラインで作業する必要があります。
私はいくつかの困難に直面しています：
グラフのデータを効率的に保存、取得、更新する方法が必要です。Java クラスからのクエリで SQLite オブジェクトを使用する必要があるか、ヒープ上の大きなカスタム Java オブジェクトを使用する必要がありますか? これはパフォーマンスにとって最も重要な側面だと思います。
ある種のショート パス アルゴリズムを効率的に実装する方法が必要です。すべての重みが正であるため、訪問したノードのコンテナーとして ArrayList を使用して Dijikstra アルゴリズムを適用する必要がありますか?
これは NDK を使用する良いケースですか? このタスクは CPU を集中的に使用しますが、メモリへのアクセスも頻繁に行うため、そうではないと思いますが、貢献することはできます。
リソースが不足していること、RAM が不足していること、ディスクが遅いこと、CPU が貴重であることを常に覚えておいてください (バッテリーに関して)。
どんなアドバイスでも大歓迎です、乾杯:)