Приоритетные очереди 2
Почитал, подумал и пришёл к следующим мыслям.
Приоритетную очередь для баннеров можно организовать следующим образом. Строим массив или связный список, в котором для каждого из баннеров есть приоритет (приоритет будет вычисляться на основе кучи показателей, как-то количество необходимых показов к данному моменту времени, приоритетов баннеров и т.п., сейчас это не важно), при этом массив отсортирован в порядке убывания приоритетов.
При выборе баннера мы всегда начинаем с начала массива. Если баннер подходит по ограничениям, мы его показываем и уменьшаем приоритет на единицу, после чего сравниваем его со следующим элементом, и, если приоритет оказался меньше, чем у следующего баннера, переставляем их местами. Если баннер не подходит, переходим к следующему элемену очереди, и так далее пока очередь не кончится, в этом случае мы покажем заглушку.
Так же будут события, которые будут повышать приоритет очереди. В этом случае, элемент у которого повысился приоритет, будет сравниваться с предыдущим элементом, и, если приоритет у предыдущего элемента оказался меньше, элементы будут меняться местами.
Плюсы данной реализации вижу в том, что опечередь будет само-регулирующаяся, беннеры будут выбираться согласно реальным приоритетам, места в памяти будет занимать минимум, не будет проблем с пересчётом ограничений (или запоминанием баннеров, для которых уже считали ограничения) в равномерно-распределённой очереди из предыдущего поста.
Но есть одна сложность. Она связана с тем, что с очередью будут работать несколько потоков. Если очередь будет общей для всех потоков, придётся прибегать к блокировкам, чего я очень не люблю, и чего мне всегда удавалось избегать. Если для каждого из потоков сделать собственную очередь, то могут появляться коллизии, когда один поток изменил порядок очереди, но другие об этом не знают. Тут можно либо сигнализировать другим потокам об изменении (что мне не нравится, потому что усложняет систему), либо периодически проверять очередь на корректность (проще, но это значит, что ресурсы не всегда будут использоваться рационально), либо забить на эту проблему, потому что поток рано или поздно дойдёт до места коллизии и исправит её, а погрешность в показах будет достаточно маленькая чтобы ею серьёзно заморачиваться, но это надо ещё обдумать.
И ещё мысль. Если предположить, что трафик в нормальной системе всегда больше чем количество необходимых показов баннеров, то получается, что очередь всегда будет проходиться от начала до конца, а не будет таких ситуаций, когда до низко-приоритетных баннеров очередь не дойдёт.
Вот такие у меня мысли 
Tags: оптимизация, программирование
Есть мнение, что равномерное распределение не рулит в реальной жизни, если продаются не показы, а клики, например.
А когда будет пост про то как правильно делать проверку отсечек. Чтобы без перекруток, но и надежности не терять?
Если продаются клики, там вообще другая стратегия получается, там нужно судить по ECPM, количеству заработанных денег на 1000 показов…
Про отсечки отличная идея, на днях напишу своё мнение по этому поводу, спасибо за тему!
А правильно ли я понимаю, что приоритет, это фактически абсолютный вес РО, который вычисляется как f(x, y, z), где x,y,z - это параметры, которые влияют на вес?
Не совсем ясно почему мы уменьшаем приоритет на единицу, а не на десять, скажем ?
Да, правильно..
Кода писал пост, в голове плотно сидел баннерообмен, а потому плюсы и минусы в зависимости от того, показался чужой баннер на сайте своём, либо показался свой баннер на чужом сайте. В рекламной сети, думаю, буде всё несколько иначе…
А приоритет может увеличиваться на любое значение, это уже зависит от логики