ノード接続チェックの見直し改良をしてみた2012年11月13日 21時17分47秒

年々まっしになってますが昨年度も道路基盤図データ作業でエラい目に合いましたので
これまでも品質を保つために各種検査ツールなどはあったのですが量とスピードを考慮して時代に沿う 形を模索しています。


ノード接続とは、ネットワーク接続用のデータや路線、道路基盤データ、地番図用の筆ポリゴンを作るために必要な形成線同士の交点が一致しているかどうかを検査してその後の処理に応用するための手法の事です。ひと昔前はプロット出力とかしたり画面チェックでやってたりしたのですが、あまりにも時間がかかり過ぎたり漏れがあったりしたのでツール開発に踏み切るようになりました。しかし処理要素数が増えると遅くなったりしてたのでプログラミングのロジック見直しする事になりました。

○印部分の頂点が接続されていない事がわかる

これまでは使用メモリをセーブする事も考慮して開発してましたが最近はメモリ価格の下落もありアマゾンで1000円程度でDDR2の1GBが購入できます。さっそく入手し実装してハードウェアとソフトウェアのベストな融合作業を発案。

テストデータは2種類用意してテスト。
旧のロジック(2分探索法=バイナリサーチ)
新のロジック(ハッシュ法←よくメモリを食う)とで比較しました。

具体的な目的は接続されていない頂点にマーキングを出すというものでした。
改良結果を以下に示します。


ハッシュ法とは、hash=切り刻むという語源から来てるアルゴリズムでハヤシライス(hashed beef rice)とかでもネーミングされています。
(関係ないけど、そういえば私は20歳くらいまでハヤシライスはハヤシさんが発案したからついた名前だと本気で思ってた(-o-;)

その中でもPerl等の連想配列で使われているチェイン法は格納部に衝突が起こると劇的に遅くなる事からノード数に変動あると実装が難しいと言われるオープンアドレス法を採用(超大変でしたが)。効果は・・・それなりに出ているようです。

旧ロジックのテストではMicroStationSE(V7)を使いましたが105万点のデータでやったところ処理数が1/3くらい(約5分)の所で暴走しました。32MBの壁を超えたようです。
効果の所は13.5倍ですが、たぶん暴走せずに3/3までやりきった事を想定して時間計算すると×3倍として40倍速いスピードになると思われます。

体感速度があがる事で技術者の成果品質も上がる・・・と期待します。