19

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).

5
  • I suppose I could first store every values in a container and iterate twice on it but ... seriously ... I hope there something better
    – log0
    May 24, 2011 at 13:37
  • Out of curiosity, what's the need for iterating twice?
    – Matt Ball
    May 24, 2011 at 13:42
  • whatever you do, just dont iterator over the iterator twice May 24, 2011 at 13:42
  • @Matt Ball: there could be a lot of situations when you want to iterate twice over a collection. Take as example the "Majority election" problem, when you have to know if there exists an element E in a collection C occurring over size(C)/2 times. You need to first do a full iteration over the elements using cs.utexas.edu/~moore/best-ideas/mjrty/index.html, which gives a correct answer only if such element exists, and then you do a second pass when you actually check if the "guessed major element" is really a major element.
    – akappa
    May 24, 2011 at 13:45
  • @log0: Did you solved the answer. When I am iterating through 2 nd loop. my cahe list is getting overwritten.
    – USB
    Mar 1, 2014 at 7:08

11 Answers 11

14

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.

0
11

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"); 
  }
}
3
  • You should change the declaration of cache to at least Collection so you can actually call add on it. Oct 16, 2012 at 20:01
  • Correct. Can't remember why I declared cache as Iterable. Smells like a copy&paste artifact ;) Oct 17, 2012 at 5:28
  • @Andreas_D:When I did the above code my cache list is getting overwritten with new value
    – USB
    Mar 1, 2014 at 6:40
10

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.

1
  • 1
    ok so that the solution I had in mind ... (as I said in comment). Otherwise I don't think I can do anything about the signature. It is imposed by the Hadoop framework (which I am using).
    – log0
    May 24, 2011 at 14:13
6

Iterators are one-traversal-only. Some iterator types are cloneable, and you might be able to clone it before traversing, but this isn't the general case.

You should make your function take an Iterable instead, if you can achieve that at all.

2

If method signature cannot be changed then I would suggest using Apache Commons IteratorUtils to convert Iterator to ListIterator. Consider this example method for iterating twice on values:

void iterateTwice(Iterator<String> it) {
    ListIterator<?> lit = IteratorUtils.toListIterator(it);
    System.out.println("Using ListIterator 1st pass");
    while(lit.hasNext())
        System.out.println(lit.next());

    // move the list iterator back to start
    while(lit.hasPrevious())
        lit.previous();

    System.out.println("Using ListIterator 2nd pass");
    while(lit.hasNext())
        System.out.println(lit.next());
}

Using code like above I was able to iterate over the list of values without saving a copy of List elements in my code.

13
  • but it does it anyway, so there's no difference in memory utilization or whatever... it's just a fancy way to save two lines of code. Does that justifies importing a library?
    – akappa
    May 25, 2011 at 15:08
  • At least in my case most of my applications already have apache commons collections as dependency for one reason or another. IMO whatever saves writing your own homegrown code is a better (read cleaner) code but of course you can always go with your first suggestion of saving those values yourself.
    – anubhava
    May 25, 2011 at 15:16
  • Well I think that it's not always the case that using some external libraries makes your code more readable, because not everyone have some knowledge of the library you're using. For complex or very boring tasks, using a library it's always a good idea, but for "micro-tasks" like this you have to go figure out what "IteratorUtils.toListIterator()" does, when a cycle that stores the values is immediately comprehensible. Don't get me wrong, I like very much Apache Commons, but I think we should use (external) library commodities with parsimony.
    – akappa
    May 25, 2011 at 16:26
  • That's exactly my point, if it is some obscure unheard of type of library we must verify everything before using that. But "Apache commons" is one of the most widely used library from their commons suite. And as I said almost all of my applications are already using it so its not really a new addition to the dependencies.
    – anubhava
    May 25, 2011 at 16:35
  • @anubhava: It is working partially for me.I also need two iterations.But when i examined by applying your code.In 1 st pass I am able to get all the values correctly.But for 2 nd pass I am only getting the first element repeatedly.Are we able to get the same value in both the passes
    – USB
    Feb 27, 2014 at 10:34
1

If we are trying to iterate twice in Reducer as below

ListIterator<DoubleWritable> lit = IteratorUtils.toListIterator(it);
System.out.println("Using ListIterator 1st pass");
while(lit.hasNext())
    System.out.println(lit.next());

// move the list iterator back to start
while(lit.hasPrevious())
    lit.previous();

System.out.println("Using ListIterator 2nd pass");
while(lit.hasNext())
    System.out.println(lit.next());

We will only output as

Using ListIterator 1st pass
5.3
4.9
5.3
4.6
4.6
Using ListIterator 2nd pass
5.3
5.3
5.3
5.3
5.3

Inorder to get it in the right way we should loop like this:

ArrayList<DoubleWritable> cache = new ArrayList<DoubleWritable>();
 for (DoubleWritable aNum : values) {
    System.out.println("first iteration: " + aNum);
    DoubleWritable writable = new DoubleWritable();
    writable.set(aNum.get());
    cache.add(writable);
 }
 int size = cache.size();
 for (int i = 0; i < size; ++i) {
     System.out.println("second iteration: " + cache.get(i));
  }

Output

first iteration: 5.3
first iteration: 4.9
first iteration: 5.3
first iteration: 4.6
first iteration: 4.6
second iteration: 5.3
second iteration: 4.9
second iteration: 5.3
second iteration: 4.6
second iteration: 4.6
1
  • +1 But it is not good for large dataset,as we are creatinga a copy of the same list
    – USB
    Mar 17, 2014 at 11:59
1

you can do that

MarkableIterator<Text> mitr = new MarkableIterator<Text>(values.iterator());
mitr.mark();
while (mitr.hasNext()) 
{
//do your work
}
mitr.reset();
while(mitr.hasNext()) 
{
//again do your work
}
  1. Reference Link 2

  2. Reference Link 2

1

Notice: if you use the cache list to cache the item, you should clone the item first then add to the cache. Otherwise you will find all the item is the same in the cache.

The situation is caused by the memory optimization of the MapReduce, In the reduce method, the Iterable reuse the item instance, for more detail can find here

0

Try this:

    ListIterator it = list.listIterator();

    while(it.hasNext()){

        while(it.hasNext()){
            System.out.println("back " + it.next() +" "); 
        }
        while(it.hasPrevious()){
            it.previous();
        }
    }
1
  • @Shevliaskovic, it seems self-evident: the code passes over the list forwards, then turns around and does a second pass backwards.
    – Mark
    May 18, 2014 at 6:44
0

if you want to change values as you go, i guess it's better to use listIterator then use its set() method.

ListIterator lit = list.listIterator();
while(lit.hasNext()){
   String elem = (String) lit.next();
   System.out.println(elem);
   lit.set(elem+" modified");
}
lit = null; 
lit = list.listIterator();
while(lit.hasNext()){
   System.out.println(lit.next());
}

Instead of calling .previous(), I just get another instance of the .listIterator() on the same list iterator object.

0

After searching and doing so many tries and errors, I found a solution.

  1. Declare a new collection (say cache) (linked list or Arraylist or any else)

  2. Inside first iteration, assign the current iterator like below example:

    cache.add(new Text(current.get()))  
    
  3. Iterate through cache:

    for (Text count : counts) {
        //counts is iterable object of Type Text
        cache.add(new Text(count.getBytes()));
    }
    for(Text value:cache) {
        // your logic..
    }
    
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.