当時の全校生徒の諸君! …ごめん。
「クラブの申込みを振り分けるプログラムを作ってくれないか」
理化部の顧問の引地(ひきち)先生からこういわれたのは高校三年の四月、 部活動と称してコンピュータ室で駄弁っているときだった。 「クラブ」というのは理化部のような課外活動のことではない。 時間割に組み込まれていて生徒全員に強制されている、 いわば授業の科目のひとつだ。 「正課クラブ」といえばわかる人もいるだろう。その選択肢は 生徒からみるとつまらないものが多かった。 「バスケット」のように課外活動にも同じものがあって部員が集まってくるような ものを除けば、生徒が自主的に選択したくなるようなものはほとんどなかった。 だから“積極的に動いたり資料を用意することなく時間をつぶせる”ような クラブ—たとえば読書クラブ—に人気が集中していた。
年度のはじめに、生徒は入りたいクラブを第三希望まで決めて申し込む。 申し込みが定員を越えていた場合は抽選が行われ、漏れたものは 第二・第三希望へとまわされていく。高倍率のものばかり書いてしまい 第三希望の抽選にも漏れ、定員割れのまったく不本意な クラブにまわされたクラスメイトの叫びを聞かない年はなかった。 申込み用紙を集計し各クラブの定員に応じて振り分ける作業は 先生の間でもちまわりの仕事らしい。今年は我らが顧問の引地先生にまわってきた というわけだった。
それは私が人から依頼された二番目のアプリケーションだった。 大人が、自分の作るプログラムは実用に耐えうると判断しているのは とても晴れがましかった。私は二つ返事で引き受け、プログラムを書きはじめた。
全校生徒は約1500人だった。
マシンはNEC PC-8001(ユーザメモリ32Kバイト)、言語はN-BASICである。 ディスクの類はついておらず外部記憶は600ボーで読み書きする テープレコーダだけだった。8001からは巻き戻しや録音/再生を制御できないので ランダムアクセスは不可能だ。 となると、すべての作業をオンメモリで処理せねばならない。
クラブは20ほどあった。そこでまず
| バスケット | … | 1 |
| ソフトボール | … | 2 |
| : | : | |
| コンピュータ | … | 19 |
| 読書 | … | 20 |
のように「科目コード」を適当に決めた。プログラムの中で一人の生徒は 第一〜第三希望のみっつの科目コードをもつことになる。
はじめ私は配列のインデックスに生徒番号を使おうとした。 生徒番号というのは在校生徒に割り当てられる四桁の数字である。 たとえば私の当時の生徒番号は3902だったが、 これは私が3年9組の出席番号2番の生徒であることを意味する。
100 DEFINT A-Z 110 DIM RQ(4000, 3)
これはコンピュータの中に次のような表を作るのと同じだ。
1 2 3
┌──┬──┬──┐
1│ │ │ │
├──┼──┼──┤
2│ │ │ │
├──┼──┼──┤
3│ │ │ │
├──┼──┼──┤
:
├──┼──┼──┤
3902│ 19 │ 20 │ 2 │
├──┼──┼──┤
:
├──┼──┼──┤
4000│ │ │ │
└──┴──┴──┘
たとえばRQ(3902, 3)の値が2だったら、それは 私の第三希望がソフトボールクラブであることを表すわけだ。 しかし、これは宣言のところですぐにエラーが出た。
run Out of memory in 110 Ok _
確保する配列の大きさをもっと小さくしなくてはならないようだ。 すぐ思いあたったのは、生徒番号は1001からはじまるということだった。 RQ(1, x)〜RQ(1000, x)は全く使われない。インデックスを生徒番号から 1000をひいたものにすれば要素の1/4を減らすことができる。
100 DEFINT A-Z 110 DIM RQ(3000, 3)
1 2 3
┌──┬──┬──┐
1│ │ │ │
├──┼──┼──┤
2│ │ │ │
├──┼──┼──┤
:
├──┼──┼──┤
2902│ 19 │ 20 │ 2 │
├──┼──┼──┤
:
├──┼──┼──┤
3000│ │ │ │
└──┴──┴──┘
しかしプログラムはDIM文にさしかかるとOut of memoryを出した。
さらに考えてみた。クラスの生徒数は50人未満だから、 RQ(50)〜RQ(99)は使われない。RQ(1050〜1099)も同様、以下同じだ。 考えてみれば1500人の生徒のために3000要素の配列を確保する 必要はない。まだ半分以上の要素が使われないのだ。 そこで生徒番号を保持する配列を別に用意することにした。
100 DEFINT A-Z 110 DIM SN(1400), RQ(1400, 3)
SN RQ 1 2 3
┌──┐ ┌──┬──┬──┐
1│ │ │ │ │ │
├──┤ ├──┼──┼──┤
: :
├──┤ ├──┼──┼──┤
1314│3902│ │ 19 │ 20 │ 2 │
├──┤ ├──┼──┼──┤
: :
├──┤ ├──┼──┼──┤
1500│ │ │ │ │ │
└──┘ └──┴──┴──┘
インデックスには意味はなくなった。RQ(100, 3)はたまたま100番目に 入力された生徒の第三希望を持つ。そのかわりSN(100)にその生徒の 生徒番号を記録しておくのだ。要素を半分近くに減らしたが、新しい 配列を作ったので全体としては1/3の節約だ。
しかしこれも駄目だった。プログラムはOut of memoryを出した。
腹を立てながら生徒番号について考えた。1年1組の1番から3年9組 の43番まで素直に1から13xx番という生徒番号がついていたら こんな苦労をしなくてすむのに。 なぜそうなっていないのか。もちろんそれでは人間が処理しにくいからた。 人間が各桁をみて学年や組を知ることができるようになっているほうが 都合がいいからだ。ではもしすべての処理を計算機でやるようになれば 生徒番号は連続になるだろうか。—いや、ならないだろう。 生徒番号は、もともと“インデックス”として使うのに適した数ではないのだ。 学年・組・出席番号を4桁に固めた“データ”にすぎないのだ。
これが頭のなかではっきりすると、目的のためにはこの「生徒番号」を 拡張して処理すればよいことに気がついた。
3902192002 ====--==-- | | | +-- 第三希望 | | +---- 第二希望 | +------ 第一希望 +-------- 生徒番号
このようにすれば、生徒番号と希望科目の情報は10桁の数字におさまる。 10桁の数字なら単精度の変数ひとつにおさまるから単精度の配列ひとつで すむではないか。
100 DEFINT I-K 110 DIM S!(1500)
S!
┌─────┐
1│ │
├─────┤
:
├─────┤
1314│3902192002│
├─────┤
:
├─────┤
1500│ │
└─────┘
今度はOut of Memoryは出なかった。
「同じ種類の部活動(課外活動)をやってる者を優先してするようにしてくれ」
プログラムの本体を作っていると引地先生がやってきてこう注文をつけた。 つまりバスケットクラブへの申し込みが定員オーバーしたら、バスケット部の 部員を優先して入れるようにしろということだ。 「ええっ。…じゃあ申し込み用紙には、どの部に入ってるかも書いてもらわないと いけませんね。部活動の一覧はないでしょうか。部活のコードも決めないと…」 「いやいや、部活に入っている者には希望するクラブの番号をマルで 囲むようにいうから。プログラムに入力するときも、マルがついてるかどうかを 入れられるようにしてくれればいい。あとはそれを優先的に振り分ける ようにしてくれ。難しいかな」「い、いえいえ。できますよ」 かくしてデータは11桁になった。
39021920021 ====--==--= | | | | +- 優先権あり | | | +--- 第三希望 | | +----- 第二希望 | +------- 第一希望 +--------- 生徒番号
「優先順位を考慮した振分け」という挑戦的な課題に夢中になっていた 私は、桁が増えたということにはあまり注意を払わなかった。 11桁の数は短精度に収まらないが、倍精度なら収まる。 あとは各データの取りだしのところを変更すれば何でもなかった。
100 DEFINT I-K 110 DIM S#(1500)
S#
┌──────┐
1│ │
├──────┤
:
├──────┤
1314│39021920021 │
├──────┤
:
├──────┤
1500│ │
└──────┘
これも大丈夫、Out of memoryは出ない。
かくしてプログラムは完成した。 少数のサンプルデータを作って試してみた。通常の場合はもちろんのこと、 定員のデータを本番よりもずっと小さく設定して、定員があふれたときに どうなるか・優先権のある生徒の希望があふれたときにどうなるかなど 思いつく限りのケースを試してみた。 それは完璧に動いているようにみえた。引地先生に操作方法を説明し、 プログラムをセーブしたテープを渡した。
「入力したけど、3時間黙りっぱなしだよ」
次の日の放課後、部活動に出てみると先生は心配そうに告げた。 なにせPC-8001とN-BASICである。データはひとつの変数に圧縮してある。 広いワークエリアがとれないため、各情報は必要になるたびにいちいち 何度も割り算をして取り出すようになっている。優先順位を考慮する部分も 「交換ソート」だ。遅いのはあたりまえだが、どのくらい遅いかを見積もる ことまでは当時の私にはできなかった。10分以上黙って走るような プログラムを作ったのはこれで二度目だった(一度目は素数の生成である)。
念のため、次のクラブの処理が始まるときに画面にその旨を表示するように してあった。じっとみていると数分おきに表示が更新されている。 プログラムのミスで無限ループにおちこんだわけではないようなので 「大丈夫だと思います」と答えた。それから2時間後、プログラムは結果を プリントしはじめた。
「あいつは剣道クラブを第一希望にしたのに落ちたんだぜ。 なのに第二希望の俺がなんで入れたんだ?」
プログラムがおかしいということがわかったのはクラブが決定して 数週間も立った後だった。最初に書いたようにクラブの申し込みは極端に 偏る。だから不本意なところに振り分けられたたくさんの生徒が不満を 漏らすのは毎年のことだった。単なる勘違いをもっともらしく 広めるものもいた。友達からこの話を聞いたとき、彼の勘違いか、 たまたま引地先生が入力を間違えたのだろうと私は思った。 プログラムの設計上たとえ第二希望のクラブにマルをつけていても第一希望の生徒よりも 優先して振り分けることはないはずだった。しかしこのての話題に 注意していると、登場人物は違うが同じ内容のエピソードを持ち出して 不満をもらすパターンが例年より多いような気がした。 ふつう生徒はクラブ振り分けがどのように行われているか知らないので 「先生がた」や「学校」に相当腹を立てている者もいた。ぎくぎくっ。
私はプログラムを見直した。他の部分に間違いがあったとしても希望 の逆転が起こることだけはありえないように見えた。 どうしてそういうことが起こるのかついにわからなかった。入力時の まちがいだと思いたかった。それでも引地先生に事情を話した。
「そうかね。まあ当分、振分けの仕事は僕にはまわってこないから、 あのプログラムはしばらく使わない」
という返事が返ってきた。一応安心はしたものの、学校の標準ツールとして 毎年使うのではなく引地先生が個人的に楽をするために依頼してきたのだと わかって拍子抜けもした。
何がおかしいのかがわかったのは、大学で情報理論の基礎と 不動小数点数の内部表現について学んだあとだった。 「倍精度の変数は16桁の数値が扱える」とマニュアルには書いてある。 高校生の私は、これは-9999999999999999〜9999999999999999 のすべての数が表せるものだと解釈していた。 しかし情報量の原理から考えればこんなはずはない。NBASICの倍精度 の変数は4バイトのメモリをとる。ビットの組み合せは4294967296通りで ある。10桁だ。10桁の数の組み合せで16桁の数値を表現しようとしても、 すべての数を表せないことは明白だ。
プログラムでは生徒番号と希望と優先権の情報を組み合わせて ひとつの数におさめようと していたのだが、任意の組み合わせが「倍精度の数」にできるわけではなかったのだ。 不動少数点数の計算では、結果が倍精度では表現できない数になると下位の方の桁の 数字が適当に変わる。デジタル計算特有の「計算誤差」というやつだ。 おそらくその過程で希望するクラブそのものが変ってしまったのだろう。
貴重な経験だった。不注意から起こったバグならつきとめられるかも しれないが、無知から起こったバグはみつけることがでぎない。自分の プログラムが人の運命を左右してしまってもそのことに気がつかないかも しれない。