如何根据需要最好地生成随机数的静态数组？
我正在处理的应用程序需要一个随机数矩阵。 矩阵可以随时在任何方向上生长，并不总是满的。 （我可能最终会用四叉树或其他东西重新实现它，而不是带有很多空对象的矩阵。）
我需要一种方法来生成相同的矩阵，给定相同的种子，无论我以何种顺序计算矩阵。
LazyRandomMatrix rndMtx1 = new LazyRandomMatrix(1234) // Seed new object float X = rndMtx1[0,0] // Lazily generate random numbers on demand float Y = rndMtx1[3,16] float Z = rndMtx1[23,-5] Debug.Assert(X == rndMtx1[0,0]) Debug.Assert(Y == rndMtx1[3,16]) Debug.Assert(Z == rndMtx1[23,-5]) LazyRandomMatrix rndMtx2 = new LazyRandomMatrix(1234) // Seed second object Debug.Assert(Y == rndMtx2[3,16]) // Lazily generate the same random numbers Debug.Assert(Z == rndMtx2[23,-5]) // on demand in a different order Debug.Assert(X == rndMtx2[0,0]) 是的，如果我知道数组的维度，最好的方法是生成整个数组，只返回值，但它们需要独立生成并按需生成。
我的第一个想法是为每次调用新坐标初始化一个新的随机数生成器，用整个矩阵的种子的一些散列和调用中使用的坐标来播种它，但这似乎是一个可怕的黑客，因为它需要创建一个吨新的Random对象。
您所谈论的通常称为“Perlin Noise”，这里有一个链接： http ： //freespace.virgin.net/hugo.elias/models/m_perlin.htm
该文章中最重要的是2D中的噪声函数：
function Noise1(integer x, integer y) n = x + y * 57 n = (n<<13) ^ n; return ( 1.0 - ( (n * (n * n * 15731 + 789221) + 1376312589) & 7fffffff) / 1073741824.0); end function
它基于x和y coordonates单独返回介于-1.0和+1.0之间的数字（以及一个硬编码的种子，您可以在应用程序的开头随机更改，或者保持原样）。
本文的其余部分是关于插入这些数字，但根据您想要这些数字的随机性，您可以将它们保留原样。 请注意，这些数字将是完全随机的。 如果您改为使用余弦插值器并使用每5-6个索引生成的噪声，并在其间进行插值，您将获得高度图数据（这是我用它的原因）。 跳过它来获取完全随机的数据。
标准随机生成器通常是序列的生成器，其中每个下一个元素都是从之前构建的。 因此要生成rndMtx1[3,16]您必须生成序列中的所有先前元素。
实际上你需要一些与随机生成器不同的东西，因为你只需要一个值，而不是序列。 您必须构建自己的“生成器”，它使用种子和索引作为公式的输入来生成单个随机值。 你可以发明很多方法来做到这一点。 最简单的方法之一是采用随机值asm hash(seed + index) （我想密码和签名中使用的哈希的想法是从输入数据中产生一些稳定的“随机”值）。
PS你可以通过制作延迟的矩阵块来改进独立生成器（ Random(seed + index) ）的方法。
我认为你的第一个想法是实例化一个新的Random对象，它由一些确定性散列（x坐标，y坐标，LazyRandomMatrix种子）播种，对于大多数情况来说可能是合理的。 通常，在托管堆上创建大量小对象是CLR非常擅长高效处理的事情。 我不认为Random.ctor（）非常昂贵。 如果需要考虑，您可以轻松测量性能。
一个非常类似的解决方案可能比创建一个好的确定性散列更容易，每次使用两个Random对象。 就像是：
public int this[int x, int y] { get { Random r1 = new Random(_seed * x); Random r2 = new Random(y); return (r1.Next() ^ r2.Next()); } }
这是一个基于SHA1哈希的解决方案。 基本上，这需要X，Y和Seed值的字节，并将其打包成一个字节数组。 然后是字节数组的散列和用于生成int的散列的前4个字节。 这应该是随机的。
public class LazyRandomMatrix { private int _seed; private SHA1 _hashProvider = new SHA1CryptoServiceProvider(); public LazyRandomMatrix(int seed) { _seed = seed; } public int this[int x, int y] { get { byte[] data = new byte[12]; Buffer.BlockCopy(BitConverter.GetBytes(x), 0, data, 0, 4); Buffer.BlockCopy(BitConverter.GetBytes(y), 0, data, 4, 4); Buffer.BlockCopy(BitConverter.GetBytes(_seed), 0, data, 8, 4); byte[] hash = _hashProvider.ComputeHash(data); return BitConverter.ToInt32(hash, 0); } } }
PRNG可以用哈希函数构建。
这就是例如MS Research在GPU上使用MD5或其他TEA并行化随机数生成所做的事情。
（实际上，PRNG可以被认为是来自（种子，状态）=> nextnumber的哈希函数。）
在GPU上生成大量随机数会带来类似的问题。
（例如，要使其并行，不应该有一个共享状态。）
虽然在加密世界中更常见，但是使用加密哈希，我已经冒昧地使用MurmurHash 2.0来提高速度和简单性。 它具有非常好的统计特性作为散列函数。 相关但不完全相同的测试表明它作为PRNG提供了良好的结果 。 （除非我在C＃代码中有fsc＃kd，就是。:)随意使用任何其他合适的哈希函数; 加密的（MD5，TEA，SHA） – 尽管加密哈希值往往要慢得多。
public class LazyRandomMatrix { private uint seed; public LazyRandomMatrix(int seed) { this.seed = (uint)seed; } public int this[int x, int y] { get { return MurmurHash2((uint)x, (uint)y, seed); } } static int MurmurHash2(uint key1, uint key2, uint seed) { // 'm' and 'r' are mixing constants generated offline. // They're not really 'magic', they just happen to work well. const uint m = 0x5bd1e995; const int r = 24; // Initialize the hash to a 'random' value uint h = seed ^ 8; // Mix 4 bytes at a time into the hash key1 *= m; key1 ^= key1 >> r; key1 *= m; h *= m; h ^= key1; key2 *= m; key2 ^= key2 >> r; key2 *= m; h *= m; h ^= key2; // Do a few final mixes of the hash to ensure the last few // bytes are well-incorporated. h ^= h >> 13; h *= m; h ^= h >> 15; return (int)h; } }
伪随机数生成器本质上是确定性地计算给定值的后继者的函数。
您可以创建一个简单的算法来计算邻居的值。 如果邻居还没有值，则首先从其各自的邻居计算其值。
像这样的东西：
- 值（0,0） =种子
- value （x + 1,0） = successor（value （x，0） ）
- value （x，y + 1） =后继（value （x，y） ）
使用successor（n）= n + 1计算值（2,4）的示例：
\ x 0 1 2 y + ------------------- 0 | 627 628 629 1 | 630 2 | 631 3 | 632 4 | 633
这个示例算法显然不是很好，但你明白了。
您希望随机数生成器可以随机访问元素，而不是顺序访问。 （注意，您可以将两个坐标缩减为单个索引，即通过计算i = x +（y << 16）。）
这种发生器的一个很酷的例子是Blum Blum Shub ，它是一个加密安全的PRNG，具有简单的随机访问。 不幸的是，它很慢。
一个更实际的例子是众所周知的线性同余发生器。 您可以轻松修改一个以允许随机访问。 考虑定义：
X(0) = S X(n) = B + X(n-1)*A (mod M)
直接评估这将花费O（n）时间（这是伪线性 ，而不是线性），但您可以转换为非递归forms：
//Expand a few times to see the pattern: X(n) = B + X(n-1)*A (mod M) X(n) = B + (B + X(n-2)*A)*A (mod M) X(n) = B + (B + (B + X(n-3)*A)*A)*A (mod M) //Aha! I see it now, and I can reduce it to a closed form: X(n) = B + B*A + B*A*A + ... + B*A^(N-1) + S*A^N (mod M) X(n) = S*A^N + B*SUM[i:0..n-1](A^i) (mod M) X(n) = S*A^N + B*(A^N-1)/(A-1) (mod M)
最后一个等式可以相对快速地计算，虽然它的第二部分有点难以正确（因为除法不会以相同的方式分配加法和乘法）。
据我所知，这里有两种基本算法：
- 基于每个坐标的
func(seed, coord)生成新的随机数 - 从种子生成一个随机数，然后将其转换为coord（类似于
rotate(x) + translate(y)或者其他）
在第一种情况下，您遇到的问题是始终生成新的随机数，尽管这可能不像您担心的那样昂贵。
在第二种情况下，问题是您在转换操作期间可能会失去随机性。 但是，在任何一种情况下，结果都是可重复的。