Создание ThreadLocal случайных генераторов с известными семенами - PullRequest
Новая
       19

Создание ThreadLocal случайных генераторов с известными семенами

0 голосов
/ 14 декабря 2011

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

ЧтоТеперь я делаю что-то вроде этого: 

class Program {
    static void Main(string[] args) {

        var seed = 10;
        var data = new List<double>();
        var dataGenerator = new Random(seed);

        for (int i = 0; i < 10000; i++) {
            data.Add(dataGenerator.NextDouble());
        }

        var results = new ConcurrentBag<double>();

        Parallel.ForEach(data, (d) => {
            var result = Calculate(d, new Random(d.GetHashCode()); 
            results.Add(result);
        });

    }

    static double Calculate(double x, Random random) {
        return x * random.NextDouble();
    }
}

Поскольку генератор случайных чисел, который создает список «данных», предоставляет начальное число, а генераторы случайных чисел, которые используются в вычислениях, - начальное число, основанное на хэш-коденомер обрабатывается, результаты повторяются.Независимо от количества потоков и порядка, в котором они создаются.

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

class Program {
    static void Main(string[] args) {

        var seed = 10;
        var data = new List<double>();
        var dataGenerator = new Random(seed);

        for (int i = 0; i < 10000; i++) {
            data.Add(dataGenerator.NextDouble());
        }

        var results = new ConcurrentBag<double>();

        var localRandom = new ThreadLocal<Random>(() => new Random());

        Parallel.ForEach(data, (d) => {
            var result = Calculate(d, localRandom.Value); 
            results.Add(result);
        });

    }

    static double Calculate(double x, Random random) {
        return x * random.NextDouble();
    }
}

Может кто-нибудь придумать хорошее решение дляэто проблема?

1 Ответ

3 голосов
/ 14 декабря 2011

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

Если вы добавляете свой локальный поток Random с одним и тем же номером каждый раз, вы сделаете результаты в этом потоке детерминированными, связанные с количеством предыдущих операций. То, что вы хотите, это псевдослучайное число, которое является детерминированным относительно ввода.

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

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

private static double Calculate(double x)
{
  unchecked
  {
    uint h = (uint)x.GetHashCode();
    h += (h << 15) ^ 0xffffcd7d;
    h ^= (h >> 10);
    h += (h << 3);
    h ^= (h >> 6);
    h += (h << 2) + (h << 14);
    return (h ^ (h >> 16)) / (double)uint.MaxValue * x;
  }
}

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

В этом и заключается компромисс всего этого подхода; Вы можете упростить вышесказанное и быть еще быстрее, но менее «случайным», или вы можете быть более «случайным» для больших усилий. Я уверен, что есть код, который является более быстрым и более «случайным», чем описанный выше, что более важно для демонстрации подхода, чем что-либо еще, но среди конкурирующих алгоритмов вы ищете компромисс качества сгенерированное число в зависимости от производительности. new Random(d).NextDouble() находится в определенной точке этого компромисса, другие подходы находятся в других точках.

Редактировать: Алгоритм повторного хэширования, который я использовал, - это хэш Ван-Дженкинса Я не мог вспомнить имя, когда писал его.

Редактировать: Имея лучшее представление о ваших требованиях из комментариев, я бы сейчас сказал, что ...

Вы хотите создать класс PRNG, он мог бы использовать описанный выше алгоритм, System.Random (с учетом отраженного кода в качестве отправной точки), алгоритм 128bitXorShift, который вы упомянули, или любой другой. Важным отличием является то, что он должен иметь метод Reseed. Например, если вы скопировали подход System.Random, ваша перекомпоновка выглядела бы как большая часть тела конструктора (действительно, вы бы, вероятно, осуществили рефакторинг, чтобы, кроме создания массива, который он использует, конструктор вызывал бы перезаполнение).

Затем вы создадите экземпляр для каждого потока и вызовете .Reseed(d.GetHashCode()) в тот момент, когда вы создадите новый Random в существующем коде.

Обратите внимание, что это дает вам еще одно преимущество: если вы зависите от последовательных результатов от вашего PRNG (что, как вам кажется), то от того, что вам не обещан согласованный алгоритм в System.Random между версиями платформы (возможно, даже включая исправления и исправления безопасности) - это плохой момент для вас, и такой подход добавляет согласованности.

Однако вам также не обещают согласованный алгоритм для double.GetHashCode(). Я сомневаюсь, что они меняют его (в отличие от string.GetHashCode(), который часто меняется), но на всякий случай вы можете заставить свой Reseed() дубль сделать что-то вроде: 

private static unsafe int GetSeedInteger(double d)
{
  if(d == 0.0)
    return 0;
  long num = *((long*)&d);
  return ((int)num) ^ (int)(num >> 32);
}

Который в значительной степени просто копирует текущий double.GetHashCode(), но теперь вы будете последовательны перед лицом изменений структуры.

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

Плюсы:

Доступ к ThreadLocal<T> обходится дороже, чем доступ к локальному T.

Если задачи согласованы в относительном времени для выполнения, вам не нужно много умения Parallel.ForEach.

Минусы:

Parallel.ForEach действительно хорош в балансировании вещей. То, что вы делаете, должно быть очень естественным образом сбалансировано, или экономить много на предварительной порции, прежде чем отказ от его использования принесет вам что-нибудь.

...