「珠玉のプログラミング」のチュートリアル的な読みもの
先日｢自然言語処理を活用したwebサービスをつくるときに参考になる5冊の書籍｣というタイトルで本を紹介したら評判が良かった。本記事では最初の一冊である「珠玉のプログラミング」のコラム1を読みつつチュートリアル的な記事を書いてみる。
さて、早速コラム1「真珠貝を開いて」を読み始めると著者が「ディスク上でのソートをしたい」という質問を受けたという話が書いてある。ここで、開発のお仕事をしている人はなんとなく想像が付くと思うのだが実は質問者は「ディスク上でのソートをしたい」わけではない｡
フレンドリーな会話に潜むトラップ！？
「1.1 フレンドリーな会話」を読むと書いてあるように質問者は「メモリがほとんど使えない状況で重複のない数値データをソート」したかったのだ。そして質問者は思考の末「ディスク上でソートをする」という結論に達し著者に相談した、というわけ。大抵の場合、質問者は問題に対してなんらかの方法を思いついていて、その方法の実現しかたを聞いてくる。なので質問を受けたら、やらないといけないのは「そもそもの問題が何なのか」を知ることだ、ということが書いてある。
また著者は質問者に対して、データの性質やサイズ、使えるメモリについて情報を聞き出している。これはとても重要。よくあるのが「汎用的なデータに対して結果を出せる方法」を考えてしまう罠。実際は扱うデータを知ることで「特定の状況で非常にうまくいく方法」を取ることができる。優れたエンジニアは「特定の状況で非常にうまくいく方法」をたくさんストックしていて、個々の問題に対して適切にぶつけることができる。
データの性質と解くべき問題をはっきりさせましょう！
「1.2 問題の正確な定義」では上で聞き出した情報に基づいて問題点を正確に定義している。ここが本当のスタート地点。質問者の問題定義を鵜呑みにせず、自分で問題点を整理しよう。で、問題の正確な定義は「10,000,000より小さい重複のない自然数の集合」を「メモリが1MB使える」ときに「昇順ソートする」ことであることがわかる。
一回の処理で扱うデータは小さく
「1.3 プログラムデザイン」ではデータをメモリに乗るサイズに分割して処理する方法を考えている。各データは10,000,000以下の自然数なので32bitの整数型を使えば十分に格納できる(2^32 = 4,294,967,296 > 10,000,000)。するとメモリが1MB( = 8,000,000bit)使えるので(8,000,000 / 32 = )250,000個のデータをメモリに載せられる。
なので最初はデータが250,000より小さいものだけ処理する、次は250,000以上で500,000より小さいものを処理する、というようにして40回繰り返せば全体をソートできる。このように一回の処理ではデータのうち自分が扱う範囲のデータ(例えば250,000以下の整数)だけ処理して、あとは素通しする。というテクニックはお仕事でも頻繁に使うので覚えておくと何かと便利。ちなみに今回この手法を取ることができたのはデータが高々10,000,000なので40回のループで終わるとわかっていたから。これが取りうる範囲がもっと大きかったら別の方法を考えないといけなかったかもしれない。このようにデータの範囲を把握しておくのはとても重要。
ビット演算まじぱないです
さて、これでそれなりに高速なソートができたわけだが、やはり40回ループさせるのは気になる。ということでより高速な方法を「1.4 コードのスケッチ」で紹介している。ここでは「データに重複がない」という情報も使っている。データに重複がなくて、データの上限もわかっているならデータをビット列で表現することが可能だ、という話。
データをビット列で持たせる話は過去に簡潔データ構造の記事でも少し触れたのだがデータサイズを非常に小さくできる(= 大きなデータもメモリに載せられる)ので大変有効なことがある。
さてビット列を使うと「ある数値がデータに含まれていればビットを立てる」という表現をすることができるのでデータサイズはデータの上限である10,000,000bitあればよい。メモリは1MB( = 8,000,000bit)使えるので、ビット列を用いた手法なら2ステップで処理が可能になる。
これはすばらしいまとめ
1.3のデータ分割の手法と、1.4のビット列を用いる手法を組み合わせると使えるメモリやデータの範囲に応じで柔軟にソートが可能になるよ、ということがわかる。そして最初の「ディスク上でのソート」に比べて速度も使用メモリも小さくすることができた。
一般に「使用メモリと速度はトレードオフの関係にある」といわれているが、今回ように、そもそも筋の悪い手法がまかり通っている場合は正しく問題を扱うことで使用メモリ、速度どちらも改善できますね、ということが「1.5 原則」に書いてある。この節で書かれていることは大変重要なので熟読するといいと思う。
問題を解いて体力をつけましょう
最後に「1.6 問題」だが、どれも優れた問題なので飛ばさず挑戦してみると良いと思う。特に2,4,6,9,10の問題のテクニックは知っていると便利なことが多い気がする。
すごい人はまじすごいので注意しよう
というわけで「珠玉のプログラミング」のコラム1のチュートリアルを書いてみた。久しぶりに読み返したが改めて良書だと実感した。本書で書いてある事柄は優れたエンジニアが無意識のうちにやっていることばかり(少なくとも私も周りのすごい人達は息を吸うように自然に実践していた)なのでぜひ身につけたい。
優れた人々は無意識にやっているので、あまりこういうことは教えてもらえない(というか当然やっていますよねJK、などと思われていたりする)ので本書のように、あらためて書いてくれている本は大変貴重だと思った次第。すごい人達が「ナイーブな手法でいいんじゃね」という時は「本書で書いてあるようなことを当然踏まえた上で適切にナイーブな手法を組み合わせて使っている」という意味だったりするので十分注意したい。
