Generate random and unique array of int values for a given size

I need to generate an array of int values for a given size, the values should be random and unique. the following implementation is "ok" for small values [1,10k], I would like to get some feedback on better implementation

/**
 * Generate an array of random & unique values in the interval [0,desiredSize*3]
 * To use only for small arrays with size in [1,50k]
 * for an array of 1k time: 0.01s
 * for an array of 10k time: 0.3s
 * for an array of 50k time: 8s 
 * @param desiredSize
 * @return
 */
public int[] generateRandAndUniq(int desiredSize) {
    int[] arrayResult = new int[desiredSize];
    Random rand = new Random();
    arrayResult[0]= rand.nextInt(desiredSize);
    int counter = 0;
    while (counter max)
            max=v;
    }
    return max;
}

While your code looks right, there are two concerns I have with it.

The first is the somewhat arbitrary use of desiredSize * 3 as the limit of the random numbers. Why that value?

The performance issue you have is the nested looping you have first to generate the values, and then inside you loop again to check for duplicates. You can reduce the inner loop significantly by using a Set in combination with the array to check for uniqueness. The set will consume more memory, but it will allow a check without any looping (it will reduce your \$O(n^2)\$ algorithm to \$O(n)\$).

The code would look something like:

public static int[] generateRandAndUniqSet(int desiredSize) {
    int[] arrayResult = new int[desiredSize];
    Set uniq = new HashSet<>();
    Random rand = new Random();
    int counter = 0;
    while (counter < desiredSize) {
        int randValue = rand.nextInt(desiredSize*3);/* a larger interval! */
        if (uniq.add(randValue)) {
            arrayResult[counter++] = randValue;
        }
    }
    return arrayResult;
}

That Set change will have a significant impact on your performance.... but, is there a better way?

Assuming your limit of desiredSize * 3 and assuming a relatively small dataset (less than a million, or so), then a better option would be for you to:

• create an array of size desiredSize * 3

• populate it with consecutive numbers [0, 1, 2, 3, 4, ....., desiredsize * 3 - 1]

• shuffle it using a Fisher-Yates shuffle.

• return the first desiredSize elements from the shuffled array.

This would require no duplicate-checking at all.

I put together some code to demonstrate this:

public static final int[] generateRandAndUniqRGL(int desiredSize) {

    // generate set of sequential values from 0 ... desiredSize * 3
    int[] set = IntStream.range(0,  desiredSize * 3).toArray();

    // shuffle them
    int index = set.length;
    // Fisher-Yates.
    Random rand = new Random();
    while (index > 1) {
        final int pos = rand.nextInt(index--);
        final int tmp = set[pos];
        set[pos] = set[index];
        set[index] = tmp;
    }

    // return the first batch of them
    return Arrays.copyOf(set, desiredSize);
}

I timed this method against yours for a few sizes of data here in ideone: https://ideone.com/MrwWLV

Note the timing results:

OP function for 10 input took  0.012ms
RL function for 10 input took  0.016ms
OP function for 100 input took  0.054ms
RL function for 100 input took  0.032ms
OP function for 1000 input took  3.896ms
RL function for 1000 input took  0.603ms
OP function for 10000 input took 164.937ms
RL function for 10000 input took  1.750ms

StackExchange Code Review Q#156191, answer score: 7