如何使用Reddit和Hacker News排名算法？

php mysql ranking

2022-08-31 01:01:30

我最近一直在研究排名算法，特别是Reddit和Hacker News使用的算法。算法本身很简单，但我不太明白它们是如何被使用的。

我可以做的一件事是直接在SQL中实现算法，这样每次用户进入显示排名帖子的页面时，都会运行类似这样的东西：

SELECT thing1, thing2 FROM table
ORDER BY ranking_algorithm DESC
LIMIT page*20, 20

SO上有几个类似的问题，但给出的唯一答案是将排名算法放在SQL查询中。然后线程死...

将算法放在SQL查询中在较小的规模上很好，但是如果网站有大量的用户和大量的帖子呢？这意味着每次任何用户打开显示排名帖子的页面时，都将运行该查询。这不可能非常有效。

现在，Reddit和Hacker News不会将他们的排名算法作为SQL查询运行，而是分别在python和ark中运行。那么，它们是如何以及何时被使用的呢？

一种可能的解决方案是从每个帖子中获取所有相关信息，并将其存储在Web服务器上的某个数据结构中。然后对此数据结构进行排序和排序。

每当有人打开显示排名帖子的页面时，您只需转到数据结构，检索正确的帖子范围并显示它们即可。

然后，每隔半小时左右，从服务器检索最新信息，对其进行排名，排序并更新数据结构。

其他成本较低的查询，例如检索和显示特定帖子中的所有信息，或显示最新帖子（而不是得分最高的帖子），可以在每次打开相关页面时在SQL中完成。

优点是您的数据库每半小时才被命中一次（对于昂贵的排名查询）。缺点是需要复制大块数据库。

答案 1

我为视频聚合器实现了Reddit排名算法的SQL版本，如下所示：

SELECT id, title
FROM videos
ORDER BY 
    LOG10(ABS(cached_votes_total) + 1) * SIGN(cached_votes_total)   
    + (UNIX_TIMESTAMP(created_at) / 300000) DESC
LIMIT 50

每当进行新投票时，cached_votes_total都会由触发器更新。它在我们当前的网站上运行得足够快，但我计划添加一个排名值列，并使用与cached_votes_total列相同的触发器对其进行更新。优化后，对于大多数任何规模的网站来说，它应该足够快。

编辑：更多信息在SQL中的Reddit Hotness Algorithm

答案 2

Reddit使用Pyrex，排序算法是Python C扩展以提高性能。

因此，当记录更新时，您可以在SQL中执行相同的操作，pex：何时向上或向下投票。

必须转换为 SQL 引擎语法的伪代码：

function hot(ups, downs, date){
    score = ups - downs;
    order = log(max(abs(score), 1), 10);
    if (score>0){
        sign = 1;
    } else {
        if (score<0){
            sign = -1;
        } else {
            sign = 0;
        }
    }
    td = date - datetime(1970,1,1);
    seconds = td.days * 86400 + td.seconds + (float(td.microseconds) / 1000000) - 1134028003;

    return round(order + sign * seconds / 45000, 7);
}

因此，您必须在后帐表中存储起伏，下降，日期和热函数结果。然后你可以在热列中进行排序。

你可以在这里看到Reddit的源代码：http://code.reddit.com/