Как реализовать Digg-подобный алгоритм? - PullRequest
Новая
       18

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

10 голосов
/ 16 сентября 2008

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

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

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

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

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

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

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

Ответы [ 5 ]

6 голосов
/ 16 сентября 2008

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

4 голосов
/ 19 сентября 2008

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

1 голос
/ 31 октября 2012

Я реализовал 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 *. После этой оптимизации она должна быть достаточно быстрой для большинства сайтов любого размера.

1 голос
/ 11 апреля 2010

Пол Грэм написал эссе о том, что он узнал в разработке Hacker News . Акцент делается больше на людях / взаимодействиях, которые он пытался привлечь / создать, чем на алгоритме как таковом, но все же стоит прочитать. Например, он обсуждает различные результаты, когда истории всплывают снизу (HN), а не взрываются вверх (Digg) на первой странице. (Хотя из того, что я видел в HN, похоже, что там тоже взрываются истории).

Он предлагает эту цитату:

Ключ к производительности - элегантность, а не батальоны особых случаев.

, что в свете предполагаемого алгоритма для генерации главной страницы HN:

(p - 1) / (t + 2) ^ 1,5

, где

p = пункты статьи и

t = время с момента подачи статьи

может быть хорошей отправной точкой.

1 голос
/ 19 сентября 2008

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

  1. Во-первых, голоса являются конечными, пользователь имеет только ограниченное количество голосов, и количество голосов зависит от очков пользователя. Чтобы заработать очки, каждый пользователь должен добавить ссылки, которые получают положительные голоса.
  2. Затем пользователи могут голосовать -3, -2, -1,1,2 или 3 голоса за каждую ссылку. Поскольку количество голосов ограничено, каждый пользователь будет голосовать только за те ссылки, которые ему нравятся.
  3. Чтобы пользователь не мог голосовать только за ссылки одного и того же пользователя, создавая группы поддержки, очки, которые каждый голос добавляет к ссылке, зависят от соотношения общего количества голосов и голосов за ссылки владельца проголосовавшей ссылки. Если вы всегда голосуете за одни и те же ссылки пользователей, ваши голоса потеряют ценность.
  4. Голоса теряют значение со временем.
  5. Новые ссылки от пользователей, у которых нет баллов (новые пользователи), будут иметь начальные 0 баллов. Новые ссылки от старых пользователей будут иметь очки в зависимости от их очков. Начиная от +3 до -бесконечно. Ссылки от пользователей с отрицательными точками будут иметь отрицательные начальные точки, ссылки от пользователей с положительными точками будут иметь положительные начальные точки.

Пользователи будут получать случайные очки при голосовании за ссылки. Положительные голоса дают положительные баллы, отрицательные - за отрицательные.

...