Package net.i2p.router.util

Class RandomIterator<E>

  • All Implemented Interfaces:
    Iterator<E>
    public class RandomIterator<E>
extends Object
implements Iterator<E>
    This is some Java code I wrote for a school project to save some time when iterating in random order over a part of list (until some condition becomes true): Here is a sample on how to use the code: 
            for(Iterator<Object> iter = new RandomIterator<Object>(myObjList); iter.hasNext();){
            Object o = iter.next();
            if(someCondition(o) )
                return o; // iteration stopped early
        }
    I wrote it to replace a Collection.shuffle call and this code gave us an overall increase in program execution speed of about 25%. As the javadoc description says, you are better off calling Collection.shuffle if you need to iterate over the entire list. But if you may stop early this class can save you some time, as it did in our case. Provides a random iteration over the given list. This effect can be achieved by using Collections.shuffle, which shuffles the entire collection in linear time. If the iteration process may end before all items are processed, this class may give a speed increase because the shuffling process is performed as items are requested rather than in the beginning. I2P changes: 
       - Use BitSet instead of boolean[]
   - Use I2P RandomSource
   - Done check in next(), throw NSEE
   - Ensure lower and upper bounds are always clear
   - Replace unbounded loop in next(). It is now O(N) time, but now
     the iterator will tend to "clump" results and thus is not truly random.
     *** This class is not recommended for small Lists,
     *** or for iterating through a large portion of a List.
     *** Use Collections.shuffle() instead.
   - Add test code