随机数的生成

生成伪随机数据

Math对象的random方法返回0到1之间的伪随机数,可能等于0,但一定小于1。

使用js生成n到m间的随机数字,主要目的是为后期的js生成验证码做准备,Math.random()函数返回0和1之间的伪随机数

一:通过时间获得随机数

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        HashSet<Integer> set = new HashSet<>();
        for(int i=0; i<100000; i++) {
            int hashCode = UUID.randomUUID().toString().replaceAll(“-“,
“”).hashCode();
            hashCode = hashCode < 0 ? hashCode * -1 : hashCode;
            
            list.add(hashCode);    
        }
        set.addAll(list);
        System.out.println(list.size());
        System.out.println(set.size());
        System.out.println(list.size()-set.size());
    }

Java里有伪随机型和安全型两种随机数生成器。伪随机生成器根据特定公式将seed转换成新的伪随机数据的一部分。安全随机生成器在底层依赖到操作系统提供的随机事件来生成数据。

生成给定范围内的随机数,包括min但不包含max

function getRandomArbitrarty(min, max) {
  return Math.random() * (max - min) + min;
}

 

因为时间的唯一性,且不重复,所以可以从中获得同一时间的唯一值

安全随机生成器

生成给定范围内的随机数,包括min也包含max

function getRandomArbitrarty(min,max) {
  return Math.random() * (max - min + 1) + min;
}
            var random = Math.random();
            console.log("0-1的随机数"+random);

            var m=100,n=1000;
            var num = Math.random()*(n-m) + m;
            num = parseInt(num, 10);
            console.log("m-n的随机数"+num);

            //生成n-m,包含n但不包含m的整数:
                //第一步算出 m-n的值,假设等于w
                //第二步Math.random()*w
                //第三步Math.random()*w+n
                //第四步parseInt(Math.random()*w+n, 10)

            //生成n-m,不包含n但包含m的整数:
                //第一步算出 m-n的值,假设等于w
                //第二步Math.random()*w
                //第三步Math.random()*w+n
                //第四步Math.floor(Math.random()*w+n) + 1

            //生成n-m,不包含n和m的整数:
                //第一步算出 m-n-2的值,假设等于w
                //第二步Math.random()*w
                //第三步Math.random()*w+n +1
                //第四步Math.round(Math.random()*w+n+1) 或者 Math.ceil(Math.random()*w+n+1)

            //生成n-m,包含n和m的随机数:
                //第一步算出 m-n的值,假设等于w
                //第二步Math.random()*w
                //第三步Math.random()*w+n
                //第四步Math.round(Math.random()*w+n) 或者 Math.ceil(Math.random()*w+n)

//            补充:
//  Math.ceil() 返回大于等于数字参数的最小整数(取整函数),对数字进行上舍入
//
//  Math.floor() 返回小于等于数字参数的最大整数,对数字进行下舍入
//
//  Math.round() 返回数字最接近的整数,四舍五入

6019@go:~$ date +%s

需要生成加密性强的随机数据的时候才用它;

生成给定范围内的整数

function getRandomArbitrarty(min, max) {
  return Math.floor(Math.random() * (max - min) + min);
}

//  使用Math.floor方法对数值进行向下取整,Math.ceil方法向上取整

 

1446458167

生成速度慢;

生成一个随机字符串

function random(min, max) {
  return Math.floor(Math.random() * (max - min) + min);
}

function randomStr(len) {
  var str = '';
  var dict = '1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
  for (var i = 0; i < len; i++) {
    str += dict[random(0, 62)];
  }
  return str;
}

var newStr = randomStr(8);
console.log(newStr);

6019@go:~$ date +%s%N

如果需要生成(Linux /dev/random
就是个这样的安全随机生成器)大量随机数据,可能会产生堵塞需要等待外部中断事件。

生成一个随机IP地址

IP地址的范围是:0.0.0.0 ~255.255.255.255
由于Math.random()生成的随机数包括0,但是不包括1,所以要生成0~255之间的随机数应该使用0~256的范围。

function random(min, max) {
  return Math.floor(Math.random() * (max - min) + min);
}

function randomIp() {
  var ipArr = [];
  for (var i = 0; i < 4; i++) {
    ipArr.push(random(0, 256));
  }
  return ipArr.join('.');
}

