Приоритетные очереди
Не первый раз сталкиваюсь с задачей, для которой я пока не придумал красивого и простого решения… Речь идёт о приоритетных очередях.
Для решения проблемы с выбором баннера, который надо показать на площадке, я знаю два решения. Первое решение — подсчёт суммы приоритетов всех баннеров, расстановка весов каждому из баннеров, а потом, случайным образом (с учётом приоритетов) выбор баннера. Такой вариант не нравится большим количеством вычислений и тем, что баннеры выбираются случайным образом, а не равномерно (на большом трафике статистика нормальная, но хочется иметь нормальную статистику и на маленьком трафике). Второй вариант — очереди. Формируется циклическая очередь, по которой бегаем. Математики мало, но есть свои проблемы.
Первый вариант очереди — массив (или связный список) в котором количество элементов того или иного баннера зависит от приоритета и элементы для одного баннера находятся последовательно (например, 1, 1, 1, 1, 2, 3, 3,…). Минусы такого подхода в том, что при большом разбросе в приоритетах, во-первых, очередь становится очень большой (например, если у одного баннера приоритет 1000, а у другого 1, то такая очередь будет состоять из 1001 элемента, где первый баннер повторяется 1000 раз), во-вторых, баннеры будут отдаваться не равномерно: сначала первый, потом второй и т.п.
Второй варинат очереди — модификация первого варианта, где элементы распределены равномерно (например, 1, 2, 1, 2, 3, 1, 2, 1). Плюс в том, что баннеры отдаются равномерно, но, в случае, если баннер не подходит по тем или иным критериям, мы не можем, как в первом варианте, просто пропустить все элемены для данного баннера, а придётся либо их постоянно перепроверять, либо хранить где-то список уже проверенных баннеров и их пропускать. Опять таки тут не решается проблема с большим разбросом приоритетов.
Третий вариант — не повторять баннеры в очереди, а иметь у каждого из них “счётчик приоритетов”, который будет уменьшаться при выборе баннера, а когда все счётчики обнулятся, они будут выставлены в изначальное значение. Тут тоже есть минус, что делать, если все баннеры со значением счётчика не равным нулю не подходят? Показывать заглушку — не вариант, это пустая трата трафика. Показывать баннер со счётчиком равным нулю, значит сбить приоритеты в очереди.
Мне больше всего нравится второй вариант, но проблема с разбросом приоритетов может стать большой проблемой, например, в баннерообменных сетях, где разброс может быть огромным. Например, сайт с трафиком в 3.000.000 показов и сайт с трафиком в 10 показов создадут очередь в 300.001 элементов, а это ни в какие рамки не лезет.
Есть мысли?
Tags: оптимизация, программирование
