Hacker News與Reddit的算法比較

鄭昀 20101213

Hacker News是Y Combinator旗下的一個新聞頻道，屬于digg類產(chǎn)品，

SEOmoz曾經(jīng)在2008年7月隆重推出Reddit、Stumbleupon、Del.icio.us和Hacker News算法全揭秘。由此，這些知名Web2.0網(wǎng)站的算法浮出水面。谷文棟曾在2009年時如下講述了Hacker News的Ranking算法：

(p – 1) / (t + 2)^1.5

其中，
1）p 表示文章得到的投票數(shù)，之所以要使用 (p – 1)，應(yīng)該是想去掉文章提交者的那一票。
2）(t + 2)^1.5， 這個是時間因子。t 表示當(dāng)前時間與文章提交時間間隔的小時數(shù)。但為什么要加 2 之后再取 1.5 的冪，似乎就沒什么道理可言了，也許是個 trial-and-error 的結(jié)果吧。

他對“1.5”這個參數(shù)也沒有做出解釋。

Amir Salihefendic（他是Plurk、Todoist的Co-Founder）在今年10月份撰文《How Hacker News ranking algorithm works 》完整地解釋了Hacker News的Ranking算法，從中我們才得以知道那個神秘的“1.5”是什么。稍后我們還會拿這個排序規(guī)則與Reddit的排序規(guī)則做對比。

?

一、Hacker News的ranking算法

Hacker News是用Arc編寫的（Arc是Lisp的一個“方言”）開源項目，源代碼可以從 http://ycombinator.com/arc/arc3.tar 獲取。Ranking算法就寫在這個包的news.arc文件里。鑒于這種語言是未來的語言，不容易看懂，所以代碼就不貼了，光把注釋貼出來：

; Ranking

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

努力領(lǐng)會這段神諭的同時，Amir說其實本質(zhì)上執(zhí)行的ranking規(guī)則是：

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

where,
P = points of an item (and -1 is to negate submitters vote)
T = time since submission (in hours)
G = Gravity, defaults to 1.8 in news.arc

也就是說，前文所謂的莫名其妙的“1.5”，其實就是“Gravity（萬有引力）”參數(shù)，默認是1.8。p之所以減去1，就是要去掉文章提交者的那一票。

1.1.Gravity(G)和Time(T)的作用

Gravity和time對于一篇文章（即一個item）的得分有著重要影響。一般來說：

• 隨著T的增加（即時間的流逝），得分將下降，意味著更早被提交進來的文章將會得到越來越低的分數(shù)；
• 對于更早的文章，如果gravity增加，得分將會下降得更快。

（在這里要說明一下，著名的搜索引擎網(wǎng)站wolframalpha的plot語法能幫你根據(jù)公式（代入?yún)?shù)）畫圖，方便編纂文檔隨時舉例或者調(diào)整算法，超贊。）

·得分是如何取決于time的

Amir利用wolframalpha繪制了公式代入?yún)?shù)后的趨勢變化圖，如下所示（下圖訪問鏈接http://goo.gl/ddYe）：

How score is behaving over time

上圖中，定參Gravity為默認值1.8，隨著時間的流逝，文章得分都會迅速下降。你還能看出來，24小時后（即t=24時）無論你的文章得到多少投票，它依然會得到一個非常低的得分。

·得分是如何取決于gravity的

當(dāng)固定投票數(shù)，改變gravity又會如何呢？（下圖訪問鏈接http://is.gd/iJSbT）：

?

How gravity parameter behaves

可以看到gravity越大，得分下降趨勢就越快。

·Ranking規(guī)則的Python實現(xiàn)

這個得分函數(shù)就是這么簡單：

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

Amir最后說道：“最關(guān)鍵的是你要理解這個算法如何起作用，以及你如何為自己的應(yīng)用定制這個算法。”

?

相對于下面要講述的Reddit排序算法，Hacker News的Ranking算法主要區(qū)別在于引入了time since submission這個參數(shù)，這個參數(shù)是不斷變化的，從而導(dǎo)致一篇文章的得分不斷變化。而Reddit下的一篇文章得分（Rank）是不變的，越新的文章得分越高，所以排序自然可能排在最前面。

?

二、Reddit的ranking算法

Reddit 是Digg類型網(wǎng)站，曾經(jīng)在Digg 4改版引發(fā)用戶眾怒時被用戶刻意追捧，獨立訪問數(shù)暴漲50%，并刻意將reddit鏈接分享至digg，使得digg主頁充斥著對手reddit的鏈接。

