-
-
Save re-fort/4cdaf3b440d6abb123dc2d3238253ccd to your computer and use it in GitHub Desktop.
(1: 最適化問題) 下記パラメータのままでElevator::tick()のみを最適化して平均待ち人数を最小化する / (2: 並列化問題) 以下のプログラムをマルチスレッドで動作させると何倍早くなるか実装して検証する / (3: チューニング問題)並列化以外の方法で本プログラムの実行時間を短縮するためにどのような改修を加えるとよいか考察する
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <iomanip> | |
#include <random> | |
#include <unistd.h> | |
using namespace std; | |
const int MAX_FLOOR = 14; | |
const int ELEVATOR_COUNT = 4; | |
const int RAISING_PROBABILITY = 10; | |
class Elevator{ | |
private: | |
int pos=0; | |
public: | |
bool dest[MAX_FLOOR]={}; | |
enum RunningStatus {MOVING, STOPPED, ARRIVED}; | |
RunningStatus state=STOPPED; | |
int get_position(); | |
RunningStatus tick(Elevator *e); | |
const char* get_state_char(); | |
}; | |
int Elevator::get_position(){ | |
return pos; | |
} | |
Elevator::RunningStatus Elevator::tick(Elevator *e){ | |
// 方針: | |
// 1.各エレベーターが監視する階を決める(エレベーターはその範囲でしか動かない) | |
// 2.各エレベーターの監視する階の範囲で最もボタンが押されている階に向かう | |
state = STOPPED; | |
int base = MAX_FLOOR / ELEVATOR_COUNT; | |
int rest = MAX_FLOOR % ELEVATOR_COUNT; | |
int min, max, last; | |
// 各エレベーターが監視する階を求める | |
for (int i=0; i<ELEVATOR_COUNT; i++){ | |
if (this != &e[i]) { continue; } | |
min = last > 0 ? last + 1 : 0; | |
max = rest - i > 0 ? min + base : min + base - 1; | |
last = max; | |
break; | |
} | |
// cout << " min=" << min << endl; | |
// cout << " max=" << max << endl; | |
// ボタンが一番押されている階は人数も多いはずなので優先して向かう | |
int target_floor; | |
int target_floor_count = 0; | |
for (int i=min; i<=max; i++){ | |
int count = 0; | |
for (int j=0; j<ELEVATOR_COUNT; j++){ | |
// ボタンが押されているか | |
if (e[j].dest[i]) { count++; } | |
} | |
if (count > target_floor_count) { | |
// 監視範囲で最もボタンが押されている階 | |
target_floor_count = count; | |
target_floor = i; | |
} | |
} | |
// 階移動 | |
if (target_floor<pos) {pos-=1;} else {pos+=1;} | |
for (int i=0; i<ELEVATOR_COUNT; i++){ | |
// 目的地に着いていなくても人が待っていれば拾う | |
if (e[i].dest[pos]) { | |
state = ARRIVED; | |
for (int j=0; j<ELEVATOR_COUNT; j++){ | |
e[j].dest[pos] = false; | |
} | |
break; | |
} else { | |
state = MOVING; | |
} | |
} | |
// 監視対象階にたどり着いていない場合は上の階に進ませる | |
if (state == STOPPED && this->get_position() < min) { pos+=1; state = MOVING; } | |
return state; | |
} | |
const char* Elevator::get_state_char(){ | |
switch(state){ | |
case Elevator::STOPPED: return "S"; | |
case Elevator::ARRIVED: return "A"; | |
case Elevator::MOVING: return "M"; | |
} | |
} | |
int main(int argc, char** argv) { | |
if (argc<2) { | |
cout << "入力パラメータを指定してください:" << endl; | |
cout << "例) ./a.out 1000 -d" << endl; | |
return -1; | |
} | |
int frame_count, sum=0; | |
Elevator e[ELEVATOR_COUNT]; | |
int waiting_people[MAX_FLOOR]={}; | |
random_device rnd; | |
for (frame_count=0; frame_count<atol(argv[1]); frame_count++){ | |
// 人が集まる | |
for (int j=0; j<MAX_FLOOR; j++){ | |
for (int k=0; k<ELEVATOR_COUNT; k++){ | |
if (rnd()%RAISING_PROBABILITY==0){ | |
int peep = 1+rnd()%5; | |
waiting_people[j] += peep; | |
e[k].dest[j]=true; // エレベータを呼ぶ | |
} | |
} | |
sum += waiting_people[j]; | |
} | |
// エレベータ動く | |
for (int j=0; j<ELEVATOR_COUNT; j++){ | |
switch(e[j].tick(e)){ | |
case Elevator::STOPPED: | |
case Elevator::ARRIVED: | |
waiting_people[e[j].get_position()] = 0; | |
break; | |
case Elevator::MOVING: | |
break; | |
} | |
} | |
// コンソール出力 | |
if ((argc >=3 && (string)"-d"==argv[2]) || (frame_count+1)==atol(argv[1])) { | |
usleep(50000); | |
cout << "\033[2J"; | |
cout << " time=" << frame_count << "sec" << endl; | |
cout << " ----------------------" << endl; | |
cout << " elevators waiting" << endl; | |
for (int i=MAX_FLOOR; --i>=0;){ | |
cout << setw(3) << i << "F"; | |
for (auto elevator:e){ | |
cout << "|" << ((elevator.get_position()==i) ? elevator.get_state_char() : (elevator.dest[i] ? "`" : " ") ); | |
} | |
cout << "|" << " " << waiting_people[i] << endl; | |
} | |
} | |
} | |
cout << "平均待ち人数=" << (float)sum / (frame_count*MAX_FLOOR) << "人" << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment