Как я могу лучше всего генерировать статический массив случайных чисел по требованию?

Question

Приложение, над которым я работаю, требует матрицы случайных чисел. Матрица может расти в любом направлении в любое время и не всегда заполнена. (Я, вероятно, в конечном итоге повторно реализую его с помощью четырехугольного дерева или чего-то еще, а не матрицы с большим количеством нулевых объектов.)

Мне нужен способ генерировать одну и ту же матрицу с учетом того же начального числа, независимо от того, в каком порядке я вычисляю матрицу.

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 объектов.

Answer 1

То, о чем вы говорите, обычно называется «шум Перлина», вот ссылка для вас: 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

Возвращает число от -1,0 до +1,0, основываясь только на координатах x и y (и на жестко закодированном начальном числе, который можно произвольно изменить в начале приложения или просто оставить как есть).

Остальная часть статьи посвящена интерполяции этих чисел, но в зависимости от того, насколько случайным вы хотите эти числа, вы можете просто оставить их как есть.Обратите внимание, что эти числа будут совершенно случайными.Если вместо этого вы применяете Cosine Interpolator и используете сгенерированный шум каждые 5-6 индексов, интерполируя между ними, вы получаете данные карты высот (для этого я и использовал их).Пропустите это для совершенно случайных данных.

Answer 2

Вот решение на основе хэша SHA1.В основном это берет байты для значений X, Y и Seed и упаковывает это в байтовый массив.Затем хеш для байтового массива и первые 4 байта хеша, использованные для генерации 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);
    }
  }     
}

Answer 3

PRNG могут быть построены из хеш-функций.
Это то, что, например, MS Research проводила распараллеливание генерации случайных чисел с MD5 или других с TEA на графическом процессоре.
(Фактически, PRNG можно рассматривать как хеш-функцию из (seed, state) => nextnumber.)
Генерация большого количества случайных чисел на графическом процессоре приводит к аналогичным проблемам.
(Например, чтобы сделать его параллельным, не должно быть единого общего состояния.)

Хотя в криптографическом мире это более распространено, используя криптографический хеш, я позволил себе использовать MurmurHash 2.0 ради скорости и простоты. Он имеет очень хорошие статистические свойства в качестве хэш-функции. Соответствующий, но не идентичный тест показывает, что он дает хорошие результаты в качестве PRNG. (если у меня есть fsc # kd что-то в коде C #, то есть. :) Не стесняйтесь использовать любую другую подходящую хэш-функцию; также крипто (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;
    }

}

Answer 4

Я думаю, что ваша первая идея создания нового объекта Random, засеянного неким детерминированным хешем (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());
    }
}

Answer 5

Стандартный генератор случайных чисел обычно является генератором последовательности, где каждый следующий элемент строится из предыдущего. Таким образом, чтобы сгенерировать rndMtx1[3,16], вы должны сгенерировать все предыдущие элементы в последовательности.
На самом деле вам нужно что-то отличное от генератора random , потому что вам нужно только одно значение, но не последовательность. Вы должны создать свой собственный «генератор», который использует начальные числа и индексы в качестве входных данных для формулы для получения единственного случайного значения. Вы можете придумать много способов сделать это. Один из самых простых способов - принять случайное значение asm hash(seed + index) (я думаю, идея хэшей, используемых в паролях и подписи, состоит в том, чтобы получить какое-то стабильное «случайное» значение из входных данных).

P.S. Вы можете улучшить свой подход с помощью независимых генераторов (Random(seed + index)), создавая ленивые блоки матрицы.

Answer 6

Требуется генератор случайных чисел с произвольным доступом к элементам вместо последовательного доступа. (Обратите внимание, что вы можете свести две ваши координаты в один индекс, то есть вычислить i = x + (y << 16).) </p>

Отличным примером такого генератора является Blum Blum Shub , представляющий собой криптографически безопасный PRNG с легким произвольным доступом. К сожалению, это очень медленно.

Более практичным примером является известный линейный конгруэнтный генератор. Вы можете легко изменить один, чтобы разрешить произвольный доступ. Рассмотрим определение:

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

Непосредственная оценка этого потребует O (n) времени (это псевдолинейное , не линейное), но вы можете преобразовать в нерекурсивную форму:

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

Это последнее уравнение может быть вычислено относительно быстро, хотя вторую его часть немного сложно получить правильно (поскольку деление не распределяется по модулю так же, как сложение и умножение).

Answer 7

Генератор псевдослучайных чисел - это, по сути, функция, которая детерминистически вычисляет преемника для заданного значения.

Вы можете изобрести простой алгоритм, который вычисляет значение из его соседей.Если у соседа еще нет значения, сначала рассчитайте его значение из соответствующих соседей.

Примерно так:

• значение _(0,0) = семя
• значение _{(x + 1,0)} = преемник (значение _{(x, 0)} )
• значение _{(x, y + 1)} = преемник (значение _{(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

Этот пример алгоритма, очевидно, не очень хорош, но вы поняли идею.

Answer 8

Насколько я вижу, здесь возможно 2 основных алгоритма:

• Создать новое случайное число на основе func(seed, coord) для каждой координаты
• Создайте одно случайное число из семени, а затем преобразуйте его для координат (что-то вроде rotate(x) + translate(y) или что-то еще)

В первом случае у вас есть проблема всегда генерировать новые случайные числа, хотя это может быть не так дорого, как вы боитесь.

Во втором случае проблема заключается в том, что вы можете потерять случайность во время операций преобразования. Однако в любом случае результат является воспроизводимым.