问题思路:
1、 预先生成好所有无重复随机数并存储,按需取数;
2、 随机生成,即时比对当前所有已生成数。若存在,则重新生成。
3、 寻找一个好的无冲突的hash算法(或冲突概率较低)。
4、 按照一定的算法来生成伪随机数,要求满足一定数量级内无相似度或较低相似度。
随机就不可能不重复,故任何算法不可能实现真正的随机.只是能够在一定程度上防止高频度的碰撞及相似度,从而给外界一个随机的假像.
思路一的相关方法及问题:
事先生成1-10000000000000,然后分组打乱,重复若干次后,即可获得所有的10万亿的数据。生成13位数(10万亿)大概是2的43次方,假设我们采用4个bit位存储一个数字(满足能表达数目至少大于九的二进制最小长度),那么一个13位的数需要52bit,即约为7Byte(字节),乘以2的43次方,可以预算整个占用空间约为56TB。无论采用何种存储方式的优化,因为随机化后的相似度极低(动态规划中的邻灰度压缩算法,包括使用数据库)优化后也是TB级的数据量,故此基于此思路上实现方法均是不现实的。
思路二的相关方法及问题:
1、 数据库用生成序列做主键(由数据库来完成不重复判断),插入失败则说明此数据已存
在,方法实现简单易行。
2、排序随机生成的随机数,采用二分查找法,并插入排序队列中的合适位置。
3、人工生成红黑树(AVL),每次插入时判断是否已存在。
此三种方法均可以实现,但是从效率而言第三种方法较好,通过数据库异常来确定数据是否重复性能明显是最差的。相比第二种方法,插入采用链表明显效率更高,但是要实现二分查找的随机访问必须要使用类似数组的序列。固采用第三种红黑树的方法是效率最高的。
但是这类方法有一个共同的缺陷,当已经生成好50%以上的数据后,这颗树的查找效率是没有问题的,但是这颗树(或者数组)的大小也快接近TB级了。从这个角度来看反而不如第一种思路实现的方法简单。而且举一个例子,十个数里面如果已经取完八个不同的数据后再生成随机数,那么重复抽到已经生成的那八个数中的一个的概率就非常大了,这样分析后可以得到,每生成一个随机数,需要遍历整颗树的次数会随着树的增大而增大,这是不可以接受的。
思路三的相关方法及问题:
1、依次Hash 1-10000000000000个数字,并将结果进行冲突检测。
2、 MD5类似强Hash算法加密固定区间内的数字,如果出现相同则说明无法逆向解密。(需要采用单向唯一映射修改长度)
3、 GUID的生成方法参考。
方法一,需要存储相应的结果来进行冲突检测,类似与思路二中的方法3,存储量非常大。方法二和方法三是同一种问题,MD5加密后是生成16或者32位不重复字符,注意这里是字符(0-9a-zA-Z),而GUID随机生成的是128位的字符,故很难找到一种将16、32甚至128位映射到32位且每一位由62(10+26+26)个字符集映射到10(0-9)位的数字字符集的方法来单向映射如此大的数字集之差。
思路四的相关方法及问题:
这个思路是我们目前推荐的且易于实现。
分段链接法;
首先我们将数据划分为6+6+1,这就将我们的数据量缩小到百万级。为什么这样划分,是根据一定的时间效率和后面的链接方法决定的。
下面我们来讨论随机生成6位随机数的方法:
1000000 个数中生成 100000 位随机数花时3s。
1000000 个数中生成 500000 位随机数花时16s。
1000000 个数中生成 800000 位随机数花时43s。
1000000 个数中生成 900000 位随机数花时 > 1h。
故我们选择第三种方案。
生成的数据截图如下:
使用同样的方法再重新生成一个6位随机数。
链接方法我们采用横向邻近无关联连接法:
如图:
(此处不使用数据库笛卡尔乘积,而采用程序读取部分数据,并在数据不足时自动缓存下一部分数据)
固此方法可以得到千亿级内不重复,八十万级数据量内无相似度;(对称链接)。而且对于整个的空间消耗都符合要求。
下面是关键的数据库随机选取随机数sql脚本。
USE Job
GO
CREATE TABLE tb2(id char(6))
CREATE UNIQUE INDEX IX_tb2 ON tb2(id)
WITH IGNORE_DUP_KEY
GO
DECLARE @dt datetime
SET @dt = GETDATE()
SET NOCOUNT ON
DECLARE @row int
SET @row = 800000
WHILE @row > 0
BEGIN
RAISERROR( 'need %d rows ', 10, 1, @row) WITH
NOWAIT
SET ROWCOUNT @row
INSERT tb2 SELECT
id = RIGHT(100000000 + CONVERT(bigint,
ABS(CHECKSUM(NEWID()))), 6)
FROM syscolumns c1, sysobjects o--, syscolumns c2
SET @row = @row - @@ROWCOUNT
END
SELECT BeginDate = @dt, EndDate = GETDATE(),
Second = DATEDIFF(Second, @dt, GETDATE())
GO
SELECT COUNT(*) FROM tb2
GO
数据打乱脚本
select identity(int,1,1) as rownumber, * into tmp_tb from tb
order by NEWID();
select identity(int,1,1) as rownumber, * into tmp_tb2 from tb2 order by
NEWID();
数据合并采用程序控制:
具体合并方法见上图。要点是记录在第一表中的位置,及错开度N。
分享到:
相关推荐
VB生成不重复的随机数 我的建议是:第一步、先做一个数组,存上这35个数(可以不是连续的数,也可以是人名、字符串什么的);第二步、随机生成一个1-35之间的数,输出;第三步:把这个数和数组的第一个单元交换;第...
Java生成32位随机数,短位随机数工具类
在Struts+Spring+Mybatis基础上写的比较灵活的产生随机数,可以用到用户编号随机产生,其中验证了随机数不会重复产生。
巧用Java实现得到任意位永不重复的随机数,很经典的代码!
详细介绍了随机数生成的方法
java生成十个不重复的随机数,要求不重复
java生成16位随机数
VBA生成不重复的随机数源码.txt
VB.NET生成1-10不重复随机数.重点是生成随机数,而且不重复。
包含C#源码 关于C#中随机数生成器 生成不重复子字母组合的随机数 并保存成TXT
可以生成随机数,稍微加以修改即可生成想要的位数
生成指定随机数不重复的例子(解压,放到myeclipse即可用)
生产不重复19位随机数,测试1000000数据没重复
通过循环创建随机种子来循环生成随机数,避免了重复调用Random的Next方法产生重复随机数的问题,程序里可设置文件的保存路径和产生的随机数长度
随机生成4位数,可用于短信验证,验证码等项目
通过移位和逻辑运算,快速生成给定区间的不重复随机数。 形象地说就是随机打乱值的顺序。 发现网上其它的方法都太慢了,又刚好想到这个方法, 就传上来了。
1. 设计并实现一个随机数生成电路,每2秒随机生成一个0~999之间的数字,并在数码管上显示生成的随机数。2. 为系统设置一个复位键,复位后数码管显示“000”,2秒后再开始每2秒生成并显示随机数,要求使用按键复位。
生成1到n的随机数。 输入数字n,生成1到n的不重复随机数。
VB.NET生成不重复的随机数源程序。 VB.NET生成不重复的随机数源程序。
易语言取不重复随机数源码,取不重复随机数