[HADOOP] mapreduce의 반복자 조작하기

mapreduce의 반복자 조작하기

나는 주어진 포인트의 합을 찾기 위해 노력하고 있는데, 하나의 감속기에서 주어진 키의 모든 값을 얻는 데 문제가있다. 이 모양입니다.

감속기 :

 public static class Reduce extends MapReduceBase implements
        Reducer<Text, IntWritable, Text, DoubleWritable> {

    public void reduce(Text key, Iterator<IntWritable> values,
            OutputCollector<Text, DoubleWritable> output, Reporter reporter)
            throws IOException {
        Text word = new Text();

        Iterator<IntWritable> tr = values;
        IntWritable v;
        while (tr.hasNext()) {
             v = tr.next();

            Iterator<IntWritable> td = values;
            while (td.hasNext()) {

                IntWritable u = td.next();
                double sum = u+v;
                word.set( u + " + " + v);
                output.collect(word, new DoubleWritable(sum));
            }
        }
    }
}

그리고 내가 이전 Iterator (위의 두 while 루프)에서 하나의 값을 얻는 동안 두 번째 반복자의 모든 값을 통과 할 수 있도록 Iterator 변수의 두 복사본을 만들려고하지만 두 개의 반복자는 모두 같은 값을 유지합니다. 시간.

이것이 올바른 방법인지 확실하지 않습니다. 어떤 도움이라도 대단히 감사합니다.

감사,

Tsegay

해결법

1. ==============================

   1.감속기의 반복기는 생각만큼 간단하지 않습니다.

   감속기의 반복기는 생각만큼 간단하지 않습니다.

   문제는 반복되는 항목의 총 수가 메모리에 맞지 않을 수 있다는 것입니다. 즉, 이터레이터는 디스크에서 읽을 수 있습니다. 이터레이터의 두 개의 독립 사본이있는 경우 두 개의 이터레이터가 가리키는 곳 사이의 데이터를 삭제할 수 없다는 것을 의미하는 한 쪽을 다른 쪽보다 훨씬 앞설 수 있습니다.

   구현의 편의를 위해 Hadoop에서는 reduce 값에 대해 하나 이상의 반복자를 지원하지 않습니다.

   이것의 실질적인 영향은 동일한 반복기를 두 번 통과 할 수 없다는 것입니다. 좋지는 않지만 그렇습니다. 당신이 절대적으로 항목의 개수가 메모리에 들어갈 것이라는 것을 알고 있다면 MrGomez가 제안한대로 모든 항목을 목록에 복사 할 수 있습니다. 모르는 경우 보조 스토리지를 사용해야 할 수도 있습니다.

   더 나은 접근법은 프로그램을 재 설계하여 감속기에 무제한 저장 장치가 필요하지 않도록하는 것입니다. 약간 까다로울 수는 있지만 문제에 대한 표준 접근법이 있습니다.

   특정 문제의 경우, 가장 큰 축소 입력 세트와 관련하여 출력 크기가 2 차 증가합니다. 이것은 대개 정말 나쁜 생각입니다. 대부분의 경우 모든 쌍을 필요로하지 않고 단지 가장 중요한 쌍만 필요합니다. 어떤 방법으로 쌍 집합을 다듬을 수 있으면 모든 집합이 이루어 지므로 모든 쌍 제약을 제거 할 수 있습니다.

   예를 들어, 각 축소 집합에 대해 가장 큰 합계를 가진 100 쌍을 찾으려는 경우, 지금까지 본 100 개의 가장 큰 입력과 100 개의 가장 큰 합계가있는 우선 순위 대기열을 갖는 우선 순위 대기열을 유지할 수 있습니다. 각각의 새 입력에 대해 지금까지 표시된 최대 100 개의 숫자로 합계를 형성하고 그 합을 두 번째 대기열에 고정 시키십시오. 마지막으로 새 입력을 첫 번째 대기열에 고정시키고 두 번째 대기열을 100 개의 요소로 트리밍해야합니다 (필요한 경우). reduce의 close 메소드에서 우선 순위 큐를 덤프해야합니다. 이 접근법은 n ^ 2 문제를 피하고 모든 항목보다 오히려 보이는 100 개의 가장 큰 항목을 유지하여 입력을 두 번 통과하지 않도록 저장소의 최소 (n ^ 2, 200) 요소 만 필요함을 보장합니다.

