計算量でわかる他の人が書いたコードを読む技術

はじめに

私はレコメンドを中心とする機械学習が専門でやっているのですが、最近 ruby のバックエンドも仕事で任されるようになりました。そこで身につけた私なりの速いコードの読み方を、計算量の観点から考えてみます。

ふつうのコードの読み方

まず、ふつうのコードの読み方を考えてみます。コードを読めと言われたら、いろいろファイルを見ていって、前にこんなクラスあったなと言って関連づけられるようになってきてコードが読めるようになってくるという感じかと思います。私は以前この読み方をしていました。
計算量で考えてみると、ループを１回回してまず読んで、２回目を回して使われているクラスがあるファイルなどを特定して関連付けるようなコードで読んでいるので、この場合の計算量は

$$O(n^2)$$

と言えます。

計算量が定数オーダーの読み方

ところが、計算量が定数オーダーの読み方が存在します。と言っても実践されている方からすれば当たり前のことかもしれません。
まずは、コードを読むとき、キーとなる根っこを掴みます。例えば router に記載されている route などです。そこからコントローラーに移り、モデルに移り、と読んでいくのは IDE の力を借りればポチポチするだけです。ポイントはベースのクラスを継承していることがあるので、そちらもポチポチするのを忘れないことぐらいでしょう。逆にモデル層などから上に遡りたい時はポチポチできる IDE でなければファイル検索でいけます。これはそんなに複数のクラスなどに枝分かれするものでないので、計算量はざっくり

$$O(1)$$

で読めてしまいます。

なんということでしょう、劇的に速くコードが読めるようになってしまいました。

まとめ

ただ、計算量的に不利な読み方が悪いと言っているわけではありません。その方が道中いろいろな発見があって楽しいかもしれません。大事なのは、今自分はどの計算量のコード、あるいはモードで読んでいるかを自覚することなのかなと思います。