Thomas Paul: I am watching your every move Should I be worried?
If you want to hit every number in a range it may be easiest to put them all in an ArrayList (pre-allocated to the right size of course) and use Collections.shuffle() (there's a method something like that). Is that any faster Paul? I couldn't find a method anything like that.
What if you stick all the numbers in a TreeSet to begin with and remove them as you find them (instead of adding them as you go along). I thought of that. It took about 2X longer.
Maybe you should really do it yourself with a custom binary search and the int[] type instead of a List of Integers, to save the time wasted on indirection. Use some magic number like -1 instead of setting things to null or removing them.
I wrote a customized IntList. You can't set items to a magic number because you need to get them out of the list so that you don't pick them over and over again. Remember, a list with 1,000,000 entries will eventually have only 1 valid entry left so you don't want to poke around the list hitting all those entries that contain the magic number.
I got 100,000 entries down to 10 seconds. 200,000 entries took 83 seconds. 1,000,000 entries still hangs.
The problem is that as the number of entries increases, removing items from the array becomes more and more expensive.
I'm going to put this out as a challenge in the Advanced forum.