3
\$\begingroup\$

I needed an iterator that produced random numbers, never repeating them, in a specified range of 0..max-1 (index for a collection). When the numbers are exhausted it should not have a next anymore.

The simplest way might be to shuffle an ArrayList and make an iterator. But in typical usage, I will want only 4-5 unique random numbers, from a total in the region of 100. So shuffle seemed too CPU-heavy. And here is the class I came up with. It is written in Java 8 (the requirement of version 8 is acceptable in my case).

import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class NonRepeatingRandom implements Iterator<Integer> {

    private List<Integer> unused;
    private Random random;

    public NonRepeatingRandom(int max) {
        unused = IntStream.range(0, max).boxed().collect(Collectors.toList()); 
        random = new Random();
    }

    @Override
    public boolean hasNext() {
        return ( unused.size() > 0 );
    }

    @Override
    public Integer next() {
        int size = unused.size();
        if ( size==0 ) {
            throw new java.util.NoSuchElementException();
        }
        int idx = random.nextInt(size);
        int result = unused.get(idx);
        unused.remove(idx);
        return result;
    }

}

I would appreciate comments on this code.

\$\endgroup\$
  • \$\begingroup\$ I would add random numbers to a Set, check if there are enough in it and crate the iterator from the set... \$\endgroup\$ – Timothy Truckle Apr 28 '17 at 12:18
  • \$\begingroup\$ @TimothyTruckle this would lead to repeated generation of randoms until they are not in the set. Definitely a no. \$\endgroup\$ – Mikhail Ramendik Apr 28 '17 at 14:44
  • \$\begingroup\$ @MikhailRamendik generating a random number from Random is like 10-20 instructions the probability of a retry in the case @Paparazzi said is 5% then a second retry is 0.25%, the infinite sum of retries is bounded by 6% performance cost which is less than 1 extra instruction on average. \$\endgroup\$ – Emily L. Apr 28 '17 at 14:55
  • 2
    \$\begingroup\$ Wow all that code, when all you need is shuffle and take the top few elements of the shuffled array, because "shuffle seemed too CPU heavy" on 100 elements? I'm always confused why future readability and maintainability is often given such low priority over minor performance considerations \$\endgroup\$ – Brad Thomas Apr 28 '17 at 17:23
  • 1
    \$\begingroup\$ @BradThomas A shuffle is not necessarily less code or more readable. \$\endgroup\$ – paparazzo Apr 28 '17 at 17:49
5
\$\begingroup\$

