Iterate twice on values (MapReduce)

Question

I receive an iterator as argument and I would like to iterate on values twice.

public void reduce(Pair<String,String> key, Iterator<IntWritable> values,
                   Context context)

Is it possible ? How ? The signature is imposed by the framework I am using (namely Hadoop).

-- edit --
Finally the real signature of the reduce method is with an iterable. I was misled by this wiki page (which is actually the only non-deprecated (but wrong) example of wordcount I found).

Answer 1

Unfortunately this is not possible without caching the values as in Andreas_D's answer.

Even using the new API, where the Reducer receives an Iterable rather than an Iterator, you cannot iterate twice. It's very tempting to try something like:

for (IntWritable value : values) {
    // first loop
}

for (IntWritable value : values) {
    // second loop
}

But this won't actually work. The Iterator you receive from that Iterable's iterator() method is special. The values may not all be in memory; Hadoop may be streaming them from disk. They aren't really backed by a Collection, so it's nontrivial to allow multiple iterations.

You can see this for yourself in the Reducer and ReduceContext code.

Caching the values in a Collection of some sort may be the easiest answer, but you can easily blow the heap if you are operating on large datasets. If you can give us more specifics on your problem, we may be able to help you find a solution that doesn't involve multiple iterations.

Answer 2

We have to cache the values from the iterator if you want to iterate again. At least we can combine the first iteration and the caching:

Iterator<IntWritable> it = getIterator();
List<IntWritable> cache = new ArrayList<IntWritable>();

// first loop and caching
while (it.hasNext()) {
   IntWritable value = it.next();
   doSomethingWithValue();
   cache.add(value);
}

// second loop
for(IntWritable value:cache) {
   doSomethingElseThatCantBeDoneInFirstLoop(value);
}

(just to add an answer with code, knowing that you mentioned this solution in your own comment ;) )

---

why it's impossible without caching: an Iterator is something that implements an interface and there is not a single requirement, that the Iterator object actually stores values. Do iterate twice you either have to reset the iterator (not possible) or clone it (again: not possible).

To give an example for an iterator where cloning/resetting wouldn't make any sense:

public class Randoms implements Iterator<Double> {

  private int counter = 10;

  @Override 
  public boolean hasNext() { 
     return counter > 0; 
  }

  @Override 
  public boolean next() { 
     count--;
     return Math.random();        
  }      

  @Override 
  public boolean remove() { 
     throw new UnsupportedOperationException("delete not supported"); 
  }
}

Answer 3

Reusing the given iterator, no.

But you can save the values in an ArrayList when iterating through them in the first place and then iterating upon the constructed ArrayList, of course (or you can build it directly in the first place by using some fancy Collection methods and then iterating directly on the ArrayList twice. It's a matter of tastes).

Anyway, are you sure passing an Iterator is a good thing in the first place? Iterators are used to do just a linear scan through the collection, this is why they don't expose a "rewind" method.

You should pass something different, like a Collection<T> or an Iterable<T>, as already suggested in a different answer.