技术头条(投递你的文章)     搜索本站     邮件订阅     微信号:IT技术博客大学习
您现在的位置首页 --> 算法 --> Hacker News 排名算法工作原理

Hacker News 排名算法工作原理

浏览:3983次  出处信息

   这篇文章我要向大家介绍Hacker News网站的文章排名算法工作原理,以及如何在自己的应用里使用这种算法。这个算法非常的简单,但却在突出热门文章和遴选新文章上表现的异常优秀。

深入 news.arc 程序代码

   Hacker News是用Arc语言开发的,这是一种Lisp方言,由Y Combinator投资公司创始人Paul Graham创造。Hacker News的开源的,你可以在arclanguage.org找到它的源代码。深入发掘 news.arc 程序,你会找到这段排名算法代码,就是下面这段:

; Votes divided by the age in hours to the gravityth power.
; Would be interesting to scale gravity in a slider.

(= gravity* 1.8 timebase* 120 front-threshold* 1 
   nourl-factor* .4 lightweight-factor* .3 )

(def frontpage-rank (s (o scorefn realscore) (o gravity gravity*))
  (* (/ (let base (- (scorefn s) 1)
          (if (> base 0) (expt base .8) base))
        (expt (/ (+ (item-age s) timebase*) 60) gravity))
     (if (no (in s!type 'story 'poll))  1
         (blank s!url)                  nourl-factor*
         (lightweight s)                (min lightweight-factor* 
                                             (contro-factor s))
                                        (contro-factor s))))

   本质上,这段 Hacker News采用的排名算法的工作原理看起来大概是这个样子:

Score = (P-1) / (T+2)^G

其中,
P = 文章获得的票数( -1 是去掉文章提交人的票)
T = 从文章提交至今的时间(小时)
G = 比重,news.arc里缺省值是1.8

   正如你看到的,这个算法很容易实现。在下面的内容里,我们将会看到这个算法是如何工作的。

比重(G)和时间(T)对排名的影响

   比重和时间在文章的排名得分上有重大的影响。正常情况下如下面所述:

  • 当T增加时文章得分会下降,这就是说越老的文章分数会越底。

  • 当比重加大时,老的文章的得分会减的更快

  •    为了能视觉呈现这个算法,我们可以把它绘制到Wolfram Alpha

    得分随着时间是如何变化的

       Score 24 hours

       你可以看到,随着时间的流逝,得分骤然下降,例如,24小时前的文章的分数变的非常低——不管它获得了如何多的票数。

       Plot语句:

    plot(
        (30 - 1) / (t + 2)^1.8, 
        (60 - 1) / (t + 2)^1.8,
        (200 - 1) / (t + 2)^1.8
    ) where t=0..24

    比重参数是如何影响排名的

       Gravity effects

       图中你可以看到,比重越大,得分下降的越快。

       Plot语句:

    plot(
        (p - 1) / (t + 2)^1.8, 
        (p - 1) / (t + 2)^0.5,
        (p - 1) / (t + 2)^2.0
    ) where t=0..24, p=10

    Python语言实现

       之前已经说了,这个评分算法很容易实现:

    def calculate_score(votes, item_hour_age, gravity=1.8):
        return (votes - 1) / pow((item_hour_age+2), gravity)

       关键是要理解算法中的各个因素对评分的影响,这样你可以在你的应用中进行定制。我希望这篇文章已经向你说明了这些 :-)

       祝编程快乐!

       编辑:

       Paul Graham 分享了修正后的HN 排名算法

        (= gravity* 1.8 timebase* 120 front-threshold* 1
           nourl-factor* .4 lightweight-factor* .17 gag-factor* .1)
    
        (def frontpage-rank (s (o scorefn realscore) (o gravity gravity*))
          (* (/ (let base (- (scorefn s) 1)
                  (if (> base 0) (expt base .8) base))
                (expt (/ (+ (item-age s) timebase*) 60) gravity))
             (if (no (in s!type 'story 'poll))  .8
                 (blank s!url)                  nourl-factor*
                 (mem 'bury s!keys)             .001
                                                (* (contro-factor s)
                                                   (if (mem 'gag s!keys)
                                                        gag-factor*
                                                       (lightweight s)
                                                        lightweight-factor*
                                                       1)))))

       :)

       


本文由外刊IT评论网(www.aqee.net)原创发表,文章地址:Hacker News 排名算法工作原理,[英文原文:How Hacker News ranking algorithm works ]


觉得文章有用?立即: 和朋友一起 共学习 共进步!

建议继续学习:

  1. 数学之美:StackOverflow问答排名算法    (阅读:9196)
  2. 用skip list实现实时排名?    (阅读:4441)
  3. 数学之美:Reddit评论排名算法    (阅读:3887)
  4. IMDB评分排名算法    (阅读:3483)
  5. 数学之美:Hacker News的热门排名算法    (阅读:3327)
  6. 实时排名,其实很简单    (阅读:2756)
  7. Reddit排名算法工作原理    (阅读:1460)
  8. 教你如何查询当前主流数据库及其排名?    (阅读:643)
  9. 浅谈 WHR 全历史排名    (阅读:595)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2017 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号