効率のいい（主に速度面）コードの書き方、の身につけ方

はじめに

今までに何件かコード改善ネタを書いてきました。

• ベタなプログラムを徐々に改善していく試み（記述量と実行速度のトレードオフ）
• 数値計算を自力でしているコードをNumPyにさせるようにしたら700倍速くなった話
• 「n要素ごとの平均を計算する」の爆速化
• Boolean Indexを使った要素設定の高速化

これの元ネタ（改善を行ったコード）は全部学生さんの書いたプログラムなのですが、プログラムを直していて、

そもそも効率のいいプログラムを書く方法を知らないんじゃないのか。また、何をもって効率がいいというのか知らないんじゃないのか。

という気持ちが徐々に募ってきました。

そんなわけで今回はこの疑問に対しての考え、また、私の履歴を通してどのように効率のいいプログラムを書く方法を身につけていったかを紹介していこうと思います。

速さの発想

CPU的な話

私が初めてプログラミングを学んだのは20年前です。年で言うと1996年です。
1996年がどういう時代かと言うと、私が初めに買ってもらったPCのCPUの動作周波数は100MHzでした。つまり、「そもそもCPU自体が速くない」という時代です。スクリプト言語は遅い、Javaなんて重いから駄目だなんて時代です。

一方で現代。動作周波数は大体3GHzでしょう。単純に考えて30倍です。CPUアーキテクチャ自体も進化してますし、スクリプト言語で言うと処理系の改善、処理系をコンパイルするためのCコンパイラの改善（最適化能力の向上）、JITなんかもあったりして無茶苦茶速くなっています。こういう環境にいると、

遅くて苦労した

という経験がないままプログラムをそこそこに学び、あるときデータ量の大きいプログラムを書いてみたら遅い、どう直したらいいのかわからない、ということになるのではないかと思いました。

プログラミング言語的な話

次にプログラミング言語的な話について。
今どきですと「プログラミング勉強します！C言語頑張ります！」みたいに書くと「Cはローレベル過ぎる。Pythonから入るのがいいですよ」的なレスが飛んできます。この話は次に続くので先に一言だけ書いておくと、

Pythonで書いたとして、遅かったとして、このスピードが最大速度（これ以上速くならない）と思っているのではないか

という気がします。本人に聞いたわけじゃないので推測ですが。

プロセッサレベルで考える

私が初めて学んだ言語はBASICです。
高校のコンピュータ部に入っててベーマガに掲載されてるプログラムをぽちぽち入力してゲームで遊んでいました。そこにはBASICの他に機械語なる謎の16進数があり入力してました。掘り起こしての記憶なので捏造が入ってるとは思いますがそこで「こいつ（BASIC）は遅い。速くするために一部の処理を機械語で直接書いている」という発想が身についたのだと思います。

さて、高校では他にコンピュータに詳しい友人がいてC言語というものがあることを教えてもらい、C言語も勉強していました。読んだ本にはインラインアセンブラの話も載ってた気がします。その他、アセンブラというものがかなり身近な状態でコンピュータに触れていました。

と、若者に嫌われるおっさんの武勇伝でもない話はこれぐらいにして何が言いたいかというと、

究極まで速さを追求するならアセンブラだ。これ以上速くはならない¹

ということです。と言っても私も常にアセンブラレベルで考えているわけではありません。別の言い方をすると、

速さを追求する必要があるとき、必要であればアセンブラ、プロセッサがどう実行するかまで追っかけて調べる意気込みを持て

となります。私の記事でPythonの話なのにすぐに生成されるバイトコードとかC実装の話にまで言及しているのはそのためです。少し寄り道してこの件について書いておくと、

すぐに実装に踏み込んで「実装がこうだから」と実装に依存したコードを書くのは最悪だ。しかし、実装について知っていると知っていないでは知っているに越したことはない。

となります。
話を戻して改めて書くと、

速さを追求する必要があるとき、ライブラリ、別言語、機械語まで徹底的に追及しろ

