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)

- Paul Tarjan

Answer 1

我认为《反恐精英》通过要求用户达到最低门槛才能获得排名解决了这个问题——你只需要准确地排序前10%或其他比例的用户。

如果你想对所有人进行排序，考虑到你不需要完美地排序他们：按两个有效数字进行排序。有了100万用户，你可以实时更新前100名用户的排行榜，接下来的1000名用户到最近的10个，然后是大众到最近的1％或10％。你不会在一轮中从第500,000名跳到第99名。

获取第500,000名上下的10个用户的上下文是没有意义的——由于指数分布，大众的排序将在每一轮中出现极大的波动。

编辑：查看SO排行榜。现在跳转到2500页中的第500页（大约20％的百分位数）。告诉声望为“157”的人，他们旁边的10个人也声望为“157”有意义吗？如果您的声望增加或减少一点，您将向任一方向跳跃20个位置。更极端的是，现在底部的1056页（2538页中的底部42％）具有相同的声望1。如果您再获得一分，您将跳 1055页。这大约是排名上升了37,000。告诉他们“如果您再获得一分，您可以击败37k人！”可能很酷，但37k数字有多少有效数字并不重要。

在你到达顶峰之前，知道梯子上的同行没有任何价值，因为除了顶部之外，他们的数量是压倒性的。

- Dustin Getz

---

请有人把这个编辑得更清晰一些，我要去睡觉了。 - Dustin Getz

我试图通过向用户展示比他们高的人来给他们设定目标，但不要太远以至于无法达到。 - Paul Tarjan

分数分布底部的抖动非常大，即使上下浮动1分，也会使您在100万名中掉落或获得数千个名次。您应该测量您的分数分布情况。 - Dustin Getz

Answer 2

一百万并不算太多，我会先试一下简单的方法。如果需要排序的是“points”属性，那么它必须成为数据库列。然后，您可以计算大于特定人物的点数总数以获得排名。要获取与特定人物相近的其他人员，请查询分数高于他的人员并按升序排序，限制所需人数即可。

难点在于保存时计算点数。您需要使用当前时间作为奖励倍增器。一个点现在必须变成比5天后少1点的数字。如果用户经常获得积分，则需要创建队列来处理负载。

- Jason Christa