Hacker Newsのランキングアルゴリズムの仕組み

[[83666]]

この記事では、Hacker News ウェブサイトの記事ランキングアルゴリズムの仕組みと、このアルゴリズムを独自のアプリケーションで使用する方法を紹介します。このアルゴリズムは非常にシンプルですが、人気のある記事を強調表示したり、新しい記事を選択したりする際に非常に優れたパフォーマンスを発揮します。

news.arc のコードに潜入

Hacker News は、Y Combinator の創設者 Paul Graham が作成した Lisp 方言である Arc で開発されています。 Hacker News はオープンソースであり、そのソースコードは arclanguage.org で見つけることができます。 news.arc プログラムをさらに詳しく調べると、次のようなランキングアルゴリズムのコードが見つかります。

 ; 投票数を年齢（時間）で割って重力乗します。
 ;スライダーで重力をスケールできたら面白いでしょう。 
 
 （＝重力* 1.8時間ベース* 120前方閾値* 1    
   nourl-factor* . 4軽量係数* . 3 ) 
 
 ( def frontpage-rank (s (o scorefn realscore) (o 重力 重力*))
  (* (/ (let base (- (scorefn s) 1 )
          ( if (> base 0 ) (expt base . 8 ) base))
        (expt (/ (+ (アイテムの年齢 s) 時間ベース*) 60 ) 重力))
     ( if (no ( in s!type 'story ' poll)) 1  
         (空白 s!url) nourl-factor*
         (軽量s) (最小軽量係数*
                                             (制御因子))
                                        (制御因子))))

基本的に、Hacker News が使用するランキングアルゴリズムは次のようになります。

スコア = (P-1) / (T+2)^G 
 
で、
 P = 記事が受け取った投票数（-1 は記事を投稿した人の投票が削除されることを意味します）
 T = 論文投稿から現在までの時間（時間）
 G = 重力、news.arc のデフォルト値は 1.8

ご覧のとおり、このアルゴリズムは簡単に実装できます。以下では、このアルゴリズムがどのように機能するかを見ていきます。

重み（G）と時間（T）がランキングに与える影響

重みと時間は記事のランキングスコアに大きな影響を与えます。通常、次のようになります。

T が増加すると、記事のスコアは減少します。つまり、記事が古ければ古いほど、スコアは低くなります。
重みが増すと、古い記事のスコアはより速く低下します。

このアルゴリズムを視覚化するには、Wolfram Alpha でプロットします。

スコアは時間の経過とともにどのように変化するか

時間が経つにつれてスコアが劇的に下がることがわかります。たとえば、24 時間前の記事は、投票数に関係なく、スコアが非常に低くなります。

プロットステートメント:

プロット（
    ( 30 - 1 ) / ( t + 2 ) ^ 1.8 、
    ( 60 - 1 ) / ( t + 2 ) ^ 1.8 、
    （ 200 - 1 ）/（t + 2 ）^ 1.8  
 ）ここでt = 0 .. 24

重み付けパラメータがランキングに与える影響

グラフからわかるように、重みが大きくなるにつれて、スコアは急速に低下します。

プロットステートメント:

プロット（
    (p - 1 ) / (t + 2 ) ^ 1.8 、
    (p - 1 ) / (t + 2 ) ^ 0.5 、
    (p - 1 ) / (t + 2 )^ 2.0  
 ）ここでt = 0 .. 24 、p = 10

Python言語実装

前述したように、このスコアリングアルゴリズムは簡単に実装できます。

 def calculate_score(投票、item_hour_age、重力= 1.8 ): 
    戻り値(投票 - 1 ) / pow((item_hour_age + 2 ), 重力)

重要なのは、アルゴリズムの各要素がスコアにどのように影響するかを理解し、アプリケーションでスコアをカスタマイズできるようにすることです。この記事でそれが明らかになったことを願っています。

楽しいコーディングを！

編集：

ポール・グラハムは改訂されたHNランキングアルゴリズムを共有しました。

 （＝重力* 1.8時間ベース* 120前方閾値* 1  
   nourl-factor* . 4軽量係数* . 17ギャグ係数* . 1 ) 
 
 ( def frontpage-rank (s (o scorefn realscore) (o 重力 重力*))
  (* (/ (let base (- (scorefn s) 1 )
          ( if (> base 0 ) (expt base . 8 ) base))
        (expt (/ (+ (item-age s) timebase*) 60 ) 重力))
     ( if (no ( in s!type 'story ' poll)) . 8  
         (空白の s!url) nourl-factor*
         （キーをメモしてください） 001  
                                        (* (制御因子)
                                           ( if (mem 'gag s!keys)
                                                ギャグ要素*
                                               （軽量級）
                                                軽量係数* 
                                                1 )))))