java.lang.Comparable, java.util.Compartor区别以及Hadoop中关于自定义类型中的compare方法

public interface Comparable<T> {
     public int compareTo(T o);
}

规定了对象内部比较的方法

 

public interface Comparator<T> {
     int compare(T o1, T o2);
     boolean equals(Object obj);
}

定义外部比较器的基本方法,其中equals是用来确定两个比较器是否相等。

 

关于对象内部比较和外部比较这两个接口的区别和使用场景如下:

个人总结:

Comparable是对象内部固有的比较,一个类的不同对象肯定需要很自然的比较,无论使用在任何地方
Comparator是外部比较,在不改变对象内部固有的比较标准的前提下,增加新的比较行为,
尤其是对已有的类型,String,Integer等,如果我们想要不同的比较行为,例如绝对值比较,那么我们不能修改这写类固有的比较标准,而是加入自定义的外部比较器,
在外部比较器中定义新的比较规则,同时在需要比较的地方,插入我们自定义的外部比较器实例

举个例子,Arrays工具类

  public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, c);
    }

其中TimSort.sort

 1 static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) {
 2         if (c == null) {
 3             Arrays.sort(a, lo, hi);
 4             return;
 5         }
 6 
 7         rangeCheck(a.length, lo, hi);
 8         int nRemaining  = hi - lo;
 9         if (nRemaining < 2)
10             return;  // Arrays of size 0 and 1 are always sorted
11 
12         // If array is small, do a "mini-TimSort" with no merges
13         if (nRemaining < MIN_MERGE) {
14             int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
15             binarySort(a, lo, hi, lo + initRunLen, c);
16             return;
17         }
18 
19         /**
20          * March over the array once, left to right, finding natural runs,
21          * extending short natural runs to minRun elements, and merging runs
22          * to maintain stack invariant.
23          */
24         TimSort<T> ts = new TimSort<>(a, c);
25         int minRun = minRunLength(nRemaining);
26         do {
27             // Identify next run
28             int runLen = countRunAndMakeAscending(a, lo, hi, c);
29 
30             // If run is short, extend to min(minRun, nRemaining)
31             if (runLen < minRun) {
32                 int force = nRemaining <= minRun ? nRemaining : minRun;
33                 binarySort(a, lo, lo + force, lo + runLen, c);
34                 runLen = force;
35             }
36 
37             // Push run onto pending-run stack, and maybe merge
38             ts.pushRun(lo, runLen);
39             ts.mergeCollapse();
40 
41             // Advance to find next run
42             lo += runLen;
43             nRemaining -= runLen;
44         } while (nRemaining != 0);
45 
46         // Merge all remaining runs to complete sort
47         assert lo == hi;
48         ts.mergeForceCollapse();
49         assert ts.stackSize == 1;
50     }

如果c==null,则使用对象内部已经定义好的比较标准

 while (left < right) {
                int mid = (left + right) >>> 1;
                if (pivot.compareTo(a[mid]) < 0)
                    right = mid;
                else
                    left = mid + 1;
            }

 

否则,使用外部比较器

1  while (left < right) {
2                 int mid = (left + right) >>> 1;
3                 if (c.compare(pivot, a[mid]) < 0)
4                     right = mid;
5                 else
6                     left = mid + 1;
7             }

 


 

我们知道hadoop中有自定义类型,需要实现, WritableComparable接口,而WritableComparable接口继承之一便是Comparable接口。

因此,自定义的类型需要实现compareTo方法

如,LongWrite.class
 @Override
  public int compareTo(LongWritable o) {
    long thisValue = this.value;
    long thatValue = o.value;
    return (thisValue<thatValue ? -1 : (thisValue==thatValue ? 0 : 1));
  }

 