console.log(randomIp());

1446458227858613268

而伪随机生成器,只依赖于”seed”的初始值。如果你给生成算法提供相同的seed,可以得到一样的伪随机序列。一般情况下,由于它是计算密集型的(不依赖于任何IO设备),因此生成速度更快。接下来,我们将回顾伪随机生成器的进化史。

生成一个随机颜色

function randomColor() {
  var dict = '0123456789abcdef';
  var arr = [];
  for (var i = 0; i < 6; i++) {
    arr[i] = dict[Math.floor(Math.random() * 16)];
  }
  arr.unshift('#');
  return arr.join('');
}

console.log(randomColor());

更多随机颜色的获取方法:javascript获取随机颜色

由此来获得随机数的基数

java.util.Random

在vim中编辑函数获得

java.util.Random 从Java
1.0开始就存在了。它是一个线程安全类,理论上可以通过它同时在多个线程中获得互不相同的随机数。这样的线程安全是通过AtomicLong实现的。

函数为

Random 使用 AtomicLong CAS
(compare-and-set)操作来更新它的seed,尽管很多非阻塞式算法中使用了非阻塞式原语,CAS在资源高度竞争时的表现依然糟糕。在后面的测试结果中你可以看到它的糟糕表现。

#!/bin/sh

java.util.concurrent.ThreadLocalRandom

function random()

Java 7增加了java.util.concurrent.ThreadLocalRandom 并企图将它与
java.util.Random
结合以克服所有的性能问题。ThreadLocalRandom类继承自java.util.Random。

{

ThreadLocalRandom 的主要实现细节:

min=$1;

它使用一个普通的 long 而不是使用 Random 中的 AtomicLong 作为seed。

max=$2-$1;

你不能自己创建ThreadLocalRandom实例,因为它的构造函数没有设置为public。可以使用它的静态工厂ThreadLocalRandom.current(),这个工厂方法调用了内置的ThreadLocal<
ThreadLocalRandom>。

num=$(date +%s+%N);

它是CPU缓存感知式的,使用8个 long 虚拟域来填充64位L1高速缓存行。

((retnum=num%max+min));

所有这些改变都是很重要的,在接下来的测试中你将会感受到。

echo $retnum;

测试

}

我们将进行下面5种测试:

for i in {1 .. 10};

一个单独的java.util.Random被N个线程共享

do

ThreadLocal< Random>

out=$(random 2 10000);

java.util.concurrent.ThreadLocalRandom

echo $i,”2-10000″,$out;

java.util.Random[],其中每个线程N使用一个数组下标为N的Random。

done;

java.util.Random[],其中每个线程N使用一个数组下标为N * 2的Random。

~

所有的测试都使用了封装在RandomTask类里的方法。每个方案都说明了如何使用随机生成器。

运算结果如下:

private static final long COUNT = 10000000;

zyc@ubuntu:~$ vim a

private static final int THREADS = 2;

zyc@ubuntu:~$ sh a

public static void main(String[] args) {

{1,2-10000,289

System.out.println( “Shared Random” );

..,2-10000,9414

testRandom(THREADS, COUNT);

10},2-10000,8819

// System.out.println(“ThreadLocal”);

二:通过内部系统变量($RANDOM)

// testTL_Random(THREADS, COUNT);

6019@go:~$ #!/bin/sh

// System.out.println(“ThreadLocalRandom”);

6019@go:~$ echo $RANDOM

// testTLRandom(THREADS, COUNT);

32657

// System.out.println(“Shared Random[] with no padding”);

6019@go:~$ echo $RANDOM

// testRandomArray(THREADS, COUNT, 1);

8785

// System.out.println(“Shared Random[] with padding”);

感觉用这个方法来生成随机数还是挺方便的

// testRandomArray(THREADS, COUNT, 2);

啊,上面内容就是随便写写,然而并不清楚这些随机数有什么用,难道就是两个人无聊的用来比大小决一胜负么。

}

//runner for all tests

private static class RandomTask implements Runnable

