CODEWITHSUNDEEP
javarandomarraylist
Ryan Sayles
Ryan Sayles

Reputation: 3441

Random vs Shuffle

I have an ArrayList which I want to grab a random value from. To do this I thought of two simple methods:

Method 1: Uses Random to generate a random number between 0 and the size of the ArrayList and then use that number for arrayList.get(x)

Method 2: Use arrayList.shuffle() and then arrayList.get(0).

Is one method preferable to the other in terms of randomness, I know it is impossible for one to be truly random but I want the result to be as random as possible.

EDIT: I only need one value from that ArrayList

Upvotes: 1

Views: 1882

Answers (5)

Rainbolt
Rainbolt

Reputation: 3660

Randomness depends on two factors, the algorithm (a.k.a the "generator") and the seed.

  • What generators does each method use?

The second overload of Collections.Shuffle() actually accepts a seeded Random. If you choose the default overload, it uses a Random anyway, as specified in the Javadoc. You're using a Random no matter what.

  • Are the generators seeded differently?

Another look at Random in the Javadoc shows that it is seeded by with some time value unless you specify a seed. Shuffle doesn't specify a time if you look at the implementation. You're using the default seed unless you specify one.

Because both use Random and both use the same default seed, they are equally random.

  • Which one has a higher time complexity?

Shuffling a list is O(n) (the Javadoc for Shuffle actually specifies linear time). The time complexity of Random.nextInt() is O(1). Obviously, the latter is faster in a case where only one value is needed.

Upvotes: 1

David Z
David Z

Reputation: 131640

To answer your direct question: neither one of these is "more random" than the other. The results of the two methods are statistically indistinguishable. After all, the first step in shuffling an array is (basically) picking a number between 0 and N-1 (where N is the length of the array) and moving that element into the first position.

That being said, there are valid reasons to pick one or the other, depending on your specific needs. Jeroen's answer summarizes those well.

Upvotes: 5

Fred Larson
Fred Larson

Reputation: 62093

If you just want one random selection, use Method 1. If you want to get a sequence of random selections with no duplicates, use Method 2.

Upvotes: 1

Jeroen Vannevel
Jeroen Vannevel

Reputation: 44449

It depends on the context.

Benefits of shuffling:

  • Once a shuffle, then just sequential grabbing
  • No repeated values

Benefits of randomizing:

  • Great for a small amount of values
  • Can repeat values

Upvotes: 9

Drifter64
Drifter64

Reputation: 1123

I would say the random number option is the best (Method 1).

Shuffling the objects takes up extra resources, because it has to move all of the objects around in the ArrayList, where generating a random number gives you the same effect without needing to use CPU time to cycle through array elements!

Also, be sure to generate a number between 0 and the size MINUS ONE. :)

Upvotes: 1

Related Questions