エレベータに見るアルゴリズムの性能と公平性のバランス｜Rui Ueyama

現実世界でもコンピュータの中でも、何らかの性能指標だけを追求すると参加者にとって極端に不公平になってしまうことがある。例えばエレベータとHDDは共通点がありそうに思えないが、この2つは性能特性的にとてもよく似ていて、リーズナブルな性能と公平性を両立させるために同じ制御方法が使われている。これについてちょっと説明してみよう。 1基しかない場合のエレベータの動き方は単純だ。一度上に動き出すと、上で待ってる人や降りる人がいる限り上昇し続ける。同じように、一度下に動き出すと、下で待っている人や降りる人がいる限り下降し続ける。これ以外の動き方をするエレベータはまず存在しないので、これが唯一の制御方法のように思えるけど、別にこうしなければいけないというルールはない。 エレベータの平均待ち時間を最適化することを考えてみよう。そうすると、一方向に動き続ける代わりに、エレベータが現在存在する階に一番近い人の

[mizoguche]

一方デザイナーはエレベータの横に鏡を設置した http://blog.livedoor.jp/lunarmodule7/archives/3675720.html

[knok]

エレベータだと消費電力に振ったアルゴリズムを使う場合もあったりして必ずしも配送効率最大化が絶対目標じゃなかったりする

[triggerhappysundaymorning]

このアルゴリズムでエレベーター制御するとエレベーター同士が「寄り添いたがる」んだよね.

[ardarim]

色々なアルゴリズムがあると思うけど、上ボタンを押してるのに下向きのが止まるエレベータ、テメーはダメだ

[yoiIT]

面白い。最新のエレベーターは時間帯も含めて開閉頻度などを自動解析して、その時に一番効率的な階で待機するようになってるから来るのが早いんだよな。

[twatw]

The TowerIIだったと思うけどエレベータの待機階とか細かく設計できて楽しかった

[lbtmplz]

階数を表示しないのは不公平に動いてるやつだ

[ROYGB]

ＨＤＤのヘッドは複数あるけどセットで動くので、エレベータの例えで言えば１基しかない場合に相当するような。

[e_denker]

人間の心理的には、平均待ち時間よりも最悪待ち時間を減らすことの方が重要だからね。エレベーターの場合は特に1Fに乗降客が集中するだろうから悪いケースが起きやすい。

[youichirou]

最近のは待ち時間の全体最適化のために必要であれば待ってる人がいる階の手前でも遠慮無く引き返したり飛ばしたりするから現在位置表示が無いんだっけ。

[ryskosn]

面白いなぁ

[massa142]

“エレベータアルゴリズムでは、一方向にアームを動かし始めるとそちら方向の読み書きリクエストがすべて満たされるまでは移動方向を変えたりしない。これにより若干平均待ち時間は伸びるものの公平性は飛躍的に改善

[okusa75]

データは移動できないが、人間は移動できる、という違いがあるので、公平性を保ちつつ平均待ち時間を減らすには、奇数階専用という手もある。一部のオフィスビルでは採用されているよね。

[indication]

HDDのNCQのことかな。途中に乗る人がいたら拾うけど、無理なら後回しにするとか。最近はシーク時間って載ってなさそう

[maicou]

エレベーターアクシデント

[toyama0919]

エレベーターはマルチスレッドプログラミングと似てる

[kirifue]

複数台や高層ビルの制御では、省エネや時間帯を含めたトータルの最適解が求められる。全体でみれば「公平」でも個々にとっては「不公平」。なので現在位置は表示しない。 #技術

[pongeponge]

エレベータに課金要素かガチャ要素を加えて公平にしよう

[midnight-railgun]

マンションのように「1階で乗ってn階で降りる(またはその逆)」が大多数を占める場合と、デパートのように「n階で乗ってm階で降りる」が頻繁に起きうる場合とで最適なアルゴリズムは違ってきそう

[blueribbon]

「エレベータアルゴリズムでは、一方向にアームを動かし始めるとそちら方向の読み書きリクエストがすべて満たされるまでは移動方向を変えたりしない。これにより若干平均待ち時間は伸びるものの公平性は飛躍的に…」

[appalerm]

この機会に皆さんも無料ゲーム Elevator Saga でエレベータのアルゴリズムを記述していきましょう http://play.elevatorsaga.com

[Cichla]

The Tower懐かしい。時間帯によって「登りは最上階までノンストップ，下りは1階ずつ」とか，10階毎に止まる大型エレベーターの併設とか，色々調整して住民の不満度を最小化するのが楽しいゲームだった

[pulldown]

職場のビルのエレベータの効率が最適化されてないのでエレベータの再開発やってやりたい。AIとか使って。

[vonucello]

もう20年以上昔だけど、就活でエレベータメーカーOB訪問した時はこの辺の制御技術の話色々聞けて面白かったな。立てた十円玉を倒さないスムーズな高速運転技術とかも。今のエレベータはもっと進化してるんだろか？

[wyukawa]

エレベータのアルゴリズムってどんぐらいパターンがあるのかな。最初に降りる階を押してから乗るエレベータもあるし、時間帯によっても混雑状況が違うだろうし。

[ene0kcal]

そんな事より洗練された分かり易い文章に読みながら感心してますた。いったい何分で書き上げたのか知りたかった（所要時間50秒）

[B-CHAN]

そう言えば、乗る前に行き先階数を押すタイプのエレベーターあるよね。あれは良いな。

[natu3kan]

エレベータとHDD

[hdkINO33]

あーそれでディスクスケジューラーを指定するカーネルオプション名は"elevator"なのか

[slkby]

上行き表示で来たエレベータが一回閉じたあとまた開いて下行きになるのホント無能

[syakinta]

猫のサムネイル主張が強すぎてうざいんでサムネイル替えてくれないかな

[nezuku]

エレベーターだとアルゴリズムどころか物理的に分割で軽減もありえますよね。上層階下層階といった分割とか。/ホールにて各籠の現在階を見せない場合、各機の位置が見えることでの不快軽減もあるのかも

[a-know]

詳解システムパフォーマンスで読んだやつだ

[chintaro3]

「エレベータアルゴリズム」

[nimroder]

実際の高層エレベータは、一旦速度が乗ってしまうと最寄りの呼び出しを無視して通り過ぎ、各階停車を避けて一気に長距離移動をしたりもする。

[progrhyme]

エレベータアルゴリズム

[htnmiki]

1基に箱2つのやつ驚いた

[shinzor]

2基以上のエレベーターの制御では、一番近い籠が来ず、イライラするものが多い。だからかどうかどこにいるか表示しないものもあるが、それはそれでイライラする

[REV]

エレベーターホールをヘリウムで満たして高速に上下させよう。