改善：高速化(C言語移植)、でも全6路線は検索できず

ちょっと寄り道して、名古屋市営地下鉄以外で最短完乗ルートの計算をしたけど、再び当初の目標の名古屋市営地下鉄の最短完乗ルートの検索を目指してプログラムの改善。

プログラムを作るためには、

• プログラムの構造
• データ構造

を決める(設計する)必要があるが、今回は試行錯誤で進めているため、途中、何度も見直しをしてきた。

試行錯誤が行いやすいようにということで、プログラムはVBScriptで作ってきたが、だいたい形になってきたのでこの週末で、VBScriptのプログラムをC言語に書き換えた。

• プログラムの構造
• データ構造

はほぼそのままに、プログラムの記述をVBScriptからC言語に変更。
こういうのをプログラムの移植といいますが、今回はその移植作業。


さっそく、東山線、桜通線、名城線の3路線で、藤が丘駅スタートで計算。

VBScript版の計算結果は次の通り。

このプログラムをC言語に移植。

C言語版の計算結果は次の通り。

結果の出力方法を変えましたが、計算結果はまったく同じ。
計算時間は341.1秒から1秒に高速化。
単純計算で341倍。

同じアルゴリズムのプログラムでこれだけスピードアップ。
VBScriptのプログラムをC/C++に書き換え(移植する)ことで1桁～2桁以上の高速化ができるだろうと思っていたが、2桁以上の高速化ができた。


もう少し路線数を増やして計算。

4路線、東山線、桜通線、名城線、名港線

6秒で計算。

5路線、東山線、桜通線、名城線、名港線、上飯田線

ちょっと時間が掛かって、28秒で計算。

6路線、東山線、桜通線、名城線、名港線、上飯田線、鶴舞線

10分程計算を続けたが終わらない。
さすがにいきなり全6路線は無理だった。


今回は単純に言語の変更だけで100倍以上の高速化を実現。
でも、全6路線の最短完乗ルートを検索するためには、まだまだ改善が必要。


つづく。