Cythonによる内製地図ライブラリの経路検索の高速化

AI技術開発部アルゴリズムグループの谷本です。「マップマッチ・経路検索などのアルゴリズムを含む内製地図ライブラリ」のメンテナンスを主業務としています。今回はpythonによって実装された内製地図ライブラリ、特に経路探索部分をCythonを使って高速化した事例を紹介します。

経路検索について

経路検索は、指定した出発地点と目的地点を結ぶ2地点間の経路の中で「最も走行時間が短い経路」を探索する技術です。この経路検索で求まる経路は「出発地点から目的地点までたどり着くまでの通過する道路の一覧」になります。また、経路検索により「その経路を通過するまでの所要時間」も求まります。経路検索はタクシーアプリ『GO』の予想到着時間の算出に用いられています。

タクシーアプリ『GO』の経路探索は弊社で内製している地図ライブラリを用いて実現しています。

内製地図ライブラリの現状

内製地図ライブラリはpythonで実装していましたが、使用メモリ量・処理時間の関係からハイスペックなインスタンスを必要としていました。

そのため、内製地図ライブラリの道路データは省メモリのための「データの配列化とmemmapによるオンデマンド読み込み」をサポートした構造を過去に導入しました。(この独自構造の詳細は https://engineer.dena.com/posts/2020.03/automotive-big-data-structure/ にて紹介しております)

内製地図ライブラリの経路検索の問題点

残りは処理時間なのですが、scipyなどの既存の高速経路検索ライブラリを使って解決することができません。既存のライブラリは道路データを全てメモリ上に読み込む必要があるため、省メモリの観点で使えません。もちろん、これらのライブラリは「データの配列化とmemmapによるオンデマンド読み込み」をサポートした構造に対応していません。

よって、解決すべき問題は「内製地図ライブラリの独自データ構造」を保ったまま、経路検索の高速化する必要がある、ということになります。

Cythonの概要と高速化対応の技術として採用した理由

CythonとはpythonライクなコードをC/C++の枠組みでビルドして高速化を図るためのライブラリです(うまくやれば桁一つ違う高速化が実現できます)。Cythonの枠組みで書かれたコードは一度C/C++のコードに変換され、その後C/C++の枠組みでビルドされます。Cythonの特徴の一つは「一部だけCythonコードで残りはpython」という構造が可能なことです。

• 公式ページ: https://cython.org/

今回の経路検索機能の実装上の特徴は

• for文、while文が多い(ダイクストラ法で実装している)
• 道路ネットワークデータ構造を管理するクラスは「道路単位の走行時間」「道路の接続情報」を取得する際に、memmapされた配列に頻繁にアクセスする

です。Cythonは

• 明示的に型宣言することで、pythonで行っている「動的型付けによるチェック処理」を省略することができる。特に1文でも何回もチェック処理をかけるfor文、while文には効果覿面。
• numpyオブジェクトに多くアクセスする(MemoryViewとして扱うことで、高速にアクセスが可能。memmapされた配列にも対応)

のケースで高速化効果が十分出るため、内製地図ライブラリでの高速化手法をCythonにしました。

Cythonによる経路探索の高速化ポイント

Cython化は「変数や引数の型を明示的に指定する」ことが主な対応です。この対応だけで簡単なコードは桁一つ違う高速化効果が得られます。しかし、今回の経路探索ロジックの場合、経路検索メソッドのコード部分(ダイクストラ法のコード)だけ「変数や引数の型を明示的に指定する」ではうまく高速化できませんでした。

そこで、高速化効果を得るために工夫したポイントを2つ紹介します。

高速化ポイント(1) pythonのカスタムクラスを経由しないように処理を書き直す

最初にやった高速化の工夫です。

Cython化した経路検索メソッドの中で、当初道路ネットワーク構造を管理するクラス(pythonカスタムクラス)から「道路単位の走行時間」「道路の接続情報」を取得するメソッドを呼び出していました。これらのメソッドはCython化したコードの影響をうけないため、高速化しません。

解決策として、道路ネットワーク構造を管理するクラスのプロパティ(memmap型のもの)の中で経路探索に必要なものだけ取り出して、Cython化した経路探索メソッド上で参照させるようにしました。こうすることでデータ取得関連の高速化を図ることができました。

高速化ポイント(2) heapq, setの代わりにC++のpriority_queue, unordered_mapに置き換える

次にやった高速化の工夫です。

さらに高速化するためにpythonのライブラリであるheapq, setをC++のSTLの中にあるpriority_queue, unordered_mapに置き換えました。C++の世界のライブラリを使った方がpythonライブラリを使うよりも高速に処理できるためです。

Cythonによる高速化の効果

今回の改善が効果があったか、経路検索を実際に行って1件あたりの平均処理時間を比較します。

比較対象の手法は

• 手法1 : 内製地図ライブラリの経路検索(高速化前)
• 手法2 : 内製地図ライブラリの経路検索(「変数や引数の型を明示的に指定する」だけ)
• 手法3 : 内製地図ライブラリの経路検索(「変数や引数の型を明示的に指定する」+ 高速化ポイント(1) )
• 手法4 : 内製地図ライブラリの経路検索(「変数や引数の型を明示的に指定する」+ 高速化ポイント(1)(2) )

です。

検証用入力データは東京23区内の地点を出発地・目的地としたデータ100件です。この出発地・目的地は東京23区の中からランダムに取ってきました。

Cythonによる高速化前と高速化後の1件あたりの平均処理時間を比較すると、「変数や引数の型を明示的に指定する」だけでは大きな高速化効果は得られません。しかし、高速化ポイント(1)を入れることで手法1(高速化前)に比べて約20倍処理ほど処理時間が短くなっています。

また、高速化ポイント(2)を入れることでダメ押し的に処理時間が短くなっています。

最終的に内製地図ライブラリの経路検索は一番処理時間が短い手法4を取り入れています。

終わりに

今回の高速化によって、pythonでも「省インフラコストかつ高速な」経路検索エンジンの実現に成功しました。私たちアルゴリズムグループの属するデータサイエンティストは「データ分析」「機械学習モデル構築」だけでなく、このようなゴリゴリのエンジニアリングの仕事も行っています。そして・・・

We're Hiring!

興味のある方は 採用ページ も見ていただけると嬉しいです。

Twitter @mot_techtalk のフォローもよろしくお願いします！