Гарантия без оптимума: нижняя граница и балансировка нагрузки

Если ты умеешь доказать гарантию 2 − 1/m для жадной раздачи задач и знаешь, на каком входе она достигается, листай до «Теперь сам».

Как думаешь, насколько плох этот ответ

Семь задач сборки длятся 3, 7, 5, 3, 1, 9, 1 минут, раннеров три. Каждую задачу по очереди отдаём тому раннеру, который сейчас освободится раньше всех. Все раннеры закончат через 15 минут.

Это хорошо или плохо? Может быть, лучше 15 вообще нельзя. А может быть, можно втрое быстрее. Ответь себе до чтения: что можно сказать о качестве ответа, если наилучшее расписание тебе неизвестно и найти его - NP-трудная задача? Перебор 3⁷ = 2187 раскладок здесь ещё посилен, но при сотне задач и десяти раннерах раскладок 10¹⁰⁰.

Ответ этого урока: можно сказать точно, и для этого не нужен ни перебор, ни оптимум. Нужно число, которое оптимум точно не побьёт.

На что это похоже

Переезд на трёх грузовиках. Сколько займёт погрузка в лучшем случае, не знает никто: надо перебрать, что в какую машину класть. Но два утверждения очевидны без всякого перебора. Если всего грузить 29 часов работы, а машин три, то хотя бы одна машина грузится не меньше трети - почти 10 часов. И если пианино грузится 9 часов, то раньше 9 часов не закончить, как ни раскладывай.

Это и есть нижние границы: они не говорят, каким будет лучший план, но говорят, каким он точно не будет. Теперь достаточно показать, что твой план не хуже такой границы в два раза, - и он автоматически не хуже лучшего плана в два раза. Сравнивают не с недоступным оптимумом, а с тем, что лежит у него под ногами.

Механизм: последняя задача и занятые серверы

Задача распределения нагрузки: n задач с длительностями p₁ … pₙ, m одинаковых серверов; каждую задачу целиком выполняет один сервер; нужно, чтобы все закончили как можно раньше. Время окончания последнего сервера называют длиной расписания, а наименьшую возможную длину обозначим OPT.

Две нижние границы. Всего работы P = p₁ + … + pₙ. Серверов m, поэтому самый загруженный сервер получает не меньше среднего: OPT ≥ P / m. И самая длинная задача целиком идёт на один сервер: OPT ≥ max pᵢ. Обе видны по входу без всякого поиска.

Жадное правило (его называют раздачей по списку): идём по задачам в данном порядке и каждую кладём на сервер с наименьшей текущей нагрузкой.

Доказательство гарантии. Пусть позже всех закончилась задача ℓ, и началась она в момент S. Жадность положила её на самый свободный сервер - значит, в этот момент нагрузка каждого из m серверов была не меньше S. Все эти нагрузки составлены из задач, кроме самой ℓ, поэтому m · S ≤ P − p_ℓ. Длина расписания:

T  =  S + p_ℓ
   <=  (P − p_ℓ) / m  +  p_ℓ
   =   P / m  +  (1 − 1/m) · p_ℓ
   <=  OPT    +  (1 − 1/m) · OPT      первое по границе P/m,
   =   (2 − 1/m) · OPT                второе по границе max pᵢ

Каждая из двух частей ответа - «работа до старта последней задачи» и «сама последняя задача» - не больше своей нижней границы. Отсюда и двойка: две части, у каждой своя граница.

Правило

Гарантию приближения доказывают через нижнюю границу оптимума - число, которое видно по входу и которого оптимум точно не меньше. Для раздачи n задач по m одинаковым серверам границы две: P / m и самая длинная задача. Раздача по списку на самый свободный сервер даёт длину не больше (2 − 1/m) · OPT, и эта оценка достигается.

Разбор: семь задач, три раннера

Функция zhadno раздаёт задачи по правилу, optimum перебирает все m⁷ раскладок - чтобы сверить гарантию с правдой. Нижняя граница по средней берётся с округлением вверх: длительности целые, значит, и длина любого расписания целая.

def zhadno(zadachi, m):
    nagruzka = [0] * m
    for p in zadachi:
        luchshij = 0
        for i in range(1, m):
            if nagruzka[i] < nagruzka[luchshij]:
                luchshij = i
        nagruzka[luchshij] = nagruzka[luchshij] + p
    return nagruzka

def optimum(zadachi, m):
    luchshee = sum(zadachi)
    for kod in range(m ** len(zadachi)):
        nagruzka = [0] * m
        x = kod
        for p in zadachi:
            nagruzka[x % m] = nagruzka[x % m] + p
            x = x // m
        if max(nagruzka) < luchshee:
            luchshee = max(nagruzka)
    return luchshee

zadachi = [3, 7, 5, 3, 1, 9, 1]
m = 3
itog = zhadno(zadachi, m)
srednyaya = (sum(zadachi) + m - 1) // m
granica = max(srednyaya, max(zadachi))
print(itog, max(itog))
print(sum(zadachi), srednyaya, max(zadachi), granica)
print(max(itog) / granica, optimum(zadachi, m))

