Quick and Efficient way to generate random numbers

问题:

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

Additional Details: These numbers are used to create a list of random numbers from 0-99 without repetition and such that every number in the range 0-99 exists in the list (In other words, the list contains 100 unique elements in the range 0-99).

Generating Random Numbers [Things already tried!]

1. I have an ArrayList of numbers from 0-100. I generate a random number and use it as an index which is used to pop out an element from the ArrayList.
2. I have 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 second approach, I replaced the second for loop with Collections.shuffle(arr).

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

1. What is the fastest way to generate random numbers?
2. What is the fastest way to generate the list of random numbers as described above?

PS:

1. I found Collections.shuffle() to be slower than the first approach
2. Someone suggested me using rngd to generate random numbers from hardware in Unix. Has anyone tried this before? How do you do that?

回答1:

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

If you are happily running on Java 7, simply use ThreadLocalRandom. Look carefully, there is a version of shuffle() taking Random instance explicitly:

Collections.shuffle(arr, threadLocalRandom);

where threadLocalRandom is created only once.

On Java 6 you can simply create a single instance of Random once per thread. Note that you shouldn't create a new instance of Random per run, unless you can provide random seed every time.

回答2:

Part of the problem might be the overhead of the Integer boxing and unboxing. You might find it helpful to reimplement the Fisher-Yates shuffle directly on an int[].

回答3:

My approach woul be to generate the numbers with the Math.random() method as in the example here and initialize the list via a static init block like this:

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

Hope this helped, have Fun!

回答4:

To shuffle an array 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 Fischer and Yattes algorithm.