待ち行列理論

ディズニーランドで、銀行のATMで、スーパーのレジで、高速道路の料金所で、我々は行列を作る。これを待ち行列といい、この問題を解くための理論、すなわち待ち時間を計算して求めたりする方法が学問としてある。

この待ち行列理論は経済産業省主宰の国家試験である情報処理技術者試験のテクニカルエンジニア (ネットワーク) の午前の問題として必ず出ることになっている。

その待ち行列の計算だが、教科書には必ず以下の 「公式」 が出てくる。

(待ち行列) =ρ x Ts / (1-ρ)

この公式に数字を当てはめれば待ち行列=待ち時間が出てくるそうである。ここで、待ち行列を理解する上で、以下の HP が参考になった。

https://www.mirai.ne.jp/~suehiro/am/kihonyougo/queuingtheory.htm

教科書にはいきなり公式がでてくるのだが、なぜその公式になるのか詳しく説明されているのがなかったので、今まで頭に入らなかった。しかし

https://www.geocities.co.jp/Technopolis-Mars/5427/mathtrtop.html

を見てその理由がわかった。高校以上の数学を駆使しないと公式が導き出せないのである。数列と微分を駆使する。私は高校時代、微積分をとっていていつもテストはクラスで3番くらい (1番は京大受かった石垣君、2 番は友だちの青木君、3 番目は私) だったが、lim なんてのは15年前の話だから、もうとっくに忘れた。が、最初から情報処理技術者試験の参考書も 「この公式は数列と微分を使って導き出すことができるものです」 と、ひとこと書いてくれたら良かったのに。いや、つまりすぐに公式を理解することをあきらめて、ただひたすら暗記に徹することができたのに、ということ。参考書は誰にでもわかるようにと中途半端な説明するから余計にわからなくなる。

閑話休題、上の公式のρ (ローと読む) とはなんぞや?実は私はその謎が解けてから行列問題が解けるようになった。

実際に問題を解いてみよう。

(H11ネットワークスペシャリスト午前問 63)

ある金融機関のATM (現金自動預け払い機) が1台設置されている。平日の昼休み時 (12時から13時) には、このATMを毎日平均15人が一人当たり平均3分の操作時間で利用している。サービス待ちがM/M/1※の待ち行列モデルに従うとすれば、この時間帯の平均待ち時間は何分か。

まず上の公式で、ρを求める。ρの求め方は、ズバリ、

「このATMでは1時間に本来何人をさばくことができて 何人をさばかなければいけないのか」

という比率を求めるのである。この比率をρと言っている。この考え方に気付いてから行列問題が簡単に思えるようになった (この道のりの長かったこと) 。

つまり、問題によれば 1 人当たり 3 分間隔で ATM を操作しているとすれば、1 時間で 20 人さばけるはずである。1 時間= 60 分を 3 分で割れば20だから、つまり 1 時間以内に絶え間なく 20 回 ATM を操作できる。問題の中には、12~13 時の 1 時間の間に 15 人が続々来る、ということだから、この ATM はどれだけ働いてるかというと、

(来客数 15 回) : (本来さばける回数は 20 回) = ρ : 100 (%)

と、比の計算で求められる。これなら小学校の高学年で出てくる算数で解ける。私が今まで見た中で、こういう解き方を書いている参考書はひとつもなかった。参考書の筆者はきっと頭がよく、プライドもあるだろうからこういう書き方は決してしないのだろう。するとρは75%である。つまりこの ATM はお昼時に本来の能力を 100% とすると 75% の力しか発揮していない、ということである。

ここで、勉強していてわかったのだが、この公式ではATMの処理能力を超えて来客することはない、という前提である。現実には高速道路の料金所やディズニーランドの人気アトラクションはそんなことはなく常にフル稼働なので、M/M/1という待ち行列のモデル (前提条件) は非常に甘々であることがわかる。しかし前提条件を甘くしても微分は出てくるのである。実際の社会で起こっている待ち行列問題を解くのは 「すごく難しい」 のであった。高速道路の渋滞がなぜ起こるのか、それは待ち行列理論をきちんと理解して道路/トラフィック設計してないからではないか?と、勘ぐりたくさえなる (もちろん考えて設計していると思うのだが、だとすればETC専用レーンを設けるなんてもってのほかだと思うのだが…???) 。

またまた閑話休題、上の公式の Ts は 「平均サービス時間」 と呼ばれ、ここではたとえば ATM にキャッシュカードを入れてから現金を引き出したり残高照会をしたり振り込みをしたりし終えるまでの時間のことを言っている。問題文中からこれは 3 分である。

これでρ=75%、Ts=3 (分) となるので、公式にあてはめてみればよい。

(待ち時間) =0.75 × 3 (分) / (1 - 0.75) = 9 (分)

ということで、昼休みにこの ATM を使う客の待ち時間は9分であることがわかった。

試験に限って言えば問題のパターンは決まっているのでコツをつかんでしまえば簡単な問題だったのだ。

* * *

