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

Zamyi · 发表于 2011-1-27 14:33

上面程序比较适合样本千万级以上抽取率10%以下。相对来说各个数大小间隔（按排序后）比较均匀，如果对此不满意，可以按一定比例随机替换部分数据。整体来说，还是借用RND来做的，如果从RND产生的原理来做，效果更好。

灰袍法师 · 发表于 2011-1-27 17:45

原帖由 lsftest 于 2011-1-27 09:35 发表
各段出的数只跟基段、位移量有关，与其它段出的数无关...

你是说如果第一段出了 1,3,7，位移量是100，那么第二段就是 101,103,107吗

这种随机性应该是不可接受的吧？

Zamyi · 发表于 2011-1-27 17:54

29楼样本取1亿以上，抽样取500万，结果出现2万多个0？只抽查其中1048575个。而且用时比40楼的稍长。

[ 本帖最后由 Zamyi 于 2011-1-27 17:57 编辑 ]

灰袍法师 · 发表于 2011-1-27 19:53

原帖由 Zamyi 于 2011-1-27 17:54 发表
29楼样本取1亿以上，抽样取500万，结果出现2万多个0？只抽查其中1048575个。而且用时比40楼的稍长。

这个问题很古怪，改为 dim i as long 就可以解决了

dim i as currency 的时候，for i=1 to 500万，i 只能累加到475万左右，所以后续的数组全为零。

shit，又是一个VBA的bug吖

我觉得应该设置一下运行条件，不然很容易导致死机，最好说明一下算法，我不知道看代码有没有理解错误。

我认为你的算法是随机决定下一个数跟前一个数的步长（随机范围是按剩余平均步长的两倍）

这样是限定了步长不可能超过两倍剩余平均值(第一个数的后续步长更加是不可能超过总体平均步长2倍)

另外在平均步长两倍以内，每个步长的出现频率一样，但这应该是不正确的。

我设置1-100选10，有时候会出现0值，1-10选1则经常出现大于10，应该还是有点小问题。

以下是一个检查不重复随机整数是否足够均匀的简单方法

生成100000到199999共10万范围，抽取五万个，然后统计 0,1,2,3,......99结尾的整数个数（完美的平均值是每种结尾都有500个）

然后计算实际生成的整数的统计结果，与完美值的差的平方值

结果发现，我29楼的算法，平方值是2万多，跟随机抽取去重复的平方值差不多

而这个算法的平方值是3万多，也许均匀度是要差一些。

当然，我也不敢说本帖所有算法都可以满足所有的统计检验，这倒是又一个值得研究一下的问题。

[ 本帖最后由灰袍法师于 2011-1-28 06:34 编辑 ]

lsftest · 发表于 2011-1-27 20:29

原帖由 灰袍法师 于 2011-1-27 17:45 发表

你是说如果第一段出了 1,3,7，位移量是100，那么第二段就是 101,103,107吗

这种随机性应该是不可接受的吧？

不是，我的意思是说：例如基段的原始顺序是：
1，2，3，4，5，6，7，8，9.。。。。。。
第一基段要出3个数，所以快速跳蚤（你说洗牌就洗牌吧）跳了3下，乱序后是：
1，3，7，4，5，6，2.。。。。。。。
出3个数，就是1，3，7了。。
第二基段可能要出5个数，这时就不必再从新生成原始基段1，2，3，4，5，6，7，8.。。。

只需继续在乱序后的1，3，7，4，5，6，2.。。。。。。。
中让跳蚤跳5次，可能变成了
3，5，2，8，6，9，14.。。。。。
取前面5个数加位移量成最终数。。。如此类推。。。

灰袍法师 · 发表于 2011-1-27 22:31

原帖由 lsftest 于 2011-1-27 20:29 发表

不是，我的意思是说：例如基段的原始顺序是：
1，2，3，4，5，6，7，8，9.。。。。。。
第一基段要出3个数，所以快速跳蚤（你说洗牌就洗牌吧）跳了3下，乱序后是：
1，3，7，4，5，6，2.。。。。。。。
出3个数 ...

哈，这个办法不错。应该是目前为止最好的算法，而且可以生成超过计算机内存能够容纳的样本数。

