珠玉のプログラミング
珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造
- 作者: ジョンベントリー,Jon Bentley,小林健一郎
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2000/10
- メディア: 単行本
- 購入: 30人 クリック: 551回
- この商品を含むブログ (162件) を見る
この本の良いところは、単にアルゴリズムとデータ構造を紹介していくだけでなく、実装もきちっと考察されている点です。2つのアルゴリズムA,Bについて理論上(漸近的計算量)はAの方が優れていると結論付けることができても、キャッシュメモリ等の存在により必ずしもAの方が優れているとは限らないことについて、実測値を示しながら論じられています。
たとえば、単なる数列を実現する場合、配列を用いる方法とリンクトリストを用いる方法があります。要素の挿入や削除を考えると一般にリンクトリストの方がその処理量やメモリ使用量の観点から、リンクトリストを用いる方法の方が優れていると考えられます。しかし、要素の挿入や削除の頻度が低いアプリケーションだった場合、配列の要素はメモリ上に連続して配置されるため、キャッシュメモリの効果によって要素の参照の性能が非常に高くなります。その結果、そのアプリケーションには配列を用いる方法の方が優れていると結論づけることができる場合もあります。
この本は非常に良い頭の体操になり楽しめますし、プログラミングに必須の基礎知識を得ることができ、お勧めです。