プログラミング実習 III (クラス 4)
- [B8] 二分探索とハッシュ
  - シェルスクリプトによる作業の自動化
    - シェルとシェルスクリプト
    - 課題 (8-3) を自動化してみる
  - Nano Banana Pro によるハッシュ法の説明スライド

プログラミング実習 III (クラス 4)

[B8] 二分探索とハッシュ

シェルスクリプトによる作業の自動化

シェルとシェルスクリプト

現在、みなさんは Windows 上の Cygwin で実習を行っている。 Cygwin は、 Windows 上で Linux 環境 (より正確には POSIX 互換の API レイヤ) をエミュレーションするためのライブラリやプログラム群である。 Cygwin を使うことで、 Windows を使いながら、 Unix 系 OS 特有の強力なツール群を利用することができる。

Cygwin Terminal を実行すると、その中では bash (GNU Bourne-Again SHell) が動作している。多くの Linux ディストリビューション (Debian GNU/Linux, Ubuntu, CentOS 等) では、この bash が標準のシェルとして採用されている。 bash は、 UNIX の初期から存在する歴史あるシェル「sh (Bourne Shell)」の上方互換となっている。 sh の機能を包含しつつ、コマンドライン編集機能やヒストリ機能などが強化されている。 sh シェルは、 UNIX の国際標準規格である POSIX (Portable Operating System Interface) にもその仕様が規定されており、 bash もまた POSIX 準拠のシェルである。したがって、ここで学ぶ知識は、将来どのような UNIX/Linux 環境 (macOS のターミナルを含む) に移行しても通用する汎用的なスキルとなる。

sh や bash は単なるコマンド入力の窓口 (ユーザーインターフェース) であるだけでなく、強力な「プログラミング言語」でもある。これらを用いて記述されたプログラムを「シェルスクリプト」と呼ぶ。普段、 Cygwin Terminal 上で ls や gcc などのコマンドを入力している時は、 bash を「対話的 (interactive)」に利用している状態である。つまり、プログラミング言語としての制御構造 (ループや条件分岐など) をほとんど利用せずに、個々のコマンド入力や実行のために使用している。

C 言語におけるソフトウェア開発を支援するツールは多数存在する。統合開発環境 (IDE) も便利だが、 UNIX 環境では、課題 B6 の時に紹介したような Emacs や vim などのテキストエディタ、ビルドツール make、デバッガ gdb などを組み合わせて使うのが伝統的であり、現在も広く用いられている。これらは「一つのことをうまくやる (Keep It Simple Stupid)」という UNIX 哲学に基づいて設計されている。これらのツールをシェルによって組み合せて利用することで、快適な開発環境が実現できる。

効率的なプログラミングのためのヒント
https://lsnl.jp/~ohsaki/lecture/pro3/2025/b6/#1-1

UNIX の効果的な利用法を体系的に学ぶには、ブライアン・カーニハンとロブ・パイクの名著「UNIX プログラミング環境」を強く勧める。単にシェルスクリプトの文法や書き方を学べるという表面的な知識にとどまらず、「ソフトウェアツールズ」といった UNIX の思想や哲学、 UNIX を効果的に利用するための「考え方」を学ぶことができる。情報系を学ぶ学生さんは、ぜひ一度は読んでみて欲しい。

UNIXプログラミング環境
https://opac.kwansei.ac.jp/iwjs0001opc/catdbl.do?pkey=BW00000843&formkeyno=329091656hXV5sE8R1E&startpos=11&hitcnt=11&tab_num=0

課題 (8-3) を自動化してみる

シェルスクリプトの具体例として、課題 (8-3) の作業を自動化してみよう。

課題 (8-3) では、アルゴリズムの性能評価を行うために、 GCC の最適化オプション (-O や -O2) がある場合とない場合について、特定の 10 個のレコードに対して線形探索を実行した時の実行時間を計測する必要がある。手動で何度もコマンドを実行して時間を計測し、それらの値のエディタ等にコピー & ペーストする作業は、退屈なだけでなく、人為的ミスの温床となる。面倒なことは人間がやるのではなくコンピュータにやらせよう。

こういった「同じような処理をパラメータを変えて複数回実行する時」や「手順が決まっている定型作業」にこそ、シェルスクリプトによる自動化の真価が発揮される。実験の再現性を担保するためにも、処理の自動化は重要である。

以下では、 bash 独自の拡張機能（配列や高度な変数展開など）はできるだけ使わずに、最も基本的な sh シェルの機能を用いる。非常に素朴なシェルスクリプトを書くことで作業を自動化する方法を示す。

プログラミングの基本戦略である「分割統治法 (Divide and Conquer)」は、スクリプト作成にも適用できる。いきなり全ての処理を行う巨大なスクリプトを書くのではなく、機能ごとに以下の小さなスクリプトに分割して作成しよう。

1. 最適化オプションなしでコンパイルするスクリプト
2. 最適化オプションありでコンパイルするスクリプト
3. あるレコードを探索した時の CPU 時間を表示するスクリプト
4. 10 個のレコードをそれぞれ探索した時の CPU 時間を表示するスクリプト

