8

假设我有大约 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)
4

2 回答 2

4

我认为 Counterstrike 通过要求用户达到排名的最低门槛来解决这个问题——你只需要准确地排序前 10% 或其他什么。

如果要对每个人进行排序，请考虑不需要对它们进行完美排序：将它们排序到 2 个有效数字。拥有 100 万用户，您可以实时更新前 100 名用户的排行榜，将接下来的 1000 名用户更新到最接近的 10 位，然后将大众更新到最接近的 1% 或 10%。你不会在一轮中从 500,000 名跳到 99 名。

将 10 个用户上下文置于 500,000 的位置之上和之下是没有意义的——由于指数分布，群众的顺序将令人难以置信地从一轮到另一轮抖动。

编辑：看看SO 排行榜。现在转到2500页中的第 500 页（大约第 20 个百分位数）。告诉有代表'157'的人他们两边的10个人也有代表'157'有什么意义吗？如果您的代表上升或下降一个点，无论哪种方式，您都会跳 20 位。更极端的是，现在底部的 1056 页（共 2538 页）或底部 42% 的用户与 rep 1 并列。你得到一分，你跳了1055 页。这大约是排名增加了 37,000 人。告诉他们“如果你再得一分，你可以打败 37k 人！”可能会很酷！但是 37k 数字有多少有效数字有关系吗？

在你已经处于顶端之前，了解你在梯子上的同龄人是没有价值的，因为除了顶端之外，他们的数量是压倒性的。

于 2009-09-08T02:07:59.330 回答
0

一百万不是很多，我会先尝试简单的方法。如果 points 属性是您要排序的东西，则它需要是一个数据库列。然后，您只需计算比相关人员更高的分数即可获得排名。为了让其他人靠近相关人员，您可以查询得分较高的人，然后按升序将其限制为您想要的人数。

棘手的事情是计算保存点。您需要使用当前时间作为奖励乘数。一点现在需要在 5 天后变成一个小于 1 点的数字。如果您的用户经常获得积分，您将需要创建一个队列来处理负载。

于 2009-09-08T19:14:35.167 回答