Testing a Random number generator

Question

Firstly, would appreciate some code-review feedback, from a TDD and design perspective.

Secondly, what are your thoughts on implementing test case: testNumbersAreUnique()? The fact that API returns a Set of immutable objects means elements will be unique, but just wanted to know your thoughts. The reason I used a do-while as against a while or for loop (and iterate ‘x’ times to populate ‘x’ Random numbers) is to ensure the set has correct number of elements (which will of course be unique) even if the random number gives something that is already existing in the Set.

The problem: Lottery Generator

The goal of the program is to generate ‘x’ distinct lottery numbers within a given range 1 to ‘N’. Both x and N are int for simplicity.

Following is my code. I wrote a controller, which will call service layer to fetch ‘x’ distinct lottery numbers:

public class Controller {
 private LotteryGeneratorService lotteryGeneratorService;
 @RequestMapping(method=RequestMethod.GET)
 public Set<Integer> getLotteryNumbers(int x){
 lotteryGeneratorService = new LotteryGeneratorService();
 return lotteryGeneratorService.generateNRandom (x);
 }
}

This is the Service class:

public class LotteryGeneratorService {
private Set<Integer> set = new HashSet<>();
private static int generateRandomInt(){
 Random random = new Random();
 return random.nextInt(N);
}
public Set<Integer> generateNRandom(int x){
 int tmp; 
 do{
 tmp =generateRandomInt(); 
 if(tmp!=0)
 set.add(tmp);
 }
 while(set.size()<x);
 return set;
}
public int getSizeOfRandomlyGeneratedSet(){
 return set.size();
 }
}

The tests:

public class LotteryTest {
LotteryGeneratorService lotteryGeneratorService;
int N;
@Before
public void setup() {
 lotteryGeneratorService = new LotteryGeneratorService();
 N=100;
}
@After
public void tearDown() {
 lotteryGeneratorService = null;
}
@Test
public void testNumberOfNumbersGeneratedIsCorrect() {
 assertEquals(6, lotteryGeneratorService.generateNRandom(6).size());
}
@Test
public void testRangeIsCorrect() {
 Set<Integer> set = lotteryGeneratorService.generateNRandom(6);
 for (int i : set) {
 assertTrue(i >= 1 && i <= N);
 }
} 
@Test
public void testNumbersAreUnique() {
 //..?
 }
}

• Tunaki: Where is N defined in return random.nextInt(N); inside LotteryGeneratorService?

Answer 1

About LotteryGeneratorService

The goal of the method generateRandomInt is to generate a random integer:

private static int generateRandomInt(){
 Random random = new Random();
 return random.nextInt(N);
}

This method creates each time it is called a new Random object, which is inefficient. It is better to create the Random object just once, and reuse it each time a new random integer is needed.

This does raise a new concern: this class would benefit from being thread-safe (as it is called by Spring @Controller methods). While Random is thread-safe, it may perform poorly when used concurrently, and it would be preferable to use ThreadLocalRandom in this case:

When applicable, use of ThreadLocalRandom rather than shared Random objects in concurrent programs will typically encounter much less overhead and contention.

As such, consider refactoring this method to:

private static int generateRandomInt() {
 return ThreadLocalRandom.current().nextInt(N);
}

which makes it perform well concurrently and doesn't create unnecessary objects over and over.

I suggest adding documentation to this method so that it's clearer the range of the random integers returned. Currently, it returns random integers between 0 and N-1 included.

The second method is generateNRandom which generates x distinct random integers. First of all, its name is a bit misleading with regard to the parameters: it generates N random integers, but takes x as input. The current implementation can be improved a lot:

• It generates a random integer between 0 (included) and N (excluded), but then it disregards 0 if it was generated. This could be solved by using the right bounds when fetching the random integer in the first place. For example, if you want to generate a random integer starting from 1 instead of 0, you can modify the generateRandomInt method to have ThreadLocalRandom.current().nextInt(1, N) instead.
• It loops until x distinct numbers have been generated. This works well when there's a large pool of possible numbers, because more often than not, you'll pick a number that hasn't been generated yet. But when this pool starts to decrease, the time it takes to find one that hasn't been generated will increase dramatically. Consider you have a range of possible numbers from 0 to 10, and you want 10 distinct numbers; by the time you have got 9 of them, you'll have 1/10 chance of getting the 10th one, when this could be deduced automatically, since there's only one possibility remaining anyway.

There's a better approach that doesn't involve "fetch or try again". Since you have a range of N integers, and you want x distinct in it, you can shuffle that range once, and then take the first x elements. They are guaranteed to be distinct, since the source elements were distinct, and they were only shuffled; and you are guaranteed to have x of them. So you could have:

public Set<Integer> generateNRandom(int x) {
 List<Integer> list = new ArrayList<>(x);
 for (int i = 0; i < N; i++) {
 list.add(i);
 }
 Collections.shuffle(list);
 return new HashSet<>(list.subList(0, x));
}

This runs in linear-time, always. (Note that list could only be created once per N, so the creation of that list could be done outside of the method as well.). Also note that with such an implementation, you don't even need the generateNRandom method anymore.

About Controller

This is a Spring Controller, as noted by the RequestMapping annotation. In this case, you shouldn't create instances of LotteryGeneratorService yourself with

lotteryGeneratorService = new LotteryGeneratorService();

Let Spring inject that for you. Annotate LotteryGeneratorService with @Component (or @Service) and autowire it inside the controller with

@Autowired
private LotteryGeneratorService lotteryGeneratorService;

This makes the controller testable, by possibly injecting a mock service.

About LotteryTest

You do not need to set your variables to null:

@After
public void tearDown() {
 lotteryGeneratorService = null;
}

This doesn't help garbage collection, and clutters the code a bit. You should just get rid of that.

Also, since the method returns a Set, the test testNumbersAreUnique is not needed: it cannot contain duplicates, by definition of a set, so the test would be useless.

Answer 2

You should not be testing the randomness of your class. See this answer on Software Engineering SE.

I don't think unit tests are the right tool for testing randomness. A unit test should call a method and test the returned value (or object state) against an expected value. The problem with testing randomness is that there isn't an expected value for most of the things you'd like to test. You can test with a given seed, but that only tests repeatability. It doesn't give you any way to measure how random the distribution is, or if it's even random at all.

Instead what you could do is mock the random number generator and make it return non-unique numbers. That way you can test that your class correctly handles them without relying on randomness.

For instance, you could create an alternative constructor for LotteryGeneratorService that takes a random number generator interface as parameter, that can either be Random or your own RandomMock.

On the topic of Random: you shouldn't create a new object for each invokation of nextInt(). Doing so will require the system to generate a new seed each time, and might actually decrease the entropy (e.g. if seed is time and two Random objects are created within the same timestamp).

Answer 3

Your test methods should always show the 3 parts arrange, act and assert visually. The names of the additional variables needed for this convey important information for the readers of your tests

after you followed @jacwah's advice you should explicitly test what your class does:

@Test 
public void generateNRandom_distinctRandoms_returnAll()
 // arrange
 when(yourRandomMock.nextInt(any(int()).tehReturn(1,2,3,4,5,6);
 // act
 int countOfNumber = lotteryGeneratorService.generateNRandom(6).size();
 // assert
 assertThat("all numbers returned",countOfNumber,equalTo(6));
}
@Test 
public void generateNRandom_oneRandomDuplicated_duplicateRemoved()
 // arrange
 when(yourRandomMock.nextInt(any(int()).tehReturn(1,2,3,4,5,6,1);
 // act
 Set<Integer> numbers = lotteryGeneratorService.generateNRandom(6);
 // assert
 assertThat("all numbers returned",countOfNumber,equalTo(6));
 for(int i=1; i<=6;i++) 
 assertTrue(i+ "is returned", numbers.contains(Integer.valueOf(i)); 
}