?

Log in

No account? Create an account

Оптимизационная задачка - Общество дровосеков Бердичева по изучению Мишны

Jun. 13th, 2013

05:23 pm - Оптимизационная задачка

Previous Entry Share Next Entry



Уж как переложил на бытовые реалии, так переложил.

Имеется поликлиника, в которых работают специалисты N разных профилей. Приходящие пациенты встают в общую очередь. Сами они объяснить, какой врач им нужен, не могут, а в ответ на вопрос "К такому-то есть кто-нибудь?" из очереди выходит первый нуждающийся в этом враче, или никто не выходит, если таких на данный момент нет. Время, затрачиваемое регистратурой на один вопрос, в обоих случаях одинаково.

Тривиальный принцип работы регистратуры - называть всех специалистов по кругу, но при "эпидемии" это очевидным образом неэффективно.

Требуется придумать адаптивный алгоритм, стремящийся максимизировать пропускную способность регистратуры, в т.ч. и в условиях изменения характера "эпидемий", сохраняя справедливость: стоящий первым в очереди никогда не должен ждать дольше, чем M вопросов.



Начинаем с колоды из N карточек с номерами от 1 до N. Далее играем раунды так:

Выкликаем согласно номерам на карточках, и раскладываем карточки в N пар кучек, в каждой паре справа - успешные вызовы (Si), слева - неудачные (Fi).


Когда колода исчерпалась, смотрим: если во всех N парах было хотя бы по одному успешному вызову (все Si > 0), то набор Si более или менее неплохо моделирует соотношение частот клиентов врачей, а для уточнения соотношения на следующем круге составляем колоду из 2*Si карточек каждого типа, если это не больше, чем M, иначе по Si каждого типа.

Если же оказалось, что какие-то Si равны нулю, то это значит, что частота запросов для этих i меньше, чем 1/K, где K - размер колоды на только что закончившемся круге. Тогда составляем колоду из min(M, 2*K) карточек так, чтобы в них было по одной карточке для тех i, для которых Si было = 0, а остальные были в той же пропорции, что и ненулевые Si.

Из полученной новой колоды отбираем по одной карточке каждого типа, кладем в порядке возрастания в начало колоды, остальные тасуем и кладем за ними.

Споласкиваем, повторяем.

Comments:

[User Picture]
From:vgramagin
Date:June 14th, 2013 01:58 am (UTC)
(Link)
При M=N решение очевидно!
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 02:04 am (UTC)
(Link)
Скажем, M много больше N - в десятки раз.
(Reply) (Parent) (Thread)
[User Picture]
From:vgramagin
Date:June 14th, 2013 02:15 am (UTC)
(Link)
Может, наоборот?
(Reply) (Parent) (Thread)
From:morfizm
Date:June 14th, 2013 04:02 am (UTC)
(Link)
Если наоборот, то при определённом раскладе имён врачей и больных нельзя построить никакого алгоритма, чтобы гарантировать меньше M вопросов. Не говоря уже об оптимальном, учитывающем эпидемии и пр.
(Reply) (Parent) (Thread)
[User Picture]
From:vgramagin
Date:June 14th, 2013 01:08 pm (UTC)
(Link)
Или я не понял условия задачи, или вы.

Пусть N=10, M=20. Очевидно, что если регистратор будет просто задавать вопросы "кто к врачу 1, кто к врачу 2,..., кто к врачу 10" - то первый в очереди к любому врачу не будет ждать дольше 10 вопросов, что, очевидно, меньше 20
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 02:37 pm (UTC)
(Link)
Ну не будет, но при эпидемиях это неоптимально.
(Reply) (Parent) (Thread)
[User Picture]
From:galkao
Date:June 14th, 2013 03:00 am (UTC)
(Link)
Называем специалиста 1. Если есть желающий к нему, то снова вызываем специалиста 1. Если есть желающий - снова, и так - до тех пор, пока количество вызовов не превышает M/N. Далее - специалист 2. Ну и по кругу.

