在Google App Engine数据存储中获取不属于列表的随机实体 [英] Get a random entity in Google App Engine datastore which does not belong to a list

问题描述

我正在使用Google App Engine构建网页游戏。游戏有一个存储的用户创建的关卡列表（可能很多，并且动态地增加），并且每个用户都有他已经玩过的关卡列表。我需要随机选择一个他以前没有玩过的用户。实体的建模如下所示：

$ p $ class User（ndb.Model）：
uid = ndb.StringProperty（）
levels_played = ndb.KeyProperty（kind ='Level'，repeated = True）
$ b $ class Level（ndb.Model）：
#some stuff here


所以基本上我需要执行一个查询，给定一个 uid ，选择一个不属于相应列表 levels_played 的随机等级。什么是最有效的方法？

解决方案

没有简单的方法，因为您无法在方式将为您执行的要求。

看看这里选择随机记录的策略。

在ndb中查询随机行

就我个人而言，我会从范围键中随机选择一个id，然后获取下一个n个记录选项。然后检查获取的n条记录中的选项是否不在播放记录列表中。如果它从n条记录列表中选择一个不同的水平。

然而，即使这样，如果您有大量播放的记录，你可以快速检查一个级别是否已经被对手玩过。

你有多少级别和多少玩家合理的期望。您可能不得不在性能上取舍很多管理数据，以便在一组关卡和玩家数量增长后获得更高的性能。另外一种方法是使用分配（获得顺序标识的）级别
并构建位图。保持一个全局位图，为每个已创建的级别id设置一个位，然后为每个用户设置一个位图，设置每个位的播放级别。您可以在一个1MB blobproperty中存储大约800万个关卡。一些操作，你有一套未玩的游戏可供选择。选择一下，并获取关卡。

I am using Google App Engine to build a web game. The game has a list of stored user-created levels (which may be a lot, and dynamically increasing as well), and each user has a list of levels which he has played already. I need to randomly pick up a level for a user which he has not played before. The Entities are modeled like this:

class User(ndb.Model):
    uid = ndb.StringProperty()
    levels_played = ndb.KeyProperty(kind='Level', repeated=True)

class Level(ndb.Model):
    #some stuff here

So basically I need to perform a query which, given a uid, chooses a random Level which does not belong to the corresponding list levels_played. What would be the most efficient way to do this?

解决方案

There will be no easy way as you cannot do a join in a way that will perform for you requirement.

Have a look at the strategies here for selecting a random record.

Query random row in ndb

Personally I would go for the randomly chosen id from a range key then fetch the next n records option. And then check that the choice from the n records fetched is not in the list of played records. If it is pick a different level from that list of n records.

However even this won't scale well once you have large numbers of played records, unless you keep a binary blob of keys, that you can quickly check if a level has been played against.

How many levels and how many players do you reasonably expect to have. You will probably have to trade off performance for a lot of house keeping data to get the performance up once the set of levels and players grows.

An alternative approach would be to use allocids (to get sequential id's) for levels and build bitmaps. Maintain a global bitmap with a bit set for each level id that has been created and then a bitmap for each user setting each bit for a level played. You could store around 8million levels in a single 1MB blobproperty. A few bit operations and you have the set of unplayed games to choose from. Pick a bit, and fetch the level.

这篇关于在Google App Engine数据存储中获取不属于列表的随机实体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！