Проблема со случайными и потоками в .NET

Question

У меня проблемы с классом Random в .NET, я реализую многопоточную коллекцию, которая работает нормально, за исключением одной мелкой детали. Коллекция представляет собой список пропусков , и те из вас, кто знаком с ним, знают, что для каждого вставленного узла мне нужно сгенерировать новую высоту <= CurrentMaxHeight+1, вот код, который я использую для этого Я знаю, что это очень неэффективно, но это работает, и это мой главный приоритет)

int randomLevel()
{
  int height = 1;

  while(rnd.NextDouble() >= 0.5 && height < MaxHeight)
    ++height;

  return height;
}

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

Так что я предполагаю (догадываюсь) , что в некотором роде есть проблема с объектом Random, но я не знаю, с чего начать копаться. Поэтому я обращаюсь к stackoverflow, чтобы узнать, есть ли у кого-нибудь идея?

Редактировать

rnd-переменная объявлена ​​в классе SkipList<T>, и к ней получают доступ из нескольких потоков (каждый поток вызывает .Add для коллекции и Add вызывает .randomLevel)

Answer 1

Попробуйте lock объект Random.

int RandomLevel()
{
    int height = 1;

    lock(rnd)
    {
        while(rnd.NextDouble >= 0.5 && height < MaxHeight) height++;
    }

    return height;
}

Может возникнуть проблема со столкновениями, когда несколько потоков одновременно обращаются к объекту Random, и начальное число может быть повреждено. Я не могу дать никакого представления о том, что может конкретно происходить, но согласно MSDN члены экземпляра типа Random не гарантируют поточно-ориентированную, поэтому lock кажется востребованным в любом случае.

Answer 2

Я бы не блокировал весь цикл while. Просто заблокируйте вызовы rnd.NextDouble ().

int RandomLevel()
{
  int height = 1;
  double newRand;

  lock(rnd) { newRand = rnd.NextDouble(); }

  while(newRand >= 0.5 && height < MaxHeight)
  {
    height++;
    lock(rnd) { newRand = rnd.NextDouble(); }
  }

  return height;
}

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

Answer 3

Похоже, что ваш цикл выполняется меньше половины времени, в течение которого он вызывается - это то, что вы ищете (когда случайное число от 0 до 1> 0,5? Это может объяснить, почему вы получаете «1»). чаще, чем вы ожидаете - по крайней мере, половину времени, он даже не запускает цикл, который увеличивает высоту - он просто устанавливает высоту в 1, не меняет ее, а затем возвращает «1». Я не знаком с пропуском списков, так что это может быть преднамеренным, но я подумал, что спросить.

Я не слишком знаком с работой со случайными числами, но возможно ли, что у вас есть проблема с посевом? Если вы не рандомизируете объект Random при создании его экземпляра, он может возвращать предсказуемый поток чисел вместо действительно случайных. Возможно, не из-за поведения, которое вы здесь видите, но из-за чего стоит двигаться дальше.