C# Random does not work like a random

Question

I have a graph, each node have 4 child nodes. I wrote a algorithm to generate a random path from a begin node to an end node. At each node, it chooses a random next node. Visited node can be revisited.

the code is like the following:

public List<Node> GetPath(Node begin, Node end) { var nodes = new List<Node>(); var node = begin; while (node != end) { nodes.Add(node); var next = node.Children[new Random().Next(4)]; node = next; } nodes.Add(end); return nodes; }

But sometimes, the Random does not work as expected. The "new Random().Next(4)" keeps generating 0. So it is always the first child node get chose and a very long repeat sequence like node1->node2->node1->node2... is generated and eventually an out of memory exception happens.

Is there a way to make the Random class works correctly?

possible duplicate of Random number generator not working the way I had planned (C#) — Alexei Levenkov
– Alexei Levenkov, Commented Jul 24, 2012 at 1:22
This question is similar to: Random number generator only generating one random number. If you believe it’s different, please edit the question, make it clear how it’s different and/or how the answers on that question are not helpful for your problem. — Filburt
– Filburt, Commented Feb 2 at 9:12

Glen Hughes · Accepted Answer · 2012-07-24 00:46:19Z

The reason is because Random is initialized based on the current time (there is no true random in computers... only psuedo-random). The while loop iterates too quickly, and the system time has not registered a change. So you're re-initializing a new Random object that starts with the same value.

Try creating one Random object that is reused throughout the method:

public List<Node> GetPath(Node begin, Node end) { var nodes = new List<Node>(); var node = begin; Random r = new Random(); while (node != end) { nodes.Add(node); var next = node.Children[r.Next(4)]; node = next; } nodes.Add(end); return nodes; }

Thanks. This does solve the problem. But I got another issue. Actually I am calling this method in multi-threads to generate a bunch of paths. If use a Random outside the loop. A lot of same paths will be generated. I think it is because of the same reason why use new Random in loop generates very long sequence.
@Ryan: if you're calling this several times in a loop, you should just use one Random per thread, preferably initialized based on the seed from a globally shared Random (note: Random is not thread-safe, so you'll need locking around the shared Random).

Kirill Polishchuk · Accepted Answer · 2012-07-24 00:38:29Z

Initialize Random instance outside loop, e.g.:

public List<Node> GetPath(Node begin, Node end) { var nodes = new List<Node>(); var node = begin; var random = new Random(); while (node != end) { nodes.Add(node); var next = node.Children[random.Next(4)]; node = next; } nodes.Add(end); return nodes; }

Richard Schneider · Accepted Answer · 2012-07-24 01:41:42Z

You mention that the method is being called upon in multiple threads. A solution is to have one random number generartor per thread that is seeded by a static rng.

I've also removed the constant 4 and changed it to node.Children.Count.

static Random seed = new Random(); [ThreadLocal] static Random rng; public List<Node> GetPath(Node begin, Node end) { var nodes = new List<Node>(); var node = begin; if (rng == null) rng = new Random(seed.Next()); while (node != end) { nodes.Add(node); var next = node.Children[rng.Next(node.Children.Count)]; node = next; } nodes.Add(end); return nodes; }

Community · Accepted Answer · 2020-06-20 09:12:55Z

There are a few things working against you here. The first is that you're expecting a different number every time you ask for one, but that's not what this class does nor is it the definition of random. So, this class is in fact working correctly.

Definition of Random

Made, done, happening, or chosen without method or conscious decision: "a random sample of 100 households".
Governed by or involving equal chances for each item.

Now, this class does its best at giving each option an equal opportunity at being chosen. So, when you think of random make sure you're putting into context the definition of the term. However, remember that this class does not work like the human mind.

Now, to address the fact that you're getting zero very frequently, it's happening for two reasons. First, you are creating a new Random class in every iteration. But more importantly, your range is too small because you're expecting it to give you a different number every time on a range of only 4 options, and since it's pseudo-random just as MSDN states you're getting the same answer frequently.

I realize the reason you're only giving it 4 options, but I think you might need to reconsider the type of functionality you're looking for because it would probably lead to less frustration.

Collectives™ on Stack Overflow

C# Random does not work like a random

4 Answers 4

2 Comments

Comments

Comments

Definition of Random

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Definition of Random

Comments

Linked

Related