Проще говоря, допустим, M/N=10, тогда 10 раз подряд называем каждого специалиста по очереди (либо, если в какой-то момент не оказалось желающего, переходим к следующему специалисту).
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 02:40 pm (UTC)
(Link)
При эпидемиях это будет неоптимально. Допустим, в очереди все к одному и тому же специалисту, тогда оптимально будет вызывать к нему вплоть до M-N+1 раз.
(Reply) (Parent) (Thread)
[User Picture]
From:galkao
Date:June 14th, 2013 03:12 pm (UTC)
(Link)
Но тогда получится более сложный алгоритм, который в регистратуре ни запомнить, ни воплотить не смогут:-)

То есть нужно хранить коэффициент для каждого специалиста. Если число желающих совпало с M/N, добавить к коэффициенту "свободные вызовы", если число желающих меньше, убавить коэффициент до количества вызовов (а "остаток" добавить к "свободным").

Опять пример: M/N=10.
Вызываем 1-го, желающих - 3. Коэффициент К1==3. Свободный увеличиваем на 7 (изначально он равен 0).
Вызываем 2-го, желающих - 7, К2==7, к свободным добавляем 3.
Вызываем 3-го, желающих - 10, по одному изымаем из свободных дополнительные вызовы до тех пор, пока либо не кончатся желающие, либо кончатся вызовы.
Вызываем 4-го, желающих - 0, К4==1 (1- минимальное значение коэффициента). К свободным добавляем 9.

Ну и далее по кругу... Если вдруг предполагается несколько эпидемий, то из свободных на каждом этапе нельзя выбирать все вызовы, а только половину, например.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 03:26 pm (UTC)
(Link)
У нас алгоритм получился такой, что и регистратуре под силу. :)
(Reply) (Parent) (Thread)
From:morfizm
Date:June 14th, 2013 04:30 am (UTC)
(Link)
Пусть freshness(k) - сколько шагов назад назывался k-й врач.
Пусть popularity(k) - сколько пациентов к k-му врачу стоит в очереди (допустим какой-то оракул знает ответ).
Сортируем врачей по лексикографическому возрастанию тупла (max(M-a(i), N), -popularity(k)), и выбираем первого.

Этот алгоритм будет эффективно приоритезировать: самый популярный врач будет обслуживаться максимально, за исключением тех врачей, которых надо назвать для соблюдения справедливости. При одинаковой популярности, трафик будет делиться поровну между всеми одинаковыми.

Допустим, мы не знаем, чему равен popularity(k). Эту популярность надо *измерить*.

Измерять её можно по-разному. Вижу две крайности:

1. "Мочить" одного врача до упора, пока не кончатся его клиенты, или пока его не вытеснят ребята, которые по справедливости. Грубо говоря, popularity(k) = 1 если на предыдущем шаге был хотя бы один клиент, иначе 0. Кстати, в этом случае если к ребятам по справедливости кто-то пришёл, то в следующем раунде они уже будут соревноваться с первым и делить с ним трафик. Но те их них, которые "кончатся", отвалятся из соревнования. В этом случае у нас такой расклад: для лузеров, к которым никого нет, будет задан один вопрос на каждые M шагов. Для тех, к кому за M-шаговый цикл пришло 5 человек, будет 5 или 6 вопросов (в зависимости от того, люди исчерпались до или после обработки лузеров).

Можно делать какую-то адаптивную политику и учитывать историю, например, не присваивать единицу в популярность, а прибавлять единицу, а в случае неудачи не обнулять, а вычитать или делить. Если мы знаем паттерны эпидемий, можно подтюнить формулы так, чтобы было счастье.

2. Можно давать каждому врачу вплоть до M/N попыток и запоминать количество успешных. Круг может закончиться раньше, чем через M шагов, если к кому-то было менее M/N пациентов. На второму круге эти числа уже можно использовать как популярность. Время от времени делать тюнинг, заново пересчитывая. Или учитывая длины новых отрезков в формулу популярности. В случае одного доминирующего и остальных отдыхающих, его throughput будет заметно меньше, т.к. он будет получать не (M-N)/M, а (M/N)/(M/N + N). Зато будет некоторый QoS, честнее пропорция трафика и быстрее реакция на появление новых популярных врачей.

