comparator和comparable的使用

前言

最近笔者被问到对象排序的时候，要求是传入不同的规则，排序不一样，类似一个按不同的条件排序的功能，笔者想到了comparator，其实comparable也是可以的，只是不太符合这个功能而已，通过comparator的切换即可实现。

comparable

comparable demo

comparable是一个接口，使用的bean实现即可，非常方便，缺点是与bean强藕联。

public class User implements Comparable<User>{

    private String name;
    private int age;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public int compareTo(User o) {
        return o.getAge() - this.getAge();
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

实现compareTo方法，一个对象是比较的其他对象，一个是对象本身，使用符号位判断大小，即0与正负数。此示例表示按照User的age倒序排列，示例如下：

public static void main(String[] args) {
        List<User> users = new ArrayList<>();
        User user1 = new User();
        user1.setAge(11);
        User user2 = new User();
        user2.setAge(22);

        users.add(user1);
        users.add(user2);
        Collections.sort(users);

        System.out.println(users);
    }

结果如下：

comparable源码分析

Collections.sort，以list的排序为例，本身是一个静态方法，T泛型限制必须实现Comparable接口。

public static <T extends Comparable<? super T>> void sort(List<T> list) {
        list.sort(null);
    }

调用的list的sort方法，笔者是ArrayList，估计其他实现略有区别

public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

调用Arrays.sort((E[]) elementData, 0, size, c);

ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);

TimSort排序，双轴快排，这里就比较复杂了

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
        assert a != null && lo >= 0 && lo <= hi && hi <= a.length;

        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted

        // If array is small, do a "mini-TimSort" with no merges
        if (nRemaining < MIN_MERGE) {
            int initRunLen = countRunAndMakeAscending(a, lo, hi);
            binarySort(a, lo, hi, lo + initRunLen);
            return;
        }

        /**
         * March over the array once, left to right, finding natural runs,
         * extending short natural runs to minRun elements, and merging runs
         * to maintain stack invariant.
         */
        ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
        int minRun = minRunLength(nRemaining);
        do {
            // Identify next run
            int runLen = countRunAndMakeAscending(a, lo, hi);

            // If run is short, extend to min(minRun, nRemaining)
            if (runLen < minRun) {
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen);
                runLen = force;
            }

            // Push run onto pending-run stack, and maybe merge
            ts.pushRun(lo, runLen);
            ts.mergeCollapse();

            // Advance to find next run
            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);

        // Merge all remaining runs to complete sort
        assert lo == hi;
        ts.mergeForceCollapse();
        assert ts.stackSize == 1;
    }

按照32的mini-TimSort划分，无需merges，超过的需要二分查找插入排序。这里就涉及真正的算法了，如果其他实现，可能不是这样的。

comparator

comparator demo

comparator是函数式接口，只有一个实现方法，基于比较接口，好处是，可以动态的更换接口的多个实现。

public static void main(String[] args) {
        List<User> users = new ArrayList<>();
        User user1 = new User();
        user1.setAge(11);
        User user2 = new User();
        user2.setAge(22);

        users.add(user1);
        users.add(user2);
//        Collections.sort(users);
        Collections.sort(users, new MyCompare());
        System.out.println(users);
    }

    private static class MyCompare implements Comparator<User> {

        @Override
        public int compare(User o1, User o2) {
            return o2.getAge() - o1.getAge();
        }
    }

运行结果同理

但是我们可以写多个实现接口的类。

Comparator源码分析

函数式接口，很明显的定义

@FunctionalInterface
public interface Comparator<T> {

sort方法，当然这个是集合工具类，我们可以自己实现排序外的逻辑

public static <T> void sort(List<T> list, Comparator<? super T> c) {
        list.sort(c);
    }

仍然

Arrays.sort((E[]) elementData, 0, size, c);

但是这里c是有比较器的，意味着使用比较器来比较

TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);

TimSort排序

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
                         T[] work, int workBase, int workLen) {
        assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;

        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted

        // If array is small, do a "mini-TimSort" with no merges
        if (nRemaining < MIN_MERGE) {
            int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
            binarySort(a, lo, hi, lo + initRunLen, c);
            return;
        }

        /**
         * March over the array once, left to right, finding natural runs,
         * extending short natural runs to minRun elements, and merging runs
         * to maintain stack invariant.
         */
        TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
        int minRun = minRunLength(nRemaining);
        do {
            // Identify next run
            int runLen = countRunAndMakeAscending(a, lo, hi, c);

            // If run is short, extend to min(minRun, nRemaining)
            if (runLen < minRun) {
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen, c);
                runLen = force;
            }

            // Push run onto pending-run stack, and maybe merge
            ts.pushRun(lo, runLen);
            ts.mergeCollapse();

            // Advance to find next run
            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);

        // Merge all remaining runs to complete sort
        assert lo == hi;
        ts.mergeForceCollapse();
        assert ts.stackSize == 1;
    }

算法类似，只是new TimSort<>(a, c, work, workBase, workLen);，传入了比较器

总结

其实很简单的比较，推荐comparator，函数式编程，更灵活。这里的比较算法使用的Arrays.sort非常复杂的算法，Arrays还可以并行排序，估计效率更高

public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
                                        Comparator<? super T> cmp) {
        rangeCheck(a.length, fromIndex, toIndex);
        if (cmp == null)
            cmp = NaturalOrder.INSTANCE;
        int n = toIndex - fromIndex, p, g;
        if (n <= MIN_ARRAY_SORT_GRAN ||
            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
            TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0);
        else
            new ArraysParallelSortHelpers.FJObject.Sorter<T>
                (null, a,
                 (T[])Array.newInstance(a.getClass().getComponentType(), n),
                 fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
                 MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
    }

可以看出小于1 << 13，即8192，还是原来的做法，多了才会并行排序。

另外Collections还可以sortedMap