※M/M/1の意味は、

  1. 「サービスが提供される窓口」 は 1 つである。
  2. 窓口でサービスを同時に受けることができるのは1人に限られる。
  3. 「サービスを受けるために順番待ちをする客の列」 は 1つである。
  4. 客はいったん待ち行列に加わったら、自分の番が来るまで待ち続ける。
  5. 客の到着の仕方がポアソン分布にしたがう。
  6. サービス時間の分布が指数分布にしたがう。

であるが、 5. のポアソン分布なんかは大学で習った統計学出てきたものだし、はっきりいって未だよく理解してないが、わからなくてもなんとかなる。

続きを読む

good enough

2003/10/20 ZDNet より。

しかし、ITの歴史の中では 「best」 のテクノロジーが生き残ってきたとは限らない。

「best」 テクノロジーの最大の敵は 「good enough」 なテクノロジーなのである。

続きを読む

TOEIC 対策の本

ここ 2 年間、数回受験した私のスコアは平均で800。定期的に会社で TOEIC の試験があり、2003/9/28 も TOEIC の試験があった。今回はある問題集を買って事前に勉強した (事前に問題集を買ってリスニングなどを勉強したのは今回が初めて)。テストを受けた直後、記憶が冷めないうちに本屋で TOEIC の本をチェックした。試験直後に本屋で問題集を探せば、同じような問題が出ている本を探しやすいと思ったからである。で、偶然にもほとんど反則技の本みつけた。

 

長本吉斉という TOEIC 専門学校の代表が書いた本で、その日に受けた 「リーディング」 の問題とまったく同じ問題が載っていた。驚いた。すかさず買った。そして家で 「リスニング」 をやってみると、これまたほとんど (またはまったく) 同じ問題があった。私が買ったその本の名前は「TOEIC Test 860点突破大特訓」。730 点版とか、650 点版とか文法の鉄則とかその他のバリエーションもあるから興味がある人はアマゾンとかで見てみて欲しい。アマゾンで彼の名前の本を検索すると、レビューでみんな絶賛してることがよくわかる (私も書いてしまった)。

そしてアマゾンでこの人の書いてる本をすべて買った。今まで TOEIC 本は数千円注ぎ込んだと思うがすべて無駄だった。…ことがよくわかった。いや、まだ彼の本を徹底的に読み込んだわけじゃないしテストも受け直したわけではないので、彼の本を読んだりトレーニングを積んだりすればスコアが上がるかどうかそれはこれからわかることだと思うが少なくとも本屋にたくさんある TOEIC 本の中で最も評価に値する本だと思った。彼の本を繰り返しこなせばコンスタントに 850 は取れるようになると確信している。それは、TOEIC 攻略法 (リスニング)で私が漠然と言及した 「ひっかけ」 問題に対するパターンが本という形で体系的になっているからである。

私は何度も TOEIC を受けて分かったのだが、 TOEIC には 「ひっかけのパターン」 があることをこの本は教えてくれる (逆にいうと TOEIC ってひっかけだらけだ!)。もっと早くこの本のことを知っておくべきだった。

ゴミ投資家シリーズの本のときもそうだったがこのような本に出会えたのは因果を感じるものだ。

 

Embedded content

Embedded content

Embedded content

Embedded content

Embedded content

続きを読む

当たらない天気予報

WetSock というソフトを何年か前から愛用している。

https://www.locutuscodeware.com/wetsock_ss.htm

このソフトは、ウィンドウズのタスクトレイにリアルタイムで今の天気と天気予報が表示されるというもの (シェアウェア、$12。2 都市までの天気は無料で使える) 。

英語版だが、世界中の都市 (3,750都市) がカバーされている。もちろん日本の主要都市の天気はこのソフトで知ることができる。

ずっと気になっていたのだが、なぜかこのソフトの 「今の天気」 と天気予報は正確だ。このソフトはネットのどこかから情報を取ってきてそれを表示しているのは明らかなのだが、先週、その情報はどこから取ってきているのか気になってこのソフトのヘルプを見てみたら、 「NOAA」 だという。これは日本でいうと気象庁のアメリカ版だと思われる。早速 NOAA のサイトを見てみたが、このソフトが NOAA のサイトのどこの情報を見ているのか、情報量が多すぎてさっぱりわからない。それならばとこのソフトが具体的にどこにアクセスしているのかパケットモニタリングという手法を使ってネットワークに流れているデータをハックして調べてみた。

すると東京 (羽田) の場合は、

https://weather.noaa.gov/cgi-bin/mgettaf.pl?cccc=RJTT

だということがわかった。確かに、ここにアクセスするとデータが表示される。しかしこのデータが何を表すのかさっぱりわからない。

さらにネットを調べているうちに、このサイトが提供しているデータには大きく分けて 2 種類あることがわかった。

それが TAF と METAR である。どうもこのソフトはこの 2 種類のデータを元に天気予報を出しているらしい。

では TAF と METAR とはいったいなんなのか、ということになる。おおざっぱに言うと、TAF は予報、METAR は現在の気象報告であることがわかった。