За неимением дополнительных знаний об эпидемиологических свойствах, я бы выкатил в продакшн п.1., ибо это максимизирует max throughput для лучшего, что есть нередко важнейшая метрика.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 02:47 pm (UTC)
(Link)
В отсутствие эпидемий алгоритм "мочить до упора" неоптимален, т.к. может быть вплоть до 50% бесполезных вопросов.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 03:45 pm (UTC)
(Link)
Идея в п. 2 логична, более тонкий вопрос - как эффективно реализовать тюнинг и как минимизировать количество магических чисел в параметрах.
(Reply) (Parent) (Thread)
From:morfizm
Date:June 14th, 2013 04:56 pm (UTC)
(Link)
Не понимаю вопрос про эффективную реализацию тюнинга. Это, типа, дальнейшее усложнение, нам важно не только оптимизировать вопросы регистратуры, но и оптимизировать вычисления? Требуется понять каков относительный вес этих вещей, и в чём измерять эффективность реализации тюнинга.

Ещё вопрос: *зачем* минимизировать количество магических чисел в параметрах?

Ещё вопрос: вы, с одной стороны, говорите, что 50% лишних вопросов это плохо, а, с другой, намекаете, что п.2. лучше, чем п.1., когда при определённом паттерне входящих, п.1. будет производить намного меньше лишних вопросов, чем п.2. Т.е. вы оцениваете, держа в голове определённый паттерн. Каков он? Для каких данных мы оптимизируем?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 05:09 pm (UTC)
(Link)
Магические параметры придется подбирать экспериментально, но экспериментальный материал может не соответствовать реальной жизни.

Нужно, чтобы один и тот же алгоритм минимизировал количество лишних вопросов как при более или менее равномерном распределении, так и при сильно смещенном распределении, и адаптировался достаточно быстро.
(Reply) (Parent) (Thread)
From:morfizm
Date:June 14th, 2013 05:17 pm (UTC)
(Link)
Сильно смещённое - это понятно, а что такое равномерное? Скажем так, интересно было бы знать, каково ожидаемое отношение K/N специалистов, могущих получить клиента (K) ко всем специалистам (N) в случае вот этой самой равномерности.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 05:39 pm (UTC)
(Link)
Близкое к единице, т.е. клиенты приходят с близкими средними частотами.
(Reply) (Parent) (Thread)
From:morfizm
Date:June 18th, 2013 07:23 am (UTC)
(Link)
Я не очень понял связь между "соотношение K/N близкое к единице" и "клиенты приходят с близкими средними частотами", мне это видится как два различных независимых параметра.

Клиенты могут приходить с теми же самыми близкими средними частотами, но вдвое реже, и K/N упадёт вдвое.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 18th, 2013 02:19 pm (UTC)
(Link)
Прошу прощения, я не так понял "могущих получить". В среднем регистратура способна разгребать очередь существенно быстрее, чем приходят клиенты, так что, скажем, K/N - порядка 1%.

Вы видели апдейт с нашим решением?
(Reply) (Parent) (Thread)
From:morfizm
Date:June 18th, 2013 04:24 pm (UTC)
(Link)
Только что посмотрел апдейт.

Мне надо ещё подумать, чтобы убедить себя, что это работоспособный алгоритм. Потенциально слабое место мне пока видится вот здесь: вероятности обновляются *только* когда 2*Si > M, соответственно, если мы имеем ситуацию, в которой это соотношение consistently не выполняется (например, уже есть эпидемия к 1-2 врачам), то про нового, третьего врача, к которому возникла эпидемия, регистратура никогда не узнает (в смысле, не начнёт увеличивать его вероятности), пока не кончится предыдущая эпидемия. Правильно ли я понял?

Вообще, после всех этих уточнений мне эта задача уже почти не нравится. Она слишком размыта в изначальной формулировке, и слишком сложна (и неуниверсальна) в деталях специфики условия, после того, как вы поделились этими деталями.


Edited at 2013-06-18 04:25 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 19th, 2013 08:07 pm (UTC)
(Link)
вероятности обновляются *только* когда 2*Si > M

Нет, почему же? Когда 2*Si > M, то мы делаем следующий раунд из Si, а если не больше, то из 2*Si. Разница будет лишь в том, с какой точностью (с каким знаменателем) мы оценим частоты разных i.

