生成不重复随机数的一段代码

灰袍法师 · 发表于 2011-1-24 16:23

洗牌算法（记住：不叫跳蚤算法）的弱点是占用 max-min大小的内存，
max-min＝1亿的时候当然会内存不足

Zamyi的做法减少一次交换数组元素，速度会快一点，但算法的缺点还是没有改变

而19楼用直接数组查询代替VBA字典，速度快得多，可以带来了跟洗牌算法一样的内存溢出问题，我觉得是得不偿失

总结，此两个问题仍然没有解决
1 洗牌算法很容易内存溢出 (内存需求是O(总体), 时间复杂度是O(抽样数) )
2 随机抽样－去重复，在抽样数超过总体数50％的时候效率低下
(内存需求大概是 O(抽样数*4)，而且抽样数不超过总体50%的时候，此算法最多就是O (2n) 时间复杂度 )

所以还是那句话：
要分情况分别采用两种算法，它们是互补的

内存足够，而且抽样数不是远远低于总体，就洗牌

否则，就随机抽样

附件已被作者删除，更好的附件在27楼和29楼

[ 本帖最后由灰袍法师于 2011-1-26 22:24 编辑 ]

zzaayy2010 · 发表于 2011-1-24 16:47

呵呵看不懂,看天文书样.

Zamyi · 发表于 2011-1-25 09:25

原帖由 toopoor 于 2011-1-24 16:06 发表
ZAMYI老师的代码如果max等于1亿就内存溢出了。为什么呢？

数组是直接在内存中开辟一个空间来存放数据，所以它运行非常快，但占用内在也多，Variant占16字节，1亿个就是1.6G内存，只要你的机子可用内存足够大，运行就没问题。换成long，只占4字节，400M多，在2G的机子上可以运行：
Dim a()as long, b()as long, i, Cou As Long
ReDim a(1 To Max - Min + 1)
ReDim b(n - 1)
Cou = Max - Min + 1
For i = 0 To n - 1
  t = Int(Cou * Rnd()) + 1
  If a(t) = 0Then b(i) = t Else b(i) = a(t)
  If a(Cou) = 0Then a(t) = Cou Else a(t) = a(Cou)
  Cou = Cou - 1
Next
ZRand = b

[ 本帖最后由 Zamyi 于 2011-1-25 10:03 编辑 ]

灰袍法师 · 发表于 2011-1-25 15:42

原帖由 Zamyi 于 2011-1-25 09:25 发表

数组是直接在内存中开辟一个空间来存放数据，所以它运行非常快，但占用内在也多，Variant占16字节，1亿个就是1.6G内存，只要你的机子可用内存足够大，运行就没问题。换成long，只占4字节，400M多，在2G的机子上可以 ...

所有人的电脑都肯定是找不到1.6GB连续内存的

而且换long也没有解决问题吖，如果换成2亿呢？800MB的连续内存，在绝大多数电脑都是找不到的，我的电脑4GB，但是只有760MB连续内存

Long最大存储21亿大小的数值，我觉得也不一定够用（尤其是看到楼上某位用来生成密码）

我在21楼的附件，还差一个补充的抽样算法，因为VBA字典肯定不能应付抽样数超过1000万的情况

而洗牌算法也不能应付总体数超过1亿的情况

那么如果是10亿以内的总体，随机抽1亿(内存够放样本数)，那么21楼的附件还是做不了。

[ 本帖最后由灰袍法师于 2011-1-25 15:43 编辑 ]

Zamyi · 发表于 2011-1-25 16:12

原帖由 灰袍法师 于 2011-1-25 15:42 发表

所有人的电脑都肯定是找不到1.6GB连续内存的

而且换long也没有解决问题吖，如果换成2亿呢？800MB的连续内存，在绝大多数电脑都是找不到的，我的电脑4GB，但是只有760MB连续内存

Long最大存储21亿大小的数值 ...

法师是在挑战极限了啊！请教一问题，如何查看连续内存的大小？
这让我想起为什么深蓝是用12台机一起工作的。如果真要这么做，那就用分段提取吧，10亿分成100段，每段提取约n/10，保证总数是n个，肯定比字典快。

灰袍法师 · 发表于 2011-1-25 19:10

原帖由 Zamyi 于 2011-1-25 16:12 发表

法师是在挑战极限了啊！请教一问题，如何查看连续内存的大小？
这让我想起为什么深蓝是用12台机一起工作的。如果真要这么做，那就用分段提取吧，10亿分成100段，每段提取约n/10，保证总数是n个，肯定比字典快。

确实有看看极限在哪里的意思，不然的话，一般人用你的代码处理1亿大小以内都绝对没问题的

查看连续内存大小的话，我在自己的一个需要大量内存的VBA里面就用了这样的方法

不断redim 一个很大的数组，直到成功，那么这个数组的大小就是最大的连续内存了

