经过更多思考后,我想出了一个解决方案。为了完整起见,我将首先展示两种简单的方法并解释它们为何存在缺陷。第三种解决方案是我要采用的解决方案。
方法一:跳过
这是一个简单的解决方案:您有一个简单的视图(我们称之为random
)带有一个地图函数,可以发出您想要从中选择的所有文档以及内置的_count
减少功能。要选择随机文档,请按照下列步骤操作:
- 查找文档总数
N
在视图中通过调用:
http://localhost:5984/db/_design/d/_view/random
- 选择随机数
0 <= i < N
- 加载
i
'文件:
http://localhost:5984/db/_design/d/_view/random?reduce=false&skip=i&limit=1
这种方法很糟糕,因为它不能很好地适应大量文档。根据“CouchDB - 权威指南”的这一部分 http://guide.couchdb.org/draft/recipes.html#slowSkip 参数只能与单位数值一起使用。
上面的解决方案必须循环通过i
归还所选文件之前。用 SQL 术语来说,它相当于全表扫描,而不是索引查找。
方法2:文档中的随机数
通过这种方法,在创建时为每个文档生成一个随机数并将其存储在文档中。示例文档:
{
_id: "4f12782c39474fd0a498126c0400708c",
rand: 0.4591819887660398,
// actual data...
}
The random
view则有如下map函数:
function(doc) {
if (doc.rand) {
emit(doc.rand, doc);
}
}
以下是选择随机文档的步骤:
- 选择一个随机数
0 <= r < 1
- 加载文档:
http://localhost:5984/db/_design/d/_view/random?startkey=r&limit=1
- 如果没有返回文件(因为
r
大于数据库中存储的最大随机数),环绕并加载第一个文档。
这非常快,第一眼看起来很棒。然而,有一个严重的缺陷:并非所有文档都有相同的被选中的机会。
在最简单的示例中,数据库中有两个文档。当我多次选择随机文档时,我希望每个文档出现一半的时间。假设文档在创建时被分配了随机数 0.2 和 0.9。所以文档 A 被选中时(r <= 0.2) or (r > 0.9)
并且当以下情况时选择文档B:0.2 < r <= 0.9
。每个文档被选中的几率不是 50%,而是 A 为 30%,B 为 70%。
您可能认为当数据库中有更多文档时情况会有所改善,但事实并非如此。文档之间的间隔变得更小,但间隔大小的变化变得更糟:想象三个文档 A、B 和 C,其随机数为 0.30001057、0.30002057 和 0.30002058(中间没有其他文档)。 B被选中的机会比C被选中的机会大1000倍。在最坏的情况下,两个文档被分配相同的随机数。那么只能找到其中一个(文档 id 较低的那个),另一个基本上是不可见的。
方法 3:1 和 2 的组合
我提出的解决方案结合了方法 2 的速度和方法 1 的公平性。如下:
与方法 2 一样,每个文档在创建时都会分配一个随机数,视图使用相同的映射函数。与方法 1 一样,我也有一个_count
减少功能。
以下是加载随机文档的步骤:
- 查找文档总数
N
在视图中通过调用:
http://localhost:5984/db/_design/d/_view/random
- 选择随机数
0 <= r < 1
- 计算随机指数:
i = floor(r*N)
我的目标是加载i
第 'th 文件(如方法 1)。假设随机数的分布或多或少是均匀的,我猜测i
'该文档的随机值约为r
.
- 查找文档数量
L
随机值低于r
:
http://localhost:5984/db/_design/d/_view/random?endkey=r
- 看看我们的猜测有多远:
s = i - L
-
if (s>=0)
http://localhost:5984/db/_design/d/_view/random?startkey=r&skip=s&limit=1&reduce=false
-
if (s<0)
http://localhost:5984/db/_design/d/_view/random?startkey=r&skip=-(s+1)&limit=1&descending=true&reduce=false
所以,诀窍是猜测分配给的随机数i
第一个文档,查找该文档,看看我们偏离了多少,然后跳过我们错过的文档数量。
即使对于大型数据库,跳过的文档数量也应该保持较小,因为猜测的准确性会随着文档数量的增加而增加。我的猜测是s
当数据库增长时保持不变,但我没有尝试过,我觉得没有资格从理论上证明它。
如果您有更好的解决方案,我会非常感兴趣!