shuffle（）会产生统一的结果吗？ [英] Does shuffle() produce uniform result ?

问题描述

我已经阅读了内置随机模块的源代码，random.py。

之后还阅读了关于Knuth的Wiki文章随机算法，我想知道是否

在random.py中实现的shuffle方法会产生模数

bias的结果。


推理如下：因为方法random（）只产生有限许多可能结果，我们得到模数偏差，当

可能结果的数量不能被大小整除时洗牌清单。


1. shuffle（）是否产生统一的结果？


2.如果没有，是否有快速均匀的洗牌（）在某处可用？


谢谢！


-tooru honda

Hi,

I have read the source code of the built-in random module, random.py.
After also reading Wiki article on Knuth Shuffle algorithm, I wonder if
the shuffle method implemented in random.py produces results with modulo
bias.

The reasoning is as follows: Because the method random() only produces
finitely many possible results, we get modulo bias when the number of
possible results is not divisible by the size of the shuffled list.

1. Does shuffle() produce uniform result ?

2. If not, is there a fast and uniform shuffle() available somewhere ?

Thanks !

-tooru honda

推荐答案

tooru honda写道：

tooru honda wrote:

我已经阅读了内置的源代码随机模块，random.py。

在阅读了关于Kn的Wiki文章之后在Shuffle算法中，我想知道是否

在random.py中实现的shuffle方法会产生模数

bias的结果。


推理如下：因为方法random（）只产生有限许多可能的结果，当

可能结果的数量不能被大小整除时，我们得到模偏差洗牌清单。


1. shuffle（）是否产生统一的结果？

Hi,

I have read the source code of the built-in random module, random.py.
After also reading Wiki article on Knuth Shuffle algorithm, I wonder if
the shuffle method implemented in random.py produces results with modulo
bias.

The reasoning is as follows: Because the method random() only produces
finitely many possible results, we get modulo bias when the number of
possible results is not divisible by the size of the shuffled list.

1. Does shuffle() produce uniform result ?

给出Mersenne的周期长度twister算法生成

基础随机数，它必须是一个很长的列表才能看到显着的偏见，你不觉得吗？你有没有在你打算使用的列表长度上做任何计算

？

Given the cycle length of the Mersenne twister algorithm that generates
the underlying random numbers, it would have to be a pretty long list to
see a significant bias, don''t you think? Have you done any calculations
on the length of list you propose to use?

2.如果没有，是否有快速和统一的shuffle（）在哪里可用？

2. If not, is there a fast and uniform shuffle() available somewhere ?

坦率地说，我认为你不必担心。


问候

Steve

-

Steve Holden [phone] [phone]

Holden Web LLC / Ltd < a rel =nofollowhref =http://www.holdenweb.comtarget =_ blank> http://www.holdenweb.com

Skype：holdenweb < a rel =nofollowhref =http://del.icio.us/steve.holdentarget =_ blank> http://del.icio.us/steve.holden

--------------- Asciimercial ------------------

上网：博客，镜头和互联网标签

许多服务目前提供免费注册

-----------感谢您阅读----- --------

Frankly I don''t think you need to worry.

regards
Steve
--
Steve Holden [phone] [phone]
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
--------------- Asciimercial ------------------
Get on the web: Blog, lens and tag the Internet
Many services currently offer free registration
----------- Thank You for Reading -------------

tooru honda< to ********* @ fast-mail.orgw仪式：

tooru honda <to*********@fast-mail.orgwrites:

我已经阅读了内置随机模块的源代码，

random.py。在阅读了关于Knuth Shuffle

算法的Wiki文章后，我想知道在random.py

中实现的shuffle方法是否会产生模偏差的结果。

I have read the source code of the built-in random module,
random.py. After also reading Wiki article on Knuth Shuffle
algorithm, I wonder if the shuffle method implemented in random.py
produces results with modulo bias.

它没有模数偏差，因为它没有使用modulo来产生一个

随机索引;它将浮点值乘以所需的

范围。我不确定这种方法是否产生任何可衡量的偏见。

It doesn''t have modulo bias because it doesn''t use modulo to produce a
random index; it multiplies the floating point value with the desired
range. I''m not sure if that method produces any measurable bias.

8月24日上午8:54，Hrvoje Niksic< hnik ... @ xemacs.orgwrote ：

On Aug 24, 8:54 am, Hrvoje Niksic <[e-mail]:

tooru honda< tooru_ho ... @ fast-mail.orgwrites：

tooru honda <[e-mail]:

我有阅读内置随机模块的源代码，

random.py。在阅读了关于Knuth Shuffle

算法的Wiki文章后，我想知道在random.py

中实现的shuffle方法是否会产生模偏差的结果。

I have read the source code of the built-in random module,
random.py. After also reading Wiki article on Knuth Shuffle
algorithm, I wonder if the shuffle method implemented in random.py
produces results with modulo bias.

它没有模数偏差，因为它没有使用modulo来生成

随机索引;它将浮点值乘以所需的

范围。我不确定这种方法是否会产生任何可测量的偏差。

It doesn''t have modulo bias because it doesn''t use modulo to produce a
random index; it multiplies the floating point value with the desired
range. I''m not sure if that method produces any measurable bias.

它产生的偏差水平与通过减少[0中的随机整数得到的''模偏差''

完全相同2 ** 53）。例如，

假设我们正在尝试生成0到6之间的整数x，包括
。如果n是一个随机变量，其值均匀分布在范围内（0,2 ** 53），那么：


x = n％7

将产生0,1,2和3概率（2 ** 53 // 7 + 1）/ 2 ** 53和4，

5和6概率（2 ** 53 // 7）/ 2 ** 53，而


x = floor（（n / 2 ** 53）* 7）


将产生0,1,3和5的概率（2 ** 53 // 7 + 1）/ 2 ** 53和2，

4和6概率（2 ** 53 // 7）/ 2 * 53。


无论哪种方式，你都很难找到这么小的偏见。

在比例的另一端，如果你试图在

[0,2 ** 53-2]（例如）中产生一个值，那么它看起来更糟糕了：任何一种方法，

其中一个值的出现频率是所有其他值的两倍。

但是既然现在有这么多的值，你又会遇到问题

检测到任何偏见。


Steven Holden写道：

It produces exactly the same level of bias as the ''modulo bias''
obtained by reducing a random integer in [0, 2**53). For example,
suppose we''re trying to produce an integer x in the range 0 through 6
inclusive. If n is a random variable whose values are uniformly
distributed across range(0, 2**53) then:

x = n % 7

will produce 0, 1, 2 and 3 with probability (2**53//7+1)/2**53, and 4,
5 and 6 with probability (2**53//7)/2**53, while

x = floor((n/2**53)*7)

will produce 0, 1, 3 and 5 with probability (2**53//7+1)/2**53, and 2,
4 and 6 with probability (2**53//7)/2*53.

Either way, you''d have a very hard time detecting such a tiny bias.
At the other end of the scale, if you''re trying to produce a value in
[0, 2**53-2] (for example) then it looks worse: with either method,
one of the values occurs exactly twice as often as all of the others.
But since there are now so many values, you''d again have problems
detecting any bias.

Steven Holden wrote:

坦率地说，我认为你不必担心。

Frankly I don''t think you need to worry.

他说了什么。


Mark

What he said.

Mark

这篇关于shuffle（）会产生统一的结果吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！