ということで、実際私は遅いけど何が原因だ？ってときすぐにライブラリの中に入ってどう実行されているのか見ています（結果、次に述べるような「ああ、俺のライブラリの使い方が間違ってたわ」とわかることもよくあります）
そこで必要とされるのはソースコードリーディング能力ですね。まあこれは趣味・趣向の力がかなり大きいですが。

ライブラリを使いこなす。あるいは数学的思考

改善ネタには「NumPyに計算させたら超速くなった」というのが何件かありますが、ここで出てくるのは「速さの発想」で挙げた「遅くて苦労した」経験がなく、「NumPyってのがあるらしい。速いらしい。これ使って書けばいいんだな。forループ・・・」

そうじゃねえ。

私の記事で書いており、他の人も書かれていますが、

Pythonでfor文書いてたらNumPy使ってても意味はありません

for文もNumPyにやらせましょう。あなたは行列計算式を書けばいいのです。そう、必要なのは行列の知識です。

私はどうやって身につけたかというと、どうやって身につけたんだろう、覚えていません（ぉぃ
情報系だったので授業でデジタル信号処理とか出てきて当時はあんまりよくわかってなかったけど「行列使うと複数の式がまとめて記述できるんだな」ってぐらいは思ってたのかもしれません。記憶を捏造していると思いますが。

現代であればまともなAIの技術本を読めば行列計算は書いてあるしPython使ってやってみようぜってことで自分でfor文書かない書き方もされてるし、何が言いたいかというと本を読めということです。

あるいはライブラリのチュートリアル。ここにはもちろんfor文使った書き方なんてされてません。ん？英語は苦手？

お前は何を言っているんだ（ミルコ略）

とりあえず読め。読んでいればなんとなく書いてあることはわかってくる。機械翻訳の性能はここ数年大きく向上したが頼るな。英語は英語のまま読め。まあ頭の中の思考言語は日本語でも構わん。

考えるな感じろ（ジャッキー略）

ちゃんとした口調に戻ると(笑)、英語で書いてあるからと言って物怖じするのではなく書いてあることを理解しようとする姿勢が重要です。「日本語の解説ないかな」と探すと結局解説書いた人の解釈をなぞることになってしまいます。「原著を当たれ」です。

アルゴリズム特に計算量

Boolean Indexを使った要素設定の高速化でおまけ的に触れていますが、アルゴリズムは重要です。特に計算量の概念です。$O(n)$とか$O(n^2)$とかいうあれです。
つまり、データが10倍になったらどうなるのかを考える、$n^2$オーダーなのだったらもっとオーダーを下げれないかを考えるということです。

で、どうやって私は身につけたですが、とりあえずアルゴリズムの本は読みました。大学1年ぐらいに。大学2年でアルゴリズムの授業がありましたがもう全部知ってました。アルゴリズムの本というと普通書いてあるのはソートの話、ソートなんてライブラリ使えばいいやんと思うかもしれませんが、

大事なのは計算量の概念

大切なので2回言いました。つまり、お題は何でもいいのですが、問題があり、それを解決する方法をいろいろ変えると計算量がどう変わるか、を知るためにアルゴリズムの本は読んでおけということです。おすすめを挙げるとしたら『数学ガール／乱択アルゴリズム』ですかね。あの書籍に書かれているソートの計算量の算出プロセスは秀逸です。

まとめ

ポエムなので特にまとめなくてもいいのですがまとめると以下ぐらいがこの記事の主張となります。

• 現代はCPUなどが十分速く小規模なプログラムでは「遅さ」が体感できない。そのままの考えで行くからデータ量が大きくなったときにどう改善すればいいかわからないのではないか
• 速さを追求する必要があるのならアセンブラレベルまで追求することを恐れるな
• ライブラリは作者の意図に沿った使い方をしよう
• 計算量の概念を持とう。もっといい方法（アルゴリズム）がないか考えよう
• 本とかチュートリアルとか、とにかくいろいろ読もう

1. アルゴリズム自体の改善は除く。その話は後で ↩