Как реализовать алгоритм, подобный Digg?
-
09-06-2019 - |
Вопрос
Как реализовать веб-сайт с системой рекомендаций, аналогичной stackoverflow/digg/reddit?То есть пользователи отправляют контент, и веб-сайт должен рассчитать своего рода «горячость» в зависимости от того, насколько популярен этот элемент.Порядок действий следующий:
- Пользователи отправляют контент
- Другие пользователи просматривают контент и голосуют за него (предположим, 90 % пользователей только просматривают контент, а 10 % активно голосуют за или против контента).
- Новый контент постоянно добавляется
Как реализовать алгоритм, который вычисляет «жаркость» отправленного элемента, желательно в режиме реального времени?Существуют ли какие-либо передовые методы или шаблоны проектирования?
Я предполагаю, что алгоритм учитывает следующее:
- Когда элемент был отправлен
- Когда был подан каждый голос
- Когда товар был просмотрен
Например.элемент, который получает постоянный поток голосов, будет постоянно оставаться несколько «горячим», в то время как элемент, который получает всплеск голосов при первой отправке, поднимется на вершину списка «горячих» голосов, но затем упадет вниз, когда голоса прекратятся. в ближайшие.
(Я использую MySQL+PHP, но меня интересуют общие шаблоны проектирования).
Решение
Вы можете использовать что-то похожее на Алгоритм Реддита - основной принцип заключается в том, что вы рассчитываете ценность сообщения на основе времени его публикации и оценки.Что хорошо в алгоритме Reddit, так это то, что вам нужно пересчитывать значение только тогда, когда оценка публикации меняется.Если вы хотите отобразить свою главную страницу, вы просто получаете n лучших сообщений из вашей базы данных на основе этого показателя.Со временем баллы естественным образом будут увеличиваться, поэтому вам не придется выполнять какую-либо специальную обработку, чтобы удалить элементы с главной страницы.
Другие советы
На моем сайте я присваиваю каждой записи уникальное целое число из монотонно возрастающей серии (более новые публикации получают более высокие номера).Каждый голос «за» увеличивает число на единицу, а каждый голос «против» уменьшает его на единицу (конечно, вы можете настроить эти значения).Затем просто отсортируйте по номеру, чтобы отобразить самые «горячие» записи.
Я разработал сайт социальных закладок, Сайты Избранное, и использовал сложный алгоритм:
- Во-первых, голоса конечны, у пользователя есть только ограниченное количество голосов, и количество голосов зависит от очков пользователя.Чтобы заработать баллы, каждый пользователь должен добавлять ссылки, получившие положительные голоса.
- Затем пользователи могут проголосовать -3, -2, -1,1,2 или 3 голоса за каждую ссылку.Поскольку голоса ограничены, каждый пользователь будет голосовать только за те ссылки, которые ему нравятся.
- Чтобы запретить пользователю голосовать только за ссылки для одного и того же пользователя, создайте группы поддержки, баллы, которые каждый голос добавляет к ссылке, зависят от соотношения общего количества голосов и голосов за ссылки владельца проголосовавшей ссылки.Если вы всегда голосуете по ссылкам одних и тех же пользователей, ваши голоса потеряют ценность.
- Голоса со временем теряют ценность.
- Новые ссылки от пользователей, у которых нет баллов (новых пользователей), будут иметь начальный 0 баллов.Новые ссылки от старых пользователей будут иметь баллы в зависимости от их баллов.Диапазон от +3 до -бесконечно.Ссылки от пользователей с отрицательными баллами будут иметь отрицательные начальные точки, ссылки от пользователей с положительными баллами будут иметь положительные начальные точки.
Пользователи будут получать случайные баллы, когда за их ссылки будут голосовать.Положительные голоса дают положительные баллы, отрицательные голоса – отрицательные.
Пол Грэм написал эссе о том, чему он научился в разработка Хакерских новостей.Акцент делается больше на людях/взаимодействиях, которые он пытался привлечь/создать, чем на алгоритме как таковом, но его все равно стоит прочитать.Например, он обсуждает различные результаты, когда истории всплывают снизу (HN) и взрываются вверху (Digg) первой страницы.(Хотя, судя по тому, что я видел в HN, похоже, что и здесь истории выходят на первый план).
Он предлагает такую цитату:
Залог эффективности — элегантность, а не батальоны особых случаев.
что в свете предполагаемый алгоритм для создания главной страницы HN:
(р - 1) / (т + 2)^1,5
где
p = баллы статьи и
t = время с момента подачи статьи
может быть хорошей отправной точкой.
Я реализовал SQL-версию алгоритма ранжирования Reddit для видеоагрегатора следующим образом:
SELECT id, title
FROM videos
ORDER BY
LOG10(ABS(cached_votes_total) + 1) * SIGN(cached_votes_total)
+ (UNIX_TIMESTAMP(created_at) / 300000) DESC
LIMIT 50
*cached_votes_total* обновляется триггером каждый раз, когда подается новый голос.На нашем текущем сайте он работает достаточно быстро, но я планирую добавить столбец значений рейтинга и обновить его с помощью того же триггера, что и столбец *cached_votes_total*.После этой оптимизации он должен быть достаточно быстрым для большинства сайтов любого размера.