Как работает сортировка у Реддита

Автор оригинала: Amir Salihefendic
  • Перевод
Сейчас на хабре продолжают обсуждать сортировки и рейтингования сущностей (записей, постов, комментов), так что я сам этим заинтересовался и, как раз находясь на реддите, решил узнать как там работает сортировка, и наткнулся на отличную и короткую статью.

Этот пост — продолжение разбора алгоритмов сортировки (в прошлый раз был Hacker News). В этот раз, мы разберем как работает сортировка постов и комментариев на Reddit. Алгоритмы у Реддита достаточно простые, чтобы понять их и реализовать.

Первая часть этой записи будет сфокусирована на сортировке постов, а вторая на сортировке комментариев. Они довольно сильно различаются, и за идеей способа сортировки комментариев стоит Randall Munroe (автор xkcd).

Разбираем сортировку постов

Реддит open-source-ный проект и его код полностью доступен на гитхабе. Он написан на питоне, исходники вы можете увидеть тут. Их алгоритмы сортировки написаны под Pyrex, для дальнейшей компиляции (трансляции) в C-код. Pyrex был выбран из-за производительности. Я переписал их реализации на чистый питон, чтобы они легче читались.

Дефолтный алгоритм сортировки, названный «hot ranking» реализуется так:
#Rewritten code from /r2/r2/lib/db/_sorts.pyx

from datetime import datetime, timedelta
from math import log

epoch = datetime(1970, 1, 1)

def epoch_seconds(date):
    """Returns the number of seconds from the epoch to date."""
    td = date - epoch
    return td.days * 86400 + td.seconds + (float(td.microseconds) / 1000000)

def score(ups, downs):
    return ups - downs

def hot(ups, downs, date):
    """The hot formula. Should match the equivalent function in postgres."""
    s = score(ups, downs)
    order = log(max(abs(s), 1), 10)
    sign = 1 if s > 0 else -1 if s < 0 else 0
    seconds = epoch_seconds(date) - 1134028003
    return round(order + sign * seconds / 45000, 7)

В математической записи, этот алгоритм выглядит так:


Устаревание записей


Вот что можно сказать об устаревании относительно сортировочных рейтингов (далее просто рейтингов) и сортировки:
  • Возраст статьи оказывает большое влияние на ее рейтинг, чем новее — тем выше рейтинг она получит
  • Рейтинг не уменьшается с устареванием статей, но растет с новыми статьями


Вот визуализация, как выглядит рейтинг статей с одинаковым кол-вом плюсов и минусов, но разным временем публикации:


Логарифмическая шкала

Hot ranking использует логарифм для того, чтобы первые n голосов весили больше чем будущие n+r голоса. В итоге получается, что первые 10 плюсов имеют такой же вес, как следующие 100, которые имеют такой же вес как следующие 1000, и т.д.

Вот как это выглядит:

А вот как выглядело бы без логарифма:


Воздействие «минусов»

Реддит — один из тех сайтов, на котором можно минусовать. Как вы видели в коде, «score» поста равен разнице плюсов и минусов.

В итоге это выглядит так:


Это оказывает большое влияние на посты, которые получают много плюсов и минусов (т.н. спорные посты), они получают меньший рейтинг, чем посты только с плюсами. Наверное поэтому котята так часто бывают на главной :) (прим. пер. — на самом деле это из-за того, что вы не отписались от /r/aww)

Заключение по сортировке постов

  • Время добавления — очень важный параметр, более новые посты получат более высокий рейтинг
  • Кривая рейтинга строится по логарифму десяти. Первые 10 плюсов равны следующим 100
  • Спорные посты, получившие и плюсы и минусы будут ниже просто «заплюсованных» постов


Как работает сортировка комментариев

Randall Munroe из xkcd стоит за идеей Реддитовского best ranking. Он написал отличную статью про это: reddit's new comment sorting system

