Django：如何创建排行榜

Question

假设我有大约1,000,000个用户。我想知道任何一个用户的排名，以及他周围的用户是谁。用户随时都可能获得新的成就，如果他能看到自己的排名更新，那就太好了。

老实说，我想到的每种方法在时间和内存上都非常耗费。有没有什么好的主意？到目前为止，我最接近的想法是先把用户排序，然后建立一些百分位数的分组，但这样无法显示用户的确切位置。

如果这对你们这些使用django的人有帮助，这里有一些代码：

class Alias(models.Model) :
    awards = models.ManyToManyField('Award', through='Achiever')

    @property
    def points(self) :
        p = cache.get('alias_points_' + str(self.id))
        if p is not None : return p

        points = 0
        for a in self.achiever_set.all() :
            points += a.award.points * a.count

        cache.set('alias_points_' + str(self.id), points, 60 * 60) # 1 hour
        return points

class Award(MyBaseModel):
    owner_points = models.IntegerField(help_text="A non-normalized point value. Very subjective but try to be consistent. Should be proporional. 2x points = 2x effort (or skill)")
    true_points = models.FloatField(help_text="The true value of this award. Recalculated with a cron job. Based on number of people who won it", editable=False, null=True)

    @property
    def points(self) :
        if self.true_points :
            # blend true_points into real points over 30 days
            age = datetime.now() - self.created
            blend_days = 30
            if age > timedelta(days=blend_days) :
                age = timedelta(days=blend_days)
            num_days = 1.0 * age.days / blend_days
            r = self.true_points * num_days + self.owner_points * (1 - num_days)
            return int(r * 10) / 10.0

        else :
            return self.owner_points


class Achiever(MyBaseModel):
    award = models.ForeignKey(Award)
    alias = models.ForeignKey(Alias)
    count = models.IntegerField(default=1)

Answer 1

一百万听起来不算多，我会先尝试简单的方法。如果你要排序的依据是“积分”，那么这个积分就得是数据库中的一列。这样你可以通过计算比某个人积分高的人数来确定他的排名。要找和某个人积分相近的其他人，你可以查询积分更高的人，并按积分从低到高排序，限制结果的数量。

比较棘手的部分是保存积分时的计算。你需要用当前时间作为一个加成的乘数。也就是说，现在的积分需要在五天后变成小于1的积分。如果你的用户经常获得积分，你可能需要创建一个队列来处理这个负载。

Answer 2

我觉得《反恐精英》通过要求玩家达到一个最低标准来解决这个问题——你只需要准确排序前10%的玩家，或者其他类似的标准。

如果你想给所有人排序，可以考虑其实不需要完全准确：只需保留两位有效数字。假设有100万用户，你可以实时更新前100名用户的排行榜，接着把接下来的1000名用户按10的单位来排序，然后把大多数用户按1%或10%来排序。这样，你不会在一轮游戏中从第500,000名跳到第99名。

对于第500,000名上下的10个用户来说，了解他们的排名是没有意义的——因为大多数人的排名在每一轮之间会因为分布的原因而变化很大。

补充一下：看看这个SO排行榜。现在去第500页（总共2500页，大约是20%的位置）。告诉那些声望为'157'的人，他们周围的10个人也有声望'157'，这有什么意义呢？如果你的声望上升或下降1点，你的排名会瞬间跳动20名。更极端的是，现在底部的1056页（总共2538页），也就是底部42%的用户，都是声望1。如果你多得1点声望，你的排名会瞬间上升1055页。这大约是37,000名的排名提升。虽然告诉他们“你只需再得1分就能超越37,000人！”听起来很酷，但这个37,000的数字有多少位有效数字又有什么关系呢？

在你还没到达顶端之前，了解你在排行榜上的同伴是没有价值的，因为在顶端之外，数量实在是太多了。