3
\$\begingroup\$

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 < desiredSize) {
        int randValue = rand.nextInt(desiredSize*3);/* a larger interval! */
        int[] tempArray= new int[counter+2];
        System.arraycopy(arrayResult, 0, tempArray,0, counter);
        tempArray[counter+1]=randValue;
        if(!checkDuplicate(tempArray)){
            arrayResult[counter]=randValue;
            counter++;
        }
    }
    return arrayResult;
}

public boolean checkDuplicate(int[] arr) {
    boolean[] bitmap = new boolean[maxValueInArray(arr)+1]; /* just put a big number to avoid looping to get the max value? */
    for (int v : arr) {
        if (!bitmap[v]) {
            bitmap[v] = true;
        } else {
            return true;
        }
    }
    return false;
}


public int maxValueInArray(int[] arr){
    int max=-1;
    for(int v:arr){
        if(v>max)
            max=v;
    }
    return max;
}
\$\endgroup\$
  • \$\begingroup\$ Why copy the array to look for a duplicate? Why not just use hashset for O(1) check for duplicate? \$\endgroup\$ – paparazzo Feb 24 '17 at 12:25
  • \$\begingroup\$ I didn't thought about it \$\endgroup\$ – M.Blaiz Feb 24 '17 at 12:36
  • \$\begingroup\$ This is C# and not the same question but how to generate unique random softwareengineering.stackexchange.com/questions/334105/… \$\endgroup\$ – paparazzo Feb 24 '17 at 14:10
6
\$\begingroup\$

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<Integer> 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:

  1. create an array of size desiredSize * 3
  2. populate it with consecutive numbers [0, 1, 2, 3, 4, ....., desiredsize * 3 - 1]
  3. shuffle it using a Fisher-Yates shuffle.
  4. 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
\$\endgroup\$
  • \$\begingroup\$ Edited to add code. \$\endgroup\$ – rolfl Feb 24 '17 at 12:16
  • \$\begingroup\$ the idea of 'desiredsize * 3' is to enlarge the interval to avoid that random picks a duplicate, but if the value is too large we loose in checking duplicates. Your implementation using random position is brilliant. \$\endgroup\$ – M.Blaiz Feb 24 '17 at 12:40

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.