1
\$\begingroup\$

I have created a utility class which allows random iteration over an array. The idea is pretty much a divide and conquer approach.

public class RandomIterator<T> implements Iterator<T> {

    //recursion stack
    private final LinkedList<int[]> offsets = new LinkedList<>();
    private final ThreadLocalRandom random = ThreadLocalRandom.current();
    private final T[] words;

    public RandomIterator(T[] words) {

        this.words = words;

        //add default lower and upper bound
        offsets.addLast(new int[]{0, words.length});
    }

    @Override
    public boolean hasNext() {
        return !offsets.isEmpty();
    }

    @Override
    public T next() {

        final int[] offset = offsets.removeFirst();

        final int upperBound = offset[1];
        final int lowerBound = offset[0];

        final T toReturn;

        if (lowerBound + 1 == upperBound) {

            //range contains only 1 index
            toReturn = words[lowerBound];
        } else {

            final int randomIndex = random.nextInt(lowerBound, upperBound);
            toReturn = words[randomIndex];

            if (randomIndex + 1 < upperBound)
                offsets.addLast(new int[]{randomIndex + 1, upperBound});
            if (randomIndex > lowerBound)
                offsets.addLast(new int[]{lowerBound, randomIndex});
        }

        return toReturn;
    }
}

You can see this in action here. It works fine, but I feel its not truly random. The original array used in the link above is a lexicographically sorted array of 2000 latin words. As we can see in the output there are multiple groups of words which appear to be in order. For e.g.. a range like this occurred in one run.

aberam
abeas
abditi
abdidimusque
abdideris
abdiderim
abdideras
abdideramus
abalienato

Suggestions will be much appreciated :)

EDIT

It seems I did not express my thoughts properly. I do not want repetitions during the random iteration. The idea is basically to cover all the array indices once, but do it randomly. The example linked above does this. It uses the same lexicographically sorted array of latin words on each run, and randomly iterates it and writes out each word to the outputstream. Randomness in the output can be defined as probability of occurrence of words with very small "distance" from each other. For eg. the words "quote" and "quoted" have very small distance. My requirement is that word with very small distance should not occur close to each other in the output (random).

When I say the output is not truly random, I mean that I can observe groups of contiguous words in the output which have very small distance from each other. Hence the output gives the expression of not being truly random.

\$\endgroup\$
  • \$\begingroup\$ I feel [it's] not truly random - write down what is: every element equally likely to be visited next, every element not yet visited, not recently, … \$\endgroup\$ – greybeard Jun 14 '16 at 17:07
  • \$\begingroup\$ @greybeard I have made some relevant edits. I hope the problem is clearer now. \$\endgroup\$ – Dexter Jun 15 '16 at 10:46
1
\$\begingroup\$

Bug?

    private final ThreadLocalRandom random = ThreadLocalRandom.current();

This doesn't look right. What happens if your current thread copies your object and spawns a new thread? It will copy the current random instance.

When you use it

            final int randomIndex = random.nextInt(lowerBound, upperBound);

You should instead say

            final int randomIndex = ThreadLocalRandom.current().nextInt(lowerBound, upperBound);

That way, even if your object exists in multiple threads, each one will access a separate instance of ThreadLocalRandom.

Your current implementation may return the same random result multiple times, which would give the "non-random" appearance that you're seeing.

Note that if you are using an old version of Java, there was apparently a bug that could cause this to happen even when called correctly.

\$\endgroup\$
  • \$\begingroup\$ (I think the non-random-appearance is inherent to the procedure, hm, coded: take lowerBound + 2 == upperBound. Either, the random value is one of the bounds, and the range gets postponed, or it is exactly halved - with both halves appended immediately next to each other. I'm not even sure if it is worth to try and fix with divide&conquer - what is the perceived advantage?) \$\endgroup\$ – greybeard Jun 15 '16 at 19:13
  • \$\begingroup\$ @greybeard yes, I realised that the "non-random-appearance is inherent to the procedure". The other option was to clone the array and shuffle it using random swaps, but I assumed that would be slower. In my approach I instantly start getting the data, so there is scope for amortising other operations with this one. In case of shuffle, ill have to first clone the array, then wait for it to get shuffled, and only then can I start iterating over it. As can probably be observed I'm amortising socket IO in the linked example. \$\endgroup\$ – Dexter Jun 17 '16 at 12:00
  • \$\begingroup\$ @mdfast13 thats a valid observation, although the created object in my case is used by a single thread only. Having said that, the iterator is definetly not thread safe. \$\endgroup\$ – Dexter Jun 17 '16 at 12:03
0
\$\begingroup\$

Just to close the question. Divide and conquer is not a good approach for the problem. I made a much simpler implementation and it is working fine.

The idea is to keep a linked list of indexes and randomly remove them. We get random indexes and avoid repetition. Although we have to create this linked list every time we want to iterate, something which I wanted to avoid in the first place, but it seems like a pre mature optimisation hence going ahead with this only.

@Override
public T next() {

    final int index = offsets.remove(getRandomIndex());
    return words[index];
}
\$\endgroup\$
  • 1
    \$\begingroup\$ (You don't need to use a linked list - without referring to "previous art": pick an index below current max. & prepare to return the value currently at that index; replace with last value; decrement current max..) \$\endgroup\$ – greybeard Jul 13 '16 at 20:34
  • \$\begingroup\$ I can not change the original array. Hence can not replace with last value. \$\endgroup\$ – Dexter Jul 14 '16 at 11:52

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.