Wikipediaのリンク最短経路を探索するウェブアプリを公開しました。
なんかGWの4日くらい消費して、半年近くフロントエンドエンジニアしてたせいでプログラミング能力が恐ろしく落ちているのを実感しました。
アルゴリズムとか詳細
計算機触った人ならだれもが尊敬するダイクストラ様のアルゴリズムを借用しています。 Celeron G530の1コアで1クエリあたり500msで処理出来ます。 始点が一緒なら終点が違う経路探索は計算結果を使いまわせるのですが、ダイクストラ法の計算結果が1MB近くのサイズになり、それをキャッシュして管理するのが面倒なのでしていません。代わりに、分散処理が容易になるようにRedisのRPUSH/BLPOPとPub/Sub(後述)を使っています。
Redis RPUSH/BLPOPとPub/Sub
- WebAppはリクエストを受け取った時点でPub/Subでサブスクリプションして、メッセージを待つ。
- WebAppはリクエストをRPUSHでジョブキューを追加して、ワーカーはBLPOPでジョブを受け取る。
- ワーカーは受け取ったジョブをこなしてPub/Subのパブリッシュでメッセージを送信。
- WebAppはPub/Subのメッセージを受信しレスポンスを返す。
といった感じで処理しています。正確には最終的な結果をキャッシュしているのでもう少し複雑ですが。