{

private final Random rnd;

protected final int id;

private final long cnt;

private final CountDownLatch latch;

private RandomTask(Random rnd, int id, long cnt, CountDownLatch latch) {

this.rnd = rnd;

this.id = id;

this.cnt = cnt;

this.latch = latch;

}

protected Random getRandom()

{

return rnd;

}

@Override

public void run() {

try {

final Random r = getRandom();

latch.countDown();

latch.await();

final long start = System.currentTimeMillis();

int sum = 0;

for ( long j = 0; j < cnt; ++j )

{

sum += r.nextInt();

}

final long time = System.currentTimeMillis() – start;

System.out.println( “Thread #” + id + ” Time = ” + time / 1000.0 + ”
sec, sum = ” + sum );

} catch (InterruptedException e) {

}

}

}

private static void testRandom( final int threads, final long cnt )

{

final CountDownLatch latch = new CountDownLatch( threads );

final Random r = new Random;

for ( int i = 0; i < threads; ++i )

{

final Thread thread = new Thread( new RandomTask( r, i, cnt, latch ) );

thread.start();

}

}

private static void testRandomArray( final int threads, final long cnt,
final int padding )

{

final CountDownLatch latch = new CountDownLatch( threads );

final Random[] rnd = new Random[threads * padding];

for ( int i = 0; i < threads * padding; ++i ) //allocate together

rnd[ i ] = new Random;

for ( int i = 0; i < threads; ++i )

{

final Thread thread = new Thread( new RandomTask( rnd[ i * padding ],
i, cnt, latch ) );

thread.start();

}

}

private static void testTLRandom( final int threads, final long cnt )

{

final CountDownLatch latch = new CountDownLatch( threads );

for ( int i = 0; i < threads; ++i )

{

final Thread thread = new Thread( new RandomTask( null, i, cnt, latch )
{

@Override

protected Random getRandom() {

return ThreadLocalRandom.current();

}

} );

thread.start();

}

}

private static void testTL_Random( final int threads, final long cnt )

{

final CountDownLatch latch = new CountDownLatch( threads );

final ThreadLocal rnd = new ThreadLocal() {

@Override

protected Random initialValue() {

return new Random;

}

};

for ( int i = 0; i < threads; ++i )

{

final Thread thread = new Thread( new RandomTask( null, i, cnt, latch )
{

@Override

protected Random getRandom() {

return rnd.get();

}

} );

thread.start();

}

}

测试结果

所有测试都是在我的工作站上(Xeon
E5-2650八核16线程2Ghz、128Gb内存、操作系统是Linux 3.5.0)完成。

Shared java.util.Random

第一个测试使用的是共享的java.util.Random实例。高争夺的CAS操作严重影响了它的性能。仅仅开两个线程都会受争夺的影响,然后现实中很少会发生这种争夺的情况。下面是所有线程的最小和最大运行时间。

1 thread – 1.69 sec

2 threads – 13.2, 13.3 sec

4 threads – 34 – 47 sec

8 threads – 89 – 135 sec

“Shared” java.util.concurrent.ThreadLocalRandom

接下来的测试使用第二个类——java.util.concurrent.ThreadLocalRandom。
如你所见,在程序运行的线程数低于CPU的线程数时性能没有下降,当程序运行的线程数超过CPU的线程数时性能才线性的降低。另一个要注意的重点是,单一线程执行的效率是第一个案例的3倍——无竞争的CAS操作仍然表现糟糕。

1 thread – 0.57 sec

2 threads – 0.55 sec

4 threads – 0.51 sec

8 threads – 0.50 sec

16 threads – 0.53 – 0.56 sec

32 threads – 0.91 – 1.07 sec

64 threads – 0.89 – 2.07 sec

128 threads – 1.1 – 4.03 sec

“Shared” ThreadLocal

把java.util.Random实例装入ThreadLocal后执行的效率有些不一样,当线程数超过CPU核心数时性能就下降了——听起来像是CAS操作不能执行那么多单元。不过接下来的性能下降是线性的,和第二个案例很相似。

1 thread – 1.69 sec

2 threads – 1.66 sec

4 threads – 1.71 sec

8 threads – 1.76 sec

16 threads – 2.12 – 2.17 sec

32 threads – 3.7 – 4.3 sec

64 threads – 7.2 – 9.3 sec

128 threads – 14.6 – 17.4 sec

