Я думаю, что это в основном заключается в том, как вы определяете количественно приемлемое решение, и как вы определяете ограничения, такие как There should be a variety in [...]. Вы также должны решить, что делать, когда ваши данные сильно коррелируют: например, если большинство ссылок на «сильные бренды» происходят из одной «отрасли», то, поскольку вы хотите, чтобы многие отрасли были представлены, у вас будет небольшая доля » Сильные фирменные »элементы в вашем наборе. В этом случае вы не сможете иметь оба.
Предположим, вам нужно отобразить n элементов на вашей странице. Это внешнее ограничение, вероятно, определяемое размером веб-элемента, содержащего список элементов; остальные ограничения выбраны вами.
Перейдите к разделу tl; dr внизу, чтобы пропустить детали.
Решение 1: дешево и (в общем) эффективно: 100% случайно
Вы можете просто выбрать n ссылки наугад и позволить вселенной решить, какие элементы попадут на вашу страницу. Если ваши данные более или менее равномерно распределены по различным столбцам, и если n «достаточно велик», большую часть времени вы будете получать достаточно хорошие данные. Это также делает ваш код очень легко обслуживаемым / обновляемым в случае, если вам нужна быстрая реализация, так что вы можете вернуться к нему позже, когда у вас есть лучший алгоритм.
Теперь это не относится к
Недавно добавленные ссылки имеют более высокую вероятность выбора
часть, так что мы можем сделать немного лучше
Решение 2: не 100% случайное
Это слегка измененная версия первого решения. В этом примере вы выполняете итерацию по своему набору данных, начиная с самого последнего «ReferenceId» и следуя в порядке убывания «ReferenceId». Каждый элемент имеет вероятность выбора p, выбранную таким образом, что элементы n обычно находятся в пределах N самых последних элементов вашего набора данных. Если вы достигли дна до того, как выбрали n элементов, просто начните сверху (или увеличьте p).
В Java это будет выглядеть так:
for (Object item : items) {
if (random.nextDouble() < p) {
result.add(item);
}
if (result.size() == n) {
break;
}
}
Однако, если ваши данные не распределены неравномерно (что может иметь место, так как вы задаете этот вопрос), вы не можете полагаться на случайность только для генерирования вашего набора элементов. Прежде чем перейти к решению 3, проверьте, работает ли это решение для вас или нет. Если нет,
Решение 3: сформулируйте ограничения и попытайтесь их удовлетворить, жадный метод
Теперь вам нужно определить, что означает набор размера n для удовлетворения требований, касающихся вашего глобального набора данных.
Вы должны знать, что, поскольку вы настраиваете шансы каждого конкретного предмета быть выбранным в финальном наборе, вы, возможно, не сможете по-настоящему иметь
они отличаются каждый раз, когда кто-то посещает мою домашнюю страницу
Чтобы быть действительно уверенным в этом, представьте пример, в котором одна из «областей» представлена только одним элементом во всем наборе данных: скорее всего, он всегда будет в конечном выбранном подмножестве, поскольку вы хотите принудительно разнести. Существует также тот факт, что, поскольку вы предоставляете привилегии недавно добавленным ссылкам, ваше распределение данных будет более точно отражать распределение самых последних записей.
Так что теперь вы в мире с не всегда обязательным истинным случайным и равномерным представлением, давайте сформулируем ограничения. Ограничение для столбца может быть в форме «Я хотел бы иметь по крайней мере n/10 отдельных элементов из этого столбца в конечном подмножестве». Вы оцениваете состояние ограничения как «удовлетворенное» или «неудовлетворенное» с помощью функции (S, n, k) -> {true, false} где:
S - текущий набор выбранных элементов n - желаемый размер для выбранных элементов k - мощность столбца
говоря "учитывая текущее подмножество элементов, это ограничение уже выполнено?" Вы также можете оценить, способствует ли элемент удовлетворению ограничения, говоря: «учитывая текущее подмножество элементов, мы ближе к выполнению этого ограничения, если добавим этот элемент?».
Выполните итерацию, как в решении 2 выше, и сохраните случайность для каждого элемента, но также добавьте проверку на соответствие ограничения с Set ограничениями. Как только ограничение выполнено, удалите его из набора ограничений.
Без подробностей реализации вы получите что-то вроде:
for (Object item : items) {
// every item still has some probability of being chosen or not
if (random.nextDouble() < p && helpsSatsfyAtLeastOne(remainingConstraints, item, result, n)) {
result.add(item);
}
for (/* Appropriate data structure */ constraint : remainingConstraints) {
if (constraint.isSatisfied(result, n)) {
constraints.remove(constraint);
}
}
if (result.size() == n) {
break;
}
}
System.out.println("Unsatisfied constraints: " + remainingConstraints);
Вы можете реализовать helpsSatsfyAtLeastOne(...) для обеспечения порядка ограничений, чтобы удовлетворить, если вам нужно расставить приоритеты для некоторых, или просто запустить его через ограничения в произвольном порядке.
Это жадный подход, и у вас нет гарантии, что конечный результат будет на 100% идеальным. Если в конце некоторые ограничения остаются неудовлетворенными, попробуйте установить приоритет в этих ограничениях.
ТЛ; др
Этот подход прост и должен дать вам достаточно хороших результатов в большинстве случаев. Если этого не произойдет, и ваш набор данных настолько конкретен, что вам нужно более точное решение, тогда есть еще много работы. Но я полагаю, что это не так, поскольку вы просто хотите, чтобы на веб-странице был хороший набор разнообразных элементов.
- Определите, что это значит, чтобы удовлетворить ваши ограничения (с точки зрения
количество элементов, относительное / абсолютное количество элементов, представляющих
колонка и т. д.)
- Итерация по ссылкам в порядке убывания даты (последние
первый)
- Каждый предмет имеет
p вероятность быть выбранным
- Если выбран элемент (с вероятностным процессом), проверьте, добавляете ли вы
это к результату вносит вклад как минимум в одно ограничение (т.е.
это увеличит количество
someColumn?). Если так, добавьте это к
результат.
- Затем проверьте, удовлетворяются ли некоторые ограничения теперь, когда этот элемент
добавлено (т. е. у меня есть достаточно из
someColumn в моем результате
установить? "). Снять эти ограничения.
- Если все ограничения выполнены, но вы все равно можете добавлять элементы в свой набор, добавьте их случайным образом любым удобным вам способом.