Fast and efficient way to generate random numbers in Java

Question

I am writing a multi-threaded Java program that generates many random numbers.

Additional Information: These numbers are used to create a list of random numbers from 0 to 99 without repeating and for each number in the range 0-99 in the list (In other words, the list contains 100 unique elements in the range 0-99).

Random Number Generation [things have already tried!]

• I have an ArrayList of numbers from 0 to 100. I generate a random number and use it as an index, which is used to push an element from an ArrayList .
• I used Collections.shuffle() .

Here is the code for approach 1:

 ArrayList<Integer> arr = new ArrayList<Integer>(); for (int i = 0; i < N; i++){ arr.add(i, i); } for(int i=0; i<N; i++){ int indx = rand.nextInt(arr.size()); res.add(arr.get(indx)); arr.remove(indx); } 

For the second approach, I replaced the second for loop with Collections.shuffle(arr) .

Since generating a list of random numbers is the most expensive part of my algorithm, I want to optimize it. This leads me to questions:

• What is the fastest way to generate random numbers?
• What is the fastest way to generate a list of random numbers as described above?

PS:

• I found Collections.shuffle() be slower than the first approach
• Someone suggested I use rngd to generate random numbers from hardware on Unix. Has anyone tried this before? How do you do this?

Answer 1

I think the problem with Collections.shuffle() is that the default is Random , which is a thread-safe singleton. You say that your program is multi-threaded, so I can imagine synchronization in Random , which is the neck of the bottle.

If you are happily working on Java 7, just use ThreadLocalRandom . Look carefully, there is a version of shuffle() by explicitly typing Random :

 Collections.shuffle(arr, threadLocalRandom); 

where ThreadLocalRandom is created only once.

In Java 6, you can simply create one instance of Random once per thread. Please note that you should not create a new instance of Random for each run, unless you can provide a random seed every time.

Answer 2

Part of the problem may be the overhead of the whole box and unboxing. You may find it helpful to override the Fisher-Yates shuffle directly on int[] .

Answer 3

My approach is to generate numbers using the Math.random() method, as in the example here , and initialize the list through a static initialization block for example:

 private static List<int> list = new ArrayList<int>(); static { for(int i = 0; i < 100; i++) { // randomize number list.add(number); } } 

Hope this helps, have fun!

Answer 4

To shuffle an array of a of n elements (indices 0..n-1):

 for i from n − 1 downto 1 do j ← random integer with 0 ≤ j ≤ i exchange a[j] and a[i] 

Check the Fisher and Yatt algorithm .