尽可能不重复的伪随机数生成器的高效实现

wuyi8808 2008-03-08 02:09:25

加精

模仿 System.Random 提供的用户界面。可以从 System.Random 继承，也可以不。

1、尽可能不重复。含义是，Next 方法在没有达到必定会重复的时候，就不能重复。
比如，生成21-24之间(含21和24)的伪随机数，则生成前4个数不能重复，当然，第5个数不可避免会重复的。
NextDouble 方法也要求返回尽可能不重复的数，也就是说，在耗尽大于或等于 0.0 而小于 1.0 的双精度浮点数之前，不得重复。
NextBytes 方法则可以要求在数组长度小于或等于 byte.MaxValue+1 (也就是256)时，返回的数组元素不得重复。若数组长度大于256，则要求前256个元素不得重复。

2、随机性。我们知道，计算机不可能生成真正的随机序列，只能要求是伪随机序列。但我们可以要求这个序列不能有十分明显的规律，比如说，不能是等差数列、等比数列、斐波拿契数列，等等。

3、高效。要求实现尽量高效，这可能会和随机性发生矛盾。比如，是否要在内部保存已生成的序列，以判定是否重复。

以上抛砖引玉，还有很多方面都可以展开讨论。欢迎大家补充。

...全文

3432 116 打赏收藏转发到动态举报

写回复

用AI写文章

116 条回复

切换为时间正序

请发表友善的回复…

发表回复

美福种田伯 2009-05-21

打赏
举报

既然是随机数，你怎么能说是高效呢？

随机就是没有规律的，可能4次里面就有4次是重复的。

cadust 2009-03-25

打赏
举报

markOO

ThenLong 2008-06-26

打赏
举报

.,..

lion533335 2008-05-31

打赏
举报

wuyi8808 2008-04-04

打赏
举报

[Quote=引用 110 楼 wuyi8808 的回复:]
总结一下，我的实现方案：

34楼：构造函数
33楼：public override void NextBytes(byte[] buffer)
36楼：public override double NextDouble()
37楼：public override int Next()
37楼：public override int Next(int maxValue)
37楼：public override int Next(int minValue, int maxValue) // 建议使用1楼的，效率高，但要求各次调的参数相同。

[/Quote]

[Quote=引用 111 楼 shinaterry 的回复:]
给出源码, 大家完善.
[/Quote]

源码在34-37楼。

shinaterry 2008-04-04

打赏
举报

给出源码, 大家完善.

wuyi8808 2008-04-04

打赏
举报

总结一下，我的实现方案：

34楼：构造函数
33楼：public override void NextBytes(byte[] buffer)
36楼：public override double NextDouble()
37楼：public override int Next()
37楼：public override int Next(int maxValue)
37楼：public override int Next(int minValue, int maxValue) // 建议使用1楼的，效率高，但要求各次调的参数相同。

3楼(sbqcel)(100分)给出了不同的思路，值得借鉴。
41楼(lalac)(100分)给出了.NET System.Random 类的源码，很有参考价值。
50楼(zhiang75)(50分)使用Guid实现，也是一种方法，不过实现的是NextDouble()，本身就不容易重复。
77楼(kingbird_Wang)(10分)提供的网站不错。

结贴了，谢谢大家。

cch1010 2008-03-31

打赏
举报

收藏。。。

cc_net 2008-03-30

打赏
举报

MARK

badegg_niu 2008-03-29

打赏
举报

收藏先。。。

oktell 2008-03-29

打赏
举报

思路如下：
比如生成10-20的随机数。
首先生成一个，判断此数是否已经存在，若存在将此数加1，继续判断，大于20后，再从10开始判断。

hearyone 2008-03-29

打赏
举报

学习之中

abagnale 2008-03-29

打赏
举报

为什么不用hashtable 一定要next方法吗？

看看这段代码这是我调试的几个重复率最低的一个



            //generate random numbers

            Hashtable hashtable = new Hashtable();

            Random rm = new Random();

            int RmNum = strlength ;

            int j = 0;

            for (int i = 0; hashtable.Count < RmNum; i++)

            {

                int nValue = rm.Next(str.Length );

                if (!hashtable.ContainsValue(nValue) && nValue != 0)

                {

                    hashtable.Add(nValue, nValue);

                    //richTextBox1 .Text += nValue.ToString() + "\t";

                    strRan[j] = nValue.ToString();

                    j++;

                }

            }

Mr-Chen 2008-03-27

打赏
举报

限制重复就违背了随机数的概念
要是需要不重复的话，可以参考GUID的产生算法

nullpassword 2008-03-25

打赏
举报

mark

Ivony 2008-03-25

打赏
举报

[Quote=引用 82 楼 wuyi8808 的回复:]
引用 67 楼 Ivony 的回复:
在值域小数量级下可以做一个值域的全排列，然后随机抽取一个全排列作为一组随机数输出。

在大数量级下一般用循环链表来解决这个问题。

即将值域中所有值作为一个循环链表，从第一个节点开始，取一个随机数便向后推进随机个节点，输出这个节点并将其从循环链表中删除。

但是如果要在链表大小范围内抽取随机数，或许向后检索一个很大的个数的时候性能不够好，即使采用双向检索（将超过链…
[/Quote]

1、你需求不清，值域至少在某个范围内必然是固定的，否则这个问题就是毫无意义的。

2、没有认真理解链表，一个链表节点删除只需要更新其前节点指向即可。

linhl 2008-03-25