プログラミング言語AWK 第2版

8章アルゴリズムの実験

ものの動作を理解する最善の方法は、その縮小版を作成し実験を重ねることだ。この事実は特にアルゴリズムに当てはまる。実際のコードを書くと、疑似コードでは簡単に見過ごしてしまう問題でも浮き彫りにでき、問題点を明らかにできる。さらにこの機能縮小版プログラムは動作確認にも使用できる。動作が想定通りかをテストできるのだ。これは疑似コードではできないことだ。

Awk はアルゴリズムの実験に最適なツールでもある。プログラムを Awk で記述すると、言語の細部に迷うことなくアルゴリズムそのものに集中できる。そのアルゴリズムが大規模プログラムに組み込まれるのであれば、まず単体で動作するプロトタイプを実装すると開発生産性が向上するだろう。小規模な Awk プログラムを複数実装する開発スタイルは、デバッグ、テスト、性能評価の基盤構築に優れた威力を発揮する。この点はアルゴリズムを最終的に実装する言語の種類に依存しない。

本章ではアルゴリズムの実験について述べる。章の前半では、アルゴリズム入門コースによくある一般的なソートアルゴリズムを 3 つ取り上げ、Awk を用いテスト、性能測定、プロファイリングを行う。章の後半では、トポロジカルソートアルゴリズムを複数取り上げ、ファイルを更新する Unix コマンド、make にまで発展させる。

8.1ソート

本節では有名かつ有用なソートアルゴリズム、挿入ソート (insertion sort)、クイックソート (quicksort)、ヒープソート (heapsort) の 3 つを題材に取り上げる。挿入ソートは簡潔だが、効率的に動作するのは要素数が少ない場合に限られる。クイックソートは汎用性が高く、ヒープソートは最悪の場合でも性能が落ちにくい特徴を持つ。上記 ...