Как реализовать алгоритм, подобный Digg?

StackOverflow https://stackoverflow.com/questions/71920

Вопрос

Как реализовать веб-сайт с системой рекомендаций, аналогичной stackoverflow/digg/reddit?То есть пользователи отправляют контент, и веб-сайт должен рассчитать своего рода «горячость» в зависимости от того, насколько популярен этот элемент.Порядок действий следующий:

  • Пользователи отправляют контент
  • Другие пользователи просматривают контент и голосуют за него (предположим, 90 % пользователей только просматривают контент, а 10 % активно голосуют за или против контента).
  • Новый контент постоянно добавляется

Как реализовать алгоритм, который вычисляет «жаркость» отправленного элемента, желательно в режиме реального времени?Существуют ли какие-либо передовые методы или шаблоны проектирования?

Я предполагаю, что алгоритм учитывает следующее:

  • Когда элемент был отправлен
  • Когда был подан каждый голос
  • Когда товар был просмотрен

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

(Я использую MySQL+PHP, но меня интересуют общие шаблоны проектирования).

Это было полезно?

Решение

Вы можете использовать что-то похожее на Алгоритм Реддита - основной принцип заключается в том, что вы рассчитываете ценность сообщения на основе времени его публикации и оценки.Что хорошо в алгоритме Reddit, так это то, что вам нужно пересчитывать значение только тогда, когда оценка публикации меняется.Если вы хотите отобразить свою главную страницу, вы просто получаете n лучших сообщений из вашей базы данных на основе этого показателя.Со временем баллы естественным образом будут увеличиваться, поэтому вам не придется выполнять какую-либо специальную обработку, чтобы удалить элементы с главной страницы.

Другие советы

На моем сайте я присваиваю каждой записи уникальное целое число из монотонно возрастающей серии (более новые публикации получают более высокие номера).Каждый голос «за» увеличивает число на единицу, а каждый голос «против» уменьшает его на единицу (конечно, вы можете настроить эти значения).Затем просто отсортируйте по номеру, чтобы отобразить самые «горячие» записи.

Я разработал сайт социальных закладок, Сайты Избранное, и использовал сложный алгоритм:

  1. Во-первых, голоса конечны, у пользователя есть только ограниченное количество голосов, и количество голосов зависит от очков пользователя.Чтобы заработать баллы, каждый пользователь должен добавлять ссылки, получившие положительные голоса.
  2. Затем пользователи могут проголосовать -3, -2, -1,1,2 или 3 голоса за каждую ссылку.Поскольку голоса ограничены, каждый пользователь будет голосовать только за те ссылки, которые ему нравятся.
  3. Чтобы запретить пользователю голосовать только за ссылки для одного и того же пользователя, создайте группы поддержки, баллы, которые каждый голос добавляет к ссылке, зависят от соотношения общего количества голосов и голосов за ссылки владельца проголосовавшей ссылки.Если вы всегда голосуете по ссылкам одних и тех же пользователей, ваши голоса потеряют ценность.
  4. Голоса со временем теряют ценность.
  5. Новые ссылки от пользователей, у которых нет баллов (новых пользователей), будут иметь начальный 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*.После этой оптимизации он должен быть достаточно быстрым для большинства сайтов любого размера.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top