Алгоритм выполнения взвешенного перемешивания с постепенным всплытием элементов списка

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

Я работаю над сайтом со списками компаний в каталогах с разбивкой на страницы, и списки должны отображаться справедливо, поэтому один бизнес не всегда может быть выше / ниже другого списка. Чистой перетасовки каталогов на самом деле недостаточно, так как случайный характер этого может привести к тому, что любой конкретный бизнес будет случайным образом перемещаться в одно и то же место в списке в течение длительного периода времени, поэтому я хотел бы обеспечить некоторые веса, чтобы каждый список постепенно продвигается вверх по списку, так что они получают достаточно равные возможности для отображения на первой странице каталога с течением времени.

РЕДАКТИРОВАТЬ:

С благодарностью от Кевина - я пытаюсь формализовать эти правила:

1) для n списков каждый список должен отображаться на позиции один один раз в n «квазиперетасовках»)

2) (нечетко) средняя (?) позиция листинга должна увеличиваться со временем, пока не достигнет позиции 1.

3) для любых двух бизнесов (А и В) за n итераций перетасовки А не должно быть выше В более чем в 50% случаев?

Я также должен добавить, что я работаю в компании, которая имеет чрезвычайно сложный и запутанный «Shuffler», который необходим, чтобы успокоить большое количество платящих клиентов, которые настаивают на том, чтобы их справедливо распределили по соответствующим категориям их бизнеса в наших каталогах. Жалобы от клиентов — это «настоящая» проблема, учитывая, что пользователи обычно выбирают элементы с первых двух страниц с разбивкой на страницы, поэтому нечестно упорядочивать клиентов в алфавитном порядке (по умолчанию), а учитывая, что пользователи читают сверху вниз, это не так. справедливо, что одно дело всегда выше другого.

Мне интересно узнать, есть ли у кого-нибудь аккуратное решение этой проблемы, которое они могли реализовать ранее.

РЕДАКТИРОВАТЬ:

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

РЕДАКТИРОВАТЬ:

Я не хочу захлопывать базу данных, и мне нужна согласованность, пока пользователь просматривает, поэтому я буду выполнять «псевдоперетасовку» только каждую ночь (один раз в день), а не при каждом отображении каталогов.


algorithm shuffle weighted
person Rob    schedule 17.09.2012    source источник
comment
Не могли бы вы дать формальное определение вашей проблемы? Что именно должен делать вес?   -  person Fred Foo    schedule 17.09.2012
comment
@larsmans медленно продвигает элементы вверх по списку - я хотел бы обеспечить некоторый вес, чтобы каждый список медленно продвигался вверх по списку, чтобы они получали достаточно равные возможности для отображения на первой странице каталога с течением времени.   -  person Rob    schedule 17.09.2012
comment
Как вы узнали, что чисто случайная перетасовка приводит к несправедливым результатам для вашего сайта? Есть ли у вас какие-либо измеримые критерии, которые мы можем использовать для оценки наших решений? Или это ситуация, когда ваш босс говорит, что клиент X жаловался, что его листинг недостаточно высок, исправьте это?   -  person Kevin    schedule 17.09.2012
comment
@Rob: Это не формальная постановка проблемы.   -  person Fred Foo    schedule 17.09.2012
comment
@Kevin - последнее, но есть общее мнение, что в идеале клиенты должны видеть устойчивый сдвиг в начало очереди с течением времени, а не случайные прыжки повсюду ...   -  person Rob    schedule 17.09.2012
comment
@larsmans извини, приятель, я не уверен, что это такое, если бы я знал, возможно, я бы не задавал этот вопрос ...   -  person Rob    schedule 17.09.2012
comment
Я думаю, что Ларсмансу нужны количественные правила, которые можно использовать для принятия или отклонения любого конкретного алгоритма как действительного. Например, такие правила: 1) для любых двух записей одна из записей не должна постоянно появляться над другой в течение более чем X перетасовок. 2) Запись должна переместить не менее Y строк за Z перетасовок. 3) В течение A перетасовок каждая запись гарантированно появится среди первых B строк (на первой странице).   -  person Kevin    schedule 17.09.2012
comment
@Kevin - спасибо за разъяснения, действительно я предполагаю, что формальные правила будут такими: 1) для n списков каждый список должен отображаться в позиции один один раз за n квазиперетасовок) 2) (нечетко) средняя (?) позиция списка должна увеличиваться со временем, пока не достигнет позиции 1   -  person Rob    schedule 17.09.2012
comment
Как насчет того, чтобы ваша компания А не всегда была выше правила компании Б? Если формальное определение таково, как я написал его одним предложением назад, то вы можете поставить компанию A выше B в 99% случаев. У вас есть более строгие требования?   -  person Kevin    schedule 17.09.2012
comment
@Kevin - Извините, да, вы правы, но возможно ли это отследить? если бы вы сказали, что для любых двух предприятий (A и B) в течение n итераций перетасовки A не должно быть выше B более чем в 50% случаев?   -  person Rob    schedule 17.09.2012
comment
Если вы соблюдаете ровно 50%, то единственным законным перетасовкой будет переворачивание всего списка. Если его немного ослабить (скажем, до 60%), то ответ будет зависеть от того, сколько у вас компаний. Если у вас есть X компаний и вы отслеживаете их в течение N перетасовок, потребуется около NXX бит памяти для хранения их взаимоотношений.   -  person Kevin    schedule 17.09.2012
comment
@Kevin - лол, ты гораздо лучше разбираешься в этом, чем я, но я очень ценю твой вклад, у меня было чувство, что 50% будут проблемой, в идеале, я думаю, я надеялся, что часть перетасовки позаботится об этом ...   -  person Rob    schedule 17.09.2012
comment
давайте продолжим обсуждение в чате   -  person Rob    schedule 17.09.2012

