排序算法：Reddit
2020-10-25 # 数据算法 # 排序算法 # 数据算法 # 排序算法

一、背景

Reddit是美国最大的网上社区，它的每个贴子前面都有向上和向下的箭头，分别表示“赞成”和“反对”。用户点击进行投票，Reddit根据投票结果，计算出最新的“热点文章排行榜”

二、算法

Python代码

Reddit的程序是开源的，使用Python语言编写。排序算法的代码大致如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from datetime import datetime,timedelta
from math import log

epoch = datetime(1970,1,1)

def epoch_seconds(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):
    s = score(ups,downs)
    order = log(max(abs(s),1),10)
    sigh = 1 if s > 0 else -1 if s < 0 else 0
    seconds = epoch_seconds(date) - 1134028003
    return round(order + sigh * seconds / 45000, 7)

在网上有看到贴github上除计算hot值外还有计算争议值：

1
2
cpdef double controversy(long ups,long downs):
    return float(ups + downs) / max(abs(score(ups,downs)),1)

数据指标

1. 帖子的新旧程度t
t = 发帖时间 - 2005年12月8日7:46:43
t的单位为秒，用unix时间戳计算。一旦帖子发表，t就是固定值，不会随时间改变，而且帖子越新，t值越大
2005年12月8日应该是Reddit成立的时间

2. 赞成票与反对票的差x
x = 赞成票 - 反对票

3. 投票方向y
y是一个符号变量，表示对文章的总体看法：
如果赞成票居多，y就是+1；
如果反对票居多，y就是-1；
如果赞成票和反正票相等，y就是0

$$y = \begin{cases}1\quad(x>0)\0\quad(x=0)\-1;(x<0)\end{cases}$$

4. 帖子的受肯定（否定）的程度z
z表示赞成票与反对表之间差额的绝对值。如果对某个帖子的评价越是一边倒，z就越大；如果赞成票等于反对票，z就等于1

$$z = \begin{cases}\mid x\mid(x\neq0)\;1\quad (x=0 )\end{cases}$$

注：根据controversy函数可以看出针对高赞成高反对高争议的帖子会有争议值的计算，例如有1000赞成1000反对的帖子相比较只有2赞0反对的帖子来说排名会靠前

数据公式

结合以上几个变量，Reddit的最终得分计算公式如下：

$$Score = \log_{10}z+\frac {yt} {45000}$$

公式拆解

（一）

$$ \log_{10}z $$

该部分表示赞成票与反对票的差额z越大，得分越大

注意点：
这里用的是以10为底的对数，意味着z = 10的时候可以得1分，z = 100的时候可以得2分。也就是说前10个投票人与后90个人（甚至再后面900个投票人）的权重是一样的，即如果一个帖子特别受到欢迎，那么越到后面投赞成票，对得分越不会产生影响
当赞成票 = 反对票时，z = 1，因此这部分为0即不产生得分
（二）

$$ \frac {yt} {45000} $$

该部分表示t越大，得分越高，即新帖子的得分会高于老帖子，它起到自动将老帖子的排名往下拉的作用

分母的45000秒相当于12.5个小时，也就是说后一天的帖子会比前一天的多得2分，结合前一部分可以得出结论：如果第一天的帖子想在第二天保持原来的排名，在这一天里它的z值必须增加100倍（净赞成票增加100倍）

y的作用是产生加分或减分：
当赞成票超过反对票时，这一部分为正，起到加分作用；
当赞成票少于反对票时，这一部分为负，起到减分作用；
当两者相等时，这一部分为0
这就保证了得到大量净赞成票的文章会排在前列，赞成票与反对票相近或相等的文章会排在后面，得到净反对票的文章会排在最后

三、结论

  • 发帖时间是一个很重要的参数，通常新帖子的得分会高于老帖子
  • 得到支持票和反对票持平的争议帖子和得到票大多数为支持的帖子相比排名将为降低
PREV
2020-10-25 # 数据算法 # 排序算法 # 数据算法 # 排序算法
NEXT