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

lsftest

原帖由 灰袍法师 于 2011-1-26 15:49 发表


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

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

不过 ...

如果要真要"分段提取，分成m段，每段提取约n/m，保证总数是n个"，是不是其实就不需要分段了？只需要建一个基段，出第一组n/m个数,再出第二组同样的个数，第二组每数加上位移作最终数，再出第三组同样的个数，第三组每数加上位移×2作最终数.。。直到最后。。。
典型例子是1～10000选100，分10段取，其实是不是就可以当成
1～1000取10，出10段数（保证100个），再在每段前相应冠上0，1，2，，，，9以标识其段号就可以了？？
虽然数据足够多，范围足够广的时候，结果的确是应该呈现平均分布状态，但如果说这是随机，总有点觉得别扭。。。

灰袍法师

原帖由 lsftest 于 2011-1-26 19:00 发表

如果要真要"分段提取，分成m段，每段提取约n/m，保证总数是n个"，是不是其实就不需要分段了？只需要建一个基段，出第一组n/m个数,再出第二组同样的个数，第二组每数加上位移作最终数，再出第三组同样的个数，第三组 ...

是的，你这样做更快，算法复杂度是O(n)

也如你所言，这种算法的分布太有规律了，100选10刚好每个0,1,2,3,4,5,6,7,8,9开头的数字都有且只有一个，哎。。。。。。

如果每个区段都很大（显然电脑内存足够容纳1000万的区段），那么会好得多，因为如果是10亿选1千万，那么每1亿生成1百万，可能就看不出来。

但是如果10亿选10，那么问题又来了，显然每个数字都至少相差1亿，这就很容易看出问题了。

所以我并没有把这个算法写成代码啦。。。。。。

29楼有一样快的算法，把n个抽样视作求 n个大于等于1的整数，并且和值等于可选的范围

29楼的附件实现了2百万亿范围内，抽取9500万个，耗时不到3分钟。

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

lsftest

“2百万亿范围内，抽取9500万个，耗时不到3分钟。”
这个效率应该能满足日常绝大部分应用需求了。。
看看。。。

lsftest

又想了一下分段法，或许还是可以考虑使用的，关键是要有手段打乱它分布太均匀这一缺陷，可以试试这样：仍以我上面1～10000选100为例，仍旧分段，但分多少段，随机决定，可能是2段，可能是4段，10段，可能是20段，可能是40段。。。之类。。分多少段决定了以后，并不是100个数平均分布到各个段里去出数，而是每个段出多少个数仍旧得事前随机生成决定。。例如说如果上面决定了要分20段，那么接着就是要随机生成这20段里每段会出多少数，这里可能有的段出数多，有的段出数少，甚至有些段不必出数。。直到满足100个数为止.
这样应该能大幅扰乱了原来分布太平均的状态，只是多加了这两轮随机生成，效率下降到什么程度还说不准。

灰袍法师

原帖由 lsftest 于 2011-1-26 23:41 发表
又想了一下分段法，或许还是可以考虑使用的，关键是要有手段打乱它分布太均匀这一缺陷，可以试试这样：仍以我上面1～10000选100为例，仍旧分段，但分多少段，随机决定，可能是2段，可能是4段，10段，可能是20段，可能 ...

哦，我又想了一下，分段法还是不可行，我在上面说错了。

因为洗牌算法本身只能打乱一个范围内的数值，而不能快速从巨大的范围内抽样

首先我们碰到的是内存问题，内存不能同时保存所有数值来洗牌，所以才要分段生成

但是，如同我之前的 按等概率抽样算法一样（此算法已经是毫无内存要求了）

分段抽样然后洗牌的过程，还是要遍历所有可选数值m！

按10亿选1000万，那么10亿可选数值装不进内存，所以要分段

按你的想法，要随机决定每一段出多少个数字是很简单的，假设内存每次能同时装1亿个数值

那么10亿范围就要分10段，每段生成n(i)个随机整数(i=1,2,3....10)

问题就可以变成 求10个随机数，总和等于抽样总数 1000万，然后每一亿个可选数值就抽对应的 n(i) 个即可

但是接下来的问题是：

每一亿个可选数值抽取 n(i)个，这个过程本身是 O(一亿)，因为洗牌算法先要生成所有的可选数值，然后交换 n(i)次

所以，虽然分10段可以避开内存不足，但是无法避开可选数值太大的问题

如果是 1万亿抽100万，那么光是每段都 for i=1 to 1亿，抽大约100个， 然后重复1万次，这已经必死无疑了。

其实现在最主要的问题是：

如何快速从 巨大的范围m( m大致是currency类型的范围)， 等可能性地抽取 n个 （n最大值由连续内存多少而定，80MB连续内存就可以保存n=1000万个样本）

样本抽取以后，洗牌算法可以高速把它们打乱。

但对于抽样过程来说，我目前觉得直接应用原始的洗牌算法还是不行。

关键是要生成了第一段以后，其余每段的抽样都可以从第一段的抽样当中随机变化出来，我现在没想好要怎么做这一步。

如果第一段出100个，第二段要出112个，那么如何靠之前100个随机生成这112个呢。。。。。。

29楼附件有错误，可能生成大于数值范围的数值，已改正。

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

lsftest

昨晚睡觉时又想了一下34楼贴的东西，其实只要控制好每段出数的个数是随机生成的，那么就已经保证了随机性，之前的随机决定分多少段就应该可以免了。。。

lsftest

“巨大的范围m( m大致是currency类型的范围)， 等可能性地抽取 n个 ”
分段操作能不能用递归方法细化下去？1000亿先分100段，随机决定每段出多少数，定好后，每段再分100段。。。按之前该段分好的个数再随机分到下一级去。。。如此类推。。。

[ 本帖最后由 lsftest 于 2011-1-27 09:39 编辑 ]

lsftest

倒是不太明白“关键是要生成了第一段以后，其余每段的抽样都可以从第一段的抽样当中随机变化出来，我现在没想好要怎么做这一步。如果第一段出100个，第二段要出112个，那么如何靠之前100个随机生成这112个呢。。。。。。”想说什么，既然基段已定，则各段出的数只跟基段、位移量有关，与其它段出的数无关（但打乱了的基段数可以连续使用，无需从新生成或整理，因为本来要的就是乱序，只需要在原本的乱序基段的基础上继续随机取数，调位就是了）

[ 本帖最后由 lsftest 于 2011-1-27 09:37 编辑 ]

cqr123

谢谢分享啊

Zamyi

500亿取500万11秒不到，因为内存不许，500万以上没测试：