Ответы (2)


arrow_upward
0
arrow_downward

Самый простой ответ, который приходит мне в голову, — это использовать подход Least-Recently-Used (LRU).

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

Это должно сработать и включает в себя обновление временной метки только элементов, отображаемых на верхней странице.

По мере добавления новых элементов и удаления старых элементов из списка это должно поддерживать изящную циркуляцию элементов.

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

Надеюсь, это поможет, Лоран.

person Laurent    schedule 17.09.2012
comment
извините, я собираюсь добавить редактирование - я не хочу захлопывать базу данных, и мне нужна согласованность, пока пользователь просматривает, поэтому я буду выполнять псевдо-перетасовку только каждую ночь (один раз в день), а не на каждом дисплее. каталогов - person Rob; 17.09.2012
comment
Я не уверен, что понимаю смысл вашего комментария по базе данных. Этот подход предполагает обновление только верхних элементов, а не всей базы данных. - person Laurent; 17.09.2012
comment
Это решение можно использовать, даже если вы выполняете обновление только один раз в день. Просто измените метку времени обновления, когда я отображаюсь на главной странице, чтобы обновить метку времени, когда я перемещаюсь в верхние X строк базы данных. - person Kevin; 17.09.2012
comment
Но это не решит ситуацию, когда бизнес A всегда находится выше бизнеса B — каким бы ни был порядок отображения по умолчанию, так они всегда будут отображаться, это главная проблема и реальная проблема для клиентов. Платящие клиенты не делают Алфавитный порядок - person Rob; 17.09.2012
comment
Вы бы заказали их по метке времени, а не по алфавиту. Это всего лишь алгоритм циклического перебора, гарантирующий, что все записи чередуются на первой странице. Случайное перемешивание может использоваться для смешивания записей при обновлении метки времени... - person Laurent; 17.09.2012
comment
@Laurent - К сожалению, в этом проблема, случайная перетасовка не идеальна, потому что нет гарантии, что один список не будет бесконечно перетасовываться случайным образом до последних 50% записей. Я в основном пытаюсь добиться кругового перебора с взвешенным перемешиванием, чтобы гарантировать, что часть случайности исключена из уравнения, используя некоторую форму взвешивания с течением времени (см. Мои отредактированные правила выше) - person Rob; 17.09.2012
comment
В моем последнем комментарии я хотел сказать: случайное перемешивание может использоваться для смешивания записей при обновлении метки времени только для обновляемых записей - person Laurent; 17.09.2012
comment
Таким образом, это в основном приведет к тому, что вы перетасовываете результаты в заданном наборе страниц, т.е. если на странице есть 10 элементов, то эти элементы будут перетасованы между собой, но все они выпадут и перейдут в конец очереди как часть раунда. Робин? - person Rob; 17.09.2012
comment
да. Но в зависимости от количества чередуемых элементов и времени, которое вы хотите, чтобы элементы перемещались с последней страницы на первую, вам, очевидно, придется применять этот процесс выпадения и поворота в конец очереди на более чем первая страница. Допустим, вы хотите гарантировать полную ротацию за 5 дней, тогда я бы применил этот процесс к первым 20% товаров. - person Laurent; 17.09.2012

arrow_upward
0
arrow_downward