Переключение между эпидемиями происходит так: допустим, N = 5, M = 100, и была эпидемия номер 1. Тогда раунд состоит из 96 окликов 1 (из которых успешных, скажем, 10), и по одной для 2-5.
Если, в каком-то раунде, кроме десяти пациентов типа 1, оказался еще и пациент типа 2, то в следующем раунде типу 2 достанется 1*(100-3)/(10+1) = 9 окликов, что почти покрывает эпидемическую интенсивность прихода пациентов. Таким образом переключение между эпидемиями происходит за два раунда.
(Reply) (Parent) (Thread)
From:morfizm
Date:June 18th, 2013 04:29 pm (UTC)
(Link)
Вы лучше выложите ваши тестовые данные (+ приберегите ещё похожих данных для проверки), и мы посоревнуемся в реализации.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 19th, 2013 07:51 pm (UTC)
(Link)
К сожалению, задача не моя, а сослуживца - неудобно просить.
(Reply) (Parent) (Thread)
From:morfizm
Date:June 19th, 2013 07:57 pm (UTC)
(Link)
Жаль.
Но вы понимаете, что существуют исходные данные + детали критериев оценки, на которых моё решение будет лучше вашего? Если же вы допилите условия до таких, на которых ваше решение будет лучше, то вы, по сути, опишите ваш test data set. Я поэтому и подумал, почему бы не оптимизировать этот процесс и не выложить test data set as is.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 19th, 2013 08:21 pm (UTC)
(Link)
Ваше решение 1 хорошо для случаев, когда регистратура работает на пределе пропускной способности, и хоть к кому-нибудь всегда кто-то есть.

Наше решение - это, собственно, и есть Ваше решение 2, с удобной конкретизацией "время от времени делать тюнинг, заново пересчитывая". Быстрая адаптивность получается естественным образом.
(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:June 14th, 2013 04:40 am (UTC)
(Link)
А какая программистская ситуация соответствует такой схеме? Чтобы пациент мог ответить на вопрос "вы к окулисту?", но не мог бы ответить на вопрос "к какому вы врачу"? Ну, т.е., человек может забыть как называется глазной врач ("окулист" - пассивное слово), но с программами этого ведь обычно не происходит?
(Reply) (Thread)
From:morfizm
Date:June 14th, 2013 04:45 am (UTC)
(Link)
Я думаю, для простоты модели можно считать, что "N разных профилей ~= N врачей с такими-то именами", т.к. несколько врачей одного профиля можно легко сгруппировать в "одного врача" (назвав его "группа окулистов", скажем), и свести задачу к предыдущей.
(Reply) (Parent) (Thread)
[User Picture]
From:ak_47
Date:June 14th, 2013 05:46 am (UTC)
(Link)
Например, простой thread scheduling вполне подходит условиям задачи.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 02:56 pm (UTC)
(Link)
Например, некое устройство с поллингом многих каналов через один хардверный порт.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:June 14th, 2013 03:52 pm (UTC)
(Link)
Тогда это неправильная аналогия :-) Это получается несколько отдельных очередей, из которых регистратура вызывает по одному.

Я бы добавил счетчик длины очереди на каждом канале, и при опросе выдавал следующего ждущего и текущую длину очереди. И потом пытался эти очереди балансировать, чаще читая из каналов с более длинной очередью.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 04:00 pm (UTC)
(Link)
Это получается несколько отдельных очередей, из которых регистратура вызывает по одному.
Если вдуматься, это эквивалентно. Выбор и опрос очереди, из которой вызывать - то же самое, что "К такому-то есть кто-нибудь?"

Добавить в прибор ничего нельзя, да и смысла нет - в sustained near-optimal mode длина очереди в каждом канале - от нуля до двух.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:June 14th, 2013 04:07 pm (UTC)
(Link)
Можно аналогичную информацию извлечь эвристически.

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

Эту логику можно расширить на хранение результатов последних N опросов. И делать специальный круг для очередей, которые вернули непусто при последних N опросах, потом при как минимум последних (именно последних, а не с перерывами в истории) N-1 опросах, как минимум N-2, и так далее. Естественно, что как только при каком-то опросе все возвращают "пусто", память сбрасывается.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 04:19 pm (UTC)
(Link)
В общих словах так, а как это оптимально реализовать?
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:June 14th, 2013 04:33 pm (UTC)
(Link)
Счетчик на каждую очередь, в котором считать количество последних непрерывных успешных попыток? Если очень захотеть, можно это даже держать не в виде массива счетчиков с индексированием по номеру очереди, а пары (номер очереди, счетчик), отсортированные в массиве по значению счетчика. Сортировка будет относительно легко поддерживаться при каждом проходе.

