Return to Revisions

I'll focus on the choice of algorithm. Choose janos' answer for style review, I'd say.

Files can be arbitrarily large. Larger than what can actually fit in your VM's memory. Your algorithm, while simple, does not deal well with a source of numbers of which the size is not known at the start.

So lets devise a better algorithm that can deal with an arbitrarily large number of inputs, of which we do not know the size beforehand.

To abstract this we will act as if our function gets as input an Iterator<T> (it could be one that reads from a file, or simply iterates a list, or reads primes from a webservice, ...)

First off, we'll need to handle the case that the Iterator is empty. Your current solution simply throws an IndexOutOfBoundsException, but we can do better.

The idea of the algotithm is that we have a current choice, and for each new input we may take the new input as our current choice. Of course, the odds that we should change our current choice should decrease proportionally to the number of inputs we've seen.

We'll need to keep track of a few things :

• the item we would have picked if we'd have seen all inputs : currentPick
• the number of inputs we've seen so far : totalInputs

When we read the first number it's the only one we can pick so far, so currentPick becomes that number and we increase totalInputs.

Then for every next input, we determine the chance that that number becomes our currentPick, and that chance is 1/totalInputs. So we ask our random source to get the next int in [0, totalInputs) and if it turns out to be 0, we change our currentPick to the latest item.

so something like this :

public static <T> T pickItem(Iterator<T> inputs) {
    if (!inputs.hasNext()) {
        throw new EmptyInputException();
    }

    T currentPick = inputs.next();
    long totalInputs = 1;

    Random random = new Random();

    while (inputs.hasNext()) {
        T next = inputs.next();
        totalInputs++;
        if (shouldPick(totalInputs, random)) {
            currentPick = next;
        }
    }
    return currentPick;
}

private static boolean shouldPick(long totalInputs, Random random) {
    return nextLong(random, totalInputs) == 0;
}

private static long nextLong(Random random, long bound) {
    return (long) (random.nextDouble() * bound);
}