2. ==============================

   2.나는 당신이 성취하려는 것을 정확하게 모르지만, 나는 이것을 많이 알고 있습니다. 하둡의 반복자의 행동은 조금 이상합니다. Iterator.next ()를 호출하면 항상 IntWritable과 동일한 인스턴스가 반환되며 인스턴스의 내용은 다음 값으로 바뀝니다. 따라서 Iterator.next ()에 대한 호출을 통해 IntWritable에 대한 참조를 유지하는 것은 거의 항상 실수입니다. 이 동작은 개체 생성 및 GC 오버 헤드의 양을 줄이기 위해 설계된 것입니다.

   나는 당신이 성취하려는 것을 정확하게 모르지만, 나는 이것을 많이 알고 있습니다. 하둡의 반복자의 행동은 조금 이상합니다. Iterator.next ()를 호출하면 항상 IntWritable과 동일한 인스턴스가 반환되며 인스턴스의 내용은 다음 값으로 바뀝니다. 따라서 Iterator.next ()에 대한 호출을 통해 IntWritable에 대한 참조를 유지하는 것은 거의 항상 실수입니다. 이 동작은 개체 생성 및 GC 오버 헤드의 양을 줄이기 위해 설계된 것입니다.

   이 문제를 해결하는 한 가지 방법은 WritableUtils.clone ()을 사용하여 Iterator.next ()에 대한 호출을 통해 보존하려는 인스턴스를 복제하는 것입니다.

3. ==============================

   3.Iterator를 복사하려면 반복자를 새 변수에 할당 할 수 없습니다. iterator 클래스의 새로운 변수에 iterator를 "복제"해야한다. 반복자 A가 다른 반복자 변수 B를 지정할 때, 반복자의 두 변수는 동일한 데이터를 가리 킵니다.

   Iterator를 복사하려면 반복자를 새 변수에 할당 할 수 없습니다. iterator 클래스의 새로운 변수에 iterator를 "복제"해야한다. 반복자 A가 다른 반복자 변수 B를 지정할 때, 반복자의 두 변수는 동일한 데이터를 가리 킵니다.

4. ==============================

   4.이전 질문으로 가면 piccolbo가 설명한 iterator 문제에 붙어있는 것처럼 보입니다. 귀하의 감속기의 공식은 또한 순진한 접근법을 위해 제안 된 알고리즘을 버렸음을 나타냅니다.

   이전 질문으로 가면 piccolbo가 설명한 iterator 문제에 붙어있는 것처럼 보입니다. 귀하의 감속기의 공식은 또한 순진한 접근법을 위해 제안 된 알고리즘을 버렸음을 나타냅니다.

   내 대답과 함께 당신의 코드를 조금 정리하자.

   // Making use of Hadoop's Iterable reduce, assuming it's available to you
   //
   //  The method signature is:
   //
   //  protected void reduce(KEYIN key, java.lang.Iterable<VALUEIN> values, 
   //   org.apache.hadoop.mapreduce.Reducer<KEYIN,VALUEIN,KEYOUT,VALUEOUT>.Context 
   //   context) throws java.io.IOException, java.lang.InterruptedException
   //
   public void reduce(Text key, Iterable<IntWritable> values, Context context)
           throws IOException, InterruptedException {
   
       // I assume you declare this here to save on GC
       Text outKey = new Text();
       IntWritable outVal = new IntWritable();
   
       // Since you've forgone piccolbo's approach, you'll need to maintain the
       // data structure yourself. Since we always walk the list forward and
       // wish to optimize the insertion speed, we use LinkedList. Calls to
       // IntWritable.get() will give us an int, which we then copy into our list.
       LinkedList<Integer> valueList = new LinkedList<Integer>();
   
       // Here's why we changed the method signature: use of Java's for-each
       for (IntWritable iw: values) {
           valueList.add(iw.get());
       }
   
       // And from here, we construct each value pair as an O(n^2) operation
       for (Integer i: valueList) {
           for (Integer j: valueList) {
               outKey.set(i + " + " + j);
               outVal.set(i + j);
               context.write(outKey, outVal);
           }
       }
   
       // Do note: I've also changed your return value from DoubleWritable to
       // IntWritable, since you should always be performing integer operations
       // as defined. If your points are Double, supply DoubleWritable instead.
   }
   

   이 방법은 효과가 있지만 거리 매트릭스를 구성 할 때 성능을 제한하는 몇 가지 가정을합니다 (조합 작업을 단일 축소 작업으로 수행해야하는 경우 포함).

   미리 입력 데이터의 크기와 크기를 알고 있다면 piccolbo의 접근 방식을 고려하십시오. 이것은 최악의 경우 선형 시간으로 입력 라인을 따라 가면서 사용할 수 있어야합니다.

   (forward iterator로 구현할 수없는 이유에 대해서는이 스레드를 참조하십시오.)

from https://stackoverflow.com/questions/3481914/manupulating-iterator-in-mapreduce by cc-by-sa and MIT license