不过你所说的跳蚤算法，真的应该叫洗牌算法：

<<计算机程序设计艺术>>（第二卷） The Art Of Computer Programming - Volume2(By Donald.E.Knuth)

该书的英文版第二卷第三章的相关内容

Algorithm P (Shuffling).
Let Xi, X2, ...... Xt be a set of t numbers to be shuffled.

PI. [Initialize] Set j = t.
P2. [Generate U] Generate a random number U, uniformly distributed between zero and one.
P3. [Exchange] Set k = j*U + 1. ((Now A; is a random integer, between 1 and j, Exchange Xk, Xj
P4. [Decrease j] Decrease j by 1. If j > 1, return to step P2

This algorithm was first published by R. A. Fisher and F. Yates [Statistical
Tables (London, 1938), Example 12], in ordinary language, and by R. Durstenfeld
[CACM 7 A964), 420] in computer language.

1938年被提出，然后1964年被写成计算机语言

[ 本帖最后由灰袍法师于 2011-1-28 06:37 编辑 ]

lsftest · 发表于 2011-1-28 14:58

原帖由 灰袍法师 于 2011-1-27 22:31 发表

哈，这个办法不错。应该是目前为止最好的算法，而且可以生成超过计算机内存能够容纳的样本数。

不过你所说的跳蚤算法，真的应该叫洗牌算法：

（第二卷） The Art Of Computer Programming - Volume2(By Do ...

ok..ok...诸法空相。。洗牌也罢，跳蚤也罢。我们要的只是本质的东西。。。
今天又想了一想。。。是关于这个洗牌（跳蚤）算法中的一个环节。。
一般用这算法，总免不得交换，
dim c
c=a
a=b
b=c
....
但有另一种交换法不须借助第三个变量，但要运算：
a＝2
b＝3
a＝a+b
b=a-b
a=a-b
这两种方法在数据量不大的时候看不出谁优谁劣，但次数多时，究竟是交换快还是运算快？？？

Zamyi · 发表于 2011-1-29 11:13

原帖由 lsftest 于 2011-1-28 14:58 发表

ok..ok...诸法空相。。洗牌也罢，跳蚤也罢。我们要的只是本质的东西。。。
今天又想了一想。。。是关于这个洗牌（跳蚤）算法中的一个环节。。
一般用这算法，总免不得交换，
dim c
c=a
a=b
b=c
....
但有另 ...

试一下不就知道了？交换两个数据，不同数据类型用时有些差异，如果是字符串，据说是用CopyMemory 最快。另外，int(n*rnd())+min非常耗时的。

[ 本帖最后由 Zamyi 于 2011-1-29 11:14 编辑 ]

lsftest · 发表于 2011-1-29 15:27

原帖由 Zamyi 于 2011-1-29 11:13 发表

试一下不就知道了？交换两个数据，不同数据类型用时有些差异，如果是字符串，据说是用CopyMemory 最快。另外，int(n*rnd())+min非常耗时的。

呵呵，看来你试过了。。
能不能给大家展示一下你各项测试的成果？

lsftest · 发表于 2011-1-29 21:14

原帖由 Zamyi 于 2011-1-29 11:13 发表

试一下不就知道了？交换两个数据，不同数据类型用时有些差异，如果是字符串，据说是用CopyMemory 最快。另外，int(n*rnd())+min非常耗时的。

呵呵，测试的结果是，运算不如交换快。。。
Private Sub CommandButton2_Click()
Dim a As Long
Dim b As Long
Dim c As Long
Randomize
t0 = Timer
For i = 1 To 10000000
a = Int((10000000 * Rnd) + 1)
b = Int((10000000 * Rnd) + 1)
c = a
a = b
b = c
Next
MsgBox Timer - t0
End Sub

Private Sub CommandButton3_Click()
Dim a As Long
Dim b As Long
Dim c As Long
Randomize
t0 = Timer
For i = 1 To 10000000
a = Int((10000000 * Rnd) + 1)
b = Int((10000000 * Rnd) + 1)
a = a + b
b = a - b
a = a - b
Next
MsgBox Timer - t0
End Sub

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

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