Function get_free_ram() As Long
'这个程序通过不断redim数组，检测电脑2GB的区域中，最大的可用连续内存块是多少
Dim mem1 As Long
Dim arr1() As Byte
Const mb = 1048576
On Error Resume Next

ReDim arr1(1)
mem1 = 2000
Do While UBound(arr1) < mb * mem1 And mem1 > 0
mem1 = mem1 - 5
ReDim arr1(1 To mb * mem1)
Loop

Erase arr1
get_free_ram = mem1
end function

[ 本帖最后由灰袍法师于 2011-1-25 22:29 编辑 ]

灰袍法师 · 发表于 2011-1-25 21:49

啊，我觉得最好的程度也就只能如附件这样了, 附件分多种情况采用不同算法，分别是：

1 随机抽样＋字典去重复，适用于
抽样的数量不多（低于200万个，且抽样比例<0.5）
或者可选数值也不多(低于5万个，这时候就不必管抽样比例了)
此算法对可选数值的范围没有任何要求，最大可以算到几十万亿选200万
但是抽样比例很高的时候就不能算，如100万选90万 (这种情况要用算法2)

2 生成全部可选数值，然后洗牌，适用于连续内存足够大，可以同时存放所有的可选数值
此算法跟算法1相反，对抽样比例没有任何要求
但是却对可选数值很多的时候不能用，耗费800MB内存，也就只能计算1亿个可选数值

3 不生成全部可选数值，而是按等概率生成需要的抽样数量，然后对抽样洗牌
此算法对抽样比例没有要求，对可选数值没有内存耗费的要求，但是要几乎要遍历所有的可选数值
所以对于1万亿范围，选1万个，就远远不如算法1了

生成算法是：
从最小的可选数值一直遍历到最大的可选数值

设定当前可选数值的出现概率 = 剩余的抽样数量 / 剩余的可选数值

如果随机数 rnd <这个概率，那么就选择此数值，否则就尝试下一个

此算法由于需要遍历所有的可选数值（注意：不需要在内存同时保存这些数值）

所以对于10亿以上的可选数值，抽样过程也会很慢。最大也就计算10亿个可选数值选择1亿吧

因为我50亿选5000万算了差不多20分钟，附图是9亿选8千万，耗时五分钟。
===========================================
综合上面三种算法，现在不能计算的情况是

100亿选200万 (算法1的字典对200万记录去重复也太慢，算法2不够内存，算法3遍历100亿也太慢，当然你不怕慢的话，算个1000亿选1亿也是可以的。。。。。。)
或者任意范围要选1亿以上 (算法1绝对不可用，算法2,3都是内存不够)
除了这样的变态要求，其余要求应该都可以在十分钟内算出来。

[ 本帖最后由灰袍法师于 2011-1-25 22:29 编辑 ]

Zamyi · 发表于 2011-1-26 10:59

原帖由 灰袍法师 于 2011-1-25 21:49 发表
啊，我觉得最好的程度也就只能如附件这样了, 附件分多种情况采用不同算法，分别是：

1 随机抽样＋字典去重复，适用于
抽样的数量不多（低于200万个，且抽样比例

50亿选5000万算了差不多20分钟，这种算法肯定不高明。我在想另外一种算法。。。

灰袍法师 · 发表于 2011-1-26 15:49

本帖最后由灰袍法师于 2012-2-5 05:14 编辑

原帖由 Zamyi 于 2011-1-26 10:59 发表
50亿选5000万算了差不多20分钟，这种算法肯定不高明。我在想另外一种算法。。。

确实如此，慢就慢在抽样的时候需要遍历所有可选数值

如果按你在上面提过的算法"分段提取，分成m段，每段提取约n/m，保证总数是n个"，那么就不需要靠随机数计算概率去抽样，速度应该可以快10倍以上。

不过还是"需要遍历所有可选数值"，这一点令人相当不爽，因为只需要n个样本，却要遍历m个可选数值。

我想，如果设计一个周期足够长的随机数生成器，那么就可以按顺序生成所有的样本，肯定没重复，连洗牌都可以省掉了。

不过要按给定范围来设计一个随机数生成器，还要保证周期比抽样数长，还要能通过统计检验，这可不大容易。

VBA字典也实在太慢了，如果换成哈希表做去重复的工作，那么速度提高几十倍，可以做到2千万左右的抽样数。

嗯。。。。。。离终极目标（任意范围一亿抽样）也不算远了。

另一个更好的方法：

把n个抽样视作求 n个大于等于1的整数，并且和值等于可选的范围

即抽样(1) = 抽样下限 + n(1)，接着抽样(i+1) = 抽样(i) + n(i+1)

这个算法的实现就非常简单和高速了,附件实现了2百万亿范围内，抽取9500万个，耗时不到3分钟。

[ 本帖最后由灰袍法师于 2011-1-27 19:56 编辑 ]

dodo2000 · 发表于 2011-1-26 16:54

用慢的算法可以测试电脑的硬件性能，辩证的看法。

		自动登录	找回密码
密码			免费注册

[原创] 生成不重复随机数的一段代码