如何从 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 加载随机文档(高效且公平)? 的相关文章

  • Python错误代码:IndexError:索引错误列表索引超出范围

    我正在尝试用 Python 编写一个模拟赛马的函数 虽然没有获胜者 但它会清除屏幕 显示马匹列表 所有马匹的索引都从零开始 然后 在我标记的行上 代码变得混乱 我发现索引错误列表超出范围 我正在尝试随机选择一匹马 随机选择一个索引号 并将该
  • 为什么 int 数组的最大大小小于 Int32.MaxValue? [复制]

    这个问题在这里已经有答案了 虽然这篇文章说它应该有效 https stackoverflow com questions 2338778 what is the maximum length of an array in net on 64
  • VBA rand 如何使用上限和下限生成随机数?

    所以也许这是多余的 也许这就像问为什么大多数人生来就有 5 个手指 最后的简短答案总是 因为事情就是这样 而且它就是这样工作的 但我讨厌这个答案 该死的我想知道怎么做VBA 中的 Rnd 函数有效 Ms Office Excel 的 MSD
  • C# 的快速线程安全随机数生成器

    我需要在多个正在运行的线程中快速生成随机浮点数 我尝试过使用System Random 但它对于我的需求来说太慢了 并且它在多个线程中返回相同的数字 当我在单线程中运行应用程序时 它工作正常 此外 我需要确保生成的数字在 0 到 100 之
  • 如何获取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
  • Ionic/Cordova 应用程序中的身份验证

    首先 我不是专业人士 在我成为一名更好的开发人员的过程中 我试图了解需要什么以及如何完成为 Ionic Framework 应用程序创建注册 登录 大多数单页应用程序 SPA 在节点服务器上处理身份验证 该服务器还为客户端提供 HTML 就
  • SQL:如何从一个表中获取另一个表中每一行的随机行数

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

    在哪里可以找到完整的教程或文档os urandom 我需要获得一个随机 int 来从 80 个字符的字符串中选择一个字符 如果你只需要一个随机整数 你可以使用random randint a b 来自随机模块 http docs pytho
  • PouchDB - 手动管理冲突

    是否可以从客户端管理同步冲突 我的意思是 当 pouchDB 进行同步并检测到冲突时 是否可以获取 PouchDB 尝试同步的本地文档和 CouchDB 文档的最新版本 如果我可以获得这两个文档 我可以将它们显示给用户 他可以选择保留哪个版
  • pandas 中数据帧中的随机/洗牌行

    我目前正在尝试找到一种方法来按行随机化数据框中的项目 我在 pandas 中按列洗牌 排列找到了这个线程 在 pandas 中对 DataFrame 进行改组 排列 https stackoverflow com questions 157
  • 为什么随机不那么随机?

    有人可以解释一下现代编程语言 java c python javascript 如何应对随机性的限制以及这些限制 例如基于时间的种子 的起源 即 如果它们是由底层操作系统和基于英特尔的硬件强加的 基本上我想了解为什么没有适当的硬件就没有真正
  • shell中如何从数组中随机选择一个项目

    我正在 Shell 脚本中创建一个机器人 Array with expressions expressions Ploink Poink I Need Oil Some Bytes are Missing Poink Poink Piiii
  • Java生成范围内不重复的随机数

    我想生成 1 到 4 范围内的随机数 包括 4 这是我的代码 int num r nextInt 4 1 r is instance of Random 但是 我在循环中运行上述代码 并且不想重复随机数 现在发生的事情我经常得到 1 1 1
  • 在 JavaScript 中使用随机数创建长度为 n 的数组

    跟进这个答案 https stackoverflow com a 34693778 1525840为了创建指定长度的数组 我执行了以下命令以获得相应的结果 但填充了随机数 而不是零 var randoms Array 4 fill Math
  • 生成总和恒定的随机数

    我在想是否有办法生成一组随机数 其总和始终是一个常数 例如 20 可以分为 5 个数字 1 2 3 4 10 我不在乎这 5 个数字分别是什么 只要它们的总和等于 20 有没有办法以编程方式执行此操作 为了获得均匀分布 技巧是将总和视为一条
  • C# 中的 Bouncy Castle SecureRandom 线程安全吗?

    答案显然是yes https stackoverflow com a 1461624 1709587对于Java中的实现 但是怎么样Org BouncyCastle Security SecureRandom in C 因为据我所知 没有
  • 来自数据类型的 Haskell 随机数

    我对 Haskell 还很陌生 我有一个数据类型 data Sentence Prop Int No Sentence And Sentence Or Sentence deriving Eq 我已经为它写了一个 Show 实例 然而 无论
  • 为什么我在这段代码中不断得到两个相同的随机值? [复制]

    这个问题在这里已经有答案了 可能的重复 为什么我的随机数生成器在 C 中不是随机的 https stackoverflow com questions 932520 why does it appear that my random num
  • mySQL 返回可能有重复项的随机行

    我正在尝试随机化一定数量的行 但假设数据库中只有 4 行 而我需要获得 6 个随机行 我希望有可能 即使表中有超过 6 行 产生重复的行行 这在 mySQL 中很容易实现吗 我当前的查询是这样的 SELECT FROM winners OR
  • 枚举上的 random.choice

    我想用random choice on an Enum I tried class Foo Enum a 0 b 1 c 2 bar random choice Foo 但是这段代码失败了KeyError 我怎样才能随机选择一个成员Enum

随机推荐