После долгих лет работы с данными и изучения алгоритмов, на которых основано все — от обнаружения мошенничества до машинного обучения, — вряд ли можно было предположить, что самое большое мое разочарование в технологиях будет вызвано чем-то настолько привычным, как лифт. Я живу на 60-м этаже одного из самых высоких зданий в Абу-Даби с видом на море — именно об этом мне мечталось в детстве, проведенном в Мумбаи. Какая панорама открывается из моих окон? Нереальная. А какова моя повседневная жизнь? Менее впечатляющая, особенно когда приходится подниматься и спускаться на лифте.
Мне приходилось работать со сложными моделями, по сравнению с которыми нейронные сети — детская забава. Но лифты — это нечто! Шесть блестящих больших кабин, половина из которых обслуживает с 1-го по 32-й этаж, а другая половина — с 33-го по 60-й. И все же несмотря на все очевидные чудеса инженерной мысли я каждый день простаиваю в ожидании лифта. При всех наших технологических достижениях мы как будто забыли, как эффективно перемещать людей между этажами.
Представьте такую картину. Вы ждете на первом этаже, нажимая на кнопку лифта, чтобы подняться на 60-й этаж. Лифт поднимается из подвального этажа уже битком набитый людьми — яблоку негде упасть. Он останавливается на первом этаже, двери открываются, и я вижу людей, зажатых внутри, как сардины в банке, прекрасно понимая, что ни один человек не выйдет, чтобы впустить меня. Двери закрываются. Лифт уезжает. А я, оставшись на первом этаже, как персонаж жестокой экзистенциальной пьесы, снова нажимаю на кнопку.
Почему он останавливается, если переполнен? Почему мне приходится участвовать в этом бесполезном ритуале? Весь мой профессиональный путь был посвящен оптимизации систем, и у меня не укладывается в голове, что алгоритм лифта — да, реальный алгоритм — может быть настолько плохо оптимизирован. Вот тут-то я обращаюсь к своим познаниям в области компьютерных наук. Как работают эти лифтовые алгоритмы и почему они так сильно меня подводят?
Как «думают» лифты: основы лифтовых алгоритмов
Приоткроем завесу и посмотрим, как работают лифты — точнее, почему они работают не так эффективно, как могли бы.
Лифты следуют алгоритму планирования (диспетчеризации), который очень похож на алгоритм SCAN, используемый при планировании работы диска. Алгоритм SCAN работает так: система движется в одном направлении, обслуживая запросы по мере их поступления, пока не достигнет последнего запроса в этом направлении. Затем она меняет направление, двигаясь в обратную сторону и обслуживая больше запросов на обратном пути. Подобно лифту, SCAN минимизирует потери времени за счет смены направлений.
Представим это в коде:
def elevatorScan(requests, currentFloor, direction="up"):
"""
Basic SCAN (elevator) algorithm.
requests: A list of floor requests to be serviced.
currentFloor: The current position of the elevator.
direction: The direction the elevator is moving ("up" or "down").
"""
while requests:
# Сортировка запросов в зависимости от направления движения (лифтовые алгоритмы опираются на предсказуемый порядок действий).
if direction == "up":
requests.sort()
else:
requests.sort(reverse=True)
for request in requests:
if (direction == "up" and request >= currentFloor) or \
(direction == "down" and request <= currentFloor):
print(f"Stopping at floor {request}")
currentFloor = request
requests.remove(request)
# Смена направления при достижении последнего этажа (лифтам чуждо круговое движение).
direction = "down" if direction == "up" else "up"
В теории все просто и эффективно. Лифт, подобно дисковой головке, меняет направление только тогда, когда достигает последней остановки на своем текущем пути. Это не позволяет ему без необходимости перемещаться зигзагами между этажами. Пока все логично, верно?
В чем проблема? В координации — точнее, в ее отсутствии
Все описанное выше работает только для одного лифта и не учитывает его вместимость. На самом деле мой этаж обслуживают три лифта, и вот тут-то все и запутывается. По логике движение лифтов должно координироваться, верно? Однако они ведут себя как конкуренты, причем каждый из них не обращает внимания на то, что делают другие. Ближайший лифт может приехать на мой этаж, даже если он переполнен; при этом остальные, вполне способные поднять меня наверх, не сдвигаются с места.
Есть несколько лифтов, нет координации
Итак, смоделируем работу нескольких лифтов. У каждого лифта есть свой алгоритм SCAN, но между ними нет обмена информацией. Это приводит к неэффективности, если ближайший к вам лифт переполнен, а вместо того, чтобы отправить другой лифт, система оставляет вас ждать, как будто наказывает за попытку добраться до работы.
Вот как выглядит система с несколькими лифтами без учета информации о вместимости:
def multipleElevators(elevators, requests):
"""
Simulate multiple elevators, each with their own SCAN algorithm.
elevators: A dictionary where keys are elevator IDs and values are dictionaries with their current state.
requests: A list of floor requests to be serviced.
"""
while requests:
for elevatorId, elevator in elevators.items():
# Проверка, движется ли этот лифт в правильном направлении, ведь координация - это слишком высокое требование.
if elevator['direction'] == 'up':
directionRequests = [r for r in requests if r >= elevator['currentFloor']]
direction = "up"
else:
directionRequests = [r for r in requests if r <= elevator['currentFloor']]
direction = "down"
if directionRequests:
# Лифт движется, сообразуясь с запросами и вместимостью, как будто вместимость сама по себе не является проблемой.
nextFloor = min(directionRequests) if direction == "up" else max(directionRequests)
if elevator['capacity'] < elevator['maxCapacity']:
print(f"Elevator {elevatorId} stopping at floor {nextFloor}")
elevator['currentFloor'] = nextFloor
elevator['capacity'] += 1 # Симуляция захода людей в лифт.
requests.remove(nextFloor)
else:
print(f"Elevator {elevatorId} is full! Skipping stop at floor {nextFloor}")
# Смена направления при отсутствии запросов в этом направлении (зачем вообще нужна командная работа?).
if not directionRequests:
elevator['direction'] = "down" if elevator['direction'] == "up" else "up"
elevators = {
'Elevator 1': {'currentFloor': 10, 'direction': 'up', 'capacity': 5, 'maxCapacity': 10},
'Elevator 2': {'currentFloor': 20, 'direction': 'down', 'capacity': 3, 'maxCapacity': 10},
'Elevator 3': {'currentFloor': 30, 'direction': 'up', 'capacity': 8, 'maxCapacity': 10},
}
requests = [5, 25, 40, 50, 60]
multipleElevators(elevators, requests)
Проблема: отсутствие информации о вместимости
В этой версии ближайший лифт может остановиться на вашем этаже, даже если он переполнен. Для человека, ожидающего на первом этаже, это просто безумие. Алгоритм учитывает направление, но не учитывает вместимость. Вот решение: нужно ввести ограничения на вместимость и в случае, если ближайший лифт переполнен, гарантировать, что вместо него приедет другой.
Решение: координирование лифтов с учетом вместимости
Теперь усовершенствуем эту систему, введя понятие вместимости и координацию между лифтами. Если ближайший лифт переполнен, необходимо обеспечить отправку ближайшего доступного лифта. Это включает проверку вместимости каждого лифта перед отправкой, и если один из них переполнен, другой лифт заступит на его место.
Вот обновленный код с проверкой вместимости и координацией:
def coordinatedElevatorsWithCapacity(elevators, requests):
"""
Simulate coordinated elevators with capacity awareness, where they communicate to balance load.
elevators: A dictionary of elevators with their current state.
requests: A list of floor requests to be serviced.
"""
while requests:
for request in requests:
closestElevator = None
minDistance = float('inf')
# Проверка того, есть ли в ближайшем лифте свободные места (очевидно, это новая идея).
for elevatorId, elevator in elevators.items():
distance = abs(elevator['currentFloor'] - request)
if distance < minDistance and elevator['capacity'] < elevator['maxCapacity']:
closestElevator = elevatorId
minDistance = distance
if closestElevator:
# Назначение ближайшего лифта, имеющего свободные места, для обработки запроса.
elevator = elevators[closestElevator]
print(f"Elevator {closestElevator} moving to floor {request}")
elevator['currentFloor'] = request
elevator['capacity'] += 1 # Симуляция захода людей в лифт.
requests.remove(request)
else:
# Если все лифты переполнены и ни один из них не сможет обслужить запрос, дальше будет "весело".
print(f"All elevators full! No available elevator for floor {request}")
# Сброс вместимости для следующего цикла после обработки всех запросов.
for elevatorId, elevator in elevators.items():
elevator['capacity'] = 0 # Сброс вместимости после обслуживания запросов.
Почему эта оптимизация решает проблему?
Благодаря совершенной оптимизации, устраняется зависимость от одного переполненного лифта. Система теперь обладает информацией о вместимости и отправит за вами лифт, в котором есть свободное место. Больше не нужно смотреть, как полный лифт останавливается на первом этаже, дразня ожидающих напрасными надеждами. Теперь, если один лифт переполнен, его место займет другой.
Будущее за «умными» лифтами
В будущем оптимизированная система лифтов будет выглядеть так: несколько лифтов координируют свое движение, проверяют возможности друг друга и следят за тем, чтобы никто не ждал впустую (если, конечно, они не будут опаздывать).
А до этого времени я буду сидеть здесь, на 60-м этаже, и ждать, когда меня подвезут, зная, что, по крайней мере, теперь мной создан алгоритм, который учитывает мое время. Даже если он не работает в реальной жизни. Просто еще один алгоритм, который я добавлю к своему постоянно растущему списку моделей, которые так и не увидели свет.
Читайте также:
- Структуры данных и алгоритмы: стек
- Как работает алгоритм YouTube?
- 5 алгоритмов, которые изменили мир
Читайте нас в Telegram, VK и Дзен
Перевод статьи Shrutika Poyrekar: Stuck Between Floors: How Elevator Algorithms Make Us Wait… and Wait… and Wait
