Optimize random number generator

If you are driven to get the absolute best performance, there are a number of things I would change. These changes will not necessarily improve the readability, but the performance will be best.

First up, creating a new Random() each time is going to slow you down. This may well be about half of your time, in fact. I recommend a static version if you can be sure you won't have threading issues, or alternatively I would recommend a ThreadLocal. In general a ThreadLocal is the better option because even though Random is thread-safe, you don't want contention when it locks one thread against another.

The second thing is "Why use a List?". Seriously, it's overkill. Use a primitive array, and preferably use char.....

String concatenation is slow, so the number += digits.get(randomDigit); is essentially the same as:

StringBuilder sb = new StringBuilder(number);
sb.append(String.valueOf(digits.get(randomDigit));
number = sb.toString();

If you insist on using String concatenation then you would be better off using:

StringBuilder sb = new StringBuilder(10);
for (...) {
 ...
 sb.append(digits.get(randomDigit));
 ...
}
return sb.toString();

Finally, when there is just one member left in the array there is no need to do the random lookup (it will always return 0), so you can just use 1 as the limit of your loop and simply append the last remaining Integer from your List.

Taking the above things in to consideration, I would recommend the following (which has a couple of other differences that I 'like'):

private static final ThreadLocal<Random> RANDOM = new ThreadLocal<Random>() {
 public Random initialValue() {
 return new Random();
 }
}
public static final String randomize() {
 final char[] digits = "0123456789".toCharArray();
 final Random rand = RANDOM.get();
 int index = digits.length;
 // Fisher-Yates.
 while (index > 1) {
 final int pos = rand.nextInt(index--);
 final char tmp = digits[pos];
 digits[pos] = digits[index];
 digits[index] = tmp;
 }
 return new String(digits);
}

EDIT

I just realized another tweak could squeeze a little more performance out too.... consider this implementation which does not even need to create an array on each invocation, and who cares what order the digits are when you are just going to reshuffle them anyway. Thus, this saves creating a char[] array each time as well. The only new instance is the returned String:

private static final class Generator {
 private final Random rand = new Random();
 private final char[] digits = "0123456789".toCharArray();
 public final String generate() {
 int index = digits.length;
 // Fisher-Yates.
 while (index > 1) {
 final int pos = rand.nextInt(index--);
 final char tmp = digits[pos];
 digits[pos] = digits[index];
 digits[index] = tmp;
 }
 return new String(digits);
 }
}
private static final ThreadLocal<Generator> GENERATOR = new ThreadLocal<Generator>() {
 public Generator initialValue() {
 return new Generator();
 }
};
public static final String randomize() {
 return GENERATOR.get().generate();
}

• \$\begingroup\$ Added an 'even-better' option. \$\endgroup\$

  rolfl

  – rolfl

  2013年11月23日 02:04:39 +00:00

  Commented Nov 23, 2013 at 2:04
• \$\begingroup\$ This could probably be optimized even further by initializing the array as it is being shuffled; see my answer below. \$\endgroup\$

  Ilmari Karonen

  – Ilmari Karonen

  2013年11月24日 08:10:32 +00:00

  Commented Nov 24, 2013 at 8:10
• \$\begingroup\$ @DaveJarvis - index != 0 will shuffle when there's just 1 thing to shuffle, index > 1 will do one less shuffle but at a (potentially slower comparison). So, question is whether 1 more time through the loop is slower than many slightly-slower comparisons. \$\endgroup\$

  rolfl

  – rolfl

  2013年12月18日 00:49:38 +00:00

  Commented Dec 18, 2013 at 0:49
• \$\begingroup\$ @rolfl: If the loop can be re-written to compare the index to 0 instead of 1, then it might save a few paltry CPU cycles. \$\endgroup\$

  Dave Jarvis

  – Dave Jarvis

  2013年12月18日 06:30:37 +00:00

  Commented Dec 18, 2013 at 6:30
• \$\begingroup\$ Oh, got it, ... thought I would edit the code, but then found I woul dhave to + 1 in the rand.nextInt(...) and also pre-check for empty-string input which may otherwise underflow.... \$\endgroup\$

  rolfl

  – rolfl

  2013年12月18日 11:38:39 +00:00

  Commented Dec 18, 2013 at 11:38

Short answer: Speed optimized? Perhaps. Memory optimized? Not that I am aware of. Improved flexibility? Yes.

• The number 10 is a magic number in your code. If you change it on one place, you need to change it everywhere else. This number should be put in a variable and could on some places be replaced with digits.size()
• You could extract some methods, one method for creating the List and one method for handling the list.
• On the method for handling the list, you can use generics (<T> in the code below) to support any kind of list.
• Use StringBuilder to create the string result.

The resulting code:

private static List<Integer> createList(int size) {
 // We are friendly towards Java and declare the *capacity* of the list here
 // because we know already how many items it should contain.
 List<Integer> result = new ArrayList<Integer>(size);
 for (int i = 0; i < size; i++) {
 result.add(i);
 }
}
private static String randomize() {
 int count = 10;
 List<Integer> digits = createList(count);
 return randomizedStringOrder(digits);
}
private static <T> String randomizedStringOrder(List<T> list) {
 Random random = new Random();
 StringBuilder result = new StringBuilder();
 for (int i = list.size(); i > 0; i--) {
 int randomIndex = random.nextInt(i);
 result.append(list.get(randomDigit));
 digits.remove(randomIndex);
 }
 return result.toString();
}

And one final improvement: Instead of getting elements randomly, we can use Collections.shuffle to shuffle the list and then simply iterate over it and add elements to the result string.

private static String randomize() {
 int count = 10;
 List<Integer> digits = createList(count);
 Collections.shuffle(digits); // this re-arranges the elements in the list
 return listToString(digits);
}
private static <T> String listToString(List<T> list) {
 StringBuilder result = new StringBuilder();
 for (T object : list) {
 result.append(object);
 }
 return result.toString();
}

• 2
  \$\begingroup\$ The random object in the last example is unnecessary. Also I'd consider having a method returning the randomized list of numbers and a different method for converting it to a string. Those are two concerns which should be separate \$\endgroup\$

  ChrisWue

  – ChrisWue

  2013年11月23日 07:50:01 +00:00

  Commented Nov 23, 2013 at 7:50
• \$\begingroup\$ @ChrisWue Thanks for the suggestion. I agree and modified the code a bit. Since the shuffling is only one line I put it in the randomize method. \$\endgroup\$

  Simon Forsberg

  – Simon Forsberg

  2013年11月23日 14:53:42 +00:00

  Commented Nov 23, 2013 at 14:53

There is not much to improve. What you are doing is basically the same as a Fisher-Yates/Knuth shuffle, so the principle is sound. It's a 75 year old algorithm that still is considered to be the most effective way to make a shuffle.

The original implementation uses an array rather than a list, and swaps item instead of removing them. That would be slightly faster, but would not normally make a noticable difference for such a small list.

You can however make use of the fact that you know that you use all items in the list. When you get to the last item, you know that there is only one left, so you don't need to pick that one by random:

 for (int i = 10; i > 1; i--) {
 int randomDigit = r.nextInt(i);
 number+=digits.get(randomDigit);
 digits.remove(randomDigit);
 }
 number+=digits.get(0);

• 1
  \$\begingroup\$ ...He's just drawing items from a list, that is not a Fisher-Yates shuffle. \$\endgroup\$

  BlueRaja - Danny Pflughoeft

  – BlueRaja - Danny Pflughoeft

  2013年11月23日 05:20:15 +00:00

  Commented Nov 23, 2013 at 5:20
• \$\begingroup\$ @BlueRaja-DannyPflughoeft: That's exactly what a Fisher-Yates shuffle is, at least as a computer implementation. The original was done using pen and paper, so if you want to be picky then it can't be implemented as a computer program at all. Have a read at the page that I linked to. \$\endgroup\$

  Guffa

  – Guffa

  2013年11月23日 09:44:53 +00:00

  Commented Nov 23, 2013 at 9:44
• 1
  \$\begingroup\$ Fisher-Yates is an algorithm for doing an in-place shuffle. It's somewhat similar to what he's doing, but it is not at all the same. \$\endgroup\$

  BlueRaja - Danny Pflughoeft

  – BlueRaja - Danny Pflughoeft

  2013年11月23日 16:42:34 +00:00

  Commented Nov 23, 2013 at 16:42
• \$\begingroup\$ @BlueRaja-DannyPflughoeft: PLEASE read the page that I linked to. The Fisher-Yates algorithm is not at all what you describe. The Knuth implementation of the algorithm is what you describe. \$\endgroup\$

  Guffa

  – Guffa

  2013年11月23日 16:49:20 +00:00

  Commented Nov 23, 2013 at 16:49
• \$\begingroup\$ @BlueRaja: The original Fisher-Yates shuffle was indeed not an in-place shuffle. One could argue that the in-place version (as popularized by Knuth) should really be named "Durstenfeld shuffle", but that name has never really caught on. (See also Stigler's law of eponymy.) \$\endgroup\$

  Ilmari Karonen

  – Ilmari Karonen

  2013年11月23日 17:14:14 +00:00

  Commented Nov 23, 2013 at 17:14

Adding a Community-Wiki Answer. Please feel free to play with the code, add your own contributions, fix issues, etc.

This contains some test code, some answers that work, and some timing data. I have added another (potentially) cheat solution to this question, which is by far the fastest solution (but all the random numbers are pre-computed ... ;-) )

I have used the aliases RL, RLv2, IK and OP to reference the rolfl, the rolfl cheat, the Ilmari Karonen and Original Poster versions

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.concurrent.atomic.AtomicInteger;
public class Randoms {
 // ============ RLv2 ==================
 private static final String[] permutations = buildPermutes();
 private static final AtomicInteger cursor = new AtomicInteger();
 private static final String[] buildPermutes() {
 long start = System.nanoTime();
 char[] initial = "0123456789".toCharArray();
 ArrayList<String> store = new ArrayList<>();
 recursePermute(new char[10], initial, store);
 Collections.shuffle(store);
 String[] ret = store.toArray(new String[store.size()]);
 System.out.printf("Generated %d unique permutations in %.2fms\n", ret.length, (System.nanoTime() - start) / 1000000.0);
 return ret;
 }
 private static void recursePermute(char[] sofar, char[] remaining, ArrayList<String> store) {
 if (remaining.length == 0) {
 store.add(new String(sofar));
 return;
 }
 final int pos = sofar.length - remaining.length;
 char[] next = Arrays.copyOf(remaining, remaining.length - 1);
 for (int i = remaining.length - 1; i >= 0; i--) {
 sofar[pos] = remaining[i];
 recursePermute(sofar, next, store);
 if (i > 0) {
 next[i - 1] = remaining[i];
 }
 }
 }
 public static final String randomizeRLv2() {
 return permutations[cursor.getAndIncrement() % permutations.length];
 } 
 // ============ RL ==================
 private static final class GeneratorRL {
 private final Random rand = new Random();
 private final char[] digits = "0123456789".toCharArray();
 public final String generate() {
 int index = digits.length;
 // Fisher-Yates.
 while (index > 1) {
 final int pos = rand.nextInt(index--);
 final char tmp = digits[pos];
 digits[pos] = digits[index];
 digits[index] = tmp;
 }
 return new String(digits);
 }
 }
 private static final ThreadLocal<GeneratorRL> GENERATORRL = new ThreadLocal<GeneratorRL>() {
 public GeneratorRL initialValue() {
 return new GeneratorRL();
 }
 };
 public static final String randomizeRL() {
 return GENERATORRL.get().generate();
 } 
 // ============ IK ==================
 private static final class GeneratorIK {
 private final Random rand = new Random();
 private final char[] digits = new char[10];
 public final String generate() {
 digits[0] = '0';
 for (int index = 1; index < digits.length; index++) {
 final int pos = rand.nextInt(index + 1);
 digits[index] = digits[pos];
 digits[pos] = (char) ('0' + index);
 }
 return new String(digits);
 }
 } 
 private static final ThreadLocal<GeneratorIK> GENERATORIK = new ThreadLocal<GeneratorIK>() {
 public GeneratorIK initialValue() {
 return new GeneratorIK();
 }
 };
 public static final String randomizeIK() {
 return GENERATORIK.get().generate();
 } 
 // ============ OP ==================
 private static String randomizeOP(){
 Random r = new Random();
 List<Integer> digits= new ArrayList<Integer>();
 String number = "";
 for (int i = 0; i < 10; i++) {
 digits.add(i);
 }
 for (int i = 10; i > 0; i--) {
 int randomDigit = r.nextInt(i);
 number+=digits.get(randomDigit);
 digits.remove(randomDigit);
 }
 return number;
 }
 // Benchmark code.
 private static abstract class RandSystem {
 final String name;
 public RandSystem(String name) {
 super();
 this.name = name;
 }
 String getName() {
 return name;
 }
 abstract String getRandom();
 }
 public static void main(String[] args) {
 System.out.println("10-digit Random Number sequences");
 RandSystem[] systems = {
 new RandSystem("OP") {
 String getRandom() {
 return randomizeOP();
 }
 },
 new RandSystem("RL") {
 String getRandom() {
 return randomizeRL();
 }
 },
 new RandSystem("IK") {
 String getRandom() {
 return randomizeIK();
 }
 },
 new RandSystem("RLv2") {
 String getRandom() {
 return randomizeRLv2();
 }
 }
 };
 for (int i = 0; i < 10; i++) {
 long[] times = new long[systems.length];
 int[] xor = new int[systems.length];
 for (int s = 0; s < systems.length; s++) {
 long start = System.nanoTime();
 int j = 1000000;
 while (--j >= 0) {
 xor[s] += systems[s].getRandom().length();
 }
 times[s] += System.nanoTime() - start;
 }
 StringBuilder sb = new StringBuilder(" ");
 for (int s = 0; s < systems.length; s++) {
 sb.append(String.format("%s: %.2fms ", systems[s].getName(), times[s]/1000000.0));
 }
 System.out.println(sb.toString());
 }
 }
}

This produces, on my machine, the results:

Generated 3628800 unique permutations in 4229.44ms
10-digit Random Number sequences
OP: 1977.11ms RL: 282.64ms IK: 209.93ms RLv2: 94.80ms 
OP: 823.61ms RL: 153.07ms IK: 160.56ms RLv2: 92.24ms 
OP: 813.06ms RL: 182.70ms IK: 180.86ms RLv2: 92.54ms 
OP: 807.10ms RL: 163.51ms IK: 163.05ms RLv2: 94.05ms 
OP: 802.40ms RL: 162.91ms IK: 163.19ms RLv2: 91.91ms 
OP: 803.28ms RL: 163.10ms IK: 162.58ms RLv2: 91.98ms 
OP: 803.49ms RL: 162.87ms IK: 162.33ms RLv2: 91.79ms 
OP: 803.23ms RL: 163.17ms IK: 163.53ms RLv2: 92.87ms 
OP: 801.11ms RL: 164.45ms IK: 162.38ms RLv2: 91.65ms 
OP: 801.21ms RL: 165.55ms IK: 162.45ms RLv2: 92.28ms 

Rolfl's code can be optimized even further by using a variant of the Fisher–Yates / Durstenfeld / Knuth shuffle that initializes the array as it's being shuffled. This saves one array read per iteration and avoids the need for the tmp variable:

private static final class Generator {
 private final Random rand = new Random();
 private final char[] digits = new char[10];
 public final String generate() {
 digits[0] = '0';
 for (int index = 1; index < digits.length; index++) {
 final int pos = rand.nextInt(index + 1);
 digits[index] = digits[pos];
 digits[pos] = (char) ('0' + index);
 }
 return new String(digits);
 }
}

(Caveat: I have neither benchmarked nor even tested this code. That said, I'd expect it to be slightly faster than the original version, although the exact performance may vary depending on compiler and JVM optimizations.)

• \$\begingroup\$ I have not benchmarked 'my' suggestions either, and, comparing your changes, I think they would be similar.... but, you should know that while I may have a tmp variable, I do not have the arithmetic in the loop (also, you will need to cast the '0' + index back to a char). So, I am pretty certain that when Java compiles the code down, my temp variable will essentially be optimized out, but the digits[pos] = (char)('0' + index); is more expensive. \$\endgroup\$

  rolfl

  – rolfl

  2013年11月24日 17:15:00 +00:00

  Commented Nov 24, 2013 at 17:15
• 1
  \$\begingroup\$ @rolfl: I did finally benchmark them and, to be honest, I'm seeing almost no difference. On my computer, you code took 55.574 seconds to run 100 million iterations (after a 1 million iteration burn-in); mine did it in 54.132 seconds, a difference which I'm willing to ascribe to random variation. \$\endgroup\$

  Ilmari Karonen

  – Ilmari Karonen

  2013年11月24日 20:23:24 +00:00

  Commented Nov 24, 2013 at 20:23
• \$\begingroup\$ Not wholly unexpected.... of interest, did you compare with the OP's code (Just curious...)? \$\endgroup\$

  rolfl

  – rolfl

  2013年11月24日 21:22:29 +00:00

  Commented Nov 24, 2013 at 21:22
• \$\begingroup\$ I have added a 'community-wiki' answer that puts the various solutions 'head-to-head'. I also added 'the fastest' solution as a precomputed options. Your modification compares well.... pretty much comes down to which solution is cosmetically better rather than which one is faster..... \$\endgroup\$

  rolfl

  – rolfl

  2013年11月24日 23:49:08 +00:00

  Commented Nov 24, 2013 at 23:49

• java
• optimization
• random