для базы данных, содержащей X компаний, создайте сетку X на X и заполните каждую ячейку названием компании. Любое заданное название компании должно появляться ровно один раз в каждой строке и столбце. Например, для базы данных из десяти компаний, каждая из которых имеет односимвольное имя, одна такая сетка будет выглядеть так:

ABCDEFGHIJ
BCDEFGHIJA
CDEFGHIJAB
DEFGHIJABC
EFGHIJABCD
FGHIJABCDE
GHIJABCDEF
HIJABCDEFG
IJABCDEFGH
JABCDEFGHI

Компания в x-й строке и y-м столбце появится на x единиц сверху списка в y-й день. Другими словами, каждый день вы обращаетесь к другой строке для упорядочивания названий вашей компании. Эта схема удовлетворяет двум вашим критериям: каждый элемент должен находиться в слоте №1 хотя бы раз в X дней, и ни один конкретный элемент не должен оставаться на одном и том же месте в течение длительного времени. Но по-прежнему существует проблема, заключающаяся в том, что компания B всегда оказывается ниже компании A, поэтому требуется дополнительная работа.

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

HIDEJBGCAF
IJEFACHDBG
JAFGBDIECH
ABGHCEJFDI
BCHIDFAGEJ
CDIJEGBHFA
DEJAFHCIGB
EFABGIDJHC
FGBCHJEAID
GHCDIAFBJE

Теперь в среднем А будет впереди Б в 50% случаев. Фактический процент будет варьироваться, но он будет падать на кривую нормального распределения с центром около 50% и лишь в редких случаях будет достигать очень неравномерной пропорции.

Компания Б может пожаловаться на то, что она всегда появляется в слоте №1 ровно через день после того, как компания А появляется в слоте №1. Если это проблема, то также выполните перемешивание строк:

GCDHBIFEAJ
HDEICJGFBA
BHICGDAJFE
JFGAEBIHDC
IEFJDAHGCB
AGHBFCJIED
CIJDHEBAGF
EABFJGDCIH
FBCGAHEDJI
DJAEIFCBHG

Теперь у вас есть схема заказа со следующими свойствами:

Плюсы

  • в течение X-дневного цикла все X компаний занимают первое место.
  • в течение цикла длиной в X дней ни одна компания не застрянет на одном и том же месте. Заняв слот K, он не вернется в этот слот до конца цикла. (В худшем случае он все еще может некоторое время «зависать» в одной и той же области, но в конечном итоге он будет перемещаться по всему списку)
  • ни одна компания не появится над другой более чем в 50% случаев. Чем больше у вас компаний, тем ближе она к 50%.
  • какая компания окажется в слоте № 1, непредсказуемо, поэтому никто не может законно заявлять о предвзятости, основанной на том, когда компания находится в центре внимания.

Минусы

  • для базы данных из N компаний создание сетки занимает O(N^2) времени и памяти. Вам нужно генерировать только один раз в N дней, и вы можете сделать это заранее, чтобы вы могли амортизировать стоимость до O (N) времени.
  • Компании не «пузырятся» со временем. Я считаю, что это ограничение противоречит ограничению «ни одна компания не должна слишком сильно выделяться над другой»; если все компании пузырятся вверх примерно с одинаковой скоростью, то те, которые стартовали выше, обычно будут выше тех, которые стартовали ниже. Метод, который я привел, является результатом отказа от одного требования для удовлетворения другого взаимоисключающего требования.
  • для любого периода времени продолжительностью X дней существует вероятность 1/N того, что компания окажется в слоте №1 два дня подряд. Это происходит, например, когда компания А находится в слоте №1 в последний день цикла, а при создании новой сетки компания А находится в слоте №1 в первый день цикла. Если это нежелательно, вы можете выполнить еще одну перетасовку, пока A не окажется в первом слоте.
person Kevin    schedule 17.09.2012
comment
спасибо за этот исчерпывающий ответ, просто интересно в связи с этим утверждением - выберите два столбца наугад и поменяйте их местами. Повторяйте этот процесс до тех пор, пока столбцы не будут достаточно рандомизированы, не может ли это привести к тому, что компания вообще не окажется в верхнем слоте № 1, не лучше ли перетасовать что-нибудь, кроме первого столбца? - person Rob; 18.09.2012
comment
Нет, каждая компания всегда попадает в топ. Это связано с тем, что каждый столбец содержит каждую компанию ровно один раз. Невозможно поменять местами столбцы и получить, скажем, два «А» или ноль «А». Это верно, даже если вы поменяете местами столбцы и местами строк. Вот что отличает этот ответ от простого рандомизации списка каждый день — он обеспечивает определенную степень справедливости в течение X дней. - person Kevin; 18.09.2012