まず、最適化オプションなしでコンパイルするスクリプト build.sh だ。

#!/bin/sh -x
gcc -Wall iata_cpu1.c iata_db.c
echo ZYL | ./a.out

このスクリプトでは、まず、 iata_cpu1.c と iata_db.c を最適化オプションなしでコンパイルしている。その後、正しく動作するかを確認するためにレコード ZYL を入力としてテスト実行している。 1 行目の #!/bin/sh はシェバン (shebang) と呼ばれ、このファイルを実行するインタプリタを指定している。ここでは -x オプションを付与しており、実行されるコマンドが逐次表示されるようにしている。

作成したスクリプトを実行するためには、 chmod コマンドでファイル build.sh に実行権限（実行ビット）を付与する必要がある。これにより ./build.sh として直接実行できるようになる (先頭の $ はシェルのプロンプトであり、入力の一部ではないことに注意せよ)。

$ chmod +x build.sh
$ ./build.sh
+ gcc -Wall iata_cpu1.c iata_db.c
+ echo ZYL
+ ./a.out
key = ZYL => Sylhet : Bangladesh - Sylhet Airport
cpu = 0.503725 [sec]

先頭に + が表示されている行は、sh のデバッグ用の出力である。シェルスクリプトの先頭で sh に -x オプションを渡しているため、実行した行がそれぞれ表示されている。 build.sh の実際の出力は以下の 2 行のみである。

key = ZYL => Sylhet : Bangladesh - Sylhet Airport
cpu = 0.503725 [sec]

次に、最適化オプションありでコンパイルするスクリプト built-opt.sh を作成しよう。

#!/bin/sh -x
gcc -Wall -O2 iata_cpu1.c iata_db.c
echo ZYL | ./a.out

内容はさきほどの built.sh と同じであるが、 gcc の引数に -O2 オプションを追加している点だけが異なっている。

これも実際に実行してみよう。

$ chmod +x build-opt.sh
$ ./build-opt.sh
+ gcc -Wall -O2 iata_cpu1.c iata_db.c
+ + ./a.out
echo ZYL
key = ZYL => Sylhet : Bangladesh - Sylhet Airport
cpu = 0.477456 [sec]

これでコンパイルと動作確認の自動化ができた。 CPU 実行時間の計測の自動化に移ろう。

まず、ある特定のレコードを探索した時の CPU 時間を表示するスクリプト measure.sh を作成する。プログラム a.out の出力には余計な情報も含まれるため、 CPU の実行時間だけを抽出（フィルタリング）する。

#!/bin/sh
key=$1; shift
echo $key | ./a.out 2>&1 | grep 'cpu =' | awk '{ print $5 }'

このシェルスクリプトは、引数として探索するキーを受け取り、以下のように実行する (chmod +x をあらかじめ実行しておく必要がある)。

./measure.sh ZYL
0.416165

このスクリプトでは、まず、コマンドライン引数の 1 番目 (ここでは ZYL) の値を変数 key に格納している。次に、変数 key の値を、プログラム a.out の標準入力に与えている。プログラム a.out は、「cpu = 0.477456 [sec]」のような形式で標準エラー出力に書き出すという仕様になっている。そこで、標準エラー出力を標準エラー入力にリダイレクトし、 grep と awk というコマンドを利用して、 CPU 実行時間の数値のみを取り出している。

これで、単一のレコードに対して CPU 時間を表示するプログラムができた。後は、計測したい 10 個のレコードに対して、この measure.sh を繰り返し実行するだけだ。

10 個のレコードをそれぞれ探索した時の CPU 時間を表示するスクリプト run.sh は以下の通り。

#!/bin/sh
for key in AAC CXI IYK MVD SJW YFB ZYL AAA LLL ZZZ
do
    echo -n "$key "
    ./measure.sh $key
done

ここではシェルの for ループを使用している。chmod +x した後、早速実行してみよう。

$ chmod +x run.sh
$ ./run.sh
AAC 0.000758
CXI 0.077451
IYK 0.147220
MVD 0.204501
SJW 0.221721
YFB 0.297454
ZYL 0.411627
AAA 0.842136
LLL 0.870249
ZZZ 0.858599

このように、単一のシェルスクリプトを実行するだけですべての計測が完了し、整形されたデータが得られる。

シェルには、ここで紹介した以外にも高度な機能がたくさんある。例えば、最適化オプションのある/なしでシェルスクリプトを 2 つ用意する必要はない (実行時オプションで切り替えられる) し、今のシェルスクリプトはコマンドがエラーにならないことを前提としている。実際にはエラー処理を組み込むことが望ましい。

しかし、単純な用途であれば、シェルの基本的な機能だけでここまでできる。

Nano Banana Pro によるハッシュ法の説明スライド

Q.データ構造とアルゴリズムにおけるハッシュの概念を、情報系の学部 3 年生が理解できるように、イラスト付きで解説する 1 枚スライドを作成して

Hiroyuki Ohsaki (ohsaki[atmark]lsnl.jp)