Вам стоит прочитать эту статью, в ней он очень понятно объясняет принцип работы алгоритма. Резюмируя ее, можно сказать:
  • Алгоритм hot ranking не подходит для рейтинга комментариев, так как он очень сильно опирается на возраст записи
  • В комментариях, вам нужно ставить лучшие комменты выше, вне зависимости от того, когда их отправили
  • Решение для этого было найдено в 1927 году Эдвином Вилсоном и названо «Вилсоновский рейтинговый интервал» («Wilson score interval»), Вилсоновский интервал может быть использован для «сортировки по доверию»
  • При сортировке по доверию общее кол-во голосов представляется как статистическая выборка гипотетического полного голоса от каждого — как в опросе мнений
  • How Not To Sort By Average Rating — хорошо описывает алгоритм рейтингования по доверию, очень рекомендую к прочтению! (прим. пер. — также есть хорошая статья на хабре)


Исследуем код сортировки комментариев

Алгоритм сортировки по доверию реализован в _sorts.pyx, я его также переписал на чистый питон (и убрал некоторые кеширующие оптимизации):
#Rewritten code from /r2/r2/lib/db/_sorts.pyx

from math import sqrt

def _confidence(ups, downs):
    n = ups + downs

    if n == 0:
        return 0

    z = 1.0 #1.0 = 85%, 1.6 = 95%
    phat = float(ups) / n
    return sqrt(phat+z*z/(2*n)-z*((phat*(1-phat)+z*z/(4*n))/n))/(1+z*z/n)

def confidence(ups, downs):
    if ups + downs == 0:
        return 0
    else:
        return _confidence(ups, downs)

Сортировка по доверию использует Вильсоновский интервал и математическая запись выглядит так:


Список параметров этой формулы:
  • p — доля положительных оценок
  • n — общее кол-во голосов
  • zα/2 — это (1-α/2) квантиль стандартного нормального распределения


Давайте подведем итог сказанному выше:
  • Сортировка по доверию представляет кол-во голосов как статистическую выборку гипотетического полного голоса каждого
  • Сортировка по доверию дает прогнозируемую оценку комментарию, которую он с вероятностью 85% получит
  • Чем больше голосов, тем ближе предполагаемый рейтинг подходит к действительному
  • Интервал Вилсона хорош также и для малого кол-ва голосов и в случаях крайней вероятности


У Рэнделла есть отличный пример, как происходит рейтингование комментариев:
Если у комментария один плюс и ноль минусов, у него 100%-ный рейтинг, но так как у нас слишком мало данных, система будет держать его внизу. Но, если у него 10 плюсов и всего один минус, система может иметь достаточно доверия (уверенности), чтобы поместить его выше какого-нибудь комментария с 40 плюсами и 20 минусами, предположив, что когда он тоже получит 40 плюсов — у него будет меньше 20-ти минусов. И лучшая часть в том, что даже если это будет неверно (что бывает в 15% случаев), система быстро получит больше данных (т.к. плохой коммент оказался вверху, его увидят и заминусуют) и коммент попадет туда, куда следует.


Как мы видим, на этот алгоритм никак не влияет устаревание записей.
Давайте посмотрим, как это выглядит:

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

