好久没写了...写点东西证明没送外卖，没跑滴滴，没转行，还活着。
题目
如何生成 M 个 1~N 的不重复的随机整数？其中 N>1 万亿，1≤M≤N。
初解析
初看这就是一道简单的算法题，用洗牌算法就可以，但 N>1 万亿，即使用 bit 也要消耗掉 116G+的存储，Swap 消耗也很大，如果每次随机然后做记录，冲突的就再随机一次？但 M 是可以接近 N 的，接近 N 时冲突变大，历史生成的随机数存储也会越来越大。怎么办？
岔开话题
想另外一个问题，如果有一天可以星际航行，你想带走地球上的所有数据，你会怎么带？带走所有数据存储的磁盘？
如果可以，把所有的数据都转换成十进制，然后在这个天文数字前加个"0."，于是它就变成了一个<1 的小数，如果我能制作出两根短/长刚好是这个小数的棍子，是不是我带着这两根棍子就带走了整个数据。
如果有这个能力，是不是 2001 太空漫游的黑石碑我们也能造了！！如果没有这个能力呢？我们能不能通过一些简单的几个数字的运算得到这个值？也许是 π/6 在 2^19937−1 小数位的截断？如果是这样，那是不是只需要在一张纸上写下这个规则即可。
当然，找到这个答案的消耗可能比带走磁盘成本大的多...
回归正题
能不能通过几个简单数字通过一定规则输出这些随机整数？
如果 N 是个质数，把 1~N 首尾相连成环。
因为质数的性质，只能被 1 和本身分解，因此随机一个[1,N]之间的数做为初始值，再随机一个[1,N)之间的数作为步长，是不是就能够稳定输出一个看似随机的数，并且不重复。
如图，N=7,start=3,step=2 就会得到一个 3572461 的随机序列，但是这显然不够随机，可以根据 35 即可推断出后续的随机数，这时候再引入一个时针的概念，每次取数时随机一个时针方向和这个时针下的取数长度。
如图，中途的随机转向可以提供一个较好的随机性，但依然不够随机，因为在初始位置和初始步长决定后，无法再获得更好的随机性，比如，不会出现 354 这样的序列。
关于随机性，可以增加嵌套环的方式，用多组初始值和步长来叠加，但依旧不够随机(如何把有序的东西在不引入相对无序下变成无序？又挖一个坑，哈哈哈)
如果 N 是个合数呢？
目前想到的是两种方案
一种是剔除 N 的所有质因数，比如遇到一个因数后随机向前或向后跳跃，直到遇到下一个非因数。但这个过程对一些大数在因数密集区要找很久。
另一种方案是，找到下一个质数，然后忽略掉之间的假数。
我们暂时采用找到下一个质数的方案简单实现一下：
Code
Talk is cheap, show me the code...
Java
package com.waitmoon.wm.rand;
import java.math.BigInteger;import java.util.concurrent.ThreadLocalRandom;
public final class WmRandom { private final long l; private final long r; private long cw; private long ccw; private long step; private ThreadLocalRandom random; private long fr; private long t; private final long s; private long ms; private boolean d; private long ns;
/** * @param r [0,r] */ public WmRandom(long r) { this(0, r, 200); }
/** * @param l left inclusive * @param r right inclusive */ public WmRandom(long l, long r) { this(l, r, 200); }
public void reset() { synchronized (this) { random = ThreadLocalRandom.current(); this.ns = fr - l; this.step = random.nextLong(1L, (ns >> 1) + 1L); while (step != 1L && (ns + 1L) % step == 0) { this.fr = BigInteger.valueOf(ns + 1L).nextProbablePrime().longValue() + l - 1L; this.ns = fr - l; } if (fr <= l) { throw new IllegalArgumentException("fillBound illegal"); } this.cw = random.nextLong(l, fr); long i = cw - step; this.ccw = i < l ? ns + i + 1L : i; this.t = 0; this.ms = random.nextLong(l, r); this.d = random.nextBoolean(); } }
/** * @param l left inclusive * @param r right inclusive * @param certainty certainty of prime */ public WmRandom(long l, long r, int certainty) { if (l >= r) { throw new IllegalArgumentException("origin must be non-negative and bound must be positive and origin must be less than bound"); } this.s = r - l + 1L; this.l = l; this.r = r; if (BigInteger.valueOf(s).isProbablePrime(certainty)) { this.fr = r; } else { this.fr = BigInteger.valueOf(s).nextProbablePrime().longValue() + l - 1L; } random = ThreadLocalRandom.current(); this.ns = fr - l; this.step = random.nextLong(1L, (ns >> 1) + 1L); while (step != 1 && (ns + 1L) % step == 0) { this.fr = BigInteger.valueOf(ns + 1L).nextProbablePrime().longValue() + l - 1L; this.ns = fr - l; } if (fr <= l) { throw new IllegalArgumentException("fillBound illegal"); } this.cw = random.nextLong(l, fr); long i = cw - step; this.ccw = i < l ? ns + i + 1L : i; this.ms = random.nextLong(l, r); this.d = random.nextBoolean(); }
/** * @return next value */ public long next() { long v; long ms; boolean d; synchronized (this) { if (t >= s) { throw new IllegalStateException("exhausted all possible values"); } d = this.d; ms = this.ms; long i; if (random.nextBoolean()) { v = cw; if (cw > r) { long g = fr - cw; cw = cw + g - g % step; i = cw + step; cw = i > fr ? i - ns - 1L : i; v = cw; } i = cw + step; cw = i > fr ? i - ns - 1L : i; } else { v = ccw; if (ccw > r) { long g = ccw - r - 1L; ccw = ccw - g + g % step; i = ccw - step; ccw = i < l ? ns + i + 1L : i; v = ccw; } i = ccw - step; ccw = i < l ? ns + i + 1L : i; } t++; } if (d) { if (v <= ms) { return v; } long f = ((r - ms) & 1) == 0 ? 1L : 0L; long m = ms + ((r - ms) >> 1) + 1L; return m - v - f + m; } if (v > ms) { return v; } long f = ((ms - l + 1L) & 1) == 0 ? 1L : 0L; long m = l + ((ms - l) >> 1) + f; return m - v - f + m; }}
复制代码
Golang
package random
import ( "errors" "math/big" "math/rand" "time")
type WmIdRand struct { l int64 r int64 cw int64 ccw int64 step int64 fr int64 t int64 s int64 certainty int random *rand.Rand ms int64 d bool ns int64}
func New(l, r int64) (*WmIdRand, error) { return NewWithCertainty(l, r, 200)}
func NewWithCertainty(l, r int64, certainty int) (*WmIdRand, error) { random := rand.New(rand.NewSource(time.Now().UnixNano())) if l >= r { return nil, errors.New("origin must be non-negative and bound must be positive and origin must be less than bound") } s := r - l + 1 var fr int64 if big.NewInt(s).ProbablyPrime(certainty) { fr = r } else { fr = nextProbablePrime(big.NewInt(s), certainty).Int64() + l - 1 } ns := fr - l step := random.Int63n(ns>>1) + 1 for step != 1 && (ns+1)%step == 0 { fr = nextProbablePrime(big.NewInt(ns+1), certainty).Int64() + l - 1 ns = fr - l } if fr <= l { return nil, errors.New("no prime number in the range") } cw := random.Int63n(ns) + l var ccw int64 if cw-step < l { ccw = ns + cw - step + 1 } else { ccw = cw - step } ms := rand.Int63n(r-l) + l d := random.Intn(2) == 0 return &WmIdRand{ l: l, r: r, cw: cw, ccw: ccw, step: step, fr: fr, t: 0, s: s, certainty: certainty, random: random, ms: ms, d: d, ns: ns, }, nil}
func (r *WmIdRand) Next() (int64, error) { if r.t >= r.s { return 0, errors.New("exhausted all possible values") } var v int64 if r.random.Intn(2) == 0 { v = r.cw if r.cw > r.r { g := r.fr - r.cw r.cw = r.cw + (g - g%r.step) if r.cw+r.step > r.fr { r.cw = r.cw + r.step - r.ns - 1 } else { r.cw = r.cw + r.step } v = r.cw } if r.cw+r.step > r.fr { r.cw = r.cw + r.step - r.ns - 1 } else { r.cw = r.cw + r.step } } else { v = r.ccw if r.ccw > r.r { g := r.ccw - r.r - 1 r.ccw = r.ccw - (g - g%r.step) if r.ccw-r.step < r.l { r.ccw = r.ns + r.ccw - r.step + 1 } else { r.ccw = r.ccw - r.step } v = r.ccw } if r.ccw-r.step < r.l { r.ccw = r.ns + r.ccw - r.step + 1 } else { r.ccw = r.ccw - r.step } } r.t++ if r.d { if v <= r.ms { return v, nil } m := r.ms + ((r.r - r.ms) >> 1) + 1 f := int64(0) if ((r.r - r.ms) & 1) == 0 { f = 1 } return m - v - f + m, nil } if v > r.ms { return v, nil } f := int64(0) if ((r.ms - r.l + 1) & 1) == 0 { f = 1 } m := r.l + ((r.ms - r.l) >> 1) + f return m - v - f + m, nil}
func (r *WmIdRand) Reset() error { r.random = rand.New(rand.NewSource(time.Now().UnixNano())) r.step = r.random.Int63n(r.ns>>1) + 1 if r.step != 1 && (r.ns+1)%r.step == 0 { r.fr = nextProbablePrime(big.NewInt(r.ns+1), r.certainty).Int64() + r.l - 1 r.ns = r.fr - r.l } if r.fr <= r.l { return errors.New("fillBound illegal") } r.cw = r.random.Int63n(r.ns) + r.l
if r.cw-r.step < r.l { r.ccw = r.ns + r.cw - r.step + 1 } else { r.ccw = r.cw - r.step } r.t = 0 r.ms = r.random.Int63n(r.r-r.l) + r.l r.d = r.random.Intn(2) == 0 return nil}
func nextProbablePrime(n *big.Int, certainty int) *big.Int { next := new(big.Int).Set(n) if next.Bit(0) == 0 { next.Add(next, big.NewInt(1)) } else { next.Add(next, big.NewInt(2)) } for { if next.ProbablyPrime(certainty) { return next } next.Add(next, big.NewInt(2)) }}
复制代码
可能有小伙伴好奇，为什么环不用 mod N 的形式，这样写起来也简单，因为 mod 的性能不如简单加减运算~
目前只想到了这种随机性不太够的方案，有新的方案欢迎探讨交流~
评论