Array of java.util.Random

最后我想要检查CPU缓存行对ThreadLocalRandom
的改善作用和模拟java.util.Random在缺乏这种功能下的情况。你需要做的就是创建可以被很多线程使用的java.util.Random实例,我用java.util.Random[]来实现此目的并用array[N]表示第N个线程。

8线程测试的结果是4 sec和13.9 sec,看来缓存很重要!

我决定找出合适的填充数组大小以避免缓存失效,我给testRandomArray方法添加了一个padding参数然后测试。当padding=2时缓存问题解决了:8线程测试的时间是1.765
– 1.77 sec(和之前用ThreadLocal<
java.util.Random>进行8线程测试花的时间差}不多)。

使用Linux perf工具来分析结果

我很想知道为什么会得到这样的结果,在看了reviewed Systems Performance:
Enterprise and the Cloud这本书之后,我用perf stat
-d命令运行8线程的各方案测试,它会打印详细的统计数据(你可以加-e参数打印更多信息;
用 perf list 命令查看可用选项)。

不幸的是,这些数据中包括了JVM的启动时间,因此对于运行时间短的程序要格外小心。

Random and ThreadLocalRandom

让我们来比较一下差异比较大的两个测试结果——shared java.util.Random 和
java.util.concurrent.ThreadLocalRandom。第一个图是Random的测试结果,第二个图是ThreadLocalRandom的测试结果

2,553,076,870,919 cycles # 2.398 GHz

2,501,593,471,621 stalled-cycles-frontend # 97.98% frontend cycles idle

2,454,797,083,551 stalled-cycles-backend # 96.15% backend cycles idle

42,807,128,658 instructions # 0.02 insns per cycle

# 58.44 stalled cycles per insn

4,999,510,690 branches # 4.697 M/sec

862,334,730 branch-misses # 17.25% of all branches

12,231,515,289 L1-dcache-loads # 11.490 M/sec

5,471,297,449 L1-dcache-load-misses # 44.73% of all L1-dcache hits

9,321,932,029 cycles # 2.206 GHz

6,767,646,797 stalled-cycles-frontend # 72.60% frontend cycles idle

2,049,190,051 stalled-cycles-backend # 21.98% backend cycles idle

10,094,934,215 instructions # 1.08 insns per cycle

# 0.67 stalled cycles per insn

816,688,169 branches # 193.249 M/sec

1,506,379 branch-misses # 0.18% of all branches

1,683,890,500 L1-dcache-loads # 398.451 M/sec

4,508,729 L1-dcache-load-misses # 0.27% of all L1-dcache hits

如上表所示,Random的结果很糟糕——它完成同样任务所需的机器周期是ThreadLocalRandom的284倍!几乎每个周期都停滞在CPU管道上了。用25500亿
的机器周期只执行了428亿指令,这揭露了它糟糕的性能——一个机器周期只执行了0.02个指令(好的非基于IO类软件每个机器周期至少执行1个指令)。下一个指标是分支数——被执行大约50亿个分支,但是有17.25%的分支预测出错了(这个预测率很糟糕还会导致CPU管道重置)。最后,程序要通过一级缓存加载数据122亿次,但是44.73%失败了,随后我们再解释这些值的意义。

ThreadLocalRandom只需要93亿个机器周期来完成同样的事情。停滞指令的份额比较小——只有22%的后台指令失效,我认为多数的失效是在JVM启动的时候发生的。这次我们只需执行100亿指令(比上一个例子少4倍——通过这个差异你可以期望到单线程方案下的差异;实际相差大约是3.4倍)和8.16亿次分支而且几乎全部都预测对了(这正是你预期的结果)。我们从一级缓存加载数据17亿次几乎每次都成功了(失败率是0.27%).

接下来我们解释上面那些值的意义。首先,我们有8个线程,每个线程执行循环1亿次,所以我们应该先找8亿的倍数。

Branches是最明显的, 我们有8个线程,每个线程都执行for loop
1亿次,这意味着测试程序执行8亿个分支。ThreadLocalRandom执行8.16亿分支,因此我们有1600万分支留给JVM启动时检验用。我们可以断定没有分支需要ThreadLocalRandom,不然我们可以在输出中看到至少16亿分支(每个循环有额外的一个分支)。没有分支的代码一般运行得更快。