Как отмечает Evan Miller, Вилсоновский интервал можно использовать не только для рейтинга.
Вот три примера, которые он привел:
  • Обнаруживать спам: какой процент людей, которые видят это, отметят это как спам?
  • Создание списка «лучшее»: какой процент людей, кто увидит это, отметят как «лучшее»?
  • Создание списка «most emailed»: какой процент людей, которые видят эту страницу, нажмут «Email»?
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 21

    +5
    пост №1: ляляля, интервал вилсона, ляляля, так работает елп и реддит
    пост №2: ляляля, интервал вилсона это из другой оперы, есть более простые формулы, вот они и что они значат
    пост №3: ляляля, интервал вилсона, ляляля, так работает реддит

    может, хватит уже повышать энтропию? ну что за ерунда? ну ок, давайте в третий раз прочитаем про интервал вилсона. ок.
      +3
      На самом деле меня этот пост больше заинтересовал из-за первой части. А то, что про вильсона уже писали я обнаружил, когда пост был почти дописан.
        0
        А мне вот было интересно почитать и про интервал Вилсона я не знал, и про квантиль нормального распределения узнал дополнительно, так что, автору спасибо за статью.
          +7
          а кому-то будет и в пятый раз интересно про интервал вилсона прочитать, и в шестой. я уверен, что если раз в месяц постить статью про интервал вилсона, каждый раз будут находиться пользователи которым это будет неизвестно.
          давайте так теперь поступать, да?

          книжки нужно читать, So1, квантиль нормального распределения он не знал. а если уж решили благодарить автора, то пойдите и поблагодарите автора, а не переводчика. квантиль нормального распределения он не знал, охохо. скоро за hello world начнём благодарить, «не знал как написать хеллоу ворлд, теперь знаю и узнал как написать это два раза дополнительно. спасибо автору за статью»
            0
            Вы, очевидно знаете все-все в своей сфере, а еще все-все в смежных сферах и еще очень много во всем множестве сфер. Будьте попроще. Люди все-равно не потянутся, зато будете попроще.
              0
              Опс, сорри за некропостинг, тема в новый обсуждениях всплыла.
        +2
        Спасибо за перевод! Что касается первого алгоритма, то он показался мне более чем странным… Я пробовал строить рейтинг на его основе, и подумал, что что-то неправильно перевёл, или не правильно понял. В итоге сделал по-своему взяв за основу сам принцип:

        Рейтинг_в_ленте = f1(рейтинг публикации) + f2(дата публикации)
        

        Т.е. мы банально прибавляем к рейтингу дату устанавливая между ними какое-то равновесие. Например рейтинг +100 = 5 дням, + 1000 = 10 дням и т.д. В качестве f1 я пробовал использовать как logn(up-down), так и тот же willson score на что-нибудь помноженный. Оба работают неплохо, но Вилсоновский мне нравится больше (за исключением работы с отрицательным рейтингом down > up).

        Что происходит при отрицательном и нулевом рейтинге в Reddit — вообще не ясно. При положительном up-down к рейтингу дата прибавляется, при нулевом не прибавляется, а при отрицательном вообще (!) вычетается (при up < down, y = -1, при up = down, y = 0). Или я что-то не правильно понял?
          +1
          >> Рейтинг не уменьшается с устареванием статей, но растет с новыми статьями

          Вот это плохо, на мой взгляд. Рейтинг позволяет сделать сортировку, но не позволяет непосредственно оценить, насколько хороша та или иная отдельная статья.

          Также непонятно, с какого потолка взята в формуле цифра 45000?

          >> В комментариях, вам нужно ставить лучшие комменты выше, вне зависимости от того, когда их отправили

          Спорный вопрос. Почему?

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

          Вот несколько мыслей об идеальном механизме рейтингования чего угодно:

          1) Рейтинг каждой сущности должен находиться в заранее заданных фиксированных пределах — например 0-5 (это позволит оценить ценность каждой отдельной сущности не сравнивая ее с другими)

          2) Рейтинг каждой сущности должен падать при появлении новых сущностей (а не с течением времени, т.к. появление новых сущностей может быть нерегулярным)

          3) Если пользователи видят оценки других пользователей, то влияние первых оценок должно быть выше влияния последующих (логарифмический спад, чтобы скомпенсировать стадный инстинкт)

          4) Если оценка сущности сопровождается комментарием — то оценка должна быть числовой, например 0-5 (т.к. человек, написавший комментарий способен на более тщательный анализ сущности, чем просто «Хорошо/Плохо»).

          5) Если оценка не сопровождается комментарием — то «Плюс/Минус».

          6) Числовые оценки, сопровождаемые комментарием должны влиять на рейтинг сильнее, чем бездумные плюсы/минусы (для простоты можно отказаться от одного из типов оценок).

          7) Рейтинг сущности должен рассчитываться и отображаться после первой оценки, поставленной сущности, но с поправкой на малое количество оценок (малое количество пятерок дает меньший рейтинг, чем большое количество пятерок).

          8) За одну сущность один пользователь может голосовать только один раз
            0
            Поправлюсь:

            2) Рейтинг каждой сущности должен падать при добавлении новых ОЦЕНОК другим сущностям (для компенсации эффекта «богатые богатеют»).
              0
              > Вот это плохо, на мой взгляд. Рейтинг позволяет сделать сортировку, но не позволяет непосредственно оценить, насколько хороша та или иная отдельная статья.
              Как я и сказал в статье, рейтингом мы называли сортировочный рейтинг. Если нужен человеко-понятный рейтинг — можно показать upvotes-downvotes, если же нужно что-то более крутое, надо вести лог всех плюсов и минусов — потом можно хоть графики строить, хоть пересчитывать рейтинг какими-то очень сложными формулами.
              45000 видимо, как обычно, была подобрана опытным путем.

              > >> В комментариях, вам нужно ставить лучшие комменты выше, вне зависимости от того, когда их отправили
              >
              > Спорный вопрос. Почему?
              Ну как почему, вы вероятно не были на реддите. В любом случае — это вопрос концепции, не реализации.

              > 1) Рейтинг каждой сущности должен находиться в заранее заданных фиксированных пределах — например 0-5 (это позволит оценить ценность каждой отдельной сущности не сравнивая ее с другими)
              это имеет свои плюсы конечно, но и минусы. и, как мы видим, сейчас все выбирают наоборот неограниченный рейтинг.

              > 2) Рейтинг каждой сущности должен падать при появлении новых сущностей (а не с течением времени, т.к. появление новых сущностей может быть нерегулярным)
              Это звучит конечно логично, но на деле, я не вижу причин, по которым следует так сделать. С подсчетом новых сущностей будут явно проблемы, и это явно сложнее, чем разница между переменной и константой.

              > 4) Если оценка сущности сопровождается комментарием — то оценка должна быть числовой, например 0-5 (т.к. человек, написавший комментарий способен на более тщательный анализ сущности, чем просто «Хорошо/Плохо»).
              даже если я пишу комментарий к статье, я бы не хотел себя утруждать выбором между 1, 2, 3, 4 и 5. серьезно, это сложно и утомительно. Когда же я нажимаю на стрелочку вверх, я просто говорю этим — это интересно, посмотрите.

              > 6) Числовые оценки, сопровождаемые комментарием должны влиять на рейтинг сильнее, чем бездумные плюсы/минусы (для простоты можно отказаться от одного из типов оценок).
              Да, вот еще, это также зависит от кол-ва активных пользователей. На реддите их достаточно, чтобы точности «плюс-минус» системы рейтингов было достаточно.
                0
                >> Ну как почему, вы вероятно не были на реддите. В любом случае — это вопрос концепции, не реализации

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

                >>Рейтинг каждой сущности должен находиться в заранее заданных фиксированных пределах
                >> это имеет свои плюсы конечно, но и минусы. и, как мы видим, сейчас все выбирают наоборот неограниченный рейтинг.

                Пока не вижу никаких минусов, а плюсы вижу. У Гугла в PageRank как раз фиксированная шкала. И это довольно удобно для быстрой оценки важности сайта. А вот у Яндекса ТИЦ как раз неудобен, т.к. эта цифра не говорит ни о чем.

                >> Это звучит конечно логично, но на деле, я не вижу причин, по которым следует так сделать. С подсчетом новых сущностей будут явно проблемы, и это явно сложнее, чем разница между переменной и константой.

                То, что это сложнее — не вызывает сомнения. Но этот вариант точнее и адекватнее реальности. Если уж искать оптимальный алгоритм расчет рейтинга — то сложность расчетов не должна нас останавливать.

                >> даже если я пишу комментарий к статье, я бы не хотел себя утруждать выбором между 1, 2, 3, 4 и 5. серьезно, это сложно и утомительно. Когда же я нажимаю на стрелочку вверх, я просто говорю этим — это интересно, посмотрите.

                Если человек пишет комментарий — он УЖЕ себя утруждает этим. И дополнительно напрячься, чтобы выбрать одну цифру — это не проблема. Кроме того, написание комментария, это уже сама по себе рекомендация «это интересно, посмотрите». Если бы это не было интересно — то комментарий писать не стал бы.

                Цифра — это информация. Плюс/минус — это эмоция. Цифра более информативна, а значит ценнее.

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

                Да, большое количество пользователей — это добро. Десять плюсов определенно ценнее, чем 1 оценка «пять». Однако, я бы еще подумал на предмет — какая система оценок полезнее и удобнее.
                  +1
                  Ну, скажу тут одно — я не согласен, что нужен универсальный алгоритм. Точечные удары всегда эффективней, проще, быстрей и дешевле
              0
              Хорошая статья
                +1
                Всё ок, только графики, которые начинаются не с нуля — это ужасная практика.
                  0
                  Поясните, пожалуйста, пару моментов.
                  1. Если ts — положительная величина (модуль разницы во времени), то с увеличением возраста статьи, ее рейтинг будет только увеличиваться (за счет слагаемого y ts / 45000). Если же это — отрицательная переменная (мы вычитаем из даты публикации текущую дату, которая больше), то чем старее статья, тем ее рейтинг ниже, т.к. то слагаемое отрицательное и, следовательно, вычетается из log10z. Однако, представим теперь, что статья заминусована, т.е. x = U-D < 0, следовательно y = -1, следовательно правое слагаемое получается положительным, и чем статья старее, тем ее рейтинг выше?

                  2. Вы говорите, что статья, у которой U=1000, D=900 получит рейтинг чуть ниже, чем та, у которой U=100, D = 0. А почему? По формуле мы считаем только разницу x, которая в обоих случаях равна 100. И дальше везде пляшут от нее.
                    0
                    1. Выше ur001 уже заметил это, я не знаю ответа, поэтому ничего не отписал. Но думаю, что для ранкинга заминусованных реддит просто использует другой алгоритм. Дело в том, что при просмотре постов в режиме хот ранкинга заминусованных вообще не бывает, они скорее всего просто фильтруются на уровне запроса к БД. Иначе же да, посты с отрицательным score станут сортироваться в обратном порядке.
                    2. Нет, такого я не говорил, это касается только комментов, статьи сортируются без учета соотношения upvote-ов к downvote-ам
                      0
                      1. Ок, как вариант вполне возможно.
                      2. Как это не говорили, а это?
                      В итоге это выглядит так:

                      Это оказывает большое влияние на посты, которые получают много плюсов и минусов (т.н. спорные посты), они получают меньший рейтинг, чем посты только с плюсами.
                        0
                        «This has a big impact for stories that get a lot of upvotes and downvotes (e.g. controversial stories) as they will get a lower ranking than stories that just get upvotes. This could explain why kittens (and other non-controversial stories) rank so high :)»

                        Ну ошибки в переводе я не вижу, скорее всего автор имел ввиду именно ту ситуацию, что изображена на картинке (у второго поста upvote-ов больше, но он сравнялся с первым за счет downvote-ов). Хотя я могу ошибаться, если так поправьте :)
                          0
                          Ошибки в переводе нет, автор четко говорит: «stories that get a lot of upvotes and downvotes… will get a lower ranking than stories that just get upvotes». Т.е. если мы проголосуем 1000 раз вверх и 900 вниз, то рейтинг будет ниже, чем если просто 100 раз вверх, что не согласуется с описанной математикой. На графике, кстати, синяя колонка выглядит ниже. Но, скажем прямо, плохо он его нарисовал, поэтому судить по нему негоже.
                            +1
                            В общем я спросил у автора оригинальной статьи и оказалось, что он просто тупит, говоря следующее:
                            Please see this example:

                            A popular post of a cat gets 1000 up votes and 100 down votes
                            A controversial post (politics?) gets 2000 upvotes and 1500 downvotes

                            The post of a cat will rank way higher than the controversial post.

                            Козе понятно, что второй пост получает более низкий рейтинг, но не потому, что он спорный, а просто потому, что его score (x) равен 500, а у первого 900.
                      0
                      Формула Вильсона в примере переписанного кода не соответствует математической записи, которая идёт следом за кодом. Обратите внимание на то, что взято под корень. Интересно, что на момент публикации статьи ошибка в исходном файле уже была исправлена.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое