智能方式生成唯一的随机数
我想生成一系列在00000001到99999999范围内的唯一随机数。
所以第一个可能是00001010,第二个可能是40002928等。
简单的方法是生成一个随机数并将其存储在数据库中,并且每次下次再次执行它并检查数据库中是否已存在该数字,如果存在,则生成一个新数据,再次检查等等。但是看起来不对,如果生成的项目数量很大,我可以重新生成一个数字100次。
有更聪明的方法吗?
编辑总是我忘了说为什么我想要这个,它可能会让事情变得更清楚,也许可以得到一个替代品,它是:我们想要为预订生成订单号,所以我们可以使用000001,000002等。但是我们不想让竞争对手知道创造了多少订单(因为它不是一个大批量的市场,我们不希望他们知道我们是在2个月后订购30还是订单100。所以我们希望拥有一个随机的订单号(但却是唯一的)
你可以构建一个包含所有可能数字的表,给记录一个’used’字段。
- 选择所有尚未“使用”的记录
- 选择1和记录计数之间的随机数(r)
- 记录号r
- 从记录中获取“随机值”
- 设置’used’标志并更新db。
这应该比选择随机数更有效,查询数据库并重复直到找不到,因为这只是为最后几个值乞求永恒。
您可以使用线性同余发生器(LCG)或线性反馈移位寄存器(LFSR)。 谷歌或维基百科了解更多信息。
使用正确的参数,两者都可以在“全周期”(或“完整周期”)的基础上运行,这样它们将在一个周期内仅生成一次“伪随机数”,并生成该范围内的所有数字。 两者都是“弱”发生器,因此对于网络摄影没有好处,但对于明显的随机性可能“足够好”。 您可能必须将周期限制在“十进制”最大值内,因为需要“二进制”周期。
更新:我应该补充一点,没有必要以任何方式预先计算或预先存储以前的值,您只需要保留先前的种子值(单个int)并计算“按需”下一个数字序列。 当然,如果需要,您可以将预先计算的数字链保存到数据库中,但这不是必需的。
如何创建一组所有可能的数字并简单地随机化订单? 然后你可以从尾巴中选择下一个数字。
每个数字在集合中只出现一次,当您想要一个新的数字时,它已经生成了,因此在您想要的时候,开销很小。 您可以在内存或您选择的数据库中执行此操作。 您只需要一个合理的锁定策略来提取下一个可用的数字。
使用伪随机数生成器。
例如 – 线性同余随机数发生器
(如果增量和n是互质的,则代码将生成从0到n-1的所有数字):
int seed = 1, increment = 3; int n = 10; int x = seed; for(int i = 0; i < n; i++) { x = (x + increment) % n; Console.WriteLine(x); }
输出:4 7 0 3 6 9 2 5 8 1
基本随机数发生器
Mersenne Twister
使用这种算法可能是合适的,虽然它的内存消耗: http : //en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle将数字中的数字从1到99999999并进行随机播放。
对于极其有限的数字大小,你不能指望任何类型的随机生成的唯一性。
您正在生成一个32位整数,而要达到唯一性,您需要一个大约128位的数字,这是GUID使用的大小,保证始终是全局唯一的。
如果您碰巧有权访问某个库,并且想要深入了解并理解该问题,请查看
计算机编程的艺术,第2卷:研究数学算法
作者:Donald E. Knuth。 第3章是关于随机数的。
你可以把你的数字放在一个集合中。 如果在生成N个数字后设置的大小太小,则生成更多。
做一些试运行。 你平均需要生成多少个数字? 尝试找出一个最佳的解决方案,以“产生太多的数字”/“经常检查重复”。 此最优值是数字M,因此在生成M个数字后,您的集合可能会包含N个唯一数字。
哦,也可以计算M:如果你需要一个额外的数字(你的集合包含N-1),那么随机数已经在集合中的几率是(N-1)/ R,其中R是范围。 我要在这里进行交叉,所以你必须自己解决这个问题(但这种东西让编程变得有趣,不是吗?)。
您可以对包含随机数的列设置唯一约束,然后通过重新生成数字来处理任何约束声音。 我认为这通常会对列进行索引,因此这会更快。
你用C#标记了这个问题,所以我猜你正在使用C#来生成随机数。 也许考虑让数据库在存储过程中生成随机数,然后返回它。
您可以尝试使用起始编号和增量编号来编写用户名。 您从一个数字(例如12000)开始,然后,对于创建的每个帐户,该数字将增加增量值。
id = startValue + (totalNumberOfAccounts * inctrementalNumber)
如果incrementalNumber是一个素数值,您应该能够绕过最大帐户值而不是另一个值。 这会产生随机id的错觉,但也应该有很少的冲突。 在发生冲突的情况下,您可以添加一个数字以在发生冲突时增加,因此上面的代码变为。 我们想要处理这种情况,因为如果我们遇到一个相同的帐户值,当我们增加时,当我们再次增加时,我们将遇到另一个冲突。
id = startValue + (totalNumberOfAccounts * inctrementalNumber) + totalConflicts
我之前必须做这样的事情(为URL的一部分创建一个“随机查找”号码)。 我所做的是创建一个随机生成的密钥列表。 每次需要一个新数字时,它只需从keys.Count中随机选择一个数字,然后输入密钥和给定的序列号,然后输出前缀值(在基数62中),前缀为键索引(在基数62中)。 我还检查输出以确保它不包含任何无效的单词。 如果它只是采取下一个键,并有第二个去。 解密数字同样简单(第一个数字是要使用的键的索引,一个简单的XOR,你就完成了)。
我喜欢andora的答案,如果你正在生成新的数字,并且可能已经使用了我已知的。 但是,如果我再次这样做,我会简单地使用UUID 。 大多数(如果不是每个)平台都有一个生成它们的方法,长度不是URL的问题。
您可以尝试改组可能的值集合,然后依次使用它们。
我喜欢Lazarus的解决方案,但是如果你想避免为每个可能的数字有效地预先分配空间,只需将使用过的数字存储在表中,但是通过将所有可能的数字添加到集合中来在内存中构建“未使用的数字”列表然后删除数据库中存在的每一个。 然后选择其中一个剩余数字并使用它,显然将其添加到数据库中的列表中。
但是,就像我说的,我喜欢Lazaru的解决方案 – 我认为对大多数情况来说这是你最好的选择。
function getShuffledNumbers(count) { var shuffledNumbers = new Array(); var choices = new Array(); for (var i = 0; i= selectedNumber) { // This basically says "it was choice number (selectedNumber) on the last step, // but if it's greater than or equal to this, it must have been choice number // (selectedNumber + 1) on THIS step." selectedNumber++; } } shuffledNumbers[i] = selectedNumber; } return shuffledNumbers; }
这是我能想到的一种快速方式,并且只使用内存,但是如果你一直运行它将使用双倍内存,因为它有两个数组, choices
和shuffledNumbers
。
运行一次线性同余生成器来生成每个数字很容易产生相当微弱的结果。 通过多次迭代运行它,这对您的基础来说是相对优势的(在这种情况下为100,000,000)将大大改善它。 如果在报告生成器的每个输出之前,通过一个或多个其他排列函数运行它,最终输出仍然是所需数量的无重复排列(最多100,000,000)但是如果选择了正确的函数结果可以加密强大。
-
创建并存储间隔为[0..N]的ind db两个混洗版本(SHUFFLE_1和SHUFFLE_2),其中N = 10’000;
-
无论何时创建新订单,您都可以像这样分配其ID:
ORDER_FAKE_INDEX = N * SHUFFLE_1 [ORDER_REAL_INDEX / N] + SHUFFLE_2 [ORDER_REAL_INDEX%N]
我也遇到了同样的问题但在C#中。 我终于解决了。 希望它也适合你。
假设我需要0和某些MaxValue
之间的随机数,并且随机类型对象说是随机的。
int n=0; while(n
通过拖拽线,我们可以获得例如6个非重复随机数,范围例如1到100。
var randomNumbers = Enumerable.Range(1, 100) .OrderBy(n => Guid.NewGuid()) .Take(6) .OrderBy(n => n);
愚蠢的方法:构建一个表来记录,首先存储所有的numble,以及每次使用的numble,并将其标记为“used”
System.Random rnd = new System.Random(); IEnumerable numbers = Enumerable.Range(0, 99999999).OrderBy(r => rnd.Next());
这会在您的范围内随机抽取一组整数。 然后,您可以按顺序遍历集合。
关于这一点的好处是你实际上并没有在内存中创建整个集合。
请参阅下面的注释 – 当您迭代到第一个元素时,这将在内存中生成整个集合。