オンライン経路検索 Web サービスを開発したいと考えています。2 つの頂点 V1、V2 間のエッジ距離の合計が最小になるグラフ G のパスを検索します。
問題は、G が信じられないほど大きいことです。1,000 万近くのエッジが含まれています。
G が十分に小さければ、単純だったかもしれません。私はむしろ...
- G のすべてのエッジ/頂点を一覧表示します。これは、いくつかの RDB (例: MySQL または PostgreSQL) との関係です。
- PHPで独自のWebサービスを実装するか、Gで最短パスを検索するもの
私自身のPHPスクリプトは...
- RDB からすべてのエッジ/頂点を選択し、PHP のクラスまたは虚数配列などを使用してメモリ上に G を構築します。
- ダイクストラのアルゴリズムをオンメモリ G に適用し、最短経路を応答します。
このアプローチは、次の理由により、巨大な G では機能しません。
- オンメモリ G をビルドするには非常に時間がかかります。
- エッジごとに大量のメモリを使用します。PHP のオブジェクトはスマートですが、今のところ必要ありません。
これは、リクエストを検索する前に、構築されたネットワークをメモリ上で準備する必要があり、各頂点/エッジ オブジェクトをより軽量にする必要があることを意味します。
私はこのサービスを C で実装することにしました。Apache モジュールを実装する方が、完全にゼロから同時実行の高性能ネットワーク デーモンを実装するよりもはるかに簡単になると思いました (より良い解決策があれば、それについて知りたいです)。 .
では、オンメモリ G はどこに構築すればよいのでしょうか?
ご存じのとおり、Apache Web サーバーはマルチスレッドのマルチプロセッシング デーモンです。プロセスごとにメモリ上に G を構築する愚かなモジュールを開発すると、10 個の処理を行うサーバーのメモリ上にほぼ 1 億のエッジ (10 個の同じ構造) が構築されます。
実行中のプロセスの数に関係なく、モジュールをよりスマートにして、各プロセスから 1 つのオンメモリ G を共有したいと考えています。
Apache モジュールでデータ構造を構築するのに最適な場所はどこだと思いますか?