转载

伪随机数的妙用

伪随机数的妙用

作者:王集鹄 2015年12月15日

背景

大部分计算机上的伪随机数,并不是真正的随机数,只是重复的周期比较大的数列,是按一定的「算法」和「种子值」生成的。 参考:随机数生成器

如果「随机数生成器」的「算法」和「种子值」相同,那么生成的「随机数序列」则是相同的,这就是「伪随机」的规律。

不妨写个代码验证一下

正好 .NET 提供了可以指定随机种子的 Random 类。

( 在线调试 )如下:

var rand1 = new Random(1024); var rand2 = new Random(1024); var flag = true; for (var i = 0; i < 1000; i++) {     if (rand1.next() != rand2.next()) {         flag = false;         break;     } } Console.WriteLine(flag); // True 

结果符合预期:相同种子值两个随机数序列完全相同。

脑洞

利用「伪随机生成器」这个特性,我们就可以用很少的字节生成非常大的恒定随机数序列

应用场景

那些情况会用到恒定随机数序列?

各种带随机性的游戏

  • 「俄罗斯方块」出现方块的形状序列

http://jsbin.com/riyibenazu/edit?html,console

<script src="http://jhtmls.com/jrands/jrands.js"></script> <script> 'use strict'; let next2015 = jrands(2015); // 随机种子值指定为 2015 const next = (x) => parseInt(next2015() * 7); let blocks = []; for (let i = 0; i < 100; i++) {   blocks.push(next()); } console.log(blocks.join('')); // 2014635212545523621... 诸位看到的也是这个结果 </script> 
  • 「泡泡龙」掉落泡泡的颜色序列

http://jsbin.com/jilipiliva/edit?html,console

<script src="http://jhtmls.com/jrands/jrands.js"></script> <script> 'use strict'; const colors = ['red', 'yellow', 'gray', 'blue', 'white', 'green', 'none']; let next2016 = jrands(2016); // 随机种子值指定为 2016 const next = (x) => colors[parseInt(next2016() * colors.length)]; let balls = []; for (let i = 0; i < 100; i++) {   balls.push(next()); } console.log(balls.join(',')); // "none,gray,none,none,gray,gray,yellow,green.." </script> 
  • 「爱消除」排列的图案
  • 「帝国时代」随机地形
  • 「麻将」、「扑克」牌的顺序
  • 「连连看」随机双份图案

随手写一个洗牌算法。思路:就是给每一张牌分配一个排序权重。

http://jsbin.com/welilisolo/edit?html,console

<script src="http://jhtmls.com/jrands/jrands.js"></script> <script> 'use strict'; let next2017 = jrands(2017); // 随机种子值指定为 2017  // 一幅完整的牌 let cards = []; for (var i = 0; i < 54; i++) {   cards.push(i); }  cards = cards.map((value) => ({   value: value,   ranking: next2017() // 随机生成排序权值 }))   .sort((a, b) => a.ranking - b.ranking) // 按排序权值排序   .map((item) => item.value); console.log(cards.join(',')); // "9,45,47,3,26,41,42,11,35,..." </script> 

数据加密

随机数出现的序列是很难预测的,这和加密要达到的目的很类似,总之就是让人很难找到变化的规律。

http://jsbin.com/magibakape/edit?html,console

<script src="http://jhtmls.com/jrands/jrands.js"></script> <script> 'use strict'; const randomXor = (text, seed) => {   let next = jrands(seed);   let result = '';   for (var i = 0; i < text.length; i++) {     result += String.fromCharCode(text.charCodeAt(i) ^ parseInt(256 * next()));   }   return result; }; console.log(randomXor(randomXor('Hello World!', 2018), 2018)); // > Hello World! </script> 

如果要提高加密的复杂度,可以增加几个随机种子或者随机种子再随机生成等等手段。

总结

这个脑洞其实是在十多年前写多人对战的俄罗斯方块时想出来的,已经有实际应用。

优势

  • 能用最少的内容存储海量恒定随机数序列

缺点

  • 如果「随机算法」和「随机种子值」都被截获,那所有结果就是能预测的。

由于 JavaScript 里的 Math.random 显然不能指定「种子值」,所以按 .NET Random 类写了一个小库, jrands 随手安利一下。

正文到此结束
Loading...