珠玉のプログラミング

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

この本は本当に面白いです！取り上げられる問題は興味深いものが多いし、その解決方法となるアルゴリズムとデータ構造もいろいろと紹介されていきます。また、章末に練習問題がたくさん掲載され、どの問題も面白くうならせるものばかりです。残念ながらそれらの練習問題を解く時間がなかったので、時間があるときに実際にコーディングして確かめながらじっくりと解きたいものです。

この本の良いところは、単にアルゴリズムとデータ構造を紹介していくだけでなく、実装もきちっと考察されている点です。２つのアルゴリズムA,Bについて理論上（漸近的計算量）はAの方が優れていると結論付けることができても、キャッシュメモリ等の存在により必ずしもAの方が優れているとは限らないことについて、実測値を示しながら論じられています。

たとえば、単なる数列を実現する場合、配列を用いる方法とリンクトリストを用いる方法があります。要素の挿入や削除を考えると一般にリンクトリストの方がその処理量やメモリ使用量の観点から、リンクトリストを用いる方法の方が優れていると考えられます。しかし、要素の挿入や削除の頻度が低いアプリケーションだった場合、配列の要素はメモリ上に連続して配置されるため、キャッシュメモリの効果によって要素の参照の性能が非常に高くなります。その結果、そのアプリケーションには配列を用いる方法の方が優れていると結論づけることができる場合もあります。

この本は非常に良い頭の体操になり楽しめますし、プログラミングに必須の基礎知識を得ることができ、お勧めです。