个人中心
文章发布
退出
作者热门文章
- html - 出于某种原因，IE8 对我的 Sass 文件中继承的 html5 CSS 不友好？
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景？
25
4
<分区>
这不是 #11766794 “What is the optimal algorithm for generating an unbiased random integer within a range?” 的副本.它的最高投票答案和接受答案都与浮点外推有关，它甚至不会产生完全统一的整数。这个问题是在询问如何快速获得统一随机整数的良好近似值，给定可服务的统一 float rand()值(value);我是在完美统一随机整数算法的背景下问这个问题的，给定一个真实的random bit generator。 (确定性或其他；问题同样适用于任何一种方式)。
具体来说，我要问的是关于效率 w/r/t 使用随机比特方面的理论最优性:给定一个随机比特流，算法是什么在给定范围内生成完全均匀的随机整数的过程中，它消耗的位数最少？
例如，CPython 3.9.0's random.randbelow 至少有一个微不足道的低效率——当调用 2 的任意幂(包括微不足道的范围)时，它会浪费一个随机位:
def randbelow(n):
"Return a random int in the range [0,n). Returns 0 if n==0."
if not n:
return 0
k = n.bit_length() # don't use (n-1) here because n can be 1
r = getrandbits(k) # 0 <= r < 2**k
while r >= n:
r = getrandbits(k)
return r
虽然通过将“not n”替换为“n <= 1”和将“n.bit_length()”替换为“(n-1).bit_length()”很容易修补，但一点分析表明它还有更多不足之处:
假设要生成一个范围在 [0, 4097) 范围内的整数: 一半 对 getrandbits(13) 的所有调用将超出该值:如果第一位和，说，第二位是高电平，无论如何它都会消耗 11 个更多位，并在看似没有消耗时丢弃它们需要。所以看起来这个算法显然不是最优的。
今晚我能在一个小时内得出的最好结果是以下算法:
def randbelow(n):
if n <= 1:
return 0
k = (n - 1).bit_length() # this is POPCNT for bignums
while True:
r = 0
for i in reversed(range(k)):
r |= getrandbits(1) << i
if r >= n:
break
else:
return r
但是，我不是数学家，仅仅因为我修复了我可以立即看到的低效问题，并不能给我任何信心，让我相信我在一个下午就立即偶然发现了最有效的方法统一整数选择算法。
例如，比特是从量子或大气 RNG 服务购买的；或作为多方协议(protocol)的一部分，其中每个单独的位生成都需要多次往返；或 an embedded device without any hardware RNG support ...无论情况如何，我只问一个直接的问题:从真正的随机比特流生成(完美)均匀随机整数的算法是最有效的相对于随机比特消耗？ (或者，如果不确定， 什么是当前最佳候选人？)
(我在这些示例中使用了 Python，因为这是我本赛季主要从事的工作，但这个问题绝不是特定于任何语言的，除非算法本身必须概括为数字超过 264.)
25
4
0
我在一本书(Interview Question)中读到这个问题，想在这里详细讨论这个问题。请点亮它。 问题如下:- 隐私和匿名化 马萨诸塞州集团保险委员会早在 1990 年代中期就有一个绝妙的主意
我最近接受了一次面试，面试官给了我一些伪代码并提出了相关问题。不幸的是，由于准备不足，我无法回答他的问题。由于时间关系，我无法向他请教该问题的解决方案。如果有人可以指导我并帮助我理解问题，以便我可以改
这是我的代码 public int getDist(Node root, int value) { if (root == null && value !=0) return
就效率而言，Strassen 算法应该停止递归并应用乘法的最佳交叉点是多少？ 我知道这与具体的实现和硬件密切相关，但对于一般情况应该有某种指南或某人的一些实验结果。 在网上搜索了一下，问了一些他们认为
我想学习一些关于分布式算法的知识，所以我正在寻找任何书籍推荐。我对理论书籍更感兴趣，因为实现只是个人喜好问题(我可能会使用 erlang(或 c#))。但另一方面，我不想对算法进行原始的数学分析。只是
我想知道你们中有多少人实现了计算机科学的“ classical algorithms ”，例如 Dijkstra's algorithm或现实世界中的数据结构(例如二叉搜索树)，而不是学术项目？ 当有
我正在解决旧编程竞赛中的一些示例问题。在这个问题中，我们得到了我们有多少调酒师以及他们知道哪些食谱的信息。制作每杯鸡尾酒需要 1 分钟，我们需要使用所有调酒师计算是否可以在 5 分钟内完成订单。 解决
关闭。这个问题是opinion-based .它目前不接受答案。 想要改进这个问题？ 更新问题，以便 editing this post 可以用事实和引用来回答它. 关闭 8 年前。 Improve
我开始学习 Nodejs，但我被困在中间的某个地方。我从 npm 安装了一个新库，它是 express -jwt ，它在运行后显示某种错误。附上代码和错误日志，请帮助我! const jwt = re
我有一个证书，其中签名算法显示“sha256rsa”，但指纹算法显示“sha1”。我的证书 SHA1/SHA2 的标识是什么？ 谢谢! 最佳答案 TL;TR:签名和指纹是完全不同的东西。对于证书的强度
我目前在我的大学学习数据结构类(class)，并且在之前的类(class)中做过一些算法分析，但这是我在之前的类(class)中遇到的最困难的部分。我们现在将在我的数据结构类(class)中学习算法分
有一个由 N 个 1x1 方格组成的区域，并且该区域的所有部分都是相连的(没有任何方格无法到达的方格)。 下面是一些面积的例子。 我想在这个区域中选择一些方块，并且两个相邻的方块不能一起选择(对角接触
我有一些多边形形状的点列表，我想将其包含在我页面上的 Google map 中。 我已经从原始数据中删除了尽可能多的不必要的多边形，现在我剩下大约 12 个，但它们非常详细以至于导致了问题。现在我的文
我目前正在实现 Marching Squares用于计算等高线曲线，我对此处提到的位移位的使用有疑问 Compose the 4 bits at the corners of the cell to
我正在尝试针对给定算法的约束满足问题实现此递归回溯函数: function BACKTRACKING-SEARCH(csp) returns solution/failure return R
是否有包含反函数的库？ 作为项目的一部分，我目前正在研究测向算法。我正在使用巴特利特相关性。在 Bartlett 相关性中，我需要将已经是 3 次矩阵乘法(包括 Hermitian 转置)的分子除以作
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎与 help center 中定义的范围内的编程无关。 . 关闭 8 年前。 Improve
问题的链接是UVA - 1394 : And There Was One . 朴素的算法是扫描整个数组并在每次迭代中标记第 k 个元素并在最后停止:这需要 O(n^2) 时间。 我搜索了一种替代算法并
COM 中创建 GUID 的函数 (CoCreateGUID) 使用“分散唯一性算法”，但我的问题是，它是什么？ 谁能解释一下？ 最佳答案 一种生成 ID 的方法，该 ID 具有一定的唯一性保证，而不
在做一个项目时我遇到了这个问题，我将在这个问题的实际领域之外重新措辞(我想我可以谈论烟花的口径和形状，但这会使理解更加复杂).我正在寻找一种(可能是近似的)算法来解决它。 我有 n 个不同大小的容器，
我是一名优秀的程序员,十分优秀！