https://www7.plala.or.jp/nsbsc/tip/t_f03.htm

このページが大いに役に立った。

このページの冒頭には以下のように書いてあった。ちなみに、意外なことにこれはウィンドサーファーが書いたページだった。

「的中率高し!こだわりの風予報」

TV や電話の 177 のしろうと向けの天気予報だと、台風のときなど、まるですごい風が吹くような予報を流して一般人を海に行かせないようにする傾向があります。それを信じてウインドサーファは逆に喜んで海に行くわけですが、誇張された予報なんで結局、弱い風だったということが多々あるようです。

航空気象通報はパイロット等のプロ向け予報なので、おおげさに誇張した予報は流しません。また、一般の天気予報だと 「~のちやや強く」 等の予報が出ていても、 「のち」 の時刻があいまいで、喜んで海に行ったけど、結局夕方暗くなってから吹いてきたという失敗もあります。航空気象通報だと航空機の高速性の関係上、時間単位で予報が出るわけで 1 日の中の何時ごろにどういう天気になるかが分かります。

そうか、TAF、METAR は航空気象だったのか!上にもあるようにだから正確だったんだ!!!確かに、WetSock で選べる日本の都市って空港しかなかったよな!! (今まで不思議には思っていたのだが)

ということで、

METAR はほぼ全部の飛行場から出ていますが、TAF は原則として国際線を運行している飛行場のみです。要は何時間もかかって到着する飛行機は到着時の予報がほしいためです。TAF には 12 時間以内の短時間 TAF と、27 時間以内の長時間 TAFがあります。

だということがわかった。

ところで、全世界の空港にはそれを識別するために 3 レターコードと 4 レターコードというものが付いているらしい。3 レターコードとは、IATA が付けているもので、海外に行ったことのある人ならサンフランシスコ=SFO、ロサンゼルス=LAX、ホノルル=HNL、成田=NRT、みたいな馴染みの深い (<?…少なくとも私はいくつか暗記していたから、知ってる人は知ってる…) コードのことである。一方、4 レターの方は、RJTT、RJAA …など、初めてみるものばかりである。こちらは ICAO という組織 (?) が定めたものらしい。TAF、METAR はこちらをつかっている。

◆ ◇ ◆

ここで、自分でソフトを作っていて気付いた点があった。アメリカの主要な空港は、IATA の 3 レターコードに、 「K」 をつけるだけでいいらしい。例えば、サンフランシスコの 4 レター版は 「KSFO」 となる。

日本は、というと、RJ で始まるようだ。沖縄はなぜか RO となっている。で、RJTT が東京国際空港、すなわち羽田なのだが、成田は RJAA、千歳が RJCC、仙台が RJSS、名古屋が RJNN、伊丹が RJOO、関空が RJBB、福岡が RJFFとなっており、どうやら主要都市は RJ に続き 3 文字目と 4 文字目はその都市のイニシャルで同じ文字を重ねているようだ。そういうネーミングコンベンション (名付けルール) があると、こういった文字の羅列は一見複雑そうに見えて暗記する必要がなくなってくる。地方の空港の場合は、その地方空港がある地域の主要空港の、4 レターコードの 1~3 文字目+その地方空港のイニシャルであるようだ。例えば厚木なら、その地方 (関東・東京) の主要空港が RJTT (羽田) であり、この 1~3 文字目 RJT+A (厚木) ということだ。横田はRJTY だ。下総は RJTL なのだが、この 「L」 はまさか 「下」 =Lowということなんだろうか。覚え方としてはそれでいいと思うのだが。

◆ ◇ ◆

さてそれならば、この METAR や TAF なるデータを解析すれば自分でも天気予報のサイトが作れそうである。iモードには天気に関する基本的な絵文字はあったので、そのまま使うことにした。PC からでもケータイからアクセスしたのと同じような細長い画面にした。

また、自分で天気 (予報) のサイトを作っているうちに、knot (ノット) など、どうしても調べなければならないこともあった。それは 「海の上での距離と速度」

https://homepage2.nifty.com/arumukos/unnk/ntclml.html

に書いてあった。読んでみると 「へぇー」 って感じなのだけれど、このページは 「生きていくのには不必要な知識」 のひとつだそうだ。確かに、私も自分でサイトを作ったりしなかったら、knot など一生縁のない単位かも知れなかった (単位としてそういうのがある、というのはもちろん知っているが、 「ノットは秒速 (メートル/秒) の倍の数値」 なんか、別にどうでもいいことだ) 。

ほかにも、雲って 3 次元なんだなあ…つまり空を見上げると 2 次元に広がる雲も、実は (というか当たり前なのですが) 低層~中層~高層が重なりあってできてるんだな、とか、それをウェブの画面で表現するにはどうしたらいいものか…? と、一見するとどうでもいいことに悩むのであった。

というわけで作ってみたのがコレ↓である (作るのに全部で 20 時間くらいかかった)。

i-Weather (https://twinkle.cc/i/e/)
続きを読む
Subscribe to