Оно мне, кстати, напомнило задачку, которую мне как-то задавали на интервью. Там было про разделение пропускной способности канала между несколькими потоками данных согласно заданным пропорциям, но если некий поток использует меньше лимита, то оставшаяся от него лишняя пропускная способность делится между теми, кому нужно больше.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 04:53 pm (UTC)
(Link)
Это близко к тому, что у нас. Как это выглядит в бытовых терминах, расскажу на днях.
(Reply) (Parent) (Thread)
From:morfizm
Date:June 14th, 2013 04:41 am (UTC)
(Link)
Ещё - интуитивно кажется, что для реальных задач может хорошо подойти алгоритм на основе вышеуказанного, но в котором есть следующие дополнения:
1. У каждого врача есть лимит на количество вопросов подряд, вначале limit(k) = 2.
2. В случае упирания в limit после цепочки из q вопросов, происходит следующее: если все q были обработаны, то limit := limit * 2 (по сути он будет 2q), а popularity := q. Если же цепочка закончилась в результате облома, и на последний вопрос никто не откликнулся, сбрасываем в начало: limit := 2, popularity := 0.

Получаем ситуацию, в которой у врача-лузера есть шанс постепенно "разогнаться" и потом делить канал почти поровну с предыдущим победителем, пока один из них не исчерпает спрос.
(Reply) (Thread)
From:morfizm
Date:June 14th, 2013 05:11 am (UTC)
(Link)
О... понятно, сортировку надо подтюнить - вместо max(M-a(i), N) делать что-то вроде max(M-N-a(i), N). Чтобы в случае когда осталось M-2*N шагов, уже начинать сортировать оставшихся, т.к. каждому лузеру полагается до 2 попыток.

P.S. Я там где-то мог не учесть +1 или -1, это в юнит тестах отлаживается :)
(Reply) (Parent) (Thread)
[User Picture]
From:vymenets
Date:June 14th, 2013 06:09 am (UTC)
(Link)
Такое чувство, что условие неполное. Время приёма специалиста больше нуля? Больше или меньше времени на вопрос регистратуры? Может ли регистратура узнать, что конкретный специалист освободился?
(Reply) (Thread)
From:morfizm
Date:June 14th, 2013 11:14 am (UTC)
(Link)
Пусть автор меня поправит, но я думаю, что здесь имеется в виду, что время приёма у специалиста равно (или: не больше) времени вопроса. Скажем, регистратура задаёт вопрос раз в минуту, и этой минуты хватает, чтобы обслужить. Можно представить себе, что под именем специалиста скрывается целая группа похожих специалистов, которые позволяют такое быстрое обслуживание. Соответственно, перед каждым следующим вопросом все специалисты свободны, а работает только один из них одновременно. Но "оплата" идёт только за вопросы регистратуры. Каждый вопрос, даже если он вхолостую (никого из очереди к этому специалисту не оказалось), стоит минуту времени.

Второй вариант (изоморфный) после направления к специалисту пациент переходит в другую очередь (конкретно к этому специалисту), в которой время уже никак не учитывается и обслуживание идёт в порядке очереди.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 02:53 pm (UTC)
(Link)
Да, совершенно верно.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 02:49 pm (UTC)
(Link)
Специалисты сами разбираются с очередями конкретно к ним и открывают дополнительные точки приема, если надо.
(Reply) (Parent) (Thread)
[User Picture]
From:dvv
Date:June 14th, 2013 01:24 pm (UTC)
(Link)
Ну чо, веса́ накидывать на используемых специалистов (с time decay). Логарифмически or something. Обычное дело…
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 03:10 pm (UTC)
(Link)
Именно что or something. Эргодичности никто не обещал.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:June 14th, 2013 03:44 pm (UTC)
(Link)
Что-то тут не так. "Сами они объяснить, какой врач им нужен, не могут" не вяжется со способностью ответить на вопрос "К такому-то есть кто-нибудь?". Получается, что кто-то (регистратура?) должен им это объяснить перед тем, как поставить в очередь.

Решение - регистратура самообслуживания. Чтоб каждый пациент самостоятельно классифицировал, к какому врачу ему надо.

То есть, переходя на кнопкодавские реалии, вызывал функцию, назначающаю врача, в контексте своего собственного треда.
(Reply) (Thread)