【Guava 教學】(3)高階排序概念的實現 by caterpillar | CodeData
top

【Guava 教學】(3)高階排序概念的實現

分享:

【Guava 教學】(2)命名明確的條件檢查 << 前情

排名這種東西,人類還蠻愛的,到了程式設計領域,排序這東西依舊舉足輕重。在 Java 中要進行排序,可以使用標準 API 中 Collectionssort 方法,使用前必須遵守的協定是物件本身必須有天生的順序(Natural ordering),也就是必須擁有 Comparable 的行為,語法上具體來說,就是必須實作 Comparable 介面。由於 Collections 已經實作了排序演算法,你只需要告訴它,如果物件要與另一個物件比較時,順序上哪個大哪個小,也就是 compareTo 傳回 1、0、-1 分別來告訴它,順序上物件比另一物件大、相等或小。

用三個值來表示順序,蠻方便的,不是嗎?並不是!有多少次你弄錯了 1、0、-1 的意義呢?實際上,排序的要求還蠻多的,例如你可能想要排序時先依某人的姓來排,如果姓相同再依名來排,如果姓名都相同,再依他們居住地的郵遞區號來排,那你就可能會寫出像 compare/compareTo 中的程式碼:

class Person implements Comparable<Person> {
  private String lastName;
  private String firstName;
  private int zipCode;

  public int compareTo(Person other) {
    int cmp = lastName.compareTo(other.lastName);
    if (cmp != 0) {
      return cmp;
    }
    cmp = firstName.compareTo(other.firstName);
    if (cmp != 0) {
      return cmp;
    }
    return Integer.compare(zipCode, other.zipCode);
  }
}

你覺得 compareTo 好讀嗎?如果你學過 SQL,應該知道有 ORDER BY 這東西,相較之下,compareTo 的邏輯並不清楚,如果你使用 Guava 的 ComparisonChain,可以寫成這樣:

import com.google.common.collect.ComparisonChain;

class Person implements Comparable<Person> {
  private String lastName;
  private String firstName;
  private int zipCode;

  public int compareTo(Person other) {
    return ComparisonChain.start()
             .compare(lastName, other.lastName)
             .compare(firstName, other.firstName)
             .compare(zipCode, other.zipCode)
           .result();
  }
}

ComparisonChainstartcompare 都會傳回 ComparisonChain 實例,在最後 result 計算結果時,就如原先 compareTo 的實作,會逐一比較要比較的對象,只要它們各自的 compareTo 不為 0 時就傳回結果。

Guava 在排序上提供了一些 API ,確實是很好用,不過這不是這篇文章要論述的,這邊要談的是,如何觀察並抽取出程式碼中更高階的抽象概念,像是排序這樣的東西,其實也一直重複著某些模式。上例中的模式就是:

int cmp = f1.compareTo(other.f1);
if (cmp != 0) {
  return cmp;
}
cmp = f2.compareTo(other.f2);
if (cmp != 0) {
  return cmp;
}
cmp = f3.compareTo(other.f3);
if (cmp != 0) {
  return cmp;
}
...

談到模式,物件導向的開發者都會想到設計模式,想到有關創建、結構與行為模式。實際上寫程式時也有許多流程重複著一定模式,只是因為程式碼太混亂,程式區塊混著太多職責,而觀察不出來罷了,只要你能讓每段程式流程的職責單一化,就可以觀察並抽取出更高階的語義,像是這邊就可抽取出每個 compare 的語義,而這就是 ComparisonChain 在做的事,在使用它之前,你就像是在告訴電腦低階指令,1、0、-1?這什麼東西?在使用 ComparisonChain 之後,會比較像是在跟人說話了。

程式碼太混亂,程式區塊混著太多職責,觀察不出模式,抽取不出高階抽象的另一壞處就是,沒辦法重用某些基礎元素,沒辦法基於這些元素建構更複雜的的元素,因此,每次都得撰寫重複的東西。

舉例來說,如果你不想要用物件天生的順序進行排序,那麼 Collectionssort 還有另一個版本,可以指定一個比較器,也就是實現了 Comparator 介面的物件,它的 compare 方法也是得傳回 1、0、-1,告訴 Collectionssort 兩個被傳入的元素順序為何。例如,如果有個 List 中某些索引處包括 null,現在你打算讓 那些 null 排在最前頭,之後依字串的長度由大到小排序,那會怎麼寫?

class StringLengthInverseNullFirstComparator implements Comparator<String> {
    @Override
    public int compare(String s1, String s2) {
        if(s1 == s2) {
            return 0;
        }
        if(s1 == null) {
            return -1;
        }
        if(s2 == null) {
            return 1;
        }
        if(s1.length() == s2.length()) {
            return 0;
        }
        if(s1.length() > s2.length()) {
            return -1;
        } 
        return 1;
    }
}

不怎麼好讀,對吧!更別說為了表示這個比較器的目的,必須取個又臭又長的類別名稱,雖然在必要的時候,不用去畏懼取個較長的名稱,不過名稱真的太長,長到影響可讀性,或者很難簡短地描述出它的意圖時,就得想一下,是不是它做了太多事了?

仔細想想,將 null 全部排序在前或者在後,其實是一種常見的需求,長度是個整數,本身就有由小至大的天生順序,如果要由大至小,就是反向排序,反向排序也是一個經常的需求。有沒有辦法將這些常見需求抽取出來呢?試試看!

