代码之家 › 专栏 › 技术社区 › dlras2

如何最好地按需生成随机数的静态数组?

random algorithm c#

dlras2 · 技术社区 · 15 年前

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 物体。

8 回复 | 直到 15 年前

Blindy 15 年前

你所说的通常被称为“柏林噪音”,这里有一个链接: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

  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坐标返回一个介于-1.0和+1.0之间的数字(以及一个硬编码种子,您可以在应用程序开始时随机更改或保持原样)。

本文的其余部分是关于插值这些数字的,但是根据您想要这些数字的随机性,您可以将它们保持原样。注意这些数字是完全随机的。如果你改为使用余弦插值器,每5-6个索引使用一次生成的噪波,在中间进行插值,你就得到了heightmap数据(这就是我使用它的目的)。对于完全随机的数据跳过它。

ony 15 年前

标准随机生成器通常是序列生成器,其中下一个元素都是从上一个元素生成的。所以要产生 rndMtx1[3,16]
事实上你需要一些不同于随机的东西 发电机 hash(seed + index) (我猜在密码和签名中使用哈希的想法是从输入数据中产生一些稳定的“随机”值)。

另外,你可以用独立发电机改进你的方法( Random(seed + index) )通过制造矩阵的惰性块。

C. Dragon 76 15 年前

我认为你的第一个想法是实例化一个新的随机对象,这个对象由一些确定性散列(x坐标,y坐标,LazyRandomMatrix种子)作为种子,这在大多数情况下可能是合理的。一般来说,在托管堆上创建许多小对象是CLR非常擅长有效处理的事情。我不认为Random.ctor()非常昂贵。你可以很容易地衡量性能,如果它是一个问题。

一个非常类似的解决方案可能比创建一个好的确定性哈希更容易,就是每次使用两个随机对象。比如:

public int this[int x, int y]
{
    get
    {
        Random r1 = new Random(_seed * x);
        Random r2 = new Random(y);
        return (r1.Next() ^ r2.Next());
    }
}

Chris Taylor 15 年前

下面是一个基于SHA1散列的解决方案。基本上,这会获取X、Y和种子值的字节,并将其打包到字节数组中。然后是字节数组的散列和用于生成 int

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);
    }
  }     
}

Andras Vass 15 年前

PRNGs can be built out of hash functions.
这就是MS Research所做的并行随机数生成 with MD5 或 others with TEA
(事实上,prng可以被认为是来自(seed,state)=>下一个号码。)
在GPU上生成大量的随机数也会带来类似的问题。

虽然使用加密哈希在加密世界中更为常见,但我还是冒昧地使用了 MurmurHash 2.0 good results 作为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;
    }

}

dtb 15 年前

伪随机数生成器本质上是一个函数,它确定地计算给定值的后继值。

你可以发明一个简单的算法,从它的邻居那里计算出一个值。如果一个邻居还没有一个值,首先从它各自的邻居计算它的值。

像这样:

_(0,0)
=后继(值 )
价值 _(x,y+1) _(x,y) )

示例 后继(n)=n+1 计算价值 _(2,4) :

 \ x  0      1      2
y  +-------------------
 0 | 627    628    629
 1 |               630
 2 |               631
 3 |               632
 4 |               633

这个例子算法显然不是很好,但你得到的想法。

Craig Gidney Mihai 15 年前

这种发电机的一个很酷的例子是 Blum Blum Shub ,这是一种易于随机访问的加密安全PRNG。不幸的是,它非常慢。

一个更实际的例子是著名的线性同余发生器。您可以很容易地修改一个允许随机访问。考虑一下定义:

X(0) = S
X(n) = B + X(n-1)*A (mod M)

pseudo linear ,不是线性的),但可以转换为非递归形式:

//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)

Java Drinker 15 年前

据我所知,这里有两种基本算法:

生成一个新的随机数基于 func(seed, coord)
从seed生成一个随机数,然后将其转换为坐标(类似于 rotate(x) + translate(y) 或者别的什么)

在第一种情况下,您总是有生成新随机数的问题,尽管这可能没有您担心的那么昂贵。

在第二种情况下,问题是在转换操作期间可能会丢失随机性。然而,无论哪种情况,结果都是可重复的。