google-app-engine - 如何在 Google App Engine 中实现互联网高分

Question

我想为我的游戏实现互联网高分。并向玩家反馈他们的位置(不仅是前 100 名或类似的东西)。在普通的 SQL 中，它看起来像这样:

SELECT COUNT(*) FROM Scores WHERE points > :newUsersPoints

和GQL有相似之处

db.GqlQuery("SELECT * FROM Score WHERE points > :1", newUsersPoints).count()

但由于 count() 仅限于 1000，因此对我来说用处不大。您对如何实现它有什么想法吗？

我有两个

首先:

1. 使用分片计数器的想法 ( http://code.google.com/intl/pl/appengine/articles/sharding_counters.html )创建新的“表”，存储某个范围内的分数(from_points，to_points)

2. 总结上表中的所有计数器，其中 range.to_points < newUsersPoints

3. 找出有多少分数大于新分数所在范围内的分数db.GqlQuery("SELECT * FROM Score WHERE points > :1 AND points >= :2 AND points < :3", newUsersPoints, range.from_points, range.to_points).count() + sumfrom2

4. 找到新分数所在的范围并增加其计数器

5. 拆分计数器大于 1000(或 999)的范围，以便 3. 不会达到限制

6. 将新分数添加到分数表

这是相当复杂且容易出错的。在添加分数之前，我们可能会增加一些范围和超时。 (非交易)

第二个想法:

不时(每天一次？)按点对所有分数进行排序并给它们新的位置(脚本可能会超时，所以我们必须分块进行)

要找出新分数在哪个位置，我们就这样做

db.GqlQuery("SELECT * FROM Score WHERE points > :1 LIMIT 1", newUsersPoints).get().precalculated_position + 1

还有其他想法吗？

Answer 1

我已经在几个 GAE 应用程序中实现了 Ranker。它们是 Facebook 应用程序，有成千上万的人在玩。它运作良好，但就我的目的而言，它有一个很大的缺点:您需要提前声明参与者分数的最终范围。所以这很糟糕，原因有二:

1. 如果你有一场没有尽头的比赛，人们的分数可以无限攀升，你就完蛋了。

2. 在比赛开始时，当每个人都聚集在一起接近零时，ranker.py 使用的树结构效率不高。这棵树非常深，几乎没有使用它的宽度。

换句话说，ranker.py 非常适合参赛者的分数在已知值范围内以均匀方式随机分布的情况。对于其他用途，它不是最佳的。

我希望尽快开发出更通用的排名引擎。发生这种情况时肯定会更新此线程!