class Natural implements Comparator<Comparable> {
    @Override
    public int compare(Comparable c1, Comparable c2) {
        return c1.compareTo(c2);
    }
}

class Inverse implements Comparator {
    private Comparator comparator;

    public Inverse(Comparator comparator) {
        this.comparator = comparator;
    }

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

class NullsFirst implements Comparator {
    private final static int LEFT_IS_GREATER = 1;
    private final static int RIGHT_IS_GREATER = -1;

    private Comparator comparator;

    public NullsFirst(Comparator comparator) {
        this.comparator = comparator;
    }

    @Override
    public int compare(Object o1, Object o2) {
        if(o1 == o2) {
            return 0;
        }
        if(o1 == null) {
            return RIGHT_IS_GREATER;
        }
        if(o2 == null) {
            return LEFT_IS_GREATER;
        }
        return comparator.compare(o1, o2);
    }
}

NaturalInverseNullsFirst 都是從過去排序經驗中,不斷重現的流程模式中抽取出來的比較器,這樣一來,先前那個 StringLengthInverseNullFirstComparator 就可以基於它們來建構了:

interface F1<P, R> {
    R apply(P p);
}

class StringLengthInverseNullFirstComparator implements Comparator<String> {
    private Comparator comparator = new NullsFirst(new Inverse(new Natural()));
    private F1<String, Integer> f = new F1<String, Integer>() {
        @Override
        public Integer apply(String p) {
            return p == null ? null : p.length();
        }
    };
    @Override
    public int compare(String s1, String s2) {
        return comparator.compare(f.apply(s1), f.apply(s2));
    }
}

好吧!難道不能傳入 F1 實例就好嗎?這麼一來,連上頭那個 compare 方法中的流程也能重用了:

class OnResultOf<P, R> implements Comparator<P> {
    private Comparator comparator;
    private F1<P, R> f;

    public OnResultOf(F1<P, R> f, Comparator comparator) {
        this.f = f;
        this.comparator = comparator;
    }

    @Override
    public int compare(P p1, P p2) {
        return comparator.compare(f.apply(p1), f.apply(p2));
    }    
}

現在你連 StringLengthInverseNullFirstComparator 都不用定義了,可以直接建構並組合相關實例就可以進行複雜的排序了:

List names = Arrays.asList("Monica", null, "Justin", null, "Jao");

Collections.sort(names, 
        new OnResultOf(new F1<String, Integer>() {
            @Override
            public Integer apply(String p) {
                return p == null ? null : p.length();
            }}, 
        new NullsFirst(new Inverse(new Natural())))
);

這麼一連串的抽取,達到了一些元素的重用,不過語義上並不怎麼流暢,如果比較器可以主動生出另一個比較器,可以改進一下這個問題。在繼續進行重構之前,你發現了 Guava 做了你想做的事了,那就拿來用吧!

Collections.sort(names, 
        Ordering.natural().reverse().nullsFirst()
                .onResultOf(new Function<String, Integer>() {
                    @Override
                    public Integer apply(String p) {
                        return p == null ? null : p.length();
                    }
               })
);

Ordering 本身就是比較器,這看看它的類別定義就知道了:

public abstract class Ordering<T> extends Object implements Comparator<T>

不過,它是個功能強悍的比較器,可以基於目前的比較器,加上某個條件,直接產生新的 Ordering 實例,就如上面的例子中看到的,不過我承認,那個匿名類別實例語法挺惱人的,如果可以用上 JDK8 的 Lambda 語法,也許會好一些:

Collections.sort(names, 
        Ordering.natural().reverse().nullsFirst()
            .onResultOf(p -> p == null ? null : p.length())
);

只要事物不斷重複,就會形成一種模式,若能抽取出模式,就能用更高階的語義來表述意圖。Guava 在排序這方面,某些部份就是在表現這類意涵,不僅只有排序,實際上撰寫程式時,還存在許多高階語義在程式流程之中,只是就如先前所談到的,也許是因為程式碼太混亂,或者程式區塊混著太多職責,而觀察不出來罷了,因為看不出來,所以重複的工作就一再進行,日復一日地…

Guava 看來只是個程式庫,但它實際上包括了不少高階觀念,先前的兩篇文章 從避免使用 null 開始命名明確的條件檢查,其實也都是在談這些高階觀念,想善用 Guava,瞭解這些觀念是必要的,不然,只是當個程式庫來使用,就沒辦法用得順手,這樣是有點可惜了。

嗯?Ordering 更多的範例?其實看 API 文件應該就夠清楚了,如果你瞭解 Ordering 存在的目的的話!網路上搜尋一下 「Guava Ordering」,你可以找到一卡車的資料。好吧!我知道有些人很性急,那麼 google’s guava library tutorial part 2: joys of Ordering 這個鏈結有不少簡單易懂的範例。

後續 >> 【Guava 教學】(4)實作 toString、equals 與 hashCode 的幫手

分享:
按讚!加入 CodeData Facebook 粉絲群

留言

留言請先。還沒帳號註冊也可以使用FacebookGoogle+登錄留言

caterpillar06/28

Guava的Wiki對Ordering的說明中指出,Ordering的操作鏈閱讀時應由右往左讀,才能瞭解排序的結果,這反而令人不易瞭解語意;人類閱讀方式基本上就是由左而右,Ordering的操作鏈由左而右的閱讀方式,目的在於自然地瞭解Ordering實例會是如何組裝而成。

熱門論壇文章

熱門技術文章