こんにちは。技術部サーバーサイドエンジニアの大河原です。
ゲーム作ってます。一応まだ新卒です。
こちらはTech KAYAC Advent Calendar 2017 の23日目の記事になります。
（昨日の記事は我らが@commojunの「新卒一年間で確立した紙のノート仕事術！」でした。）
ちなみに前回僕が書いた記事はカヤックのエンジニアのエディタ事情 2017 です。こちらもよかったら是非。
今回は普段から僕らが利用しているエレベータとエレーベータのアルゴリズムについて調べてみました。
ポルトガル・リスボンの観光地でもあるサンタ・ジュスタのエレベーター。上の展望台からはリスボン市街地を一望できる。
■ なんでエレベータ？
言うまでもなく、弊社はエレベータを設計したり製造したりしていません。←
これといった大きな理由はないんですが、僕自身昔から電化製品とか電子機器とか見るとその性能よりも「どういうギミックで動いてるんだろ？」と不思議に思う性格で、いろんなものを壊しては親に怒られるタイプの子供でした。 （まあ、いい言い方をすれば好奇心旺盛、悪い言い方をすればものを大切にしない性格ということです。）
その意味で高校のときに出会ったアルゴリズムの勉強はとても興味深いものでした。
…で、どうしてエレベータ？って話ですよね。
弊社は鎌倉に本社を構えており僕自身も現在鎌倉勤務なのですが、実は横浜駅前にもオフィスがあります。
「そもそも、なぜわざわざ鎌倉に本社を？」
と思った方は是非弊社代表の柳澤の書いたこちらの記事を読んでみて下さい。
ご存じの方もいらっしゃるかもしれませんが、鎌倉は歴史ある街であることもあり、市の規定により市街地含め一部地域では15メートル以上のビルを建設することが規制されています。
僕が通っているオフィスも例に漏れず駅前の4階建ての自社ビルでエレベータはなく階段で移動しています。
ただ、たまにイベントやMTGなどで横浜オフィスにいくことがあるんですが、こちらの横浜オフィスのほうは横浜駅前の三井ビルディングの30F（最上階）にあり当然最新式のエレベータが複数台設置されています。
人間誰しもオフィスビルやショッピングモールなどで待てども待てどもエレベータが全然来なかったり、「来た！」と思っても反対方向行きだったりしてイライラしたことがあると思います。
エンジニアであれば尚更、「全然エレベータこねーじゃねーか！！どんなアルゴリズムで動いてんだ？俺が一から実装し直してやろうか！！」と寝坊して遅刻しそうな自分を棚に上げて考えたことが一度はあることでしょう（？）
つい先日久しぶりに横浜オフィスに足を運んだときに、まさに上のような状況になって（…あれ？でも待てよ？たしかにこいつら一体どんな仕組みで30階ものフロアを行ったり来たりしてるんだ？しかも複数台で…！？）と不思議に思い、持ち前の好奇心で今回調査してみた次第です。
■ エレベータのアルゴリズムとエレベータアルゴリズム
『エレベータ アルゴリズム』とかで検索するとまず引っかかるのが「エレベータアルゴリズム」というものです。
これで意外とあっさりブログが書き終わってしまいそうと思われたかもしれませんが、残念ながらこれはある特定のアルゴリズムを指すものであり、僕らが普段利用するエレベータに直接適用されているアルゴリズムではありません。
アルゴリズムだけ簡単にまとめると、
- ある１つのリクエストを受信すると、同じ移動方向で別のリクエストが有る限りその方向に移動し処理しつづける(無くなれば2へ)
- 1とは逆方向でリクエストが有る限りその方向に移動し処理しつづける(また無くなれば1へ)
といった具合ですごくシンプルな内容です。
このアルゴリズムは身近なところで使われています。
つい最近だと、GoogleのRui Ueyamaさんのnoteでも話題に挙げられていたHDDのヘッダのスケジューリングの基本アルゴリズムの一つだったりします。
エレベータの下の階が「HDDのトラックの内側」で上の階が「HDDのトラックの外側」とイメージするとわかりやすいと思います。
このアルゴリズムを使ったSCAN方式と呼ばれるものはあくまでディスクスケジューリングアルゴリズムの一つであり、他にも色々とあるようです。
ここでは上のエレベータアルゴリズムを含むディスクスケジューリングのアルゴリズムをいくつか紹介します。
- FCFS (First-Come-First-Served)
単純にリクエストが来た順に処理して行くアルゴリズム。どのリクエストも公平に処理され余計な遅延も起きないが、アクセス時間は非効率でパフォーマンスも悪くなりやすい。
- SSTF (Shortest Seek Time First)
現在位置から一番近い（移動時間が短い）リクエストを順に処理して行くアルゴリズム。平均のレスポンスタイムがFCFSより早くなる一方でリクエストによってはずっと処理されず餓死状態になる場合がある。
- SCAN
上で出たエレベータアルゴリズム。（SCANがなんの略なのかはわからなかった。）移動方向が変わらないため応答時間の変動が少なく上２つに比べると単位時間あたりの処理能力が高くなる。デメリットは追加のリクエストに対しても一度通過してしまった場所だと処理が後回しにされる点や両端のトラックの待ち時間が必然的に長くなってしまうこと。（まさにエレベータ）
- LOOK
SCANとすごく似ているアルゴリズム。実はSCANはある一方向にリクエストを処理しづけて終端まで移動してしまうのに対して、これはそれ以降その方向にリクエストがない場合に引き返す、というアルゴリズム。
- C-SCAN
最初のCはCircularのC。SCANは終端までチェックし続けて引き返すがつまりそれは一度走査した箇所を再度チェックして行くことになる。それに対してC-SCANは一気にもう片方の終端まで飛んでから再度同一方向に移動しながらリクエストを処理する（つまり循環する）、というアルゴリズム。
- C-LOOK
説明不要かと。つまり循環するLOOKということ。
より詳しく知りたいという方はgeelsforgeeksの記事 とか イリノイ工科大学の授業資料 を読んでみると面白いかもしれません。
さて、実際のエレベータもそのビルに1台しか設置されていないのであればこのアルゴリズム（あるいはそれを少し拡張したもの）に則るだけで十分な性能が得られそうですが、多くの場合そうではなく2,3台、大きなビルとなればもっと多くのエレベータが同じエントランスに存在することになります。
しかし、これまた有名な話で恐縮ですが、SCANのような単純なアルゴリズムで複数台のエレベータを運転させた場合、最終的にエレベータ同士が連れ添ったような動き（団子運転）をしてしまうことが知られています。
これを解消するためにあるのが 郡管理 と呼ばれるシステムです。
正確には郡管理システムという言葉自体は、企業や工場などで複数の制御対象に対してある法則に則って連動させることで高効率化を測ることを意図したシステムを意味します。（ただしざっとググった感じだと特にエレベータのシステムに対して使われている印象です。）
群管理システムには例えば「過去の利用データから各時間帯の利用者数を予想して効率的に人を運送する方式」であったり、あるいは「運行効率を工夫することでより省エネを実現できる方式」であったり、はたまた「心理学の観点からエントランスでの待ち時間と実際の乗車時間のうちそれぞれの時間あたりのストレス値などを計算して乗客のイライラを最小限にする方式」であったり...他にも様々な方式が存在し、大手電気メーカの開発・技術関連のページを巡回してみるだけでも面白い情報が得られます。
そういえば最近、現在の階数表示がされていないエレベータをよく見かけますね。あれは、そのエレベータの群管理システムによって敢えて乗車希望者のいるフロアを通過していたりするのを隠すためにあるようです。たしかにいくら全体の効率が良くなるからと言って自分の目の前をエレベータが素通りしていったらストレスたまりそうですよね。
そして当然といえば当然のことですが、それらの詳細なシステムロジックについては各企業の最重要機密事項に当たるため簡単に調査することはできませんでしたあぁああぁああぁ。←
■ 閑話休題
「ボタン押したのに全然こねーじゃねーか！」
以外のエレベータあるあるに「やっべ、違う階のボタン押しちゃった！」があると思います。
あまり知られていませんが製造元メーカによっては押したボタンをキャンセルできる機能がついてたりします。
エレベータの動くロジックとは直接関係ありませんが、自分の会社が入っているオフィスビルのキャンセル方法くらいは覚えておいて損はないかと思います。
（もちろん型番によってキャンセルできる/できない場合があることも含めて。）
余談ついでにもう一つ言うと、世界初のエレベータはかのアルキメデスが発明したそうです。
とはいえ、彼が生きていたのは紀元前。ロープと滑車を使った人力のもので人ではなく荷物を運搬するためだったそうです。
■ エレベータのアルゴリズムを書いてみる ~ Elevator Saga ~
エレベータのアルゴリズムについて調べていたらたまたまElevator Sagaというサイトを見つけました。（GitHubはこちら)
Elevator Sagaはエレベーターのシミュレーションゲームを通じてプログラミングの基礎を学べるサイトのようです。利用できるAPIがドキュメント込みで公開されているのでパズル感覚でアルゴリズムを考えられます。（言語はJavaScriptです。）
例えば「エレベータが待ち状態の時には1階に行く」みたいな指示は次のように書けます。
elevator.on("idle", function() { elevator.goToFloor(0); });
これらのAPIを駆使して指定時間内に目標人数を行きたい階数に輸送できるとクリアとなります。
面白そうなので最初の簡単なレベルだけ挑戦してみました。
lv.1 3階建て:60秒で15人を輸送せよ
{ init: function(elevators, floors) { var elevator = elevators[0]; elevator.on("idle", function() { elevator.goToFloor(0); elevator.goToFloor(1); elevator.goToFloor(2); }); }, update: function(dt, elevators, floors) { } }
まだよくわかってないのでとりあえず1階から3階までを巡回するだけのエレベータを作ってみました。
（実際あったらブチ切れそう。）
elevatorsとあるようにレベルが上がって行くに従ってエレベータの数自体も増えて行きます。
ちなみに lv2 は上と変わらずに巡回する階数を増やせばクリアできます。
lv.3 5階建て:60秒で23人を輸送せよ
{ init: function(elevators, floors) { var elevator = elevators[0]; _.each(floors, function(floor) { floor.on("up_button_pressed down_button_pressed", function() { elevator.goToFloor(floor.floorNum()); }); }); elevator.on("floor_button_pressed", function(floorNum) { elevator.goToFloor(floorNum); }); }, update: function(dt, elevators, floors) { } }
今度は少し工夫しました。と言っても
- 「各フロアでボタンが押されたらその階に移動する」
- 「乗客が押した階に移動する」
と行ったエレベータのごくごく基本的な動作を入れただけです。
台数が増えてこのあとLv4あたりから本番、と行った感じです。
普段から競プロとかやられてる人はこう言ったゲームおそらく得意でしょうね。
■ 最後に
いかがだったでしょうか。おそらくこのブログの読者層からして普段の業務には１ミリも役立たない内容だったかと思いますが、通勤時間の暇つぶしくらいにはなったんじゃないでしょうか。
最後に募集告知です。
カヤックでは、でかいオフィスビルでいつまでもエレベータを待っていられない！一秒でも長くコードを書いていたい！というエンジニアを募集しています。（強引）
さて、毎日コツコツ続けてきたカヤックのAdvent Calenderも残すはあと僅か！
明日は@butchi_yの記事を予定しております。お楽しみに。
クリスマスを目前に、ずっとエレベータのアルゴリズムについて調べてて一体俺はなんなんだ感がすごい。
— おかわり (@okwra) 2017年12月21日
本記事で参考にさせていただいたサイト
- エレベータアルゴリズムとエレベータのアルゴリズム - ksmakotoのhatenadiary
- 蒸発皿 - 寺田寅彦
- The Hidden Science of Elevators - popular mechanics
- エレベーターの歴史・変遷 - 一般社団法人 日本エレベーター協会
- Elevator Saga – レッツトライ！エレベータのアルゴリズムをJavaScriptで書く- MOONGIFT
- Everyday Algorithms: Elevator Allocation - austingwalters.com
- エレベーターアルゴリズム - cagylogic
- 団子運転
- Pixabay - Elevador De Santa Justa, Lisbon
