読者です 読者をやめる 読者になる 読者になる

Folioscope

プログラミング/Unix系/デザイン/CG などのメモがもりもり

もしも順番待ちのデータ構造がキューではなくスタックだったら

プログラマなら人の行列を見て一度は考えたことがあるだろう.

「もしこの行列のデータ構造が,キューではなくスタックだったら」

ということで,もし行列がスタックだったらとシミュレートしてみた.

問題のモデル化

まずどんな待ち行列を想定するか. 病院でも銀行でもハンバーガーショップでもいいが,今回は遊園地のアトラクションを想定する. 待ち行列理論にはM/M/1などの素晴らしいモデルが多数存在するのが,今回のケースに当てはめるのは難しい. そこでコンピュータの力を使って,乗客一人ひとりの待ち時間を計算してみる.

用意するのはキューまたはスタックで実装される人間の行列を格納する配列. 時間を進めると配列に新たな乗客が並ぶ(到着). また一定時間ごとに数人の乗客が行列からアトラクションに移る(サービス). 開園時間は8時から20時と仮定し,1分毎に時間をすすめる.

乗客の到着数

まず考えるべきはアトラクションの搭乗数. 到着数は一定ではなく,時間毎に推移する, 遊園地のアトラクションの搭乗数はおそらく昼間にピークを迎えるので,山なりになると思われる. また入園待ちの乗客も考慮すると,開演時間にも多くの人が並ぶ. これを遊園地分布と呼ぶことにする. この遊園地分布を1時間毎の乗客数に表したのが次のグラフとなる.

f:id:ibenza:20131017100400p:plain

1日の総搭乗数は1080人となった. 遊園地を経営したことは無いが,おそらく人気のあるアトラクションには1日このくらいの人數が乗っているだろう.

アトラクションの処理能力

次にアトラクションの処理の応力を決める. これも適当でいいが,今回は9分毎に13人を捌くとする.

すでにこの地点で時間ごとの行列の長さの推移を算出することができる. キューにせよスタックにせよ長さには影響しない. 各時間ごとの行列の長さの推移が次のグラフとなる.

f:id:ibenza:20131017100412p:plain

まず8時の時点で開演前から待っていた客を捌きながら,9時あたりで一度行列の長さが0付近となる. そして11頃から入場者が徐々に増えて行列が次第に長くなる. 17時ごろにピークを迎え,それから再び行列は短くなる. 20時(赤線)の時点ですでに新たな搭乗者は発生せず,行列の客が0になるまで待つ.

キューとスタックを比較

さてここまで出揃ったら,行列をキューとスタックで実装してみた. ここで見るデータは,乗客の待ち時間である. アトラクションから出てきた乗客順の待ち時間は次のグラフのようになった.

f:id:ibenza:20131017100435p:plain

キューの場合はなだらかな曲線を描く. 待ち時間がピークの乗客は一番混んでいる時間帯(行列が長い時間帯)に並んだ乗客であろう. 一方スタックの場合は,待ち時間の差が大きくなった. 真ん中あたりの人たちは待ち時間が極端に短いが,後からでてきた乗客は待ち時間が極端に長い. おそらく朝方から並んでいたにもかかわらず,先に来た客が先にアトラクションに乗ったからである.

次にキューおよびスタックで実装した行列の,平均・最大待ち時間を見てみる. まずキューのデータは次のようになった.

キューの場合
最大 : 106
平均 : 50

人気のあるアトラクションの待ち時間もこのくらいだろうか. 自分が記憶している限りでは,USJができた年の夏休みにジュラシック・パークに2時間以上並んだのを覚えている. それと比較すると随分良心的な待ち時間といえる.

続いてスタックのデータは次のようになった.

スタックの場合
最大 : 602
平均 : 50

平均はキューの場合と同じ. しかし最大待ち時間がなんと602分. 営業時間が12時間のうち,一番運が悪かった乗客は10時間も並ぶ必要があるということになる. これでは何のために遊園地に来たのかがわからないぞ.

幸福度

さて一見スタックの行列には欠陥があるように見えるが,これを人の幸福度という観点から考察する. 人の幸福度を定量的に測定するとこは難しいが,ここでは待ち時間から算出することにする.

人の感覚は一次関数的ではなく指数関数的だと言われる. つまり,5分と10分の違いは大きいが,100分と105分の違いは小さいということだ. そこで待ち時間と幸福度の変化を以下の指数関数のグラフに当てはめてみた.

f:id:ibenza:20131017100450p:plain

待ち時間0分のとき幸福度が1と一番幸福である.そしてそこから待ち時間の長さに応じて幸福度は減衰する.

キューの場合の乗客の幸福度の平均は0.48となった. 一方スタックの場合はの幸福度の平均は,なんと0.80であった. そう,キューの行列よりスタックの行列の方が明らかに幸福度が高くなったのである.

これらのデータから,人の行列はキューよりスタックのほうが全体の幸福度は高い. そのため行列は,キューよりスタックで実装すべきであると言える.