Optimize random number generator

Question

I have a method that generates a 10 digit random number where each digit occurs only once.

eg:

0123456789
3645720918

Is there any way this method could be optimized/improved?

    private static String randomize(){
        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;
    }

Answer 1

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();
}

Answer 2

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();
}

Answer 3

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);

Answer 4

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 

Answer 5

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.)