c#随机产生不重复数组

我们现在经常在用伪随机数,比如
rand() 方法,就是一个伪随机数。什么是伪随机数呢?就是说这个随机数是人为按照一定算法出来的,具有可预测性,如果我们拿这个伪随机数作为
token,去获取重要资源,就有可能被人猜出来,别人就可能仿冒 token。

在.NET技术 C#区看到一个小问题:从1,50随机20个不重复数。

public class MyRandom { private decimal Seed { get; set; } public
MyRandom() { Seed = DateTime.Now.Millisecond; } public decimal Next() {
Seed = (Seed * 123 + 456) % 789; return Seed; } } MyRandom r = new
MyRandom(); for (int i = 0; i < 10; i++) { Response.Write(r.Next() +
“<br />”); }

问题不复杂,提问者其实已经有了自己的答案,但他似乎觉得答案不太理想。

如上,就是我随便写的一个随机数算法,虽然有待优化,但是各语言的伪随机数算法原理就是这么回事,基于一个
Seed,除了第一次
Seed 不确定外,第二次、第三次都可以推算得出结果。

图片 1ArrayList list =new
ArrayList();
图片 2int k
=0;
图片 3do
图片 4{
图片 5k =random
.Next (1,51);
图片 6if
(!list.Contains(k))
图片 7list.Add(k);
图片 8}
图片 9while
(list.Count <20);

这时有人会说,那我每次使用 Next 之前都初始化一下
Seed,这样就预测不到结果了吧?

这种方法应该说比较常规,效率也算不差了。但有没有更好的方法呢?换个思路想一想就有了下面这个方法。

的确不那么好猜了,但是我们要知道由于
Seed 初始化是基于当前时间的(目前都是类似做法),所以我们可以预测到一个范围,比如前面是毫秒,那么
Seed 无非就是 0-999 这 1000 个数,那么猜
1 次就有 1/1000 机率猜中,如果我猜得非常快,极短时间内可以猜
1000 次,那么必定会猜出来。

此方法经测试性能会有所提高,尤其是结果较大时。

这时有人会说,那我不用毫秒,用更细的纳秒,这样被猜中的机率就更小了?

publicint[]
GetRandomUnrepeatArray(int
minValue, int maxValue, int
count)
图片 10 {
图片 11 Random rnd =new
Random();
图片 12int length
= maxValue – minValue
+1;
图片 13 byte[]
keys =newbyte[length];
图片 14 rnd.NextBytes(keys);
图片 15 int[]
items =newint[length];
图片 16 for
(int i =0; i
< length; i++)
图片 17 {
图片 18 items[i] = i

是的。但是如果产生随机数,非常频繁,比如每毫秒产生
1 个,虽然我们种子用的是纳秒,被人猜中的机率也是
1/1000,同时提高猜的频率,同样很容易猜出来。

  • minValue;
    图片 19 }
    图片 20 Array.Sort(keys, items);
    图片 21 int[]
    result =newint[count];
    图片 22 Array.Copy(items, result,
    count);
    图片 23 return
    result;
    图片 24}
    图片 25

有人说,以上都是你的理论,能不能有个实例?看看一个例子吧:

和常规思路不同,不是采取先获取一个随机数再查找有无重复之后加入结果集,而是先利用 Random.NextBytes 方法得到一个随机数字节数组,然后利用 Array.Sort
的重载方法用这个随机数字节数组将顺序源数组排序为乱序,最后 Copy 出结果集。

for (int i = 0; i < 1000; i++) { Random rnd = new Random();
Response.Write(rnd.Next(0, 100).ToString() + “<br>”); }

由于只用了一个循环来为顺序源数组赋初值,只使用了简单数组类型而没有用集合或泛型集合类,利用 Random.NextBytes
方法一次获得一组随机数而不是在循环中多次调用,利用 Array.Copy
方法复制结果集。因而性能得到优化。

由于执行速度很快,new
Random() 使用的种子(即当前时间)只变过一次,所以上面试图产生
1000 个随机数,却只有 2 个不重复的数(如果你的计算机够快,可能只会产生
1 个)。

这里要注意Random.NextBytes 方法获得的数组是字节数组,其长度大于
256 时必定是有重复的,但 Array.Sort 方法的 QuickSort
算法刚好是不稳定排序,这样我们得到的排序结果刚好符合要求。

所以伪随机数安不安全,要不要用,得根据我们的应用需求、我们的产生频率、能猜多快来决定。

另外这里的随机数仅作为排序用,所以这个方法只需要改动返回类型和源数组赋初值的操作就可以输出任何简单数据类型的随机不重复数组。

那么什么是真随机数呢?计算机能不能产生呢?

其实这个例子如果用C++或别的什么语言来实现我们可以有更多的优化考虑,但.NET的优点在于让我们可以摆脱那些头痛的算法而更多的关注业务。

关于“真随机数”,要看这个定义怎么看,反正我觉得一般来说是统计学上的随机,计算机要产生这样的随机数,往往不光是用时间作
Seed,还要加入更多因素,比如噪音、温度、鼠标输入等,尽量增加随机性,但是在我看来,这也仅仅是增加了
Seed 复杂度,并没有改变本质。但是从应用级上来说,要安全得多,比如以前猜
1 亿次就有可能猜中 1 次,现在猜 1000000 亿次才有可能猜中 1 次。

最后,如果不考虑性能用泛型类尤其是排序泛型类来写代码可以更简练。

所以,不必一杆子打死,要考虑实际应用。

我们在做能自动生成试卷的考试系统时,常常需要随机生成一组不重复的题目,在.net
Framework中提供了一个专门用来产生随机数的类System.Random。

相关阅读

  对于随机数,大家都知道,计算机不可能产生完全随机的数字,所谓的随机数发生器都是通过一定的算法对事先选定的随机种子做复杂的运算,用产生的结果来近似的模拟完全随机数,
这种随机数被称作伪随机数。伪随机数是以相同的概率从一组有限的数字中选取的。所选数字并不具有完全的随机性,但是从实用的角度而言,其随机程度已足够
了。伪随机数的选择是从随机种子开始的,所以为了保证每次得到的伪随机数都足够地“随机”,随机种子的选择就显得非常重要。如果随机种子一样,那么同一个
随机数发生器产生的随机数也会一样。一般地,我们使用同系统时间有关的参数作为随机种子,这也是.net
Framework中的随机数发生器默认采用的方法。

发表评论

电子邮件地址不会被公开。 必填项已用*标注