Lucene學(xué)習(xí)筆記之-核心數(shù)據(jù)結(jié)構(gòu)PriorityQueue的實(shí)現(xiàn)原理

Luene的核心應(yīng)用場(chǎng)景是全文檢索。簡(jiǎn)單來(lái)說(shuō)，就是通過(guò)用戶(hù)輸入的關(guān)鍵詞來(lái)匹配相關(guān)文檔，然后根據(jù)匹配程度返回TopN的查詢(xún)結(jié)果給用戶(hù)。 這里需要解決的一個(gè)核心問(wèn)題就是如何快速返回TopN的結(jié)果，這本質(zhì)上是一個(gè)排序的問(wèn)題。說(shuō)起排序，我們有很多選擇，冒泡，快排，歸并...。 這些排序算法在數(shù)據(jù)量小的時(shí)候，不是問(wèn)題。一旦數(shù)據(jù)量過(guò)大，就成為問(wèn)題了。

例如對(duì)1000萬(wàn)的數(shù)組排序:

        Integer[] a = new Integer[10000000];

        for(int i=0;i<10000000;i++){
            a[i] = (int) (Math.random()*10000000);
        }
        long start = System.currentTimeMillis();
        Arrays.sort(a);
        System.out.println((System.currentTimeMillis() - start) +" 毫秒");

在我的電腦耗時(shí)需要5秒左右， 這個(gè)等待時(shí)間對(duì)于用戶(hù)體驗(yàn)來(lái)說(shuō)，就不那么feeling good了。

這時(shí)候，該考慮優(yōu)化了。優(yōu)化基本上是一個(gè)做減法的過(guò)程。再回到我們的核心需求: 基于搜索關(guān)鍵詞返回TopN的結(jié)果。 也就是說(shuō)，我們只需要TopN的結(jié)果有序就可以了。 基于上述需求，我們引入一個(gè)新的數(shù)據(jù)結(jié)構(gòu): 堆(Heap)。

堆是一種特殊的二叉樹(shù)。所謂二叉樹(shù)就是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn): 最多生二胎，超生不被允許的。

對(duì)于二叉樹(shù)這種樹(shù)形結(jié)構(gòu)，最核心的關(guān)系就是父子節(jié)點(diǎn)關(guān)系。 定義不同的節(jié)點(diǎn)關(guān)系，我們就能得到豐富多彩的數(shù)據(jù)結(jié)構(gòu)，以應(yīng)對(duì)不同場(chǎng)景的業(yè)務(wù)問(wèn)題。比如:

規(guī)定“子節(jié)點(diǎn)不能大于父節(jié)點(diǎn)”， 我們可以得出根節(jié)點(diǎn)是最大的節(jié)點(diǎn)， 得到大頂堆。

規(guī)定“子節(jié)點(diǎn)不能小于父節(jié)點(diǎn)”， 我們可以得出根節(jié)點(diǎn)是最小的節(jié)點(diǎn)， 得到小頂堆。

規(guī)定“根節(jié)點(diǎn)大于左子樹(shù)，小于右子樹(shù)；子樹(shù)亦是如此”， 我們得到二叉搜索樹(shù)；為了使二叉搜索樹(shù)的左右盡量平衡，我們又得到了“紅黑樹(shù)”，“AVL樹(shù)”，Treap等不同策略的平衡樹(shù)。

這些概念性的東西，能理解就OK.

理解了堆的來(lái)龍去脈， 我們可能會(huì)有點(diǎn)困惑，它并沒(méi)有直接維護(hù)一個(gè)有序的結(jié)構(gòu)。 是的，它沒(méi)有直接維護(hù)有序的結(jié)構(gòu)，它是通過(guò)刪除數(shù)據(jù)實(shí)現(xiàn)排序功能的。理解這一點(diǎn)特別重要。 以大頂堆為例: 由于堆頂是最大的元素，所以我們能確信，對(duì)于一個(gè)堆: 我們只要不斷地刪除堆頂?shù)臄?shù)據(jù)，直至空堆，就能得到一個(gè)有序的結(jié)果。這就是堆排序的思想。

那么如何利用堆實(shí)現(xiàn)TopN的有序輸出呢？ 以搜索的打分作為排序項(xiàng)，我們希望輸出得分最高的N個(gè)結(jié)果。 我們先遍歷N個(gè)結(jié)果，得到有N個(gè)元素的小頂堆。由于堆頂?shù)脑刈钚。?遍歷剩下的打分結(jié)果，只需要跟堆的根節(jié)點(diǎn)對(duì)比即可。如果打分結(jié)果小于堆的根節(jié)點(diǎn)，棄之；如果打分結(jié)果大于堆的根節(jié)點(diǎn)，刪除根節(jié)點(diǎn)；然后使用該打分結(jié)果更新到堆中。 這樣最后這個(gè)堆就維護(hù)了我們想要的TopN。

