9

我正在尝试编写一个 GQL 查询,该查询返回 N 个特定类型的随机记录。我当前的实现有效,但需要对数据存储进行 N 次调用。如果可能的话,我想对数据存储进行 1 次调用。

我目前为放入数据存储的每种类型分配一个随机数。当我查询随机记录时,我生成另一个随机数并查询记录 > rand ORDER BY asc LIMIT 1。

这可行,但是,它只返回 1 条记录,所以我需要进行 N 次查询。关于如何进行这一查询的任何想法?谢谢。

4

6 回答 6

5

“在后台”单个搜索查询调用只能从某个索引返回一组连续的行。这就是为什么一些 GQL 查询(包括任何使用 !=)扩展到多个数据存储调用的原因。

N 个独立的均匀随机选择(通常)在任何索引中都不是连续的。

QED。

您可能可以使用 memcache 来存储实体,并降低获取 N 个实体的成本。或者,如果您不介意索引中的“随机”选择靠近在一起,请在一个查询中选择一个(例如)100 个随机选择的块,然后从中随机选择 N 个。由于您有一个已经随机化的字段,因此外人不会立即看出这 N 个项目是相关的。至少,直到他们查看大量样本并注意到项目 A 和 Z 从未出现在同一组中,因为它们在随机索引中相距超过 100。如果性能允许,您可以不时重新随机化您的实体。

于 2009-07-09T16:59:10.743 回答
5

你在寻找什么样的权衡?如果您愿意忍受插入这些实体时对性能的小幅影响,您可以创建一个解决方案来快速获取其中的 N 个。

这是您需要做的:

插入实体时,请指定密钥。您想按顺序为您的实体提供密钥,从 1 开始并从那里向上。(这将需要一些努力,因为应用程序引擎没有 autoincrement() 所以你需要跟踪你在其他实体中使用的最后一个 id,我们称之为 IdGenerator)

现在,当您需要 N 个随机实体时,生成 N 个介于 1 和您生成的最后一个 id 之间的随机数(您的 IdGenerator 会知道这一点)。然后,您可以使用 N 个键按键进行批量获取,这只需要一次访问数据存储,并且比查询更快,因为键获取通常比查询更快,AFAIK。

这种方法确实需要处理一些烦人的细节:

  1. 如果您在动态中插入大量这些项目(超过几秒钟),您的 IdGenerator 可能会成为瓶颈,这将需要某种分片 IdGenerator 实现。如果所有这些数据都是预加载的,或者不是大量数据,那么您就很容易了。
  2. 您可能会发现某些 Id 实际上不再具有与之关联的实体,因为您将其删除或因为 put() 在某处失败。如果发生这种情况,您将不得不抓取另一个随机实体。(如果您想花哨并降低这种可能性,您可以将此 Id 提供给 IdGenerator 以重复使用以“填补漏洞”)

因此,问题归结为您需要这 N 个项目的速度与添加和删除它们的频率,以及一点额外的复杂性是否值得提高性能。

于 2009-07-09T18:49:10.803 回答
3

看起来唯一的方法是将随机整数值存储在每个实体的特殊属性中并对其进行查询。如果您只添加一个自动初始化的属性,这可以非常自动地完成。

不幸的是,如果您的数据存储区已经填写完毕,这将需要对所有实体进行一次处理。

这很奇怪,我知道。

于 2009-07-09T17:05:13.773 回答
1

我同意史蒂夫的回答,没有这样的方法可以在一个查询中检索 N 个随机行。

然而,即使是检索单个实体的方法通常也无法使返回结果的概率均匀分布。返回给定实体的概率取决于其随机分配的数字与下一个更高的随机数之间的差距。例如,如果分配了随机数 1,2 和 10(并且没有分配任何数字 3-9),则算法返回“2”的频率将是“1”的 8 倍。

我已经以稍微更昂贵的方式解决了这个问题。如果有人感兴趣,我很乐意分享

于 2009-12-22T23:35:11.120 回答
0

我只是有同样的问题。我决定不将 ID 分配给数据存储中已经存在的条目并这样做,因为我已经从分片计数器中获得了总数。

这从“totalcount”条目中选择“count”条目,按key排序。

    # select $count from the complete set
    numberlist = random.sample(range(0,totalcount),count)
    numberlist.sort()

    pagesize=1000

    #initbuckets
    buckets = [ [] for i in xrange(int(max(numberlist)/pagesize)+1) ]
    for k in numberlist:
        thisb = int(k/pagesize)
        buckets[thisb].append(k-(thisb*pagesize))
    logging.debug("Numbers: %s. Buckets %s",numberlist,buckets)

    #page through results.

    result = []
    baseq =  db.Query(MyEntries,keys_only=True).order("__key__")
    for b,l in enumerate(buckets):
        if len(l) > 0: 
            result += [ wq.fetch(limit=1,offset=e)[0] for e in l ]

        if b < len(buckets)-1: # not the last bucket
            lastkey  = wq.fetch(1,pagesize-1)[0]
            wq = baseq.filter("__key__ >",lastkey)

请注意,这对我来说有些复杂,而且我仍然不相信我没有过错或过错的错误。

请注意,如果 count 接近 totalcount 这可能会非常昂贵。请注意,在数百万行上,可能无法在 appengine 时间范围内完成。

于 2009-09-13T11:52:15.243 回答
-1

如果我理解正确,您需要检索 N 个随机实例。

这简单。只需使用键进行查询。并对键的列表结果执行random.choice N 次。然后通过获取键来获取结果。

keys = MyModel.all(keys_only=True)

n = 5 # 5 random instance

all_keys = list(keys)
result_keys = []

for _ in range(0,n) 
    key = random.choice(all_keys)
    all_keys.remove(key)
    result_keys.append(key)

# result_keys now contain 5 random keys.
于 2012-10-03T09:19:14.873 回答