但是hadoop并没有直接使用这个基于对象内部比较机制,对需要排序比较的地方进行key的排序,而是借助外部比较器,统一介入的。
hadoop中的外部比较器,
WritableComparator。

 1 public static WritableComparator get(
 2       Class<? extends WritableComparable> c, Configuration conf) {
 3     WritableComparator comparator = comparators.get(c);
 4     if (comparator == null) {
 5       // force the static initializers to run
 6       forceInit(c);
 7       // look to see if it is defined now
 8       comparator = comparators.get(c);
 9       // if not, use the generic one
10       if (comparator == null) {
11         comparator = new WritableComparator(c, conf, true);
12       }
13     }
14     // Newly passed Configuration objects should be used.
15     ReflectionUtils.setConf(comparator, conf);
16     return comparator;
17   }

 

该方法会被Job调用,获得当前类型对应的外部比较器实例。WritableComparator内部有缓存,其中会缓存类型和其对应的外部比较器。get方法会从缓存中取得类型对应的外部比较器,如果取得为空,则手动生成一个外部比较器,

外部比较器,默认的比较方法是按照对象的内部比较标准进行的。

 
1   @SuppressWarnings("unchecked")
2   public int compare(WritableComparable a, WritableComparable b) {
3     return a.compareTo(b);
4   }
5 
6   @Override
7   public int compare(Object a, Object b) {
8     return compare((WritableComparable)a, (WritableComparable)b);
9   }

 

但是,hadoop在使用这个外部比较器的地方的,使用方式是:(例如,MapOutputBuffer,map端spill)

 1  public int compare(final int mi, final int mj) {
 2       final int kvi = offsetFor(mi % maxRec);
 3       final int kvj = offsetFor(mj % maxRec);
 4       final int kvip = kvmeta.get(kvi + PARTITION);
 5       final int kvjp = kvmeta.get(kvj + PARTITION);
 6       // sort by partition
 7       if (kvip != kvjp) {
 8         return kvip - kvjp;
 9       }
10       // sort by key
11       return comparator.compare(kvbuffer,
12           kvmeta.get(kvi + KEYSTART),
13           kvmeta.get(kvi + VALSTART) - kvmeta.get(kvi + KEYSTART),
14           kvbuffer,
15           kvmeta.get(kvj + KEYSTART),
16           kvmeta.get(kvj + VALSTART) - kvmeta.get(kvj + KEYSTART));
17     }

 

使用的是外部比较器的这个方法,如下

 1 @Override
 2   public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
 3     try {
 4       buffer.reset(b1, s1, l1);                   // parse key1
 5       key1.readFields(buffer);
 6       
 7       buffer.reset(b2, s2, l2);                   // parse key2
 8       key2.readFields(buffer);
 9       
10     } catch (IOException e) {
11       throw new RuntimeException(e);
12     }
13     
14     return compare(key1, key2);                   // compare them
15   }

 

而这个方法默认也是使用对象内部比较的标准。

在考虑性能的时候,需要将这个方法的默认行为改成基于bytes字节的比较,那么就需要用户自己写一个外部比较类的子类,并手动放到WritableComparator类中的内部缓存。

这种手动放入到缓存的过程,在自定义类型中完成,(LongWritable为例)
(1)自定义外部比较器的子类。

 1 public static class Comparator extends WritableComparator {
 2     public Comparator() {
 3       super(LongWritable.class);
 4     }
 5 
 6     @Override
 7     public int compare(byte[] b1, int s1, int l1,
 8                        byte[] b2, int s2, int l2) {
 9       long thisValue = readLong(b1, s1);
10       long thatValue = readLong(b2, s2);
11       return (thisValue<thatValue ? -1 : (thisValue==thatValue ? 0 : 1));
12     }
13   }

 

(2)手动注入到缓存中
1 static {                                       // register default comparator
2     WritableComparator.define(LongWritable.class, new Comparator());
3   }

 

这样,就改变了外部比较器默认的比较标准,按照用户自定义的compare方法进行比较。



那么,什么时候要自定义外部比较器呢?

1)效率考虑,如上所述
2)排序的规则发生变化,所有需要排序的地方,可以指定外部比较器,让其发生比较规则的改变(默认的比较都是自定义类型中的外部比较器比较规则

比如,二次排序等。

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。