MergeSorter.java
上传用户:quxuerui
上传日期:2018-01-08
资源大小:41811k
文件大小:3k
源码类别:

网格计算

开发平台:

Java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one
  3.  * or more contributor license agreements.  See the NOTICE file
  4.  * distributed with this work for additional information
  5.  * regarding copyright ownership.  The ASF licenses this file
  6.  * to you under the Apache License, Version 2.0 (the
  7.  * "License"); you may not use this file except in compliance
  8.  * with the License.  You may obtain a copy of the License at
  9.  *
  10.  *     http://www.apache.org/licenses/LICENSE-2.0
  11.  *
  12.  * Unless required by applicable law or agreed to in writing, software
  13.  * distributed under the License is distributed on an "AS IS" BASIS,
  14.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15.  * See the License for the specific language governing permissions and
  16.  * limitations under the License.
  17.  */
  18. package org.apache.hadoop.mapred;
  19. import java.util.Comparator;
  20. import org.apache.hadoop.io.IntWritable;
  21. import org.apache.hadoop.util.MergeSort;
  22. import org.apache.hadoop.io.SequenceFile.Sorter.RawKeyValueIterator;
  23. /** This class implements the sort method from BasicTypeSorterBase class as
  24.  * MergeSort. Note that this class is really a wrapper over the actual
  25.  * mergesort implementation that is there in the util package. The main intent
  26.  * of providing this class is to setup the input data for the util.MergeSort
  27.  * algo so that the latter doesn't need to bother about the various data 
  28.  * structures that have been created for the Map output but rather concentrate 
  29.  * on the core algorithm (thereby allowing easy integration of a mergesort
  30.  * implementation). The bridge between this class and the util.MergeSort class
  31.  * is the Comparator.
  32.  */
  33. class MergeSorter extends BasicTypeSorterBase 
  34. implements Comparator<IntWritable> {
  35.   private static int progressUpdateFrequency = 10000;
  36.   private int progressCalls = 0;
  37.   
  38.   /** The sort method derived from BasicTypeSorterBase and overridden here*/
  39.   public RawKeyValueIterator sort() {
  40.     MergeSort m = new MergeSort(this);
  41.     int count = super.count;
  42.     if (count == 0) return null;
  43.     int [] pointers = super.pointers;
  44.     int [] pointersCopy = new int[count];
  45.     System.arraycopy(pointers, 0, pointersCopy, 0, count);
  46.     m.mergeSort(pointers, pointersCopy, 0, count);
  47.     return new MRSortResultIterator(super.keyValBuffer, pointersCopy, 
  48.                                     super.startOffsets, super.keyLengths, super.valueLengths);
  49.   }
  50.   /** The implementation of the compare method from Comparator. Note that
  51.    * Comparator.compare takes objects as inputs and so the int values are
  52.    * wrapped in (reusable) IntWritables from the class util.MergeSort
  53.    * @param i
  54.    * @param j
  55.    * @return int as per the specification of Comparator.compare
  56.    */
  57.   public int compare (IntWritable i, IntWritable j) {
  58.     // indicate we're making progress but do a batch update
  59.     if (progressCalls < progressUpdateFrequency) {
  60.       progressCalls++;
  61.     } else {
  62.       progressCalls = 0;
  63.       reporter.progress();
  64.     }  
  65.     return comparator.compare(keyValBuffer.getData(), startOffsets[i.get()],
  66.                               keyLengths[i.get()],
  67.                               keyValBuffer.getData(), startOffsets[j.get()], 
  68.                               keyLengths[j.get()]);
  69.   }
  70.   
  71.   /** Add the extra memory that will be utilized by the sort method */
  72.   public long getMemoryUtilized() {
  73.     //this is memory that will be actually utilized (considering the temp
  74.     //array that will be allocated by the sort() method (mergesort))
  75.     return super.getMemoryUtilized() + super.count * 4; 
  76.   }
  77. }