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

Question

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

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

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

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

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

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

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

(р - 1) / (т + 2)^1,5

где

р = баллы статьи и

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

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

Answer 5

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

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

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