然而Random需要大概50亿的分支。从上面我们可以发现,JVM仅仅负责处理很小一部分分支,因此seed上的每个CAS操作需要大约6.25个分支。8.62亿的分支失效次数说明了这次CPU期望循环继续(即便CAS操作赋值失败)并且把成功的处理也当做了失效。

L1 cache loads.
我们企图从L1缓存中加载122亿个Random和17亿ThreadLocalRandom。看下面的代码,每次迭代需要至少访问内存中的随机
seed 2次(一次是获取,一次是用来比较),但实际上可能不止两次。

protected int next {

long oldseed, nextseed;

AtomicLong seed = this.seed;

do {

oldseed = seed.get();

nextseed = (oldseed * multiplier + addend) & mask;

} while (!seed.compareAndSet(oldseed, nextseed));

return (nextseed >>> (48 – bits));

}

ThreadLocalRandom.next同样需要访问内存2次

protected int next {

rnd = (rnd * multiplier + addend) & mask;

return (rnd >>> ;

}

在ThreadLocalRandom这个方案中每次迭代要进行2次内存访问,需要一级缓存加载16亿次。

不幸的是,在没有生成汇编代码前不容易发现Randon.next每次迭代真正需要进行多少次内存访问。

ThreadLocal

33,255,538,502 cycles # 2.338 GHz

26,334,159,876 stalled-cycles-frontend # 79.19% frontend cycles idle

13,886,446,385 stalled-cycles-backend # 41.76% backend cycles idle

19,278,411,972 instructions # 0.58 insns per cycle

# 1.37 stalled cycles per insn

2,431,012,359 branches # 170.882 M/sec

1,462,720 branch-misses # 0.06% of all branches

5,700,951,571 L1-dcache-loads # 400.734 M/sec

6,710,655 L1-dcache-load-misses # 0.12% of all L1-dcache hits

在这个例子中我们没有执行的是无竞争的Random,
这样可能得到的计数器值是最小的。

我们有24亿个分支,这意味着1次迭代需要3个分支。第一个分支在for
loop测试中,其它的分支出现在Random.next中。

do {

oldseed = seed.get();

nextseed = (oldseed * multiplier + addend) & mask;

} while (!seed.compareAndSet(oldseed, nextseed));

while对应第二个分支, AtomicLong.compareAndSet对应第三个分支。

Random[] with no padding

最后我们来看2个不同的Random实例进行CPU缓存争夺的例子。在下表中,分支数和一级缓存加载数和之前无争夺的例子非常相似。但是缓存加载失败的次数暴涨到了17亿,这暗示了每次迭代会有两次缓存加载失效。上面的一小段代码显示每次迭代都会访问seed两次(第二行和第四行各访问一次)。这意味着每次迭代都会访问两次RAM,使得程序慢了6倍。

209,445,037,827 cycles # 2.416 GHz

189,365,989,000 stalled-cycles-frontend # 90.41% frontend cycles idle

169,936,986,823 stalled-cycles-backend # 81.14% backend cycles idle

19,659,497,312 instructions # 0.09 insns per cycle

# 9.63 stalled cycles per insn

2,475,303,839 branches # 28.552 M/sec

2,315,797 branch-misses # 0.09% of all branches

5,719,174,890 L1-dcache-loads # 65.968 M/sec

1,703,679,647 L1-dcache-load-misses # 29.79% of all L1-dcache hits

总结

任何情况下都不要在多个线程间共享一个java.util.Random实例,而该把它放入ThreadLocal之中。

Java7在所有情形下都更推荐使用java.util.concurrent.ThreadLocalRandom——它向下兼容已有的代码且运营成本更低。

大家可以点击加入群:606187239【JAVA大牛学习交流】里面有Java高级大牛直播讲解知识点
走的就是高端路线(如果你想跳槽换工作 但是技术又不够 或者工作上遇到了瓶颈
我这里有一个JAVA的免费直播课程 讲的是高端的知识点基础不好的误入哟
只要你有1-5年的开发经验可以加群找我要课堂链接 注意:是免费的
没有开发经验误入哦)

发表评论

电子邮件地址不会被公开。 必填项已用*标注