Looks pretty reasonable. Just a few minor issues:

    public NonRepeatingRandom(int max) {

That's fine for general-purpose use, but you should consider adding a constructor which takes (int, Random) for testing purposes.


    @Override
    public boolean hasNext() {
        return ( unused.size() > 0 );
    }

I generally recommend favouring isEmpty() over size() == 0. For many collections isEmpty() just calls size(), but for some it is much more efficient, so it's a good habit to always use isEmpty().


        int idx = random.nextInt(size);
        int result = unused.get(idx);
        unused.remove(idx);

This is the biggest problem, although for your typical use case it might be relatively minor because it doesn't sound like this iterator is going to be a bottleneck.

Removing a random element from a list takes \$O(n)\$ time. But since you don't care about the order of the elements in the list, you could copy the last element to position idx and then delete the last element in \$O(1)\$ time.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Well, if I did not care about performance at all I'd just use a shuffled list to make an iterator automatically. And I was not aware that removing a random element was expensive. So what is the right way to remove one in my case? unused.set(idx,unused.get(size-1)); unused.remove(size-1); ? \$\endgroup\$ – Mikhail Ramendik Apr 28 '17 at 13:22
  • 1
    \$\begingroup\$ @MikhailRamendik, if you remove a random element from an ArrayList then it has to copy everything after that element to the previous index, taking linear time on average; and if you remove a random element from a LinkedList then it takes linear time on average to find the correct node. The code in your comment is correct. \$\endgroup\$ – Peter Taylor Apr 28 '17 at 14:49
  • \$\begingroup\$ Don't need to remove at all. Just copy and decrement the index to the list by 1. \$\endgroup\$ – paparazzo Apr 28 '17 at 15:38
  • \$\begingroup\$ @Paparazzi, I'm not sure exactly what you mean by decrement the index to the list by 1, but I think it involves adding a field to the iterator and changing the implementation of hasNext() as well as next(). Removing the element from the list is an elegant way of tracking how many elements have not yet been returned. \$\endgroup\$ – Peter Taylor Apr 28 '17 at 15:40
  • 1
    \$\begingroup\$ OK remove is elegant. Not as efficient as just decrement an index so last is no longer considered. \$\endgroup\$ – paparazzo Apr 28 '17 at 15:44
2
\$\begingroup\$

Okay so I'm kind of gleaning from your code and description that you want to visit all numbers in the range \$[0,n]\$ in a (pseudo) random order without visiting any number twice. I'm saying pseudo random here because you are using Random which is just a pseudo random generator.

You can use something called a Linear Congruential Generator (LCG). This is a type of well known pseudo random number generator, in fact java.util.Random is an LCG.

Funny thing about LCGs is that they have a period and if you choose your constants suitably you can pick that period and guarantee that you will not have any repeats in the period, the PRNG is said to have a full period.

The general form of the algorithm is: $$x_{k+1} = (a*x_k+c) \%n$$ where \$0<n\$ and \$0<a,c<n\$. The value of \$x_0\$ is simply chosen as a seed value.

If \$n\$ and \$c\$ are co-prime, \$a-1\$ is evenly divisible by all prime factors of \$n\$ and \$a-1\$ is evenly divisible by 4 if \$n\$ is divisible by 4. Then the LCG will have a full period.

I did a test here. I was a bit sneaky: to make sure \$c\$ and \$n\$ are coprime, I simply picked \$c\$ to be a very large prime. In fact if you pick \$c\$ as a prime number such that \$c\$ > \$\text{INT_MAX}/2\$ then \$c\$ and \$n\$ will always be co-prime unless \$c=n\$ in which case simply have two such \$c\$ values that you pick between. To make \$a-1\$ evenly divisible by all the prime factors of \$n\$ and 4 if \$n\$ is divisible by 4, I simply pick \$a=n+1\$.

Note that these values do not fulfill the conditions as listed on Wikipedia: \$0<a,c<n\$. However they seem to work just fine. So consider it a word of caution to either check up the maths yourself to see if this is OK or to use a more robust way of selecting \$a\$ and \$c\$.

At any rate using an LCG will be the most efficient in terms of memory and computation provided that you can choose the coefficients easily.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This sounds like a good idea in principle, but I am definitely not enough of a mathematician to rely on a DIY implementation of a pseudorandom generator and expect it to not repeat without a safety check, probably in the form of a set. The safety check would negate the performance gain. \$\endgroup\$ – Mikhail Ramendik Apr 28 '17 at 14:41
  • \$\begingroup\$ @MikhailRamendik Actually if you use a HashSet the safety check will be \$O(1)\$ time which is faster than your current code which is \$O(n)\$ due to the call to remove(). The memory requirement will still be the same at \$O(n)\$. So it's still better than what you have now :) \$\endgroup\$ – Emily L. Apr 28 '17 at 14:44
  • \$\begingroup\$ Upon re-reading the description I don't even understand what "m" is supposed to be... really not enough of a mathematician - it's probably obvious to a professional? \$\endgroup\$ – Mikhail Ramendik Apr 28 '17 at 14:52
  • \$\begingroup\$ @MikhailRamendik Oops sorry my bad, I kind of switched from \$n\$ to \$m\$ in the middle without noticing. I've fixed it. \$\endgroup\$ – Emily L. Apr 28 '17 at 14:58
  • \$\begingroup\$ ...but now n has two meanings (max and index of x) and I'm not sure which is which in the formula? \$\endgroup\$ – Mikhail Ramendik Apr 28 '17 at 15:05
1
\$\begingroup\$

In regards to speed / efficiency the remove(idx); is the weakness.

Use hasNext() in checking for the Next exception.

A couple options:

  1. Don't create the list up front. Use a HashSet to track used numbers. Call random and check the HashSet for used numbers. If you are only producing a small fraction of the range then this is the most efficient. Even producing 1/3 the range this is most efficient (from my experience). Can enhance with reduce the range if you produce the first or last. For this in C#.
  2. Create the List but track the index. Based on random produce the number and then copy the last active value (index) in the List to the random. Then index--. Use index as the range for the random and for any left. This removes the call to remove(idx);.

    public class NonRepeatingRandom implements Iterator<Integer> {    
    
    private List<Integer> unused;
    private Random random;
    private Integer size;
    
    public NonRepeatingRandom(int max) {
        unused = IntStream.range(0, max).boxed().collect(Collectors.toList()); 
        random = new Random();
        size = max;
    }
    
    @Override
    public boolean hasNext() {
        return ( size > 0 );
    }
    
    @Override
    public Integer next() {
        if ( !hasNext() ) {
            throw new java.util.NoSuchElementException();
        }
        int idx = random.nextInt(size);
        int result = unused.get(idx);
        unused[idx] = unused[size-1];
        size--;
        return result;
    }
    }
    
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ With respect to unused[idx] = unused[size-1];, has Java added C#-style indexers? \$\endgroup\$ – Peter Taylor May 22 '18 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.