Этот вопрос был задан мне во время собеседования - Какая структура данных эффективна для реализации механизма лифта?
Я не могу найти эффективную структуру данных для него даже после большого количества Google.
Я могу думать о очереди Priority для ее реализации. В очереди приоритетов для реализации механизма элевации существует эффективная структура данных или более эффективная структура данных?
Спасибо!
Поскольку вы не можете реализовать механизмы в программном обеспечении (хотя, конечно, можете их моделировать), я предполагаю, что вопрос был о алгоритме лифта.
Алгоритм выглядит обманчиво простым, но на удивление очень сложно реализовать его, даже с хорошим набором структур данных в руке. Хорошей структурой для этого алгоритма является три очереди приоритетов:
Ваша реализация сначала решит направление, затем выберите очередь, в которую помещается запрошенная пара значений {from, to}.
Что делать, если мы использовали два связанных списка один для запросов движения вверх, а другой для запроса движения вниз.
например
Первый запрос: a). В то время как лифт находится на 0-м этаже, и просьбы приходят на 3-й этаж.
связанный список для движения вверх.
3- > нулевым.
связанный список для движения вниз.
нуль.
Второй запрос: б). в то время как лифт переместился на 1-й этаж, и запрос поступает с 2-го этажа для движения вверх.
связанный список для движения вверх.
2- > 3- > нулевым
связанный список для движения вниз.
нуль.
Третий запрос: c) Предположим, что 2 человека входят на 2-й этаж, один нажимает кнопку для 5-го этажа, а другой на 1-й.
связанный список для движения вверх.
3- > 5- > нулевым
Примечание: здесь 2 был удален из восходящего списка, поскольку он был достигнут.
связанный список для движения вниз.
1- > нуль.
d) Предположим, что человек входит на 3-й этаж и нажимает кнопку для 0-го этажа
связанный список для движения вверх.
5- > нулевым
связанный список для движения вниз.
1- > 0- > нуль.
После того, как пятый этаж iis достиг восходящего запроса, связанный список становится пустым, поэтому связанный список вниз можно рассматривать для перемещения.
Если оба связанного списка пусты, тогда лифт будет в состоянии покоя.
Итак, я думаю, что связанный список также может быть эффективной структурой данных для лифта
Ниже приведен один из способов разработки системы лифтов. Каждый лифт использует Queue (это может быть блокировка очереди) для хранения запросов на пол. Также имеется центральный диспетчер ElevatorManager, который контролирует все очереди лифта и может делегировать запросы на определенный лифт в зависимости от некоторых бизнес-правил. Это задача LiftManager для эффективного делегирования запросов на соответствующий лифт. Ниже псевдокода не оптимизируется алгоритм делегирования, но он показывает, как фактическое делегирование может быть сделано для списка лифтов.
Классы, необходимые для системы лифта:
ElevatorManager [Singleton - это основная программа лифта, которая будет управлять n лифтами в здании]
<Б > Пользователи:
Список Лифт
Queue of Floor.Request//Это поддерживает запрос для обоих направлений. Одним из улучшений может быть сохранение двух очередей, по одному для каждого направления, но это увеличит сложность
MIN_FLOOR
MAX_FLOOR
Операции:
delgate()
halt()//установить всю систему лифта в режиме обслуживания или остановить работу
Лифт [Представляет отдельные лифты. В здании может быть n лифтов]
<Б > Пользователи:
Очередь пола//это нужно отсортировать, поэтому может быть использовано PriorityQueue
Направление: Enum [Перечисление направления - вверх, вниз, ждать, бездействовать, обслуживание]
CurrentFloor: Этаж
Операции:
работать()
MoveUp()
MoveDown()
openDoor()
closeDoor()
callEmergencyLine()
getDirection()
getCurrentFloor()
setInMaintenanceMode()
Этаж [представляет собой отдельные этажи]
<Б > Пользователи:
eNum of Floors
запрос класса {
currentFloor
destinationFloor
Направление [Вверх, Вниз]
}
<Б > Операция:
GoUp()
Godown()
Некоторые из основных псевдокодов для вышеуказанных компонентов:
class Floor {
goUp() {
ElevatorManager.queue.offer(new Request(currentFloor, destinationFloor, up));
}
goDown() {
ElevatorManager.queue.offer(new Request(currentFloor, destinationFloor, down));
}
}
ElevatorManager {
delegate() {
// Instead of using one object, we could use a list to track idle and elevators moving in same direction so that these list could be used for next requests in queue
// but again to simplify pseudocode, I am using single objects instead of lists
Elevator idleElevator; // track idle elevator
Elevator elevatorMovingInSameDirection; // elevator moving in same direction as next request in main elevator manager queue
while(!halt()) { //keep delegating until powered down or whole system is halted through main controls
if(queue.peek() != null) {
Request req = queue.peek();
boolean startAgain = false; // flag to start from beginning if the request is already pushed to one of the elevators queue during iterating elevators
for(Elevator elevator : elevators) {
// first find if there is an elevator at current floor going in same direction as current request in queue
if(req.currentFloor == elevator.currentFloor && req.direction == elevator.direction) {
elevator.queue.offer(req.destinationFloor);
queue.poll(); // remove this request from Elevator Manager queue
startAgain = true;
break;
}
// check if this elevator is idle
if(elevator.direction == "idle")) {
idleElevator = elevator; // For this simple design, I am ok to overwrite idle elevator value and instead get the latest idle elevatior
}
// check if this elevator is moving in desired direction and elevator current floor is behind desired floor in queue
if(elevator.direction == req.direction) {
// Make sure elevators moving in same direction should also be behind the floor where request is made
if(req.direction == "Up" && req.currentFloor - elevator.currentFloor > 0) {
elevatorMovingInSameDirection = elevator; // Same as above, it ok to get this overwritten and instead get the latest elevator moving in same direction
}
// Make sure elevators moving in same direction should also be behind the floor where request is made
if(req.direction == "Down" && req.currentFloor - elevator.currentFloor < 0) {
elevatorMovingInSameDirection = elevator;
}
}
}
// Only delegate to other floors if you could not find elevator going in same direction at same floor from where the request was made
if(!startAgain && idleElevator != null) {
idleElevator.queue.offer(req.destinationFloor);
queue.poll();
}
// if we could neither find elevator at current floor nor idle elevator then send this request to elevator behind current Floor and moving in same direction as the request
if(!startAgain && elevatorMovingInSameDirection != null) {
elevatorMovingInSameDirection.queue.offer(req.destinationFloor);
queue.poll();
}
}
}
}
}
Elevator {
moveUp() {
this.currentFloor += 1;
}
moveDown() {
this.currentFloor -= 1;
}
operate() {
while(queue.peek() != null) {
Floor nextFloorInQueue = queue.peek();
while(this.currentFloor != nextFloorInQueue.request.destinationFloor) {
if(this.direction == "Up") {
moveUp();
} else if(this.direction == "down") {
moveDown();
}
}
queue.poll(); // remove the request from queue
open(); //open door
Direction backUpDirection = this.direction; //back up elevators direction to retrieve it later once dooor closes
this.direction = "idle"; // set state to idle to let elevatorManager know that requests at current floor could be offered to this elevator queue
Thread.sleep(10000); // sleep for 10 seconds so that people can leave elevator
close(); // once people are out close door to move to next floor in queue
this.direction = backUpDirection;
}
this.direction = "idle"; // once queue is empty set the direction to idle
}
}
Он также доступен здесь на моем Github: https://github.com/prabhash1785/Java/blob/master/ObjectOrientedDesign/src/com/prabhash/java/design/objectoriented/elevator/ElevatorDesignWithPseudocode.md
Как насчет наличия массива, где каждая запись массива представляет собой пол. Когда пользователь хотел остановиться на полу, он отметит эту запись в массиве, и лифт будет смотреть в массив и очистить запись, если отметит, когда лифт достигнет этого пола. Подобно алгоритму планирования SCAN/CSAN. Я с нетерпением жду ваших комментариев.
Для простоты рассмотрим a одна лифтовая система.
Используемая структура данных: простые списки для хранения пол #, перечисления для события и состояния.
Система может быть выполнена в режиме Event-State. Каждый аспект поведения пользователей или среды должен быть рассмотрен при решении вопроса о том, какие сценарии можно выбросить на лифте.
Events of the elevator : GOINGUP, GOINGDOWN, STOP
States of the elevator : ONMOVE, WAITING (between door open and close), IDLE (serving no one), UNDERMAINTENANCE
Elevator movement is usually driven by two activites:
1. Press Up or Down key (before the entry gate of elevator) and wait for the elevator to come and serve you. (Press-And-Wait, say PAW)
2. Enter inside the elevator and make request by pressing keys (Enter-And-Request, say EAR)
So it can said that PAW from outside and EAR from inside can decide the hops of the elevator. But what about direction?
Two possible types of PAW: PAWup (press Up button) and PAWdown (press Down button)
Now, EAR can be any of the three types depending upon the users behavior. These are the critical challenges in deciding the algorithm:
1.) Normal - same direction as PAW (wanted to go down and enter lower floor#)
2.) Opposite - wanted to go down BUT enter higher floor#
3.) Indecisive - Do Nothing, no key press
Now comes all the important rules:
RULE 1: If at IDLE, use FCFS to decide between the DownList front and UpList front - whoever is oldest, serve it first to ensure less waiting time.
RULE 2: When both lists (DownList and UpList) are empty, move elevator to IDLE state.
RULE 3: Elevator state change GOINGUP->STOP clears that floor# from UpList. Similarly, GOINGDOWN->STOP clears that floor from DownList.
RULE 4: Absolute Zero Skipping: GOINGxxx serves as many floors in xxxList as possible.
RULE 5: Elevator doesn't favour Opposite-EAR, and obviously can't serve Indecisive-EAR.
RULE 6: Elevator in UNDERMAINTENANCE state is shunned from all external signals.
RULE 7: In the event of Power-cuts or Fire, the elevator goes and stops at Lobby. Flooding??
To achieve RULE#5, GOINGDOWN clears all the lower floor# in DownList in ONE GO. Similarly, GOINGUP clears all the higher floor# in UpList.
Lets discuss one scenario to clear the above concepts:
Say, an elevator is resting at floor 7 is at IDLE state,
DownList :
UpList :
[email protected] - [email protected] then [email protected] then [email protected]
DownList : 12, 13 (older requests at lower index.Push new requests at front.)
UpList : 9
Using RULE#2, in the above case,
Event: GOINGUP to [email protected]
[email protected] - 12 cleared following RULE#3
MeanWhile, [email protected] then [email protected] then [email protected], so updated lists are:
DownList : 13, 10
UpList : 9, 8, 10
So here, in the current situation, if the EAR is
1.) Normal, GOINGDOWN(towards new EAR) is triggered.
2.) Opposite/Indecisive, GOINGDOWN(towards 9) is triggered and add the new EAR in UpList.
Используя вышеупомянутые правила, лифт продолжает свою обычную работу.
Каждое нажатие кнопки приводит к запросу лифта, который должен быть подан. Каждый из этих запросов отслеживается на глобальном уровне. ElevRequests - класс, в котором хранятся запросы на лифт, может использовать различные стратегии для планирования запросов на лифте. Лифт управляется классом контроллера, который мы называем ElevatorController. Контроллер лифта инструктирует лифт, что делать, а также может выключить/запустить лифт здания. Контроллер лифта считывает следующий запрос лифта, который должен обрабатываться и обслуживает его.
Кнопка - абстрактный класс, определяющий общее поведение, такое как подсветка, doNotIlluminate. FloorButton, ElevatorButton расширяет тип кнопки и определяет placeRequest(), который вызывается при нажатии кнопки. Нажимайте кнопки напольного нажатия и кнопку лифта, добавляя запросы в обычное место.
ElevatorController запускает показ, читая следующий запрос для обработки и инструктирования лифта, что делать.