[15, 7, 7] 15
29 10 9 10
1.5 10

Жадность дала 15. Работы 29 минут, средняя нагрузка с округлением вверх - 10, самая длинная задача - 9, значит, оптимум не меньше 10. Без всякого перебора доказано: ответ хуже оптимума не больше чем в 15 / 10 = 1,5 раза. Перебор подтверждает, что оптимум и есть 10 (например, 9 + 1, 7 + 3, 5 + 3 + 1), так что граница здесь оказалась точной.

Откуда потеря. Позже всех закончилась задача на 9 минут: она пришла шестой, когда все серверы уже были загружены на 6-7 минут, и её пришлось положить сверху. Жадность не знала, что впереди длинная задача, и разложила мелочь поровну - ровно та ситуация, которую описывает доказательство.

Разбор: вход, на котором двойка почти достигается

Гарантия - это утверждение про худший случай. Проверим, что 2 − 1/m не завышена: построим вход, на котором жадность ошибается ровно на столько. Рецепт подсказывает само доказательство: сначала много мелких задач, которые разложатся поровну, а в конце одна длинная. Возьмём m(m − 1) задач длины 1 и последнюю длины m.

def zhadno(zadachi, m):
    nagruzka = [0] * m
    for p in zadachi:
        luchshij = 0
        for i in range(1, m):
            if nagruzka[i] < nagruzka[luchshij]:
                luchshij = i
        nagruzka[luchshij] = nagruzka[luchshij] + p
    return max(nagruzka)

for m in [2, 3, 4, 5]:
    zadachi = [1] * (m * (m - 1)) + [m]
    print(m, len(zadachi), zhadno(zadachi, m), m, 2 - 1 / m)

2 3 3 2 1.5
3 7 5 3 1.6666666666666667
4 13 7 4 1.75
5 21 9 5 1.8

Столбцы: число серверов, число задач, ответ жадности, оптимум, гарантия. Мелочь ложится по m − 1 на каждый сервер, длинная задача садится сверху: 2m − 1. Оптимум равен m: длинная задача одна на своём сервере, а остальные m − 1 серверов берут по m единиц. Отношение (2m − 1) / m = 2 − 1/m - совпадает с гарантией до знака. Значит, улучшить анализ нельзя: улучшать надо сам алгоритм. Подсказка, как именно, видна во входе: всё испортила длинная задача, пришедшая последней. Если раздавать задачи от длинных к коротким, гарантия становится 4/3 - об этом следующий урок.

Что ломается без этого

Гарантию проверяют на тестах. «На ста случайных входах жадность ошибалась не больше чем на 20%» - это наблюдение, а не гарантия. Плохой вход из второго разбора на случайных данных почти не встречается, но в жизни он типичен: ночная пачка мелких задач и одна тяжёлая миграция в конце очереди.

Берут одну границу вместо двух. Только средняя нагрузка не видит одну огромную задачу: 10 задач по 1 минуте и одна на 100 минут на десяти серверах дают среднюю 11, а раньше 100 не закончить. Только самая длинная задача не видит объёма: тысяча задач по минуте. Каждая граница слепа в своём месте, поэтому доказательство берёт обе.

Сравнивают с оптимумом, который не посчитать. Фраза «ответ не хуже оптимума вдвое» бесполезна в отчёте, если нельзя предъявить число. Нижняя граница - это и есть предъявляемое число: «не меньше 10 минут при любом расписании» проверит кто угодно калькулятором.

Зачем это в работе

Ты раскладываешь тесты по раннерам CI, сегменты индекса по машинам, пакеты пересчёта по воркерам. Заказчик спрашивает: «А нельзя ли быстрее?» Честный ответ без перебора: «Быстрее 10 минут нельзя при любом раскладе - это треть всей работы. У нас 15. Выигрыш, если он есть, не больше трети». Это разговор с числами вместо «мы старались».

И второе следствие: жадной раздаче не нужно знать будущих задач. Она кладёт задачу в момент прихода, а гарантия 2 − 1/m верна для любого порядка. Поэтому балансировщики очередей устроены именно так, и поэтому раздача по списку - один из первых примеров онлайн-алгоритмаРазбирается в разделе 22, глава «Онлайн-алгоритмы и конкурентный анализ»: Аренда лыж: решать, не зная будущего.

Теперь сам

1. Задачи 4, 4, 4, 4, 4, 4, 12, серверов три, порядок как дан. Какую длину даст жадность и какую нижнюю границу видно по входу? Какое отношение доказано?
2. Почему в доказательстве написано m · S ≤ P − p_ℓ, а не m · S ≤ P? Какая гарантия получилась бы со второй, более грубой оценкой?
3. На двух серверах жадность дала 30. Какое наименьшее значение может иметь оптимум?