逗子駅での客待ちタクシーの意外なデータ構造 〜年月が磨くデータ形式：組み込みエンジニアの現場力養成ドリル（25）（1/3 ページ）
OSやアルゴリズムの授業で必ず学習する「データの構造」や「データの編成方式」。今回は、実社会で自然発生的に、経験的に出来上がったデータ構造を考えます。意外にスゴイことをやっています。
はじめに
OSやアルゴリズムの授業で必ず学習するのが「データの構造」や「データの編成方式」です。先頭からデータを読む「シーケンシャルアクセス」、本の索引のような「インデックスアクセス」、テレビのリモコンのボタンを押して直接見たい番組を表示するような「ダイレクトアクセス」など、いろいろなデータ構造や編成方式があります。
データを格納する方式を決める場合、図書館で本を収納するのと同じで、以下の要素を考えねばなりません。
- スペース効率
- 小さな図書館のスペースで大量の書籍（データ）を収納できるか？
- 最大にするには部屋中を本で埋め尽くせばよいが、一番奥の本を出すのは大変。
- アクセスの容易さ／速さ
- 図書館で学生から閲覧要請のあった本を素早く出し入れできるか？
- 書庫に通路をたくさん取れば、早く出し入れできるが、収納量が減る。
- 再編成の容易さ
- 本が増えて書庫を拡張したり、コマ切れになった空きエリアをまとめて1つの大きなエリアにしたりすることが容易か？
- 信頼性（ファイルの保全性）
- 本がなくならない。なくなってもすぐに見つかる。
- データの複製を作り、別エリアに置くと信頼性は高いが、高価でスペース効率は悪い。
- 価格効率
- 図書館の維持やメンテナンスの経費が安い。
上記の1〜5には、トレードオフがあり、全部を同時に満足することはできません。何を最重視するかでファイルのデータ構造が決まります。これは、駐車場やトランクルームでも同じす。
「東京競馬場」方式
データ編成方式のスペース効率で、強烈に印象に残っていることがあります。
昔、東京競馬場（府中競馬場）の近くに住む友人宅を訪ねた時のことです。その日は、天皇賞の開催日でした。JR南武線の府中本町駅から友人宅へ歩く途中にあった駐車場はどこも満車です。大きなレースの開催日なので、どこも満車なのは納得できるのですが、車の停め方が異常でした。全ての駐車場で、前後の車間距離が5cm、左右は人間がやっと通れる30cmしかありません。化学でいう「最密充填」方式だったのを見て、驚きました。
普通の駐車場には、満車であっても道路へ出入りできるように、アプローチ（誘導路）がありますが、東京競馬場付近の駐車場にはそんなものはありません。誘導路まで駐車スペースになっています。こうなると、典型的なFILO（First In Last Out）で、一番奥の自動車は、入り口付近の車が全部出て行かないと出られません。
駐車場のオーナーは、少しでも儲けたいので、スペース効率を極限にするため、この強引な駐車方式を採用したのでしょう。整然としたデータ構造や、アクセスしやすいデータの編成方式でいつも頭を絞っているソフトウェア技術者には、絶対に考えつかない大胆な発想ですね。あの光景は、強烈に印象に残っており、今でも、「動画の脳内再生」ができます。これを見て、今まで私の思考過程に立ちはだかっていた「壁」や「良い子の常識」が消え、「ゲリラ的な極端な方式もアリ」と、考える幅が急激に広がったように思います。
今回は、「東京競馬場方式」のように、自然発生的に、あるいは、経験的に出来上がった実社会でのデータ構造を考えます。意外にスゴイことをやっています。
逗子駅の最終電車のタクシー争奪戦
筆者がJR横須賀線の逗子駅から通勤していた頃の話です。東京駅発の横須賀線下りの終電が逗子駅止まりで、逗子駅着が午前0時54分。終電には、東京、新橋、品川から宴会帰りのサラリーマン数百人が乗ってきます（私もその酔っ払いの一人でした）。
問題は、逗子駅から自宅までの交通手段です。徒歩圏内の人はよいのですが、バスで通勤しているサラリーマンは、タクシーで帰らねばなりません。また、終電には、逗子駅の利用客だけでなく、逗子よりも先の駅（東逗子〜久里浜）に住んでいる人も乗っていて、当然、タクシーで帰ります。当時、逗子駅前で営業しているタクシーは、運転手さんに聞いたところ、38台だったそうです。一方、ざっと数えて、200人がタクシー待ちをします。最後の人は1時間近く待たねばなりません。
というわけで、終電が逗子駅に到着すると、ドアが開いた瞬間、乗客は一斉にタクシー乗り場へ走ります。終電恒例の熾烈なタクシー争奪戦ですね。みなさん、100ｍを5秒で走る勢いです。ピンヒールを履いたオネエサンもハンドバッグのひもをブンブン振り回して疾走します。中には少数ながら、私のように、「走るのが面倒なので、最後でいいや」と諦めて、ゆっくり歩く人もいます。いつも、「争奪戦パワー」に圧倒されていました。
ところで、タクシーが客待ちをする形態はいろいろです。最も多いのが、道路に沿って一直線に駐車する方式です。品川駅では、タクシーの列が国道15号に沿って、泉岳寺駅まで1kmも伸びていることもあります（それを見るたびに、散々客待ちして、乗ってきた客が初乗り料金の超近距離客だったら運転手さんは脱力するだろうなぁと思います）。逗子駅では、一直線方式ではなく、図1のように、駅前の「タクシー溜まり」で待つ方式です。図1では4列ですが、実際には6列で、各列には4〜5台駐車できます。
タクシーが客を乗せて待ち行列から出ていき、空のタクシーが帰ってきて、タクシー溜まりの待ち行列に並びます。そんなタクシー乗り場を見ていて不思議なことに気が付きました。タクシーは、厳密に、そして、整然とFIFO（First In First Out）になっているのです。図1の場合だと、①から⑫まで順番に客を拾っています。
順番を管理する誘導員（ポインター？）がいる訳でもないのに、タクシー溜まりで帰着タクシーが並ぶ場所が決まっている訳でもないのに、最も長く客待ちをしていたタクシーが最初に客を乗せ、最後に来たタクシーは最後に客を乗せます。昼のOSの授業で、ファイル構造を解説したばかりなので、「どうやってデータ（タクシー）の順序を制御しているのだろう？ どうやってFIFO構造にしているのだろう？」とものすごく不思議に思いました。
当初は、「タクシー乗り場に駐車しているタクシーの全数を数え、その台数が客を拾えば次は自分の番」という方式かと思いましたが、夜間の暗い中、全数をカウントするのは大変ですし、数え間違いのエラーが発生しそうです。1カ月ほど観察しているうちに、「こういう方式で順序制御をしているのではないか？」との仮説にたどり着きました。乗車した時に運転手さんに聞くと、「その通りですよ」と言われ、ものすごく嬉しくなったことを覚えています。では、ここで問題です。
問題1（制限時間：30分）
逗子駅前のタクシーは、どのようにして、客待ちを処理しているのでしょうか？ 以下の条件で、「タクシーの待ち行列のデータ制御方式」を考えてください。
- 一番長く客待ちをしていたタクシーが次の客を乗せます。すなわち、完全に、FIFOになっており、順番は厳格に維持されています。
- タクシー溜まりに帰ってきたタクシーは、任意の空いている場所に並びます。図1の場合、⑫は、⑧の後ろか⑨の後ろに並びます（どちらに並んでも構いません）。
- したがって、自分の前のタクシーが最後尾とは限りません。
- どのタクシーが次に客を乗せるかを管理している人はいません。タクシー会社の無線配車センターも一切関与していません。タクシーの運転手さんだけで「運営」しています。
- 順番を書いた紙やボードのような「ツール」も一切使っていません。タクシーだけで「完結」しています。
Copyright © ITmedia, Inc. All Rights Reserved.