dimanche 10 décembre 2017

How to efficiently build a random String with a custom alphabet?

I have an alphabet with an amount of c characters and want to create random Strings of length n with that alphabet.

As an example, let's say the alphabet consists of the letters a-w (so c = 23) and the generated Strings should have a length of n = 67.

An intuitive but also naive approach to generate such a String could look like this:

String alpha = "abcdefghijklmnopqrstuvw";
int c = alpha.length();
int n = 67;

SecureRandom random = new SecureRandom();
StringBuilder sb = new StringBuilder();

for(int i = 0; i < n; i++) {
    int nextPosition = random.nextInt(c);
    sb.append(alpha.charAt(nextPosition));
}

System.out.println(sb.toString());

While this works, I have a feeling that I'm wasting too much entrophy. In this example, I'm asking the RNG n = 67 times for another number, and all of that just for generating one single String.

  • Wouldn't it be more efficient (...entrophy saving) to call the RNG a much smaller amount of times and make better use of the returned values? E.g. calling the RNG only once with the method nextBytes(byte[] bytes) and a byte array just large enough to create a String of length 67?
  • But in the latter case, I don't know how to map the random byte array to the desired String. It would be easy if one character had a size of one byte (or the multiple of one byte), so for n = 67 I could ask the RNG for 67 random bytes and then just map directly from each byte in the array to one character. However, with an alphabet of size c = 23, each character has only five bytes, without even making use of all the five bytes - if we enumerate all the characters from above, then the first character 'a' has a binary value of 00000 whereas the last character 'w' has a binary value of 10110 (it's not a coincidence that I've chosen prime numbers for n and c, it really should work in any case).



Aucun commentaire:

Enregistrer un commentaire