谷文棟也曾于2008年12月發(fā)表過《Social Media Algorithm: Reddit》詳細地解釋了Reddit的公式及其參數(shù)構(gòu)成。2010年11月，Amir也對此作了圖文并茂的闡述：《How Reddit ranking algorithms work》。

它的公式如SEOmoz所描述的：

reddit formula

具體參數(shù)定義我就不再贅述了，可參考谷文棟或SEOmoz的文章。

Reddit也是開源的，其Python代碼可從 http://code.reddit.com/ 尋到。他們的排序算法則因為性能問題改由Pyrex實現(xiàn)（Pyrex 是一種專門設(shè)計用來編寫 Python 擴展模塊的語言。根據(jù) Pyrex Web 站點的介紹，“它被設(shè)計用來在友好易用的高級 Python 世界和凌亂的低級 C 世界之間搭建一個橋梁。”據(jù)說，“使用 Python like 的語法來編寫 Python 的 C Module ，自動翻譯成C語言代碼，進而編譯獲取C代碼的高效率。而且配合 Python 的 Distutils ，使得構(gòu)建過程簡單到了只需要 setup.py 的程度”）。

你可以點擊鏈接 http://code.reddit.com/browser/r2/r2/lib/db/sorts.py?rev=4778b17e939e119417cc5ec25b82c4e9a65621b2 查看這個“hot ranking”算法被翻譯為Python后的代碼。

reddit很強調(diào)submission time（文章提交時間）。

2.1.提交時間的作用

提交時間對于文章評級有如下作用：

• 提交時間對ranking有很大影響，新文章肯定比老文章rank值高；
• 這個得分將不會隨著時間流逝而遞減，但新文章會得到更高的得分。這與Hacker News的算法有著顯著區(qū)別。

下圖顯示了，固定Up和Down投票數(shù)的情況下，不同的提交時間，rank分值的變化：

從上圖可以看出，同樣的，隨著時間的推移，新文章的得分會逐漸超越高同樣投票數(shù)的老文章。

2.2.log函數(shù)的作用

這個“hot ranking”算法用了logarithm函數(shù)來確保最前面的投票權(quán)重大于接下來的投票。它的彎彎繞說法是這樣的：

The first 10 upvotes have the same weight as the next 100 upvotes which have the same weight as the next 1000 etc...

谷文棟是這么解釋的：

前 10 票獲得的權(quán)重，與 11 到 101 票所獲得的權(quán)重是一樣的。

圖形化的闡釋是：

?

如果不用logarithm函數(shù)，那么情況就會是這樣：

還是圖解看上去直觀吧？

2.3.反對票的作用

Reddit是少數(shù)幾個允許有反對票的Digg類型新聞聚合網(wǎng)站，Hacker News就沒有投反對票一說。

它的公式中有這么一個因子：

up_votes - down_votes

它的作用可以圖形化為：

也就是說，那些有爭議性話題的文章，得分將會比只得到贊同票的文章更低。

2.4.總結(jié)

Amir總結(jié)了一下Reddit的算法：

• Submission time（提交時間）是一個非常重要的參數(shù)，玩聚SR和RT就都是參照Reddit重視文章或熱門消息的發(fā)布時間的。
• 前10票的得分，和接下來的100票，是一樣的。這樣，得了10票的文章，就可能和得了50票的文章得分相似。
• 爭議性話題（得了很多反對票的）得分會很低。

（Amir還講了Reddit的comment ranking，有興趣可以自己去看看）

?

三、小結(jié)

就我在玩聚SR上使用Reddit排序算法的經(jīng)驗：

Hacker News的算法能夠讓老文章消失得更快，比如24小時之前的文章，基本就不會在榜單上存留。

Reddit的算法則能夠讓眾望所歸的那些優(yōu)秀文章能夠停留相當(dāng)長時間，然后隨著時間流逝，一點一點地被新的、好的文章擠下去。

Reddit的算法還有一個好處就是，當(dāng)投票數(shù)變化了，才需要去重新計算一次文章的Rank，不用管時間的流逝。

?

參考資源：

1、Amir 2010年 《How Hacker News ranking algorithm works》；

2、谷文棟 2009年 《Social Media Algorithm: Hacker News》；

3、谷文棟 2008年 《Social Media Algorithm: Reddit》；

4、SEOmoz 2008年 《Reddit, Stumbleupon, Del.icio.us and Hacker News Algorithms Exposed!》。

轉(zhuǎn)載于:https://www.cnblogs.com/zhengyun_ustc/archive/2010/12/15/amir.html

總結(jié)

以上是生活随笔為你收集整理的Hacker News与Reddit的算法比较的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。