algorithm - 估算 Google App Engine 查询中的结果数

Question

我正在尝试估算将返回大量结果的应用引擎查询的结果总量。

为了做到这一点，我为每个实体分配了一个介于 0 和 1 之间的随机 float 。然后我执行了我想用以下 3 个设置估计总结果的查询:

 * I ordered by the random numbers that I had assigned in ascending order * I set the offset to 1000 * I fetched only one entity

然后我将为此目的分配的实体的随机值代入以下等式以估计总结果(因为我使用 1000 作为上面的偏移量，在这种情况下 OFFSET 的值将是 1000):

1 / RANDOM * OFFSET

这个想法是因为每个实体都有一个分配给它的随机数，并且我按该随机数排序，实体的随机数分配应该与结果的开始和结束相对于它的偏移量成比例(在这种情况下，1000)。

我遇到的问题是我得到的结果给了我低估。并且估计值越低，偏移量越低。我曾预计我使用的偏移量越低，估计值就越不准确，但我认为误差范围会高于和低于实际结果数。

下面的图表展示了我在说什么。如您所见，随着偏移量从 1000 增加到 5000，预测变得更加一致(准确)。但是随后预测可预测地遵循 4 部分多项式。 (y = -5E-15x4 + 7E-10x3 - 3E-05x2 + 0.3781x + 51608)。

我是不是在这里犯了一个错误，或者标准的 python 随机数生成器没有为此目的足够均匀地分配数字？

谢谢!

编辑:

原来这个问题是我的失误造成的。在程序的另一部分，我从系列的开头抓取实体，进行操作，然后重新分配随机数。这导致接近尾声的随机数分布更密集。

我进一步深入研究了这个概念，解决了问题，并在不同的查询上再次尝试(因此结果数量与上面不同)。我发现这个想法可以用来估计查询的总结果。需要注意的一件事是，“错误”对于附近的偏移量非常相似。当我在 excel 中绘制散点图时，我期望每个偏移量的预测准确度为“云”。这意味着在最开始的偏移量会产生更大、密度更低的云，随着偏移量变大，云会收敛到实际值周围非常小、密集的云。这不是发生的事情，正如您在下面的购物车中看到的那样，每个偏移量的预测有多远。我原以为会有一团团的点，​​但实际上是一条线。

这是每次偏移后的最大值图表。例如，10000 之后的任何偏移量的最大误差都小于 1%:

Answer 1

使用 GAE 时，不要尝试在读取上做大量工作更有意义 - 它是为非常快速的请求周转而构建和优化的。在这种情况下，在创建实体时维护结果计数实际上更有效。

如果您有标准查询，这相当简单 - 只需使用 sharded counter创建实体时。您可以使用 map reduce 作业对此进行播种以获得初始计数。

如果您有可能是动态的查询，这就比较困难。如果您知道可能执行的查询范围，您会希望为每个可能运行的查询创建一个计数器。

如果可能的查询范围是无限的，您可能需要考虑聚合计数器或以更有创意的方式使用它们。

如果您告诉我们您尝试运行的查询，可能会有人有更好的主意。