测试输出随机 64 位浮点数的黑匣子的随机性

2024-01-10

我收到了这个面试问题,需要为其编写一个函数。我失败了。

因为这是一个电话面试问题,所以我认为我应该编写的代码实际上不需要成为完美的随机测试人员。

有任何想法吗?

如何在面试期间的 30 分钟内编写一些代码成为一名合理的随机性测试人员?

edit

本题的分布是均匀分布


由于这是一个面试问题,我认为面试官会通过两种方式进行评估:

  1. 能够理解问题的真正要求是什么。
  2. 能够想到一些可以满足这些要求的代码。

在某些情况下,这可能是一个非常好的面试问题,特别是如果面试官愿意在必要时向候选人提出问题的话。

在理解问题的要求方面,如果您知道这是一个非常困难的问题,那么会有所帮助,见证顽固测试 http://en.wikipedia.org/wiki/Diehard_tests中提到的睡衣的答案 https://stackoverflow.com/a/22917301/834521。从根本上来说,我认为候选人需要表现出对两件事的欣赏:

(a)整体分配数字应该与所需的分布相匹配(我假设在这种情况下它是统一的,但正如 @pjs 在评论中指出的那样,这个假设应该明确)。

(b)每个抽出的号码应该是独立的从之前抽出的数字中。

在电话面试中花半个小时编写一些代码,你不可能走得太远。如果我回答这个问题,我会尝试提出以下建议:

(a)要测试分布,请为浮点数提供一组相同大小的箱,并计算落入每个箱的数字。绘制直方图并观察它(绘制数据总是一个好主意)。为了扩展这一点,您可以使用卡方检验,如中所述阿米特的回答 https://stackoverflow.com/a/22916643/834521.

然而,正如评论中所讨论的,并且here http://www.cs.indiana.edu/~kapadia/project2/node14.html

卡方检验的主要问题是区间数量和大小的选择。尽管经验法则可以帮助产生良好的结果,但并没有适用于所有类型应用的灵丹妙药。

为此,柯尔莫哥洛夫-斯米尔诺夫 http://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_test可以使用测试。这个测试背后的想法是,如果你绘制了ordered数据应该非常适合完美有序的数据(称为累积分布)。对于均匀分布,完美的有序数据是一条直线:您期望数据的第 10 个百分位数为该范围的 10%,第 20 个百分位数为该范围的 20%,依此类推。因此,以编程方式,您可以对数据进行排序,根据理想值绘制它,您应该得到一条直线。您还可以应用正式的定量统计测试,该测试基于实际值和理想值之间的差异。

(b)为了测试独立性,有多种方法。自相关 http://en.wikipedia.org/wiki/Autocorrelation在不同的时间滞后是一个相当明显的问题:当时的价值有多大?t与当时的值相似t+1, 例如。这运行测试 http://en.wikipedia.org/wiki/Wald%E2%80%93Wolfowitz_runs_test另一个不错的方法是:根据所有数字是否高于或低于中位数,将它们转换为 1 或 0,然后可以使用游程长度的分布来构建统计检验。游程测试还可用于测试一个方向或另一个方向的游程,如所述here http://www.cs.indiana.edu/~kapadia/project2/node17.html and here http://www.cs.indiana.edu/~kapadia/project2/node17.html(这对于您的情况可能更有用)。只要您手头有公式,这两种方法都有相当简单的实现!

除了顽固测试之外,讨论随机数生成器的其他好来源包括here http://www.cs.indiana.edu/~kapadia/project2/node12.html and here http://www.eg.bucknell.edu/~xmeng/Course/CS6337/Note/master/node42.html.

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