例如對(duì)1000萬(wàn)的數(shù)據(jù)，我們給出最大的前100個(gè)數(shù)，代碼如下:

Integer[] a = new Integer[10000000];

        for(int i=0;i<10000000;i++){
            a[i] = (int) (Math.random()*10000000);
        }
        long start = System.currentTimeMillis();

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(100) {
            @Override
            protected boolean lessThan(Integer t1, Integer t2) {
                return t1 < t2;
            }
        };

        for(int i=0;i<10000000;i++){
            pq.insertWithOverflow(a[i]);
        }
        Integer[] b = new Integer[100];
        for(int i=99;i>=0;i--){
            b[i] = pq.pop();
        }
        System.out.println((System.currentTimeMillis() - start) +" 毫秒");
        System.out.println(Arrays.asList(b));

這個(gè)耗時(shí)只需要50多毫秒。 這個(gè)性能差距幾乎是100倍?？梢?jiàn)堆這種數(shù)據(jù)結(jié)構(gòu)在TopN這個(gè)場(chǎng)景下是多么適合。

其實(shí)JDK有自己基于堆實(shí)現(xiàn)的優(yōu)先隊(duì)列PriorityQueue, 為啥Lucene要再造一遍輪子呢？

JDK默認(rèn)的PriorityQueue是可以自動(dòng)擴(kuò)展的，Lucene需要定長(zhǎng)的。
JDK默認(rèn)的PriorityQueue將數(shù)據(jù)結(jié)構(gòu)封裝得比較緊密，而Lucene需要一定的靈活性，比如調(diào)整堆頂。

小頂堆是一種二叉樹(shù)，所以其邏輯結(jié)構(gòu)大致如下:

    1
 3    2
5 8  7 6

如果觀察，可以發(fā)現(xiàn)這個(gè)一個(gè)規(guī)律，就是第一層只有1個(gè)元素;第二層最多有2個(gè)元素; 第三層最多有4個(gè)元素， 即第N層有2^(n-1)個(gè)元素。 這個(gè)規(guī)律后面有用。

那么怎么編碼實(shí)現(xiàn)一個(gè)堆呢？ 最簡(jiǎn)單的實(shí)現(xiàn)方式是基于數(shù)組，以Lucene的實(shí)現(xiàn)為例，學(xué)習(xí)一下:

public abstract class PriorityQueue<T> {
    private int size;
    private final int maxSize;
    private final T[] heap;

定義了一個(gè)數(shù)組。 只需要做如下的規(guī)定，那么就能滿足對(duì)的邏輯結(jié)構(gòu):

1. heap[0]位空置不用。
2. heap[1]為根節(jié)點(diǎn)。
3. heap[2~3]為第二層，heap[4~7] 為第三層 ... heap[2^n ~ 2^(n+1)-1]為第n+1層

這樣，元素在數(shù)組的哪個(gè)位置，我們就能知道它屬于哪一層了。

接下來(lái)要解決的問(wèn)題是:

1. 如何插入一個(gè)元素到堆中？

假設(shè)前面有N個(gè)元素了， 那么代碼很簡(jiǎn)單

    public final T add(T element) {
        ++this.size;
        this.heap[this.size] = element;
        this.upHeap(this.size);
        return this.heap[1];
    }

兩步走： s1 將元素添加到尾巴上。 s2: 由于這個(gè)元素有可能比其父節(jié)點(diǎn)小，所以遞歸地跟其父節(jié)點(diǎn)比較，換位置即可，這里有點(diǎn)冒泡的感覺(jué)。即想象把乒乓球按入水中，松手后就會(huì)上浮。

2. 如何從堆中刪除一個(gè)元素？

   public final T pop() {
        if (this.size > 0) {
            T result = this.heap[1];
            this.heap[1] = this.heap[this.size];
            this.heap[this.size] = null;
            --this.size;
            this.downHeap(1);
            return result;
        } else {
            return null;
        }
    }

兩步走: s1: 用數(shù)組尾巴上的元素覆蓋跟節(jié)點(diǎn)元素。 s2: 由于這個(gè)元素是否能勝任根節(jié)點(diǎn)這個(gè)位置還不確定，因此需要跟兩個(gè)子節(jié)點(diǎn)比較，調(diào)整位置。這里有絲下沉的感覺(jué)。即想象把鐵球丟入水中，自己就沉了下去。

這里，堆的插入和刪除操作還是思路還是比較輕奇的，值得好好揣摩一番。

在Lucene中，PriorityQueue有那些應(yīng)用場(chǎng)景呢？

1. HitQueue， 搜索打分的核心。
2. FieldValueHitQueue， 按字段排序的核心。
   ....

總之，該數(shù)據(jù)結(jié)構(gòu)在Lucene中有30～40個(gè)子類(lèi)，應(yīng)用十分廣泛。了解其實(shí)現(xiàn)機(jī)制，對(duì)于了解其他的功能大有裨益。