Generating unique random number is increasing complexity and might cause performance overhead?

Question

Implementation:

private static List<Integer> getRandomDistribution(List<String> unsortedList, int max) {
    Random random = new Random();
    List<Integer> indexContainer = new ArrayList<>();
    for (int i = 0; i < max; i++) {
        int index = random.nextInt(max);
        // Below is what I don't like, 
        if (indexContainer.contains(index)) {
            i--;
        } else {
            indexContainer.add(index);
        }
    }
    return indexContainer;
}

So basically its saying that, until I don't find the required unique random number. I will continue the loop, what could happen is it might keep looping for a long time thus increasing the overhead.

Problems:

int index = random.next(max) is what should decide the randomness, also I will have to maintain the ordering. That why I have used List
Secondly, i-- is where I am stuck, because frankly I don't like the implementation.

NOTE: I will also have to maintain the order within the indexContainer.

Just make a `Set` out of the `List` and you´ll have unique values. — SomeJavaGuy, Jul 11 '16 at 12:21
what is the range of max? why not shuffle the list at the end? — SMA, Jul 11 '16 at 12:22
The shuffle solution proposed by @Eran is a precise solution to the question *as presented*. Apparently it does not answer the question you actually have, so you need to ask a different question. In particular, you need to be explicit that what you need is a random sample of some size `k` from the range `[0, max)`, rather than a random permutation of the entire range, which is what your example code attempts to produce. — rici, Jul 11 '16 at 15:50
Another solution would be to use a Linear Feedback Shift Register. See http://stackoverflow.com/a/694303/56778, for example. You can use that to return your random index. Also note that this approach does not require you to generate and shuffle a huge array of values. Note also that the LFSR, although "good enough" for many applications of pseudo-random numbers, is certainly not a cryptographic quality RNG. — Jim Mischel, Jul 11 '16 at 16:45

Eran · Answer 1 · 2016-07-11T12:31:05.113

4

Since you are generating a permutation of all the numbers from 0 to max-1, it would make more sense to populate the List with all the numbers from 0 to max-1 and then call Collections.shuffle(list).

Random random = new Random();
List<Integer> indexContainer = new ArrayList<>();
for (int i = 0; i < max; i++) {
    indexContainer.add(i);
}
Collections.shuffle(indexContainer, random);

edited Jul 11 '16 at 12:31

answered Jul 11 '16 at 12:23

Eran

387,369
54
702
768

That won't work, **Random random = new Random()** is what should decide the randomness of the **indexContainer**. My bigger problem is, **i--** where the loop repeats itself. – iamfazn Jul 11 '16 at 12:28
@Faz.Max so use `void shuffle(List> list, Random rnd)` instead. – Eran Jul 11 '16 at 12:30
@Faz.Max My suggestion avoids the i-- problem. – Eran Jul 11 '16 at 12:32
1

This is the actual index, int index = (int) (Math.floor(Math.pow(max * random.nextDouble(), 0.25))); the above suggestions doesn't hold well in this case. Where index will decide the random value. @Eran – iamfazn Jul 11 '16 at 12:37
@Faz.Max Is there a reason for such a complicated computation? This random index won't generate all the numbers between 0 and max-1, so your loop will never terminate (unless you change its `i < max` condition). – Eran Jul 11 '16 at 12:42
Agreed, but thats not the case always. Assuming the max value is mostly a finite number. So, how should I even approach the problem ? – iamfazn Jul 11 '16 at 13:24

Generating unique random number is increasing complexity and might cause performance overhead?

1 Answers1