Недавно передо мной стала задача написать «ротатор» некоторых объектов, приоритет показа которых я должен выставлять сам. Суть проста: больше приоритет– больше показов объекта.
Однако, на этапе проектирования алгоритма было найдено несколько неприятных особенностей.
Ну, во-первых, хотелось обойтись минимальными изменениями в базе. Уж очень не хотелось делать отдельную таблицу в mysql для подсчета количества показов. Но смирившись с этим фактом, продолжил проектирование. Первый алгоритм который я соорудил был весь тупеньким но на бумаге пару ротаций прошел и работал весьма неплохо.
Суть его состояла в том, что в таблицу ротации мы записываем не только количество реальных показов, но и некое число по формуле (далее понижающая формула)
20 - 2i
где i — это приоритет ротации. Смысл данной формулы в том, что при показе объекта я буду выбирать из базы экземпляр с минимальной понижающей формулой и прибавляю к текущей сумме предыдущих понижающих формул еще одну единичную. Таким образом получается, что объект с большим коэффициентом ротации (тот, который я хочу показывать больше) будет встречаться чаще, потому что в к понижающей формуле будет прибавляться меньшее число чем у объектов с меньшим коэффициентом.
Следующая проблема, которую я разобрал- это проблема «20». То есть, на данном алгоритме можно было бы выставлять коэффициент ротации только от 0 до 9 (если брать только числа из ряда натуральных). Понижающая формула преобразовалась теперь в зависимости от количества объектов:
2n - i
где n– это количество объектов в базе пригодные для ротации. Но теперь наложились некоторые ограничения: коэффициент ротации не может превышать общего количества объектов ротации. То есть при
2n - i
0 <= i <= n
Забегая вперед, скажу что этим убивается на самом деле полтора зайца. А убивается тем, что решена одна из проблем при добавлении нового объекта. Теперь, при добавлении объекта остается только сделать небольшие манипуляции:
1 — решить, увеличить ли все текущие коэффициенты объектов на 1;
2- записать в ротационную запись инициативную понижающую формулу, или взять уже сумму из любой записи. Через несколько итераций показы пойдут как они и должны.
Вообще чем эта форма хороша– это тем, что орудуя коэффициентами в понижающей формуле можно ранжировать мощность эффекта, который дает коэффициент ротации (то есть, на сколько больше коэффициент 2 будет влиять на показы чем 1 или 0)
Но как я сказал меня не удовлетворял способ где приходилось бы создавать отдельную таблицу в базе или добавлять мусорные поля. Конечное, рабочее решение пришло ко мне когда я подумал примерно следующее «Коэффициент должен показывать то, на сколько больше объект должен показываться в выборке. При наличии коэффициентов 2 3 1 1 объекты из 7 раз должны показываться примерно 2 3 1 1 раза соответственно.» И тут ко мне пришла еще одна мысль, быдлокодерская, но удовлетворявшая моему главному требованию. Все что мне было нужно- это добавить в объект коэффициент ротации. Далее все дело в выборке: при выборке я выбираю все объекты ротации и наполняю массив с дубликатами соответственно коэффициенту ротации. То есть имея объекты и коэффициенты:
о1 о2 о3 о4
2 3 1 1
ротационный массив будет такой:
o1 o1 o2 o2 o2 o3 o4
Теперь осталось только его перемешать, и выбрать случайный элемент. По теории вероятностей все правильно: чем больше коэффициент ротации- тем больше шансов выбрать этот объект. С первого взгляда, кажется что ранжировать мощность влияния коэффициента на ротацию не получится, но никто не мешает сделать множитель для коэффициента, либо вообще возводить его в квадрат или куб (если объектов очень много). Заметьте, что новый объект встанет в такую ротационнцю схему без каких либо костылей.
Автор: ptuchster