测试输出随机 64 位浮点数的黑匣子的随机性 的相关文章

  • 在 C# 中创建加密随机数的最快、线程安全的方法?

    请注意 在多个线程上并行生成随机数时 加密随机数生成器不是线程安全的 使用的发电机是RNGCryptoServiceProvider它似乎重复了很长一段随机位 128 位 重现此情况的代码如下所示 缺乏使用锁来保护访问RNGCryptoSe
  • 归并排序中的递归:两次递归调用

    private void mergesort int low int high line 1 if low lt high line 2 int middle low high 2 line 3 mergesort low middle l
  • 从 1 到 20 亿,像 (23,29) 这样相差 6 的连续素数对的数量

    如何在考虑时间复杂度的情况下从 1 到 20 亿 使用任何编程语言且不使用任何外部库 找到像 23 29 这样相差 6 的连续素数对的数量 尝试过埃拉托色尼筛 但获得连续素数是一个挑战 使用了生成器 但时间复杂度非常高 代码是 def ge
  • 如何使用 python 有效地找到两个大文件的交集?

    我有两个大文件 它们的内容如下所示 134430513125296589151963957125296589 该文件包含未排序的 id 列表 某些 id 可能会在单个文件中出现多次 现在我想找到路口两个文件的一部分 这就是两个文件中都出现的
  • 欧拉项目 45

    我还不是一名熟练的程序员 但我认为这是一个有趣的问题 我想我应该尝试一下 三角形 五边形 六边形 数字由以下生成 公式 三角形 T n n n 1 2 1 3 6 10 15 五边形 P n n 3n 1 2 1 5 12 22 35 六角
  • 如何在 Unity 中对齐“轨道”或模块化对象?

    我正在开发一个简单的游戏 用户可以在其中放置不同但模块化的对象 例如 轨道 道路等 我的问题是 当将一个物体靠近另一个物体时 如何匹配和放置不同的物体 我的第一种方法是为每个模块对象创建一个隐藏的子对象 一个盒子 并将其放在可以放置其他对象
  • 滚动或滑动窗口迭代器?

    我需要一个可在序列 迭代器 生成器上迭代的滚动窗口 又名滑动窗口 默认的 Python 迭代可以被视为一种特殊情况 其中窗口长度为 1 我当前正在使用以下代码 我怎样才能更优雅和 或更有效地做到这一点 def rolling window
  • 贪心技术与穷举搜索有何不同?

    我正在为一些示例问题编写伪代码 并且我注意到贪婪技术和详尽搜索之间存在令人担忧的模式 Job 1 Job 2 Job 3 Job 4 Job 5 Person 1 9 2 7 8 Person 2 6 4 3 7 Person 3 5 8
  • 如何在 Python 中使这个随机文本生成器更加高效?

    我正在研究一个随机文本生成器 不使用马尔可夫链 目前它的工作没有太多问题 首先 这是我的代码流程 输入一个句子作为输入 这称为触发字符串 被分配给一个变量 获取触发字符串中最长的单词 在所有古腾堡计划数据库中搜索包含该单词的句子 无论大写还
  • 随机打乱 C++ 数组(每次都不同)

    我想在C 中对数组进行洗牌 并且每次运行程序时 我想要进行不同的随机洗牌 我有myArray的长度 目前我正在使用 random shuffle myArray myArray N 但这每次都会产生相同的洗牌 为了包含随机数 我尝试过 ra
  • 如何检测图像是否像素化

    之前有人在 SO 上提出过这样的问题 在Python中检测像素化图像 https stackoverflow com questions 12942365 detecting a pixelated image in python还有关于q
  • 关于逻辑/算法的想法以及如何防止线程写入 Sql Server 中的竞争

    我有以下逻辑 public void InQueueTable DataTable Table int incomingRows Table Rows Count if incomingRows gt RowsThreshold async
  • 寻找局部最小值

    下面的代码正确地找到了数组的局部最大值 但未能找到局部最小值 我已经进行了网络搜索 以找到找到最小值的最佳方法 并且根据这些搜索 我认为我正在使用下面的正确方法 但是 在几天的时间里多次检查每一行之后 下面的代码中有一些我仍然没有看到的错误
  • shell中如何从数组中随机选择一个项目

    我正在 Shell 脚本中创建一个机器人 Array with expressions expressions Ploink Poink I Need Oil Some Bytes are Missing Poink Poink Piiii
  • 生成多个随机数

    我想生成 25 个唯一的随机数并将它们列在控制台中 数字的长度应至少为 10 个字符 有什么简单的方法可以做到这一点吗 尝试将数字构建为字符串 并使用 HashSet 确保它们是唯一的 Random random new Random Ha
  • Diamond-Square 算法的平滑问题

    我正在使用菱形方形算法来生成随机地形 它工作得很好 除了我让这些大圆锥形状要么伸出或伸入地形 问题似乎在于 时不时会有一个点被设置得太高或太低 Here is a picture of the problem And it can be b
  • 在Python中确定句子中2个单词之间的邻近度

    我需要确定 Python 句子中两个单词之间的接近度 例如 在下面的句子中 the foo and the bar is foo bar 我想确定单词之间的距离foo and bar 确定之间出现的单词数foo and bar 请注意 该词
  • 逐字遍历句子

    如何逐字遍历任何给定的句子 java中有内置函数吗 我不知道如何开始 像这样的事情 String sentence Your sentence here String words sentence split s splits by whi
  • 为什么我们需要检测链表中的循环

    我看到很多关于如何检测链表中的循环的问答 但我想了解的是我们为什么要这样做 换句话说 检测链表中的循环的实际用例是什么 在现实生活中 您可能永远不需要检测链表中的循环 但是执行此操作的算法很重要 我在现实生活中多次使用它们 例如 我经常会递
  • Java生成范围内不重复的随机数

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

随机推荐