プログラミングの基礎テクニック

はじめに

こんにちは、結城浩です。

ここは、月刊誌『C MAGAZINE』で『プログラミングの基礎テクニック』という連載を書いていたときのサポートページです。

この連載では、問題と解決の間のギャップを埋めるテクニックとして、

基本的なアルゴリズム
プログラミング言語のイディオム
そのほかの技法

の中から、よく使われるものを選び、具体的なプログラム例と図を使って解説します。

プログラミング言語としてはJavaやCなどを用いています。文法は理解しているけれど、経験が浅いという人を対象にして解説しますが、できれば、熟練者にとっても新しい発見があるような内容も盛り込んでいます。

内容

第1回 (2003年12月号) : Buffering ―― まとめ買いのメリット

デバイスへのアクセスに時間がかかる場合、アクセス回数を減らすことによって高速化をはかることができます。利用者とデバイスの間にバッファというメモリ領域を用意することで、デバイスへのアクセス回数を減らすことができます。

第2回 (2004年1月号) : Caching ―― すぐまた使うならそばに置け

いま、準備するのに時間がかかるデータを扱っているとしましょう。準備ができたデータを、 キャッシュと呼ばれるメモリ領域に一時的に保持しておけば、スピードアップをはかることができます。

第3回 (2004年2月号) : Binary Search ―― 問題空間を二分せよ

最も有名な検索アルゴリズム、バイナリサーチを紹介します。バイナリサーチは一言で言えば「検索対象を毎回半分に減らしていく」という検索方法です。検索対象データを繰り返して二分することで、log nのオーダーで検索対象を見つけることができます。ただし、前もってデータはソートされている必要があります。

第4回 (2004年3月号) : Quick Sort ―― 最速のソート

最も高速なソートアルゴリズム、クイックソートを紹介します。クイックソートは一言で言えば「数列を、注目している数よりも大きい部分と小さい部分に分けていく」というソート方法です。挿入ソートと比較してみます。

第5回 (2004年4月号) : Recursion ―― 再帰的な構造と再帰的な呼び出し

レベルNの問題を、レベルN-1以下の問題に帰着して記述する再帰という方法を紹介します。階乗の計算をCで書いたり、ListのS式のサブセットをJavaで解析したりします。

第6回 (2004年5月号) : Serialization ―― 構造化データの保存と復元

構造を持ったデータをファイルとして保存したり、ネットワークを通じて送ったりする必要が生じたとしましょう。その場合、メモリ上のデータをそのまま送るわけにはいきませんから、複雑な構造を壊さないように注意しながら一次元のバイト列に変換します。これがシリアライゼーションです。 PerlとJavaでシリアライゼーションの例を示します。

第7回 (2004年6月号) : Reflection ―― 自分のことを知っているオブジェクト

リフレクションというのは、「プログラムがプログラム自身の情報を取得・実行することができる」という性質のことです。オブジェクト指向プログラミングで言えば「オブジェクトがオブジェクト自身のことを知っている」と表現してもよいでしょう。リフレクションの機能を利用して、簡単なクラスブラウザをJavaで作ります。

第8回 (2004年7月号) : CallbackとFuture ―― 非同期的な処理

非同期的な処理を行うための技法としてCallbackとFutureを紹介します。 Callbackというのは、呼び出した先から呼び出し元を「呼び返してもらう」ことです。処理の結果が必要なときには、Futureが役に立つことがあります。 Callbackでは処理の結果をいわば「送りつけられる」ことになりますが、 Futureを使うと、非同期的な処理を行いながらも、処理の結果を自然な形で取得することができます。