如何从 CouchDB 加载随机文档(高效且公平)?

2024-05-17

我想从存储在 CouchDB 数据库中的一组文档中加载随机文档。单据的取放方式应符合下列要求:

  • 效率:文档的查找应该高效,最重要的是加载文档的时间不能随文档总数线性增长。这意味着skip无法使用查询参数。

  • 均匀分布:选择应该是真正随机的(尽可能使用标准随机数生成器),每个文档应该有平等的被选择的机会。

在 CouchDB 中实现此功能的最佳方法是什么?


经过更多思考后,我想出了一个解决方案。为了完整起见,我将首先展示两种简单的方法并解释它们为何存在缺陷。第三种解决方案是我要采用的解决方案。

方法一:跳过

这是一个简单的解决方案:您有一个简单的视图(我们称之为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 randomview则有如下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当数据库增长时保持不变,但我没有尝试过,我觉得没有资格从理论上证明它。

如果您有更好的解决方案,我会非常感兴趣!

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

如何从 CouchDB 加载随机文档(高效且公平)? 的相关文章

  • Random.Next() 的 Actionscript 3 实现

    我想知道 AS 3 中是否有很好的 Random Next 实现 基本上想要生成一系列给定种子的随机数 有时 最小和最大限制 类似于 C System Random 类 Random random new Random return ran
  • 如何在 R 中创建循环来生成随机样本列表?

    我正在尝试创建一个循环来创建一系列包含随机样本的对象 如下所示 sample lt ceiling runif 9 min 0 max 20 这是圆形制服的示例 但它可以替换为普通 泊松或任何您想要的 因此 我构建了一个循环来自动生成各种生
  • 如何在 couchdb 视图中调用另一个视图?

    我刚刚读完 couchdb 权威指南 一书 并开始摆弄设计文档 然而有一件事我不明白 到目前为止我看到的所有例子都有些线性 Example id 1 rev name first something blue child 2 id 2 re
  • 线性同余生成器 - 如何选择种子和统计检验

    我需要做一个线性同余生成器 它将成功通过所选的统计测试 我的问题是 如何正确选择发电机的数字以及 我应该选择哪些统计检验 我想 均匀性的卡方频率测试 每代收集10 000个号码的方法 将 0 1 细分为10个相等的细分 柯尔莫哥洛夫 斯米尔
  • 如何在android中安装和使用couch db

    我应该如何在 android 中安装和使用 couch Db 我的意思是本地沙发数据库 我可以在平板电脑和模拟器中使用它 为此我必须遵循哪些步骤 我目前正在开发一个使用它的项目 有两种选择 1 couchbase android 是的 co
  • 简单 Haskell Monad - 随机数

    我正在尝试扩展代码这个帖子 https stackoverflow com questions 3944170 haskell and state 接受的答案 允许我能够基于以种子作为参数的函数 randomGen 调用 randomGen
  • 如何获取numpy.random.choice的索引? - Python

    是否可以修改 numpy random choice 函数以使其返回所选元素的索引 基本上 我想创建一个列表并随机选择元素而不进行替换 import numpy as np gt gt gt a 1 4 1 3 3 2 1 4 gt gt
  • 在MySQL中生成随机字符串

    我正在尝试使用函数在 phpmyadmin 中获取随机字符串 我有以下代码 CREATE FUNCTION randomPassword RETURNS varchar 128 BEGIN SET chars ABCDEFGHIJKLMNO
  • SQL:如何从一个表中获取另一个表中每一行的随机行数

    我有两个数据不相关的表 对于表 A 中的每一行 我想要例如表 B 中的 3 个随机行 使用光标这相当容易 但速度非常慢 那么我该如何用单个语句来表达这一点以避免 RBAR 呢 要获得 0 到 N 1 之间的随机数 可以使用 abs chec
  • C 中使用 getrandom 实现随机浮点数

    我试图生成一个介于 0 和 1 之间的随机浮点数 无论是在 0 1 还是 0 1 对我来说都不重要 网上关于此的每个问题似乎都涉及rand 呼叫 播种time NULL 但我希望能够每秒多次调用我的程序 并每次都获得不同的随机数 这引导我找
  • pouchdb 从 couchdb 复制:非常慢

    我的 couchDB 中有一个约 10k 条目 约 30Mo 无附件 数据库 使用 Pouchdb 浏览器端 从沙发复制时 确实需要一段时间才能完成 令我惊讶的是我的沙发在此期间收到的请求数量 数千 我猜和文件一样多 这正常吗 有没有办法
  • 在三角域内生成随机位置

    我想生成x and y具有均匀分布且受限于 xmin xmax and ymin ymax 点 x y 应位于三角形内 我该如何解决这样的问题 下面是一些在平面中的任意三角形上均匀生成点的代码 import random def point
  • Java生成范围内不重复的随机数

    我想生成 1 到 4 范围内的随机数 包括 4 这是我的代码 int num r nextInt 4 1 r is instance of Random 但是 我在循环中运行上述代码 并且不想重复随机数 现在发生的事情我经常得到 1 1 1
  • 以概率从列表中选择随机元素

    我有一个包含四个项目 A B C D 的列表 每个项目都有被选择的概率 例如 A 有 74 的机会被选中 B 15 C 7 D 4 我想创建一个函数 根据其概率随机选择一个项目 有什么帮助吗 为您的项目定义一个类 如下所示 class It
  • 为 javascript 编写一个真正具有包容性的随机方法

    Javascript MATH 对象有一个随机方法 该方法从集合 0 1 返回 0 含 0 1 不包括 有没有办法返回一个真正随机的方法 其中包括 1 e g var rand MATH random 2 if rand gt 1 rand
  • 我可以为每个数据库创建多个集合吗?

    从 mongo 切换到 pouchdb 使用 Cloudant 我喜欢 每个用户一个数据库 的概念 但是有没有办法为每个数据库创建多个集合 表 Example Peter History Settings Friends John Hist
  • 如何使用 netlogo 生成 0.3 < X < 0.7 范围内的数字

    正如标题所示 希望生成 0 3 我目前使用 while 循环来检查随机浮点数是否在该范围内 我想知道是否有更好的方法来做到这一点 0 3 random float 0 4会给你 0 3 如果你真的不想要 0 3 我想你总是可以循环那个 我不
  • 为什么梅森扭转器比线性同余发生器更快?

    我使用 gcc C 标准库的梅森扭曲器实现进行了测试 它的性能优于线性同余发生器和 Crand 这很可能是 LCG 提升文档 http www boost org doc libs 1 58 0 doc html boost random
  • 如何导入 nano (couchdb) - typescript

    我在节点应用程序中导入和使用 nano 时遇到问题 js 方式 来自文档 是 var nano require nano http localhost 5984 我该如何用打字稿做到这一点 I tried import as Nano fr
  • Apache JMeter:在请求正文中添加随机数据

    我正在 Apache JMeter 中对我们的应用程序进行压力测试 我想到调用注册用户方法 该方法将在数据库中添加用户 但如果电子邮件已存在 则不会发生数据库操作 如何在身体数据中添加随机数 或者有其他方法可以对与数据库连接的应用程序进行压

随机推荐