IT技术博客大学习 共学习 共进步
全部 移动开发 后端 数据库 AI 算法 安全 DevOps 前端 设计 开发者

数学之美:Hacker News的热门排名算法

标点符 2012-07-12 23:02:51 累计浏览 5,443 次
本机暂存

    Hacker News 是一家关于计算机黑客和创业公司的社会化新闻网站,由 Paul Graham 的创业孵化器 Y Combinator 创建。与其它社会化新闻网站不同的是 Hacker News 没有踩或反对一条提交新闻的选项(不过评论还是可以被有足够 Karma 的用户投反对票,或是投支持票);只可以赞或是完全不投票。简而言之,Hacker News 允许提交任何可以被理解为“任何满足人们求知欲”的新闻。

    原图已失效

    每个新闻标题前面有一个向上的三角形,如果你觉得这个内容很好,就点击一下,投上一票。根据得票数,系统自动统计出热门文章排行榜。但是,并非得票最多的文章排在第一位,还要考虑时间因素,新文章应该比旧文章更容易得到好的排名。

    Hacker News 采用公式 (p - 1) / (t + 2)^1.5 做为排行依据(Hacker News使用Paul Graham开发的Arc语言编写,源码可以从arclanguage.org下载),其中P是投票数量,t是发表以来的时间,小时计。后来AMIX.DK 给出公式 Score = (P-1) / (T+2)^G 推广了上面的公式,Hacker News的公式变成了一个特例,其在G=1.5时的应用。历史上Hacker News有用G=1.8。

    第一个因素是得票数P

    在其他条件不变的情况下,得票越多,排名越高。从下图可以看到,有三个同时发表的帖子,得票分别为200票、60票和30票(减1后为199、59和29),分别以黄色、紫色和蓝色表示。在任一个时间点上,都是黄色曲线在最上方,蓝色曲线在最下方。

    原图已失效

    为什么是P-1?网络上的一种解释是,很多文章作者在提交的时候会给自己投上一票。其实更重要的原因是文章发布初期的投票数对排名影响非常的,仅仅是自己给自己投的一票,也占非常大的作用。

    假设P不去减去1,那公式为: p / (t + 2)^1.5

    如果一个作者发布完就给自己投票,那么文章的得分为1/(0+2)^1.5=0.3535 。假设另外一篇文章发布了8小时,那么需要多少的投票呢?x/(8+2)^1.5>0.3535 X>11.17~ 即一天前的帖子要有12票才能超过新提交的文章,这显然不合理。

    这个具体减多少还要视网络环境而定,要是换在国内,估计P-100还不够。另外如果你不期望“高投票文章”与“低投票文章差距过大,可以在得票数上加一个小于1的指数,比如(P-1)^0.8。

    第二个因素是距离发帖时间T

    在其他条件不变的情况下,越是新发表的帖子,排名越高。或者说,一个帖子的排名,会随着时间不断下降。

    从前一张图可以看到,经过24小时之后,所有帖子的得分基本上都小于1,这意味着它们都将跌到排行榜的末尾,保证了排名前列的都将是较新的内容。

    如果,用户的第一个投票是在当前,1小时,2小时获得时,这个曲线的变化是什么呢?如下图,曲线斜率从大到小分别是当前、1小时、2小时。可以看到第一个投票的作用不断弱化,其权重不断降低。

    原图已失效

    第三个因素是重力因子G

    它的数值大小决定了排名随时间下降的速度。从下图可以看到,三根曲线的其他参数都一样,G的值分别为1.5、1.8和2.0。G值越大,曲线越陡峭,排名下降得越快。

    原图已失效

    为什么G=1.5,首先,G是干嘛的。毫无疑问,G这个数字既非时间,也非评价,其实它的主要目的是控制更新频率。G的值越大,score的衰减速度越快,排行的更新越频繁。所以,确定G值需要观察系统内部投票数在时间上的分布,然后根据需要的更新频次确定G的合理取值。越火爆、用户互动越频繁的社区,为了保证排行的稳定性(不要频繁大量的刷新),G值趋向于比较低。这就是为什么Hacker News从一开始的1.8修改成1.5,过段时间可能就变成1.2了。

    拓展阅读:基于贝叶斯算法的IMDB排名

    参考文章:http://amix.dk/blog/post/19574

同分类推荐文章

  1. Four Levels Of Customer Understanding (2026-05-22 21:00:00)
  2. 除法的意义 (2026-04-12 20:52:17)
  3. 第五章:共识算法 (2026-03-18 08:00:00)

查看更多 算法 文章 →

建议继续学习

  1. 腾讯-1亿个数据取前1万大的整数-题解答 (累计阅读 10,001)
  2. 15道使用频率极高的基础算法题 (累计阅读 6,921)
  3. IMDB评分排名算法 (累计阅读 5,724)
  4. Java程序员必知的8大排序算法 (累计阅读 5,643)
  5. 深入浅出选择类排序算法(简单选择排序,堆排序) (累计阅读 4,582)
  6. Learning to rank在淘宝的应用 (累计阅读 4,504)
  7. 研发面试最常用的10大算法 (累计阅读 4,360)
  8. 排序算法 Sleep Sort (累计阅读 3,801)
  9. 基本排序算法的PHP实现 (累计阅读 3,540)
  10. 利